Sekvenční kvadratické programování - Sequential quadratic programming

tento článek poskytuje nedostatečný kontext pro ty, kteří danému tématu nejsou obeznámeni. Prosím pomozte vylepšit článek podle poskytuje čtenáři více kontextu. (Říjen 2009) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

Sekvenční kvadratické programování (SQP) je iterační metoda pro omezená nelineární optimalizace. Metody SQP se používají na matematický problémy, pro které Objektivní funkce a omezení jsou dvakrát průběžně diferencovatelné.

Metody SQP řeší posloupnost optimalizačních dílčích problémů, z nichž každý optimalizuje kvadratický model objektového objektu s linearizací omezení. Pokud je problém neomezený, metoda se redukuje na Newtonova metoda pro nalezení bodu, kde gradient cíle zmizí. Pokud má problém pouze omezení rovnosti, pak je metoda ekvivalentní použití Newtonova metoda na podmínky optimality prvního řádu nebo Karush – Kuhn – Tuckerovy podmínky, problému.

Základy algoritmu

Zvažte a nelineární programování problém formy:

${displaystyle {egin {array} {rl} min limity _ {x} & f (x) {mbox {s.t.}} & b (x) geq 0 & c (x) = 0.end {pole}}}$

The Lagrangian pro tento problém je^[1]

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

kde ${displaystyle lambda}$ a ${displaystyle sigma}$ jsou Lagrangeovy multiplikátory. Opakovaně ${displaystyle x_ {k}}$, základní sekvenční kvadratický programovací algoritmus definuje vhodný směr hledání ${displaystyle d_ {k}}$ jako řešení kvadratické programování dílčí problém

${displaystyle {egin {array} {rl} min limity _ {d} & f (x_ {k}) + abla f (x_ {k}) ^ {T} d + {frac {1} {2}} d ^ {T } abla _ {xx} ^ {2} {mathcal {L}} (x_ {k}, lambda _ {k}, sigma _ {k}) d mathrm {st} & b (x_ {k}) + abla b (x_ {k}) ^ {T} dgeq 0 & c (x_ {k}) + abla c (x_ {k}) ^ {T} d = 0.end {pole}}}$

Všimněte si, že termín ${displaystyle f (x_ {k})}$ ve výrazu výše může být vynechán pro problém s minimalizací, protože je konstantní pod ${limity minimálního zobrazení _ {d}}$ operátor.

Alternativní přístupy

• Sekvenční lineární programování
• Sekvenční lineární kvadratické programování
• Rozšířená Lagrangeova metoda

Implementace

Metody SQP byly implementovány ve známých numerických prostředích, jako jsou MATLAB a GNU oktáva. Existuje také řada softwarových knihoven, včetně open source:

• SciPy (de facto standard pro vědecký Python) má scipy.optimize.minimize (method = ‘SLSQP’) solver.
• NLopt (C / C ++ implementace, s četnými rozhraními včetně Julia, Python, R, MATLAB / Octave), implementováno Dieterem Kraftem jako součást balíčku pro optimální ovládání a upraveno S. G. Johnsonem.^[2][3]
• LabVIEW
• KNITRO^[4] (C, C ++, C #, Java, Python, Fortran)
• NPSOL (Fortran)
• SNOPT (Fortran)
• NLPQL (Fortran)
• MATLAB
• SuanShu (Jáva)

Viz také

• Algoritmus Josephy-Newton
• Newtonova metoda
• Sekanční metoda

Poznámky

Reference

• Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude; Sagastizábal, Claudia A. (2006). Numerická optimalizace: Teoretické a praktické aspekty. Universitext (druhé přepracované vydání překladu z roku 1997, francouzské vydání). Berlín: Springer-Verlag. str. xiv + 490. doi:10.1007/978-3-540-35447-5. ISBN  978-3-540-35445-1. PAN  2265882.
• Jorge Nocedal a Stephen J. Wright (2006). Numerická optimalizace. Springer. ISBN  978-0-387-30303-1.

externí odkazy

• Sekvenční kvadratické programování v příručce NEOS

Tento aplikovaná matematika související článek je a pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to.