Programare pătratică

Programarea pătratică ( English quadratic Programming , QP ) este procesul de rezolvare a unui tip special de problemă de optimizare , și anume, problema de optimizare (minimizarea sau maximizarea) a unei funcții pătratice a mai multor variabile sub constrângeri liniare asupra acestor variabile. Programarea pătratică este un caz special de programare neliniară .

Declarația problemei

Problema programării pătratice cu n variabile și m constrângeri poate fi formulată după cum urmează [1] .

Dat:

vector real n - dimensional c ,
matrice simetrică reală n × n -dimensională Q ,
matricea reală m × n -dimensională A
vector real m -dimensional b ,

Scopul unei probleme de programare pătratică este de a găsi un vector n - dimensional x , adică

minimizează	${\tfrac {1}{2}}\mathbf {x} ^{\mathrm {T} }Q\mathbf {x} +\mathbf {c} ^{\mathrm {T} }\mathbf {x }$
in conditii	$A\mathbf {x} \leq \mathbf {b} ,$

unde x T desemnează vectorul transpus . Notația A x ≤ b înseamnă că orice element al vectorului A x nu depășește elementul corespunzător al vectorului b .

O problemă de programare înrudită, Problema cuadratică cu constrângeri cuadratice are constrângeri pătratice asupra variabilelor.

Metode de rezolvare

Pentru valorile comune se folosesc diverse metode, printre care

Metoda punctului interior
Metoda setării active [2]
Metoda Lagrangiană generalizată [3]
metoda gradientului conjugat
Metoda de proiectare a gradientului
Modificarea metodei simplex [2] [4]

În cazul în care Q este definit pozitiv , problema este un caz special al problemei de optimizare convexă mai generală .

Constrângeri - Egalități

Problema programării pătratice este oarecum mai simplă dacă Q este definit pozitiv și toate constrângerile sunt egale (fără inegalități), deoarece în acest caz este posibil să se reducă problema la rezolvarea unui sistem de ecuații liniare. Dacă folosim multiplicatori Lagrange și căutăm extremul lui Lagrange, putem arăta cu ușurință că soluția problemei

minimiza	${\tfrac {1}{2}}\mathbf {x} ^{\mathrm {T} }Q\mathbf {x} +\mathbf {c} ^{\mathrm {T} }\mathbf {x }$
in conditii	$B\mathbf {x} =\mathbf {d}$

determinată de sistemul de ecuații liniare

{\begin{bmatrix}Q&B^{T}\\B&0\end{bmatrix}}{\begin{bmatrix}\mathbf {x} \\\lambda \end{bmatrix}}={\begin{bmatrix} }} }-\mathbf {c} \\\mathbf {d} \end{bmatrix}}

unde este setul multiplicatorilor Lagrange care apar odata cu solutia . $\lambda$ ${\mathbf x}$

Cel mai simplu mod de a rezolva acest sistem este de a-l rezolva prin metode directe (de exemplu, folosind descompunerea LU , care este foarte convenabilă pentru probleme mici). Pentru probleme mari, apar unele dificultăți neobișnuite, cele mai notabile atunci când problema nu este definită pozitivă (chiar dacă este definită pozitivă), ceea ce face, potențial, foarte dificilă găsirea unei abordări matematice bune și există multe abordări dependente de problemă. $Q$ .

Dacă numărul de constrângeri nu este egal cu numărul de variabile, se poate încerca un atac relativ simplu prin înlocuirea variabilelor în așa fel încât constrângerile să fie satisfăcute necondiționat. De exemplu, să spunem că (trecerea la valori non-nule este destul de ușoară). Luați în considerare restricțiile $\mathbf {d} =0$

B\mathbf {x} =0

Introducem un nou vector definit de egalitate ${\mathbf y}$

Z\mathbf {y} =\mathbf {x}

unde are dimensiunea minus numărul de constrângeri. Apoi ${\mathbf y}$ ${\mathbf x}$

BZ\mathbf {y} =0

iar dacă matricea este aleasă astfel încât , egalitățile din constrângeri vor fi întotdeauna valabile. Găsirea unei matrice înseamnă găsirea nucleului unei matrice , ceea ce este mai mult sau mai puțin ușoară, în funcție de structura matricei . Substituind noul vector în condițiile inițiale, obținem o problemă pătratică fără restricții: $Z$ $BZ=0$ $Z$ $B$ $B$

{\tfrac {1}{2}}\mathbf {x} ^{T}Q\mathbf {x} +\mathbf {c} ^{T}\mathbf {x} \quad \Rightarrow \quad { \tfrac {1}{2}}\mathbf {y} ^{T}Z^{T}QZ\mathbf {y} +(Z^{T}\mathbf {c} )^{T}\mathbf {y }

iar soluția poate fi găsită prin rezolvarea ecuației

Z^{T}QZ\mathbf {y} =-Z^{T}\mathbf {c}

Sub unele restricții ale matricei reduse , aceasta va fi definitivă pozitivă. Puteți scrie o variantă a metodei gradientului conjugat , în care nu este nevoie să calculați în mod explicit matricea [5] . $Q$ $Z^{T}QZ$ $Z$

Dualitate lagrangiană

Problema duală Lagrange pentru programarea pătratică este, de asemenea, o problemă de programare pătratică. Pentru a înțelege acest lucru, să ne oprim asupra cazului cu o matrice Q definită pozitivă. Să scriem multiplicatorii Lagrange ai funcției $c=0$

L(x,\lambda )={\tfrac {1}{2}}x^{T}Qx+\lambda ^{T}(Ax-b).

Dacă definim funcția duală (lagrangiană) ca , căutăm o limită inferioară folosind definiția pozitivă a matricei Q: $g(\lambda )$ $g(\lambda)=\inf _{x}L(x,\lambda)$ $L$ $\nabla _{x}L(x,\lambda )=0$

x^{*}=-Q^{-1}A^{T}\lambda .

Prin urmare, funcția duală este egală cu

g(\lambda )=-{\tfrac {1}{2}}\lambda ^{T}AQ^{-1}A^{T}\lambda -\lambda ^{T}b,

iar problema duală Lagrange pentru problema originală este

minimiza	$-{\tfrac {1}{2}}\lambda ^{T}AQ^{-1}A^{T}\lambda -\lambda ^{T}b$
in conditii	$\lambda \geqslant 0$ .

Pe lângă teoria dualității Lagrange, există și alte perechi duale de probleme (de exemplu, dualitatea Wolfe ).

Dificultate

Pentru o matrice definită pozitivă Q , metoda elipsoidală rezolvă problema în timp polinomial [6] . Dacă, pe de altă parte, Q nu este definit pozitiv, atunci problema devine NP-hard [7] . De fapt, chiar dacă Q are o singură valoare proprie negativă , problema este NP-hard [8] .

Pachete de soluții și limbaje de scripting

Nume	Descriere
AIMMS	Sistem de modelare si rezolvare a problemelor de optimizare si programare
ALGLIB	Bibliotecă de programe (C++, .NET) pentru analiză numerică cu licență duală (GPL/proprietar).
AMPL	Un limbaj de modelare popular pentru optimizarea matematică la scară largă.
APMonitor	Modelare și optimizare pentru probleme LP (Programare liniară), QP (Programare cuadratică), NLP (Programare neliniară), MILP (programare întregi), MINLP (programare neliniară cu întregi mixte) și DAE (Ecuații algebrice diferențiale) în MATLAB și Piton.
CGAL	Un pachet de calcul cu geometrie open source care include un sistem pentru rezolvarea problemelor de programare pătratică.
CPLEX	Sistem popular de rezolvare a problemelor cu API-uri (C, C++, Java, .Net, Python, Matlab și R). Gratuit pentru uz academic.
Găsitor de soluții în Excel	Un sistem neliniar de rezolvare a problemelor adaptat pentru foi de calcul, în care calculele funcțiilor se bazează pe valoarea celulelor. Versiunea de bază este disponibilă ca supliment standard pentru Excel.
GAMS	Sistem de simulare la nivel înalt pentru optimizare matematică
Gurobi	Un sistem pentru rezolvarea problemelor cu algoritmi paraleli pentru probleme de programare liniară la scară largă, probleme de programare pătratică și probleme cu numere întregi mixte. Gratuit pentru uz academic.
IMSL	Un set de funcții matematice și statistice pe care un programator le poate include în aplicația sa.
IPOPT	Pachetul IPOPT (Interior Point OPTimizer) este un pachet de programare pentru probleme mari neliniare.
Artelys	Pachet integrat comercial pentru optimizare neliniară
arțar	Limbajul de programare de uz general pentru matematică. Maple folosește comanda QPSolve pentru a rezolva probleme pătratice Arhivat 12 mai 2021 la Wayback Machine .
MATLAB	Limbajul de programare de uz general orientat pe matrice pentru calcule numerice. Pentru a rezolva problemele de programare pătratică în MATLAB, în plus față de produsul de bază MATLAB, este necesar add-on-ul „Optimization Toolbox”
Mathematica	Un limbaj de programare de uz general pentru matematică, inclusiv capabilități simbolice și numerice.
MOSEK	Sistem pentru rezolvarea problemelor de optimizare la scară largă, include API pentru mai multe limbi (C++, Java, .Net, Matlab și Python)
Biblioteca numerică NAG	Un set de proceduri matematice și statistice dezvoltate de Numerical Algorithms Group pentru mai multe limbaje de programare (C, C++, Fortran, Visual Basic, Java și C#) și pachete (MATLAB, Excel, R, LabVIEW). Secțiunea de optimizare a bibliotecii NAG include proceduri pentru probleme de programare pătratică cu matrici de constrângeri rare și dense, precum și proceduri pentru optimizarea funcțiilor liniare și neliniare, sume de pătrate ale funcțiilor liniare și neliniare. Biblioteca NAG conține proceduri atât pentru optimizarea locală, cât și globală, precum și pentru problemele de programare cu numere întregi.
OptimJ	Un limbaj de modelare de optimizare, distribuit gratuit, bazat pe Java, care acceptă mai multe sisteme de decizie țintă. Există un plugin pentru Eclipse [9] [10]
R	Pachetul de calcul multiplatform cu licență GPL (vezi secțiunea quadprog Arhivat la 19 iunie 2017 pe Wayback Machine a acestui pachet). Tradus în javascript Arhivat 11 aprilie 2017 la Wayback Machine sub licență MIT . Tradus în C# Arhivat 8 aprilie 2015 la Wayback Machine sub LGPL .
SAS /OR	Un sistem pentru rezolvarea problemelor liniare, întregi, combinatorii, neliniare, nediferențiabile, probleme pe rețele și optimizare constrânsă. Limbajul de modelare algebrică OPTMODEL Arhivat pe 8 septembrie 2016 la Wayback Machine și o serie de soluții verticale care vizează sarcini specifice sunt complet integrate cu \|SAS/.
Solver	Un sistem de modelare matematică și rezolvare de probleme bazat pe un limbaj declarativ bazat pe reguli de producție. Sistemul este comercializat de Universal Technical Systems, Inc. Arhivat la 1 aprilie 2022 la Wayback Machine .
TOMLAB	Suportă optimizare globală, programare cu numere întregi, toate tipurile de cele mai mici pătrate, programare liniară pătratică pentru MATLAB . TOMLAB acceptă sistemele de soluții Gurobi, CPLEX , SNOPT și KNITRO .

Vezi și

Note

↑ Nocedal, Wright, 2006 , p. 449.
↑ 1 2 Murty, 1988 , p. xlviii+629.
↑ Delbos, Gilbert, 2005 , p. 45–69.
↑ Künzi, Crelle, 1965 , p. 161-179.
↑ Gould, Hribar, Nocedal, 2001 , p. 1376–1395
↑ Kozlov, Tarasov, Khachiyan, 1980 , p. 1049–1051.
↑ Sahni, 1974 , p. 262–279.
↑ Pardalos și Vavasis, 1991 , p. 15–22.
↑ Zesch, Hellingrath, 2010 .
↑ Burkov, Chaibdraa, 2010 .

Literatură

G.P. Künzi, W. Crelle. Programare neliniară. - Moscova: „Radio sovietic”, 1965.
Jorge Nocedal, Stephen J. Wright. Optimizare numerică . — al 2-lea. - Berlin, New York: Springer-Verlag , 2006. - P. 449 . - ISBN 978-0-387-30303-1 .
Katta G Murty. Complementaritate liniară, programare liniară și neliniară . - Berlin: Heldermann Verlag, 1988. - V. 3. - C. xlviii + 629 p.. - (Seria Sigma în matematică aplicată). — ISBN 3-88538-403-5 .
F. Delbos, J. Ch. Gilbert. Convergența liniară globală a unui algoritm lagrangian augmentat pentru rezolvarea problemelor de optimizare pătratică convexă // Journal of Convex Analysis. - 2005. - T. 12 . - S. 45-69 .
Felix Zesch, Bernd Hellingrath. Un model de optimizare pentru linii de asamblare mixte // Planificarea integrată a producției și distribuției. — 2010.
Andriy Burkov, Brahim Chaibdraa. Actele celei de-a douăzeci și patra Conferință AAAI privind inteligența artificială (AAAI-10). — Atlanta, SUA: AAAI Press, 2010.
Nicholas IM Gould, Mary E. Hribar, Jorge Nocedal. Despre soluționarea problemelor de programare pătratică constrânsă de egalitate care apar în optimizare. - SIAM Journal of Scientific Computing, 2001. - V. 23 , nr. 4 . - S. 1376-1395 .
M. K. Kozlov, S. P. Tarasov, L. G. Khachiyan. Solvabilitatea polinomială a programării pătratice convexe, Zh. Vychisl. matematica. și mat. fizica.- 1980. - T. 20, , nr. 5 .
S. Sahni. Probleme legate de calcul // SIAM Journal on Computing. - 1974. - T. 3 . - S. 262-279 . - doi : 10.1137/0203021 .
Panos M. Pardalos, Stephen A. Vavasis. Programarea pătratică cu o singură valoare negativă este NP-hard // Journal of Global Optimization. - 1991. - Vol. 1 , numărul. 1 . - S. 15-22 . - doi : 10.1007/bf00120662 .
Richard W. Cottle, Jong-Shi Pang, Richard E. Stone. Problema complementarității liniare. - Boston, MA: Academic Press, Inc., 1992. - C. xxiv + 762 pp .. - (Computer Science and Scientific Computing). — ISBN 0-12-192350-9 .
Michael R. Garey, David S. Johnson. Calculatoare și intractabilitate: un ghid pentru teoria NP-completeității . - W.H. Freeman, 1979. - ISBN 0-7167-1045-5 . A6: MP2, pag.245.
Nicholas I.M. Gould, Philippe L. Toint. O bibliografie de programare patratică (PDF). Raport intern al grupului de analiză numerică RAL 2000-1 (2000). (nedefinit)

Link -uri

O pagină despre QP Arhivată pe 7 iunie 2011 la Wayback Machine
Ghid de optimizare NEOS: programare cuadratică Arhivat 18 iunie 2017 la Wayback Machine
Rezolvați un exemplu de problemă de programare patratică (QP) Arhivat 10 mai 2015 la Wayback Machine