Programare pătratică secvențială - Sequential quadratic programming

Programarea pătratică secvențială ( SQP ) este o metodă iterativă pentru optimizarea neliniară constrânsă . Metodele SQP sunt utilizate pe probleme matematice pentru care funcția obiectivă și constrângerile sunt de două ori diferențiate continuu .

Metodele SQP rezolvă o succesiune de subprobleme de optimizare, fiecare optimizând un model pătratic al obiectivului supus unei liniarizări a constrângerilor. Dacă problema este nelimitată, atunci metoda se reduce la metoda lui Newton pentru găsirea unui punct în care gradientul obiectivului dispare. Dacă problema are doar constrângeri de egalitate, atunci metoda este echivalentă cu aplicarea metodei lui Newton în condițiile de optimitate de prim ordin sau în condițiile Karush – Kuhn – Tucker ale problemei.

Bazele algoritmului

Luați în considerare o problemă de programare neliniară a formei:

${\ displaystyle {\ begin {array} {rl} \ min \ limits _ {x} & f (x) \\ {\ mbox {subject to}} & b (x) \ geq 0 \\ & c (x) = 0. \ end {array}}}$

Lagrangianului pentru această problemă este

${\ displaystyle {\ mathcal {L}} (x, \ lambda, \ sigma) = f (x) - \ lambda b (x) - \ sigma c (x),}$

unde și sunt multiplicatorii Lagrange . La o iterație , un algoritm de programare pătratică secvențială de bază definește o direcție de căutare adecvată ca soluție la subproblema de programare pătratică${\ displaystyle \ lambda}$${\ displaystyle \ sigma}$${\ displaystyle x_ {k}}$${\ displaystyle d_ {k}}$

${\ displaystyle {\ begin {array} {rl} \ min \ limits _ {d} & f (x_ {k}) + \ nabla f (x_ {k}) ^ {T} d + {\ tfrac {1} {2 }} d ^ {T} \ nabla _ {xx} ^ {2} {\ mathcal {L}} (x_ {k}, \ lambda _ {k}, \ sigma _ {k}) d \\\ mathrm { st} & b (x_ {k}) + \ nabla b (x_ {k}) ^ {T} d \ geq 0 \\ & c (x_ {k}) + \ nabla c (x_ {k}) ^ {T} d = 0. \ end {array}}}$

Rețineți că termenul din expresia de mai sus poate fi lăsat în afara problemei de minimizare, deoarece este constant sub operator. ${\ displaystyle f (x_ {k})}$${\ displaystyle \ min \ limits _ {d}}$

Abordări alternative

• Programare liniară secvențială
• Programare liniar-pătratică secvențială
• Metoda Lagrangiană mărită

Implementări

Metodele SQP au fost implementate în medii numerice bine cunoscute, cum ar fi MATLAB și GNU Octave . Există, de asemenea, numeroase biblioteci de software, inclusiv open source:

• SciPy (standard de facto pentru Python științific) are scipy.optimize.minimize (method = 'SLSQP') solver.
• NLopt ( implementare C / C ++, cu numeroase interfețe, inclusiv Julia, Python, R, MATLAB / Octave), implementat de Dieter Kraft ca parte a unui pachet pentru un control optim și modificat de SG Johnson.
• LabVIEW
• KNITRO (C, C ++, C #, Java, Python, Fortran)
• NPSOL (Fortran)
• SNOPT (Fortran)
• NLPQL (Fortran)
• MATLAB
• SuanShu (Java)

Vezi si

• Algoritmul Josephy-Newton
• Metoda lui Newton
• Metoda securizată

Note

Referințe

• Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude ; Sagastizábal, Claudia A. (2006). Optimizare numerică: aspecte teoretice și practice . Universitext (a doua ediție revizuită a traducerii ediției franceze din 1997). Berlin: Springer-Verlag. str. xiv + 490. doi : 10.1007 / 978-3-540-35447-5 . ISBN   978-3-540-35445-1 . MR   2265882 .
• Jorge Nocedal și Stephen J. Wright (2006). Optimizare numerică . Springer. ISBN   978-0-387-30303-1 .

linkuri externe

• Programare quadratică secvențială la ghidul NEOS

Acest articol legat de matematica aplicată este un butuc . Puteți ajuta Wikipedia extinzându-l . v t e