Programare secvenţială pătratică

Programarea secvenţială pătratică ( SQP ) este unul dintre cei mai obişnuiţi şi eficienţi algoritmi de optimizare cu scop general [1] , ideea principală a căruia este soluţia secvenţială a problemelor de programare pătratică care aproximează o anumită problemă de optimizare . Pentru probleme de optimizare fără constrângeri , algoritmul SQP este transformat în metoda lui Newton de a găsi punctul în care gradientul funcției obiectiv dispare. Pentru a rezolva problema inițială cu constrângeri de egalitate, metoda SQP este transformată într-o implementare specială a metodelor newtoniene de rezolvare a sistemului Lagrange .

Informații de bază

Luați în considerare o problemă de programare neliniară de următoarea formă:

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

sub restricții

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

Lagrangianul problemei ia următoarea formă:

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

unde și sunt multiplicatorii Lagrange . $\lambda$ $\sigma$

La iterația algoritmului principal, direcțiile de căutare corespunzătoare sunt determinate ca o soluție la următoarea subproblemă de programare pătratică : $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,

sub restricții

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

Vezi și

metoda lui Newton

Note

↑ Ghidul utilizatorului Trifonov A.G. Optimization Toolbox 2.2 Copie de arhivă din 11 august 2016 la Wayback Machine // Softline Co.

Literatură

Programare secvenţială pătratică

Metode de optimizare
Unidimensional	metoda secțiunii de aur Dihotomie Metoda parabolelor Căutare în grilă Metoda de căutare uniformă a blocurilor Metoda Fibonacci Căutare ternară metoda Piyavsky Metoda Strongin
Comanda zero	metoda Gauss Metoda Nelder-Mead Metoda Hook-Jeeves metoda Rosenbrock metoda Powell
Prima comanda	coborâre în gradient Metoda Zeutendijk Coordonarea coborârii Metoda gradientului conjugat Metode cvasi-newtoniene Algoritmul Levenberg-Marquardt
a doua comanda	metoda lui Newton Metoda Newton-Raphson Algoritmul Broyden-Fletcher-Goldfarb-Shanno (BFGS)
Stochastic	Metoda Monte Carlo Recoacere simulată Algoritmi evolutivi evolutie diferentiala Algoritmul furnicilor Metoda roiului de particule Algoritmul coloniilor de albine Metoda de mers aleatoriu
Metode de programare liniară	Metoda simplex algoritmul lui Gomori Metoda elipsoidă Metoda potențială
Metode de programare neliniară	Programare secvenţială pătratică