Optimizare quadratică

În optimizarea matematică , o problemă de optimizare pătratică este o problemă de optimizare în care minimizăm (sau maximizăm) o funcție pătratică pe un poliedru convex . De constrângeri , prin urmare , pot fi descrise prin liniare funcții (unul ar spune afin ). Optimizarea pătratic este disciplina care studiază problemele. Optimizare liniară poate fi văzută ca un caz special de optimizare pătratică.

Această problemă este NP-hard în cazul general. În cazul particular al minimizării unei funcții obiective convexe , problema este polinomială și vorbim de optimizare pătratică convexă ; o disciplină deja foarte bogată, cu proprietăți mai cunoscute.

Atunci când criteriul și constrângerile reprezintă o problemă de optimizare pătratică, vorbim despre orice optimizare pătratică (en) . Această clasă de probleme conține toate optimizările polinomiale și, prin urmare, este mult mai generală decât optimizarea pătratică.

Formularea problemei

O problemă de optimizare pătratică constă în minimizarea unei funcții pătratice , nu neapărat convexe, pe un poliedru convex . $q: \ mathbb {R} ^ {n} \ to \ mathbb {R}$

Criteriul de minimizat

Funcția $q$ este definită la par $x = (x_ {1}, \ ldots, x_ {n}) \ in \ mathbb {R} ^ {n}$

${\ displaystyle q (x) = g ^ {\ mathsf {T}} x + {\ frac {1} {2}} \, x ^ {\ mathsf {T}} Hx = \ sum _ {i = 1} ^ {n} g_ {i} x_ {i} + {\ frac {1} {2}} \, \ sum _ {i = 1} ^ {n} \ sum _ {j = 1} ^ {n} H_ {ij} x_ {i} x_ {j}.}$

În prima expresie a lui $q ( x )$ , expresia sub formă de matrice, este un vector și este o matrice reală simetrică (aceasta se presupune în general că este simetrică , deoarece $q$ nu vede posibila parte antisimetrică a lui $H$ ). Nu are rost să menținem termenul constant în $q$ , deoarece nu afectează soluția problemei de minimizare. $g \ in \ mathbb {R} ^ {n}$ $H \ in \ mathbb {R} ^ {n \ times n}$

Reamintim că o astfel de funcție pătratică $q$ este

convex dacă și numai dacă matricea $H$ este semidefinită pozitivă ,
strict convex dacă și numai dacă matricea $H$ este pozitivă definită .

Constrângeri

De asemenea, impunem vectorului căutat $x$ să aparțină unui poliedru convex , ceea ce înseamnă a spune că $x$ trebuie să satisfacă un număr finit de constrângeri afine. Acestea pot lua diferite forme, cum ar fi

${\ begin {array} {ll} l_ {B} \ leqslant x \ leqslant u_ {B} & {\ mbox {(constrângeri legate)}} \\ l_ {I} \ leqslant A_ {I} x \ leqslant u_ { I} & {\ mbox {(constrângeri de egalitate afine)}} \\ A_ {E} x = b_ {E} & {\ mbox {(constrângeri de egalitate afine),}} \ end {array}}$

expresii în care am remarcat

Vectorii $l$ $B$ și $u B$ de pot lua, prin urmare, valori infinite și satisfăcând $l$ $B$ $<$ $u$ $B$ , ${\ bar {\ mathbb {R}}} ^ {n}$
$A_ {I} \ in \ mathbb {R} ^ {m_ {I} \ times n}$ o matrice reală de tip $m I \times n$ ( $A I x$ denotă produsul matricei $A I$ prin vectorul $x$ ),
Vectorii $l$ $I$ și $l I$ pot, prin urmare, să ia valori infinite și să verifice $l$ $I$ $<$ $u$ $I$ , ${\ bar {\ mathbb {R}}} ^ {m_ {I}}$
$A_ {E} \ in \ mathbb {R} ^ {m_ {E} \ times n}$ o matrice reală de tip $m E \times n$ ,
$b_ {E} \ in \ mathbb {R} ^ {m_ {E}}$ un adevărat vector.

Va fi interesant să folosiți notația compactă

$[l_ {B}, u_ {B}]: = \ {x \ in \ mathbb {R} ^ {n}: l_ {B} \ leqslant x \ leqslant u_ {B} \}$

și o definiție similară pentru $[ l I , u I ]$ . Notăm cu $X Q$ setul admisibil definit de toate constrângerile de mai sus, și anume

${\ displaystyle X_ {Q}: = \ {x \ in \ mathbb {R} ^ {n}: x \ in [l_ {B}, u_ {B}], ~ A_ {I} x \ in [l_ { I}, u_ {I}], ~ A_ {E} x = b_ {E} \}.}$

Formulare compactă

Prin urmare, într-un mod compact, putem scrie problema de optimizare pătratică după cum urmează

$(P_ {Q}) \ quad \ inf _ {x \ în X_ {Q}} \, q (x).$

Spunem că această problemă este convexă dacă criteriul $q$ este convex , ceea ce este cazul dacă și numai dacă, $H$ este semidefinit pozitiv.

Analiza problemelor

Existența soluției

Rezultatul fundamental se datorează lui Frank și Wolfe (1956). Este de același tip ca cel cunoscut în optimizarea liniară . să ne amintim asta

se spune că o problemă de optimizare este fezabilă dacă setul său admisibil nu este gol (ceea ce înseamnă că valoarea sa optimă nu este egală cu $+ \infty$ ),
se spune că o problemă de optimizare fezabilă este limitată dacă valoarea sa optimă nu este $egală$ cu $-\infty$ (nu se poate găsi o serie de puncte admisibile care să orienteze criteriul către – $towards$ ).

Existența soluției - Pentru o problemă de optimizare pătratică (nu neapărat convexă), următoarele proprietăți sunt echivalente:

problema are o soluție,
problema este fezabilă și limitată,
valoarea optimă a problemei este finită.

Unicitatea soluției va apărea cu siguranță dacă $q$ este strict convex , dar ar putea apărea fără ea. Acesta este cazul, de exemplu, pentru problema cu o singură variabilă $inf { x : x \geq 0}$ , al cărei criteriu este liniar (deci nu este strict convex).

Bornitude

Iată o caracterizare a caracterului mărginit (sau nelimitat) al unei probleme pătratice convexe fezabile (adică una dintre care mulțimea admisibilă este neocupată) în ceea ce privește existența unei direcții care are interese teoretice și digitale. Aceasta a observat $X \infty$ conul asimptotic al setului $X$ .

Bornitudinea unei probleme pătratice convexe - Pentru o problemă fezabilă de optimizare pătratică convexă , a cărei mulțime poliedrică admisibilă este notată cu $X$ , următoarele proprietăți sunt echivalente:

problema este nelimitată,
există o direcție $d$ astfel încât , și . $g ^ {\ top} d <0$ $Hd = 0$ $d \ in X ^ {\ infty}$

Se scrie conul asimptotic al setului admisibil $X Q$ definit mai sus (presupus că nu este gol)

$X_ {Q} ^ {\ infty} = \ {d \ in \ mathbb {R} ^ {n}: d \ in [l_ {B}, u_ {B}] ^ {\ infty}, ~ A_ {I} d \ in [l_ {I}, u_ {I}] ^ {\ infty}, ~ A_ {E} d = 0 \}.$

Expresia lui $[ l , u ] \infty$ este dată în pagina de pe conul asimptotic .

Metode de rezoluție

Dacă există doar constrângeri de egalitate, problema se rezumă la rezolvarea unui sistem liniar. În prezența constrângerilor de inegalitate, problema în general este NP-hard și poate fi rezolvată prin următoarele abordări:

Algoritm de activare ,
Conjugați algoritmul de gradient (extensii),
Algoritmul gradientului proiectat ,
Algoritm Lagrangian mărit ,
Metoda Nelder-Mead (extensii).
Algoritmi de punct interior (pentru problema convexă).

Anexe

Notă

A se vedea apendicele (i) al articolului.
Vezi de exemplu Lemma 2.2 în articolul lui Chiche și Gilbert (2014).
Multe contribuții pe această temă. Articolul lui Delbos și Gilbert (2005) analizează convergența sa liniară globală atunci când problema are o soluție; cel al lui Chiche și Gilbert (2014) analizează comportamentul atunci când problema nu este fezabilă.

Articole similare

Link extern

Modele și metode de cercetare operațională (Paul A. Jensen și Jonathan F. Bard) [1]

Bibliografie

(ro) A. Chiche, J. Ch. Gilbert (2016). Modul în care algoritmul Lagrangian mărit poate face față unei probleme de optimizare pătratică convexă invizibilă. Journal of Convex Analysis , 23: 2, 425-459.
(ro) F. Delbos, J. Ch. Gilbert (2005). Convergența liniară globală a unui algoritm Lagrangian mărit pentru rezolvarea problemelor de optimizare pătratică convexă. Journal of Convex Analysis , 12, 45-69. [2]
(ro) M. Frank, P. Wolfe (1956). Un algoritm pentru programarea pătratică. Naval Research Logistics Quarterly , 3, 95-110.