Optimizare (matematică)

Optimizarea (sau programarea matematică , PM ) este o ramură a matematicii aplicate care studiază teoria și metodele pentru găsirea punctelor maxime și minime ale unei funcții matematice într-un domeniu specificat.

Un exemplu simplu al unei probleme de optimizare este de a maximiza sau minimiza o funcție reală a unei variabile reale într-un anumit interval de axă. Generalizarea teoriei și tehnicilor de optimizare la alte formulări constituie o arie largă de matematică aplicată. În general, optimizarea include căutarea „celor mai bune valori disponibile” ale anumitor funcții obiective într-un anumit domeniu (sau intrare), incluzând o varietate de tipuri diferite de funcții obiective și diferite tipuri de domenii.

Descriere

O problemă de optimizare, uneori numită programare matematică , poate fi formulată după cum urmează:

Date : o funcție

f:A\to \mathbb {R}

{\ displaystyle f: A \ to \ mathbb {R}}

{\ displaystyle f: A \ to \ mathbb {R}}

dintr-un set

LA

{\ displaystyle A}

LA

în număr real

Determinați un element

\mathbf {x} _{0}\in A

{\ displaystyle \ mathbf {x} _ {0} \ în A}

{\ displaystyle \ mathbf {x} _ {0} \ în A}

astfel încât

f(\mathbf {x} _{0})\leq f(\mathbf {x} )

{\ displaystyle f (\ mathbf {x} _ {0}) \ leq f (\ mathbf {x})}

{\ displaystyle f (\ mathbf {x} _ {0}) \ leq f (\ mathbf {x})}

pentru fiecare

\mathbf {x} \in A

{\ displaystyle \ mathbf {x} \ în A}

{\ displaystyle \ mathbf {x} \ în A}

(„minimizare”) sau astfel încât

f(\mathbf {x} _{0})\geq f(\mathbf {x} )

{\ displaystyle f (\ mathbf {x} _ {0}) \ geq f (\ mathbf {x})}

{\ displaystyle f (\ mathbf {x} _ {0}) \ geq f (\ mathbf {x})}

pentru fiecare

\mathbf {x} \in A

{\ displaystyle \ mathbf {x} \ în A}

{\ displaystyle \ mathbf {x} \ în A}

(„maximizare”).

Deoarece punctele maxime pentru o funcție $f$ ${\ displaystyle f}$ $f$ corespund punctelor minime pentru funcție ${\tilde {f}}=-f$ ${\ displaystyle {\ tilde {f}} = - f}$ ${\ displaystyle {\ tilde {f}} = - f}$ , nu este restrictiv să formulați probleme de optimizare în ceea ce privește minimizările.

Functia $f$ ${\ displaystyle f}$ $f$ în general se numește funcție obiectivă sau funcție cost . Întregul $LA$ ${\ displaystyle A}$ $LA$ , denumit în general un spațiu de căutare, poate fi un set discret sau continuu. În multe cazuri de importanță aplicativă relevantă, poate fi identificat cu un subset de spațiu euclidian $\mathbb {R} ^{n}$ ${\ displaystyle \ mathbb {R} ^ {n}}$ $\ mathbb {R} ^ {n}$ definit în termeni de constrângeri, adică egalități sau inegalități pe care elementele $LA$ ${\ displaystyle A}$ $LA$ trebuie să satisfacă. Multe probleme din științele naturii, atât teoretice, cât și aplicate, pot fi descrise printr-o astfel de formulare.

Problemele de optimizare necesită în mod necesar crearea unor algoritmi de rezoluție eficienți , deoarece, în general, spațiul de căutare are o astfel de cardinalitate încât să împiedice posibilitatea căutărilor exhaustive. Ca exemplu dacă $LA$ ${\ displaystyle A}$ $LA$ este descris de $n=20$ ${\ displaystyle n = 20}$ $n = 20$ variabile, fiecare dintre ele putând presupune $4$ ${\ displaystyle 4}$ $4$ valorile, spațiul de căutare conține $4^{20}\approx 10^{12}$ ${\ displaystyle 4 ^ {20} \ approx 10 ^ {12}}$ ${\ displaystyle 4 ^ {20} \ approx 10 ^ {12}}$ elemente. Prin urmare, o căutare exhaustivă este impracticabilă și este necesar să recurgeți la algoritmi care să permită exploatarea eficientă a oricăror proprietăți ale funcției $f$ ${\ displaystyle f}$ $f$ și spațiul de cercetare $LA$ ${\ displaystyle A}$ $LA$ .

Problemele de optimizare pot fi clasificate în funcție de principalele caracteristici ale spațiului de căutare $LA$ ${\ displaystyle A}$ $LA$ și funcție $f$ ${\ displaystyle f}$ $f$ . În special, se face în general o distincție între programarea continuă și discretă pe baza faptului că spațiul de căutare $LA$ ${\ displaystyle A}$ $LA$ fie continuu, fie discret. În contextul programării continue, cu spațiu pentru cercetare $A\subseteq \mathbb {R} ^{n}$ ${\ displaystyle A \ subseteq \ mathbb {R} ^ {n}}$ ${\ displaystyle A \ subseteq \ mathbb {R} ^ {n}}$ , distingem între programarea liniară , dacă funcția obiectivă și constrângerile sunt liniare și programarea neliniară în caz contrar. O altă clasificare poate fi făcută distingând problemele de programare statică și problemele de programare dinamică . În optimizarea dinamică, se adaugă o variabilă temporală la formularea expusă anterior de care depind cantitățile implicate, adică spațiul de căutare și, eventual, funcția obiectivă.

Minim și maxim

Același subiect în detaliu: maxim și minim al unei funcții .

Prin urmare, obiectivul programării matematice este identificarea punctului $X$ ${\ displaystyle x}$ $X$ în domeniul funcției obiective (adică valorile care trebuie atribuite $n$ ${\ displaystyle n}$ $n$ variabile de decizie) care, respectând constrângerile, minimizează sau maximizează valoarea funcției obiective.

Minime și maxime locale

Grafic care arată un maxim relativ și două minime ale unei funcții, dintre care unul este, de asemenea, un minim absolut.

Este $A\subseteq \mathbb {R} ^{n}$ ${\ displaystyle A \ subseteq \ mathbb {R} ^ {n}}$ ${\ displaystyle A \ subseteq \ mathbb {R} ^ {n}}$ și fie $f\colon A\to \mathbb {R}$ ${\ displaystyle f \ colon A \ to \ mathbb {R}}$ ${\ displaystyle f \ colon A \ to \ mathbb {R}}$ o functie. Un minim local (sau relativ ) este un element $\mathbf {x} ^{\ast }\in A$ ${\ displaystyle \ mathbf {x} ^ {\ ast} \ în A}$ ${\ displaystyle \ mathbf {x} ^ {\ ast} \ în A}$ astfel încât există o $\delta >0$ ${\ displaystyle \ delta> 0}$ $\ delta> 0$ pentru care cineva are $f\left(\mathbf {x} ^{\ast }\right)\leq f\left(\mathbf {x} \right)$ ${\ displaystyle f \ left (\ mathbf {x} ^ {\ ast} \ right) \ leq f \ left (\ mathbf {x} \ right)}$ ${\ displaystyle f \ left (\ mathbf {x} ^ {\ ast} \ right) \ leq f \ left (\ mathbf {x} \ right)}$ pentru fiecare $\mathbf {x} \in A$ ${\ displaystyle \ mathbf {x} \ în A}$ ${\ displaystyle \ mathbf {x} \ în A}$ astfel încât $\left\Vert \mathbf {x} -\mathbf {x} ^{\ast }\right\Vert \leq \delta .$ ${\ displaystyle \ left \ Vert \ mathbf {x} - \ mathbf {x} ^ {\ ast} \ right \ Vert \ leq \ delta.}$ ${\ displaystyle \ left \ Vert \ mathbf {x} - \ mathbf {x} ^ {\ ast} \ right \ Vert \ leq \ delta.}$ Adică în „aproape” de $\mathbf {x} ^{\ast }$ ${\ displaystyle \ mathbf {x} ^ {\ ast}}$ ${\ displaystyle \ mathbf {x} ^ {\ ast}}$ toate valorile funcției sunt mai mari sau egale cu valoarea lui $f\left(\mathbf {x} ^{\ast }\right)$ ${\ displaystyle f \ left (\ mathbf {x} ^ {\ ast} \ right)}$ ${\ displaystyle f \ left (\ mathbf {x} ^ {\ ast} \ right)}$ . Valoarea $f(\mathbf {x} ^{\ast })$ ${\ displaystyle f (\ mathbf {x} ^ {\ ast})}$ ${\ displaystyle f (\ mathbf {x} ^ {\ ast})}$ se numește valoarea minimului local .

Un punct maxim local (sau relativ ) este definit într-un mod similar.

Minime și maxime absolute

Este $A\subseteq \mathbb {R} ^{n}$ ${\ displaystyle A \ subseteq \ mathbb {R} ^ {n}}$ ${\ displaystyle A \ subseteq \ mathbb {R} ^ {n}}$ și fie $f\colon A\to \mathbb {R}$ ${\ displaystyle f \ colon A \ to \ mathbb {R}}$ ${\ displaystyle f \ colon A \ to \ mathbb {R}}$ o functie. Un minim global (sau absolut ) este un element $\mathbf {x} ^{\ast }\in A$ ${\ displaystyle \ mathbf {x} ^ {\ ast} \ în A}$ ${\ displaystyle \ mathbf {x} ^ {\ ast} \ în A}$ pentru care cineva are $f\left(\mathbf {x} ^{\ast }\right)\leq f\left(\mathbf {x} \right)$ ${\ displaystyle f \ left (\ mathbf {x} ^ {\ ast} \ right) \ leq f \ left (\ mathbf {x} \ right)}$ ${\ displaystyle f \ left (\ mathbf {x} ^ {\ ast} \ right) \ leq f \ left (\ mathbf {x} \ right)}$ pentru fiecare $\mathbf {x} \in A.$ ${\ displaystyle \ mathbf {x} \ în A.}$ ${\ displaystyle \ mathbf {x} \ în A.}$ Adică este un punct al domeniului pentru care valorile pe care funcția le asumă în celelalte puncte sunt toate mai mari sau egale cu valoarea $f\left(\mathbf {x} ^{\ast }\right)$ ${\ displaystyle f \ left (\ mathbf {x} ^ {\ ast} \ right)}$ ${\ displaystyle f \ left (\ mathbf {x} ^ {\ ast} \ right)}$ care se numește valoarea minimă absolută .

Un punct maxim global (sau absolut ) este definit într-un mod similar, adică dacă toate valorile asumate de funcție în celelalte puncte sunt mai mici sau egale cu valoarea din maximul absolut.

Programarea matematică este împărțită în mai multe familii de probleme în funcție de caracteristicile funcției obiective, constrângerile și, prin urmare, tehnicile de abordare. În general, se disting trei categorii:

Programare liniară caracterizată prin funcție obiectivă și constrângeri liniare cu valori în $\mathbb {R} ^{n}$ ${\ displaystyle \ mathbb {R} ^ {n}}$ $\ mathbb {R} ^ {n}$ ;
Programare liniară întregi caracterizată prin funcție obiectivă și constrângeri liniare cu valori în $\mathbb {Z} ^{n}$ ${\ displaystyle \ mathbb {Z} ^ {n}}$ ${\ mathbb {Z}} ^ {n}$ ;
Programare neliniară caracterizată prin funcții obiective sau constrângeri neliniare.

Metode numerice

Rezolvarea unei probleme de optimizare matematică se referă - în acest context - la

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 $f$ ${\ displaystyle f}$ $f$ , Regularitatea sa ( continuitate , diferențialitate ), proprietăți specifice ( egale , convexe ), cunoașterea vecinilor scopurilor sale,
Constrângerile $LA$ ${\ displaystyle A}$ $LA$ care caracterizează ansamblul de puncte admisibile.

Simplificări

Problema de origine este înlocuită cu o problemă echivalentă. De exemplu, cu o schimbare de variabile pentru a împărți problema în subprobleme sau înlocuirea necunoscutelor pentru a reduce numărul.

Tehnica multiplicatorului Lagrange permite depășirea unor constrângeri; această metodă este echivalentă cu introducerea unor penalități crescânde pe măsură ce punctul se apropie de constrângeri. Algoritmul multiplicator al lui Hugh Everett vă permite să actualizați în mod constant valorile multiplicatorului la fiecare iterație pentru a asigura convergența. Acesta din urmă a generalizat și interpretarea acestor multiplicatori pentru a le aplica funcțiilor care nu sunt nici continue, nici diferențiabile ^[1] .

Căutați zerourile gradientului

Numeroase metode și algoritmi pentru calcularea unui zero dintr-o funcție pot fi utilizate pentru a găsi un zero din derivata lui $f$ ${\ displaystyle f}$ $f$ (unele sunt specifice funcțiilor unei variabile ) sau gradientului acesteia $\mathbf {\nabla } f$ ${\ displaystyle \ mathbf {\ nabla} f}$ ${\ displaystyle \ mathbf {\ nabla} f}$ . Acestea se aplică valabil în situațiile în care constrângerile asupra $LA$ ${\ displaystyle A}$ $LA$ rămâne inactiv.

Toate aceste metode sunt dezvoltate ca parte a unui proces iterativ .

Aceste abordări pot suferi anumite limitări. În special:

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 aproximarea acesteia.
Nu este întotdeauna posibil să se exprime în mod explicit gradientul funcției obiective.
Condițiile inițiale trebuie stabilite înainte de a începe procesul iterativ. Alegerea inițială poate influența considerabil rezultatul (divergența de procesul iterativ). Metodele care converg rapid sunt, în general, mai sensibile în acest sens.
În unele cazuri, viteza convergenței poate fi dezastruoasă: iterații succesive se succed laborios (atunci vorbim de „stagnare”) de-a lungul unei văi înguste (funcția Rosenbrock).
Dacă soluția obținută este într-adevăr o extremă (după verificarea faptului că nu este un punct de șa), ea poate fi și locală.

Caz special: când $f$ ${\ displaystyle f}$ $f$ este polinom de gradul 2 în argumentele sale ( formă pătratică și liniară ) și fără constrângere, anularea gradientului este ca rezolvarea unui sistem liniar.

Clasificarea JEL

Journal of Economic Literature clasificare locuri de programare matematică, tehnici de optimizare, și subiecte conexe în subcategoriile JEL: C61-C63.

Notă

^ (EN) Hugh Everett, metodă de multiplicare generalizată Lagrange pentru rezolvarea problemelor de alocare optimă a resurselor, în Operations Research, vol. 11, n. 3, 1963, pp. 399-417.

Bibliografie

( EN ) Reiner Horst, Panos M. Pardalos, eds. (1995): Manual de optimizare globală , Kluwer Academic Publishers, ISBN 0-7923-3120-6
(EN) Jonas Mockus, William Eddy, Audris Mockus, Linas Mockus, Gintaras Reklaitis (1997): abordare euristică bayesiană la Discrete and Global Optimizationn, Kluwer, ISBN 0-7923-4327-1
( EN ) Hector O. Fattorini (1999): Optimizarea dimensională infinită și teoria controlului , Cambridge University Press, ISBN 0-521-45125-6
(EN) Stephen Boyd, Lieven Vandenberghe (2004): Convex Optimization, Cambridge University Press. ISBN 0-521-83378-7 , disponibil și în format PDF .
( EN ) Aleksander Schrijver (1986): Teoria programării liniare și întregi , J.Wiley , ISBN 0-471-90854-1
( EN ) Evgenij S. Levitin (1994): Teoria perturbării în programarea matematică și aplicațiile sale , J.Wiley , ISBN 0-471-93935-8

Elemente conexe

Alte proiecte

Wikimedia Commons conține imagini sau alte fișiere despre optimizare

linkuri externe

( EN ) Optimization , în Encyclopedia Britannica , Encyclopædia Britannica, Inc.

Controlul autorității	Thesaurus BNCF 21954 · LCCN (RO) sh85107312 · GND (DE) 4043664-0 · BNF (FR) cb11932649z (data)

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică

[1] (EN) Hugh Everett, metodă de multiplicare generalizată Lagrange pentru rezolvarea problemelor de alocare optimă a resurselor, în Operations Research, vol. 11, n. 3, 1963, pp. 399-417.

[1]