Sekvenční kvadratické programování

Sekvenční kvadratické programování ( SQP ) je jedním z nejběžnějších a nejefektivnějších univerzálních optimalizačních algoritmů [1] , jehož hlavní myšlenkou je sekvenční řešení problémů kvadratického programování, které aproximují daný optimalizační problém . Pro optimalizační problémy bez omezení je algoritmus SQP transformován do Newtonovy metody nalezení bodu, ve kterém gradient účelové funkce jde na nulu. Pro vyřešení původního problému s omezeními rovnosti je metoda SQP transformována do speciální implementace newtonovských metod pro řešení Lagrangeova systému .

Základní informace

Zvažte problém nelineárního programování následujícího tvaru:

\min \limits _{x}f(x),

pod omezeními

b(x)\geqslant 0,\;c(x)=0.

Lagrangián problému má následující podobu:

L(x,\;\lambda ,\;\sigma )=f(x)-\lambda ^{T}b(x)-\sigma ^{T}c(x),

kde a jsou Lagrangeovy multiplikátory . $\lambda$ $\sigma$

Při iteraci hlavního algoritmu se určí odpovídající směry hledání jako řešení následujícího dílčího problému kvadratického programování : $x_k$ $d_{k}$

\min \limits _{d}L(x_{k},\;\lambda _{k},\;\sigma _{k})+\nabla L(x_{k},\;\lambda _{k},\;\sigma _{k})^{T}d+{\frac {1}{2}}d^{T}\nabla _{xx}^{2}L(x_{k} ,\;\lambda _{k},\;\sigma _{k})d,

pod omezeními

b(x_{k})+\nabla b(x_{k})^{T}d\geqslant 0,\;c(x_{k})+\nabla c(x_{k})^{ T}d=0.

Viz také

Newtonova metoda

Poznámky

↑ Uživatelská příručka Trifonov A.G. Optimization Toolbox 2.2 Archivní kopie ze dne 11. srpna 2016 na Wayback Machine // Softline Co.

Literatura

Sekvenční kvadratické programování

Optimalizační metody
Jednorozměrný	metoda zlatého řezu Dichotomie Parabolová metoda Vyhledávání v mřížce Jednotná metoda vyhledávání bloků Fibonacciho metoda Ternární hledání Piyavského metoda Stronginovou metodou
Nulové pořadí	Gaussova metoda Metoda Nelder-Mead Hook-Jeevesova metoda Rosenbrockova metoda Powellova metoda
První objednávka	gradientní sestup Zeutendijkova metoda Souřadnicový sestup Metoda konjugovaného gradientu Kvazi-newtonské metody Levenberg-Marquardtův algoritmus
druhá objednávka	Newtonova metoda Newton-Raphsonova metoda Algoritmus Broyden-Fletcher-Goldfarb-Shanno (BFGS)
Stochastické	Metoda Monte Carlo Simulované žíhání Evoluční algoritmy diferenciální evoluce Algoritmus mravenců Metoda roje částic Algoritmus včelstva Metoda náhodné chůze
Metody lineárního programování	Simplexní metoda Gomoriho algoritmus Elipsoidní metoda Potenciální metoda
Metody nelineárního programování	Sekvenční kvadratické programování