Optimizare (matematică)

Optimizarea este o ramură a matematicii care încearcă să modeleze, să analizeze și să rezolve analitic sau numeric problemele care sunt de a minimiza sau maximiza o funcție pe un set.

Optimizarea joacă un rol important în cercetarea operațională (un domeniu la granița dintre informatică , matematică și economie ), în matematica aplicată (fundamentală pentru industrie și inginerie ), analiza și analiza numerică. , În statistici pentru estimarea probabilității maxime de o distribuție , pentru căutarea strategiilor în cadrul teoriei jocurilor sau chiar în teoria controlului și comenzii .

Multe sisteme capabile să fie descrise de un model matematic sunt optimizate. Calitatea rezultatelor și a predicțiilor depinde de relevanța modelului, de alegerea corectă a variabilelor pe care se caută să le optimizeze, de eficiența algoritmului și de mijloacele de procesare digitală .

Istorie și nume

antichitate

Primele probleme de optimizare au fost formulate de Euclid , secolul III î.Hr., în articolele sale istorice de lucru . Trei sute de ani mai târziu, Heron of Alexandria in Catoptrica afirmă „principiul celei mai scurte căi” în contextul opticii (vezi figura).

Introducerea calculului diferențial

În XVII - lea secol, apariția de calcul conduce la inventarea de tehnici de optimizare, sau cel puțin o face simt nevoia. Newton dezvoltă o metodă iterativă care permite găsirea extremelor locale ale unei funcții prin punerea în joc a noțiunii de derivat , rezultat din munca sa cu Leibniz . Această nouă noțiune permite mari progrese în optimizarea funcțiilor, deoarece problema se reduce la căutarea rădăcinilor derivatei.

În secolul al XVIII- lea, lucrarea matematicienilor Euler și Lagrange a condus la calculul variațiilor , o ramură a analizei funcționale care implică mai multe metode de optimizare. Acesta din urmă inventează o tehnică de optimizare sub constrângeri: multiplicatorii Lagrange .

Dezvoltări, aplicații și nume

XIX - lea lea a fost marcat de interesul tot mai mare de economiști pentru matematică. Ei stabilesc modele economice care ar trebui optimizate, ceea ce accelerează dezvoltarea matematicii. Din această perioadă, optimizarea a devenit un pilon al matematicii aplicate, iar profuzia tehnicilor este de așa natură încât nu poate fi rezumată în câteva rânduri.

Se poate la fel evocă inventarea mai multor metode iterative folosind gradientul a funcției , precum și folosirea termenului „programare matematică“, pentru a desemna probleme de optimizare.

Din punct de vedere istoric, primul termen introdus a fost cel de „programare liniară”, inventat de George Dantzig în jurul anului 1947. Termenul „programare” în acest context nu se referă la programarea computerizată (deși computerele sunt utilizate pe scară largă astăzi pentru rezolvarea problemelor. Programe de matematică). Provine din utilizarea cuvântului „program” de către forțele armate americane pentru a stabili programe de antrenament și alegeri logistice , pe care Danzig le studia la acea vreme. Utilizarea termenului „programare” a fost, de asemenea, de interes pentru a elibera fonduri într-un moment în care planificarea devenea o prioritate pentru guverne .

Astfel, din 1939, matematicianul Leonid Kantorovich a început lucrările teoretice privind optimizarea liniară pentru a atrage aplicații concrete la optimizarea producției economice planificate a Uniunii Sovietice .

Termenul „programare matematică”, care necesită explicația lungă de mai sus, tinde să fie abandonat. De exemplu, în iunie 2010, societatea învățată internațională care reprezintă această disciplină și-a văzut numele anterior Societatea de programare matematică schimbată în Societatea de optimizare matematică ; din același motiv, astăzi preferăm să folosim expresiile „liniar / pătratic / ... optimizare” în loc de „liniar / pătratic / ... programare”

Definiții

Minimizare

Mai formal, optimizarea este studiul problemelor care sunt exprimate după cum urmează.

Problemă de optimizare - Având în vedere o funcție definită pe un set cu valori în setul de numere reale (posibil în linia completată ), găsiți un element de așa natură încât pentru toate în . $f: A \ rightarrow \ mathbb {R}$ $LA$ $\ mathbb {R}$ ${\ displaystyle {\ overline {\ mathbb {R}}}: = \ mathbb {R} \ cup \ {- \ infty, + \ infty \}}$ ${\ bar x}$ $LA$ ${\ displaystyle f ({\ bar {x}}) \ leqslant f (x)}$ $X$ $LA$

Spunem că încercăm să minimalizăm funcția peste set . $f$ $LA$

Funcția are diferite denumiri: cost-funcție sau pur și simplu cost , obiectiv-funcție sau pur și simplu obiectiv , criteriu etc. $f$

Mulțimea se numește mulțimea admisibilă și punctele lui sunt numite punctele admisibile ale problemei (mai ales atunci când face parte dintr-o altă mulțime și nu vrem să aparțină complementarului ). Spunem că problema este fezabilă dacă este non-goală (mulțimea admisibilă este adesea definită implicit, caracterul său ne-gol nu este neapărat evident, ceea ce justifică necesitatea acestui concept de fezabilitate). $LA$ $LA$ $B$ ${\ bar x}$ $B \ setminus A$ $LA$

Punctul se numește soluția problemei de optimizare (sau minim sau minimizator ). De asemenea, se numește uneori o soluție globală pentru a o deosebi de conceptele locale introduse mai jos. Se spune că este un gol minim în cazul în care și pentru tot . ${\ bar x}$ ${\ displaystyle {\ bar {x}} \ în A}$ ${\ displaystyle f ({\ bar {x}}) <f (x)}$ ${\ displaystyle x \ în A \ setminus \ {{\ bar {x}} \}}$

Putem scrie această problemă în diferite moduri:

${\ displaystyle \ inf _ {x \ in A} \, f (x) \ quad {\ mbox {or}} \ quad \ inf {\ {f (x) \ mid x \ in A \}} \ quad { \ mbox {or}} \ quad \ inf {f (A)} \ quad {\ mbox {or}} \ quad \ left \ {{\ begin {array} {l} \ inf {f (x)} \\ x \ în A. \ end {array}} \ right.}$

Uneori observăm toate soluțiile la problemă. ${\ displaystyle \ operatorname {arg \, min} \, \ {f (x) \ mid x \ în A \}}$

Setul face parte din (sau dacă este valori în ), iar limita inferioară (sau infimă) se numește valoarea optimă a problemei. Această valoare optimă este atinsă (adică există astfel încât ) dacă și numai dacă problema de optimizare are o soluție. Da , spunem că problema este limitată . ${\ displaystyle f (A): = \ {f (x) \ mid x \ în A \}}$ $\ mathbb {R}$ ${\ displaystyle {\ overline {\ mathbb {R}}}}$ $f$ ${\ displaystyle {\ overline {\ mathbb {R}}}}$ ${\ displaystyle \ inf {f (A)}}$ ${\ displaystyle {\ bar {x}} \ în A}$ ${\ displaystyle f ({\ bar {x}}) = \ inf \, f (A)}$ ${\ displaystyle \ inf {f (A)}> - \ infty}$

Spunem că problema este convexă dacă este o parte convexă a unui spațiu vectorial și dacă este o funcție convexă pe . ${\ displaystyle \ inf {\ {f (x) \ mid x \ în A \}}}$ $LA$ $f$ $LA$

Maximizare

Problema descrisă mai sus este o problemă de minimizare . Așa cum am făcut noi

${\ displaystyle \ sup _ {x \ in A} {f (x)} = - \ inf _ {x \ in A} \ left (-f (x) \ right),}$

o problemă de maximizare a funcției (stânga sus) este echivalentă cu problema minimizării (dreapta sus). Echivalența aici înseamnă că soluțiile sunt aceleași și că valorile optime sunt opuse. În special, o metodă de analiză / rezolvare a unei probleme de minimizare ar putea fi utilizată pentru a analiza / rezolva o problemă de maximizare. $f$ $-f$

Soluție locală

În anumite condiții, procesul de optimizare găsește maximul general. Dar, în unele cazuri de optimizare - cum ar fi rețelele neuronale artificiale , rezultatul poate fi o soluție locală.

Un maxim local este un punct astfel încât există un cartier în cazul în care pentru toți , . Un minim local este definit în mod similar. $la$ $LA$ $V$ $x \ în V$ ${\ displaystyle f (x) \ leqslant f (a)}$

În general, este ușor să se determine numerele maxime locale cu algoritmi de coborâre - cum ar fi cu algoritmul de gradient . Pentru a verifica dacă soluția găsită este un maxim global , este uneori posibil să se recurgă la cunoștințe suplimentare despre problemă. În funcție de natura sau funcția , diverse teoreme oferă proprietăți particulare ale soluției care simplifică căutarea acesteia (a se vedea principiul maxim ). $LA$ $f$

Optimizare combinatorie

Cel mai adesea, este un subset al spațiului euclidian . Când este un subset al sau , constând din vectori care satisfac un anumit număr de constrângeri (de tip egalitate sau inegalitate), vorbim de optimizare combinatorie . $LA$ $\ mathbb {R} ^ {n}$ $LA$ ${\ displaystyle \ mathbb {N} ^ {n}}$ ${\ displaystyle \ mathbb {N} ^ {p} \ times \ mathbb {R} ^ {q}}$

Unele clase de probleme

Optimizarea este împărțită în sub-discipline suprapuse, în funcție de forma funcției obiective și cea a constrângerilor: optimizarea în dimensiune finită sau infinită (vorbim aici despre dimensiunea spațiului vectorial al variabilelor care urmează să fie optimizate) , optimizare continuă sau combinatorie (variabilele care urmează a fi optimizate sunt discrete în acest din urmă caz), optimizare diferențiată sau neuniformă (se califică aici regularitatea funcțiilor care definesc problema), optimizare liniară (funcții afine), pătratic (obiectiv pătratic) și constrângeri afine), semidefinită pozitivă (variabila care trebuie optimizată este o matrice pentru care este necesară pozitivitatea semidefinită ), copozitivă (variabila care trebuie optimizată este o matrice pentru care este necesară co- pozitivitatea ), conică (generalizarea disciplinelor anterioare, în care minimizăm o funcție liniară pe intersecția unui con și a unui subspatiu afin), convex ( funcții convexe ), neliniar , comanda optim optim e , stocastic (en) și optimizare robustă (prezența pericolelor), optimizare multicriterială (se caută un compromis între mai multe obiective contradictorii), optimizare algebrică (funcții polinomiale), optimizare pe două niveluri , optimizarea sub constrângeri de complementaritate , disjunctiv optimizare (setul admisibil este o întâlnire de seturi) etc.

Această abundență de discipline provine din faptul că practic orice clasă de probleme modelabile poate duce la o problemă de optimizare, cu condiția să introducem parametri de optimizat. Mai mult, condițiile de optimitate ale acestor probleme de optimizare oferă uneori expresii matematice originale care, prin mecanismul precedent, conduc la rândul lor la noi probleme de optimizare.

Cele liniare de optimizare studiilor de caz în care funcția obiectiv și constrângerile ce caracterizează toate sunt liniare . Este o metodă utilizată pe scară largă pentru a stabili programe de rafinărie de petrol, dar și pentru a determina cea mai profitabilă compoziție a unui amestec sărat, sub constrângeri, din prețurile actuale de pe piață. $LA$
Programare Integer studii problemele de optimizare liniară , în care unele sau toate variabilele sunt constrânse să ia valori întregi. Aceste probleme pot fi rezolvate prin diferite metode: separare și evaluare , metoda planurilor secante .
Optimizarea pătratic studiază cazul în care funcția obiectiv este o formă pătratică (cu constrângeri liniare ) $LA$
Optimizare neliniară considerând cazul general în care obiectivul sau constrângerile (sau ambele) conțin porțiuni neliniare, eventual non-convexe.
Optimizarea stocastic (în) studiază cazul în care unele dintre constrângerile depind de variabile aleatoare . În optimizarea robustă , se presupune că pericolele sunt situate în intervale în jurul pozițiilor nominale și căutăm să optimizăm sistemul supus unor astfel de pericole, în cel mai rău caz.
Programarea dinamică utilizează proprietatea că o soluție constă în soluții în mod necesar suboptime (notă: opusul nu este adevărat în general) pentru a descompune problema prin evitarea exploziei combinatorie . Poate fi folosit atunci când funcția obiectivă este o sumă de funcții monotonice în creștere ale căror argumente sunt necunoscute distincte. Este o programare dinamică care permite, de exemplu:
- producătorii de aeronave să găsească planurile optime de decolare pentru mașinile lor,
- inginerii bazinului să distribuie producția minieră între diferitele sonde,
- producătorii de energie electrică să planifice funcționarea centralelor hidroelectrice,
- pentru a planificatorii mass - media pentru a distribui în mod eficient un buget publicitar între diferite medii.

Metode numerice

O tehnică pentru rezolvarea unei probleme de optimizare matematică denotă aici

transformarea problemei inițiale într-o problemă echivalentă,
o metodă teoretică a cărei descriere permite dezvoltarea unui algoritm aplicabil numeric.

Alegerea unei tehnici adecvate depinde de

natura funcției obiective , a regularității sale ( continuitate , derivabilitate ), a proprietăților specifice ( paritate , convexitate ), a cunoașterii vecinătăților extremelor sale, $f$
constrângeri care caracterizează setul de puncte admisibile. $LA$

Simplificări

Pentru a găsi o soluție la optimizare, problema inițială este înlocuită de o problemă echivalentă. De exemplu, este posibil să se schimbe variabilele care permit defalcarea problemei în subprobleme sau înlocuirea necunoscutelor făcând posibilă reducerea numărului acestora.

Tehnica multiplicatorului Lagrange face posibilă depășirea anumitor constrângeri; această metodă echivalează cu introducerea unor penalități crescânde pe măsură ce punctul se apropie de constrângeri. Un algoritm datorat lui Hugh Everett face posibilă actualizarea constantă a valorilor multiplicatorilor la fiecare iterație pentru a asigura convergența. De asemenea, el a generalizat interpretarea acestor multiplicatori pentru a le aplica funcțiilor care nu sunt nici continue, nici derivabile. Lambda exprimă un coeficient de penalizare (noțiunea de cost marginal de o constrângere în economie ).

Găsirea gradientului zero

Multe metode și algoritmi fac posibilă găsirea unui zero din derivata lui (unele sunt specifice funcțiilor unei variabile ) sau a gradientului său . Acestea se aplică valabil în situațiile în care constrângerile rămân insuficiente. $f$ $\ mathbf {\ nabla} f$ $LA$

Toate aceste metode sunt dezvoltate în cadrul unui proces iterativ .

Aceste abordări pot suferi de câteva defecte:

Funcția trebuie să fie suficient de regulată (cel puțin local) pentru a fi diferențiată (sau de două ori diferențiată pentru a accesa matricea Hessian sau o aproximare a acesteia).
Nu este întotdeauna posibil să se exprime în mod expres gradientul funcției obiective.
Condițiile de pornire trebuie stabilite înainte de a începe procesul iterativ. Alegerea inițială poate influența considerabil rezultatul (divergența procesului iterativ). Metodele care converg rapid sunt, în general, mai sensibile din acest punct de vedere.
În anumite cazuri, viteza convergenței poate fi dezastruoasă: iterațiile succesive merg greu (stagnare) de-a lungul unei văi înguste ( funcția Rosenbrock ).
Dacă soluția obținută este într-adevăr un extremum (după verificarea faptului că nu este un punct de șa ), acesta se poate dovedi local.

Caz particular: Când este polinomul de gradul 2 în argumentele sale ( formă pătratică și liniară ) și fără constrângere, anularea gradientului echivalează cu rezolvarea unui sistem liniar (cf Categorie: Analiza numerică a matricei ). $f$

Metode analitice directe

În această categorie, majoritatea algoritmilor generali se aplică situațiilor în care constrângerile nu sunt foarte active. Acestea se bazează pe câteva idei dominante: $LA$

Mișcări de-a lungul unei linii purtate de un gradient.
Aproximarea printr-o funcție mai simplă (de exemplu extinderea Taylor a ordinii 2), actualizată în timpul iterațiilor. $f$

S-au făcut diverse îmbunătățiri pentru a evita:

stagnări (de exemplu, metoda gradientului conjugat în optimizarea neliniară (în) )
calculul explicit sau prea frecvent al matricei Hessian (de exemplu BFGS )

Aceleași defecte ca cele menționate în categoria anterioară pot apărea și aici.

Categoria: Algoritmul de optimizare prezintă o listă și oferă acces la aceste metode.

Tehnici de optimizare combinatorie

Tehnicile de optimizare combinatorie se ocupă de probleme în care o parte (cel puțin) a variabilelor setului ia valori discrete . Îi întâlnim în cadrul $LA$

teoria grafurilor ( traseul optim al cărui agent de vanzari Problemă )
teoria jocului ( strategie de performanță)
teoria controlului , reglementării și automată (cf Categorie: Automat )
optimizarea multidisciplinară

Euristică și metaheuristică

Pentru a rezolva probleme dificile (de exemplu, cele cu multe extreme locale sărace), au fost concepute tehnici pentru a determina puncte care nu sunt strict optime, ci abordează-le. Aceste metode, numite euristică și metaheuristică , se bazează în general pe fenomene fizice, biologice, socio-psihologice sau apelează la întâmplare. Domeniile de aplicare sunt vaste și deseori se extind dincolo de problemele pentru care au fost concepute inițial.

recoacerii simulate
metoda Nelder-Mead cu recoacere simulată
a algoritmilor de colonii de furnici
a algoritmilor genetici
a algoritmilor evolutivi
metode de optimizare a roiului de particule

Categorie: Metaheuristic prezintă o listă și oferă acces la aceste metode.

Tehnici de optimizare multiobective

Problemele optimizării multiobiective depășesc cadrul strict al definiției date mai sus: la un punct admisibil, funcția obiectivă nu asociază o valoare numerică, ci un punct al unui set care va fi cel mai adesea asociat cu un vector. Obiectivul este apoi de a optimiza simultan toate componentele acestui vector. Se poate vedea, de asemenea, optimizarea multiobiectivă ca un set de probleme de optimizare în funcție de aceiași parametri, având obiective posibil contradictorii și pe care se caută să le rezolve cât mai bine.

În general, spațiul în care este exprimat vectorul soluție este prevăzut cu o ordine parțială care implică criterii de dominanță (de exemplu în raport cu frontiera Pareto ). Rezoluția constă în găsirea unui punct admisibil al cărui obiectiv nu este dominat de niciun altul.

Domenii de aplicare

Sunt extrem de variate: optimizarea unui traseu , forma unui obiect , prețul de vânzare , o reacție chimică , controlul traficului aerian , eficiența unui dispozitiv, funcționarea unui motor , gestionarea liniilor de cale ferată, alegerea economiei investiții, construcția unei nave etc. Optimizarea acestor sisteme face posibilă găsirea unei configurații ideale, obținerea unei economii de efort, timp, bani, energie, materie primă sau chiar satisfacție.

Problemele dinamicii de solide nedeformabil ( în special dinamica corpurilor rigide articulate) adesea au nevoie de tehnici matematice de optimizare, deoarece putem vedea dinamica corpurilor rigide ca rezolvarea unei ecuații diferențiale ordinare pe o varietate constrânsă; constrângerile sunt diverse constrângeri geometrice neliniare, cum ar fi „aceste două puncte trebuie să coincidă întotdeauna” sau „acest punct trebuie să fie întotdeauna pe această curbă”. De asemenea, problema calculării forțelor de contact poate fi completată prin rezolvarea unei probleme de complementaritate liniară , care poate fi văzută și ca o problemă de optimizare pătratică.

Mai multe probleme de proiectare pot fi exprimate și ca probleme de optimizare. Această aplicație se numește optimizarea formei. Un subset recent și în creștere al acestui domeniu se numește Optimizare multidisciplinară , care, deși este utilă în mai multe probleme, a fost aplicată în special problemelor de inginerie și tehnologie spațială .

Un alt domeniu care utilizează tehnici de optimizare este cercetarea operațională .

Optimizarea este unul dintre instrumentele centrale ale microeconomiei care se bazează pe principiul raționalității și optimizării comportamentului, profitului pentru companii și utilitate pentru consumatori .

În mecanică, există trei forme de optimizare:

optimizarea mărimii sau optimizarea parametrică , care constă în optimizarea dimensiunilor (lungimea, grosimea, diametrul etc.) ale structurii mecanice;
optimizarea formei , care este de a optimiza plicul unei încăperi fără a schimba topologia, adică fără adăugarea de găuri în piesa de prelucrat;
optimizare topologie , care implică variația distribuției materialului într - un volum de pornire dat.

Departe de a constitui o listă exhaustivă, aceste câteva exemple atestă varietatea formulărilor și prefigurează diversitatea instrumentelor matematice capabile să rezolve aceste probleme.

Note și referințe

(fr) Acest articol este preluat parțial sau în totalitate din articolul din Wikipedia engleză intitulat „ Optimizare (matematică) ” ( vezi lista autorilor ) .

Sebastian Xhonneux, „ Percepția optimizării în matematică și economie de-a lungul secolelor și predarea teoremei lui Lagrange ” , pe APMEP ,27 octombrie 2008(accesat la 15 martie 2010 ) .
A se vedea articolul „ Metoda lui Newton ”.
(în) GB Danzig, „Maximizarea unei funcții liniare a variabilelor supuse inegalităților liniare” în Tj. C. Koopmans, Analiza activității producției și alocării , New York, Wiley,1951, p. 339-347.
(în) „ Mathematical Optimization Society (MOS) ” pe mathopt.org .
M. Gori și A. Tesi , „ Cu privire la problema minimelor locale în propagarea înapoi ”, IEEE Transactions on Pattern Analysis and Machine Intelligence , vol. 14, n o 1,1992, p. 76–86 ( ISSN 0162-8828 , DOI 10.1109 / 34.107014 , citit online , accesat la 21 august 2019 )
Catherine Vayssade, „ Optimizare mecanică, optimizare topologică ” ,2004(accesat la 24 decembrie 2008 ) .

Vezi și tu

Articole similare

Lucrări generale

(ro) JF Bonnans, J. Ch. Gilbert, C. Lemaréchal și C. Sagastizábal, Optimizare numerică - Aspecte teoretice și numerice [ detaliul edițiilor ]
(ro) JF Bonnans și A. Shapiro, Analiza perturbării problemelor de optimizare , Springer, 2000 ( ISBN 978-0-387-98705-7 )
(în) Christodoulos A. Floudas Pardalos și Panos M. (eds) Encyclopedia of Optimization , ediția a 2- a , 2009 ( ISBN 978-0-387-74758-3 )
Michel Minoux, Programare matematică - teorie și algoritmi , ediții Dunod, 1983 ( ISBN 2040154876 )

linkuri externe

„ Râul ” [PDF] , pe ÉducMath : problema celei mai scurte poteci dintre două case care trec pe lângă râu
(ro) Ghid NEOS
(ro) „ Glosar de programare matematică ”