Kvadratisk programmering

Kvadratisk programmering ( engelsk quadratic programmering , QP ) er processen med at løse en speciel type optimeringsproblem , nemlig optimeringsproblemet (minimering eller maksimering) af en kvadratisk funktion af flere variable under lineære begrænsninger på disse variable. Kvadratisk programmering er et særligt tilfælde af ikke-lineær programmering .

Problemformulering

Problemet med kvadratisk programmering med n variable og m begrænsninger kan formuleres som følger [1] .

Givet:

reel n - dimensional vektor c ,
n × n - dimensional reel symmetrisk matrix Q ,
m × n -dimensional reel matrix A
reel m -dimensional vektor b ,

Målet med et kvadratisk programmeringsproblem er at finde en n - dimensional vektor x , dvs

minimerer	${\tfrac {1}{2}}\mathbf {x} ^{\mathrm {T} }Q\mathbf {x} +\mathbf {c} ^{\mathrm {T} }\mathbf {x }$
under forhold	$A\mathbf {x} \leq \mathbf {b} ,$

hvor x T angiver den transponerede vektor. Notationen A x ≤ b betyder, at ethvert element i vektoren A x ikke overstiger det tilsvarende element i vektoren b .

Et relateret programmeringsproblem, Quadratic Problem with Quadratic Constraints har kvadratiske begrænsninger på variabler.

Løsningsmetoder

Forskellige metoder bruges til fælles værdier, bl.a

Indvendig punktmetode
Aktiv sætmetode [2]
Generaliseret lagrangisk metode [3]
konjugeret gradient metode
Gradientprojektionsmetode
Ændring af simpleksmetoden [2] [4]

I det tilfælde, hvor Q er positiv bestemt , er problemet et specialtilfælde af det mere generelle konvekse optimeringsproblem .

Begrænsninger - ligheder

Problemet med kvadratisk programmering er noget enklere, hvis Q er positiv bestemt , og alle begrænsninger er ens (ingen uligheder), da det i dette tilfælde er muligt at reducere problemet til at løse et system af lineære ligninger. Hvis vi bruger Lagrange-multiplikatorer og leder efter ekstremum af Lagrangian, kan vi nemt vise, at løsningen på problemet

minimere	${\tfrac {1}{2}}\mathbf {x} ^{\mathrm {T} }Q\mathbf {x} +\mathbf {c} ^{\mathrm {T} }\mathbf {x }$
under forhold	$B\mathbf {x} =\mathbf {d}$

bestemmes af systemet af lineære ligninger

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

hvor er mængden af Lagrange-multiplikatorer, der vises sammen med løsningen . $\lambda$ ${\mathbf x}$

Den nemmeste måde at løse dette system på er at løse det ved direkte metoder (for eksempel ved hjælp af LU-nedbrydning , hvilket er meget praktisk til små problemer). For store problemer opstår nogle usædvanlige vanskeligheder, mest bemærkelsesværdige, når problemet ikke er positivt bestemt (selvom positivt bestemt), hvilket gør det potentielt meget svært at finde en god matematisk tilgang, og der er mange problemafhængige tilgange. $Q$ .

Hvis antallet af begrænsninger ikke er lig med antallet af variable, kan et relativt simpelt angreb forsøges ved at erstatte variablerne på en sådan måde, at begrænsningerne ubetinget er opfyldt. Lad os for eksempel sige, at (det er nemt nok at overføre til ikke-nul-værdier). Overvej begrænsningerne $\mathbf {d} =0$

B\mathbf {x} =0

Vi introducerer en ny vektor defineret af ligheden ${\mathbf y}$

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

hvor har dimensionen minus antallet af begrænsninger. Derefter ${\mathbf y}$ ${\mathbf x}$

BZ\mathbf {y} =0

og hvis matrixen er valgt sådan , vil lighederne i begrænsningerne altid holde. At finde en matrix betyder at finde kernen af en matrix , hvilket er mere eller mindre nemt, afhængigt af matrixens struktur . Ved at indsætte den nye vektor i startbetingelserne får vi et kvadratisk problem uden begrænsninger: $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 }

og løsningen kan findes ved at løse ligningen

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

Under nogle restriktioner på den reducerede matrix vil den være positiv bestemt. Du kan skrive en variant af den konjugerede gradientmetode , hvor der ikke er behov for eksplicit at beregne matricen [5] . $Q$ $Z^{T}QZ$ $Z$

Lagrangiansk dualitet

Det dobbelte Lagrange-problem til kvadratisk programmering er også et kvadratisk programmeringsproblem. For at forstå dette, lad os dvæle ved tilfældet med en positiv bestemt matrix Q. Lad os udskrive Lagrange-multiplikatorerne for funktionen $c=0$

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

Hvis vi definerer den (lagrangske) dobbeltfunktion som , leder vi efter en nedre grænse ved at bruge den positive bestemthed af matrixen Q: $g(\lambda )$ $g(\lambda )=\inf _{x}L(x,\lambda )$ $L$ $\nabla _{x}L(x,\lambda )=0$

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

Derfor er den dobbelte funktion lig med

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

og det dobbelte Lagrange-problem for det oprindelige problem er

minimere	$-{\tfrac {1}{2}}\lambda ^{T}AQ^{-1}A^{T}\lambda -\lambda ^{T}b$
under forhold	$\lambda \geqslant 0$ .

Ud over Lagrange-dualitetsteorien er der andre dobbelte par af problemer (for eksempel Wolfe-dualitet ).

Sværhedsgrad

For en positiv bestemt matrix Q løser ellipsoidmetoden problemet i polynomisk tid [6] . Hvis Q på den anden side ikke er positiv bestemt, så bliver problemet NP-hårdt [7] . Faktisk, selvom Q har en enkelt negativ egenværdi , er problemet NP-hårdt [8] .

Løsningspakker og scriptsprog

Navn	Beskrivelse
AIMMS	System til modellering og løsning af optimerings- og planlægningsproblemer
ALGLIB	Programbibliotek (C++, .NET) til numerisk analyse med dobbelt licens (GPL/proprietær).
AMPL	Et populært modelleringssprog til matematisk optimering i stor skala.
APMonitor	Modellering og optimering for LP (lineær programmering), QP (kvadratisk programmering), NLP (ikke-lineær programmering), MILP (heltalsprogrammering), MINLP (blandet heltals ikke-lineær programmering) og DAE (Differential Algebraic Equations) problemer i MATLAB og Python.
CGAL	En open source geometri computing-pakke, der inkluderer et system til løsning af kvadratiske programmeringsproblemer.
CPLEX	Populært problemløsningssystem med API'er (C, C++, Java, .Net, Python, Matlab og R). Gratis til akademisk brug.
Solution Finder i Excel	Et ikke-lineært problemløsningssystem tilpasset til regneark, hvor funktionsberegninger er baseret på værdien af celler. Basisversionen er tilgængelig som en standard tilføjelse til Excel.
GAMS	Simuleringssystem på højt niveau til matematisk optimering
Gurobi	Et system til løsning af problemer med parallelle algoritmer til store lineære programmeringsproblemer, kvadratiske programmeringsproblemer og blandede heltalsproblemer. Gratis til akademisk brug.
IMSL	Et sæt matematiske og statistiske funktioner, som en programmør kan inkludere i sin ansøgning.
IPOPT	IPOPT (Interior Point OPTimizer) pakken er en programmeringspakke til store ikke-lineære problemer.
Artelys	Kommerciel integreret pakke til ikke-lineær optimering
ahorn	Generelt programmeringssprog til matematik. Maple bruger QPSolve- kommandoen til at løse kvadratiske problemer Arkiveret 12. maj 2021 på Wayback Machine .
MATLAB	Matrix-orienteret alment programmeringssprog til numeriske beregninger. For at løse kvadratiske programmeringsproblemer i MATLAB er tilføjelsen "Optimization Toolbox" ud over det grundlæggende MATLAB-produkt påkrævet
Mathematica	Et generelt programmeringssprog til matematik, herunder symbolske og numeriske evner.
MOSEK	System til løsning af store optimeringsproblemer, inkluderer API til flere sprog (C++, Java, .Net, Matlab og Python)
NAG Numerical Library	Et sæt matematiske og statistiske procedurer udviklet af Numerical Algorithms Group til flere programmeringssprog (C, C++, Fortran, Visual Basic, Java og C#) og pakker (MATLAB, Excel, R, LabVIEW). Optimeringsdelen af NAG-biblioteket omfatter procedurer for kvadratiske programmeringsproblemer med sparsomme og tætte begrænsningsmatricer, samt procedurer til optimering af lineære og ikke-lineære funktioner, summer af kvadrater af lineære og ikke-lineære funktioner. NAG-biblioteket indeholder procedurer for både lokal og global optimering, samt for heltalsprogrammeringsproblemer.
OptimJ	Et frit distribueret, Java-baseret optimeringsmodelleringssprog, der understøtter flere målbeslutningssystemer. Der er et plugin til Eclipse [9] [10]
R	GPL -licenseret generel computerpakke på tværs af platforme (se afsnittet quadprog Arkiveret 19. juni 2017 på denne pakkes Wayback Machine ). Oversat til javascript Arkiveret 11. april 2017 på Wayback Machine under MIT-licensen . Oversat til C# Arkiveret 8. april 2015 på Wayback Machine under LGPL .
SAS /ELLER	Et system til løsning af lineære, heltallige, kombinatoriske, ikke-lineære, ikke-differentierbare problemer, problemer på netværk og begrænset optimering. Algebraic Modeling Language OPTMODEL Arkiveret 8. september 2016 på Wayback Machine og en række vertikale løsninger rettet mod specifikke opgaver er fuldt integreret med \|SAS/.
Solver	Et system af matematisk modellering og problemløsning baseret på et deklarativt sprog baseret på produktionsregler. Systemet kommercialiseres af Universal Technical Systems, Inc. Arkiveret 1. april 2022 på Wayback Machine .
TOMLAB	Understøtter global optimering, heltalsprogrammering, alle typer mindste kvadrater, lineær kvadratisk programmering til MATLAB . TOMLAB understøtter Gurobi, CPLEX , SNOPT og KNITRO løsningssystemer .

Se også

Noter

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

Litteratur

G.P. Künzi, W. Crelle. Ikke-lineær programmering. - Moskva: "Sovjetradio", 1965.
Jorge Nocedal, Stephen J. Wright. Numerisk optimering . — 2. - Berlin, New York: Springer-Verlag , 2006. - S. 449 . - ISBN 978-0-387-30303-1 .
Katta G Murty. Lineær komplementaritet, lineær og ikke-lineær programmering . - Berlin: Heldermann Verlag, 1988. - V. 3. - C. xlviii + 629 s.. - (Sigma Series in Applied Mathematics). — ISBN 3-88538-403-5 .
F. Delbos, J. Ch. Gilbert. Global lineær konvergens af en udvidet Lagrangian-algoritme til løsning af konvekse kvadratiske optimeringsproblemer // Journal of Convex Analysis. - 2005. - T. 12 . - S. 45-69 .
Felix Zesch, Bernd Hellingrath. En optimeringsmodel for samlebånd med blandede modeller // Integrated Production-Distribution Planning. – 2010.
Andriy Burkov, Brahim Chaibdraa. Proceedings of the 24th AAAI Conference on Artificial Intelligence (AAAI-10). — Atlanta, USA: AAAI Press, 2010.
Nicholas IM Gould, Mary E. Hribar, Jorge Nocedal. Om løsningen af lighedsbegrænsede kvadratiske programmeringsproblemer, der opstår i optimering. - SIAM Journal of Scientific Computing, 2001. - V. 23 , no. 4 . - S. 1376-1395 .
M.K. Kozlov, S.P. Tarasov, L.G. Khachiyan. Polynomisk solvabilitet af konveks kvadratisk programmering, Zh. Vychisl. matematik. og mat. fysik - 1980. - T. 20, , no. 5 .
S. Sahni. Beregningsrelaterede problemer // SIAM Journal on Computing. - 1974. - T. 3 . - S. 262-279 . - doi : 10.1137/0203021 .
Panos M. Pardalos, Stephen A. Vavasis. Kvadratisk programmering med én negativ egenværdi er NP-hård // Journal of Global Optimization. - 1991. - Vol. 1 , udgave. 1 . - S. 15-22 . - doi : 10.1007/bf00120662 .
Richard W. Cottle, Jong-Shi Pang, Richard E. Stone. Det lineære komplementaritetsproblem. - Boston, MA: Academic Press, Inc., 1992. - C. xxiv + 762 s .. - (Computer Science and Scientific Computing). — ISBN 0-12-192350-9 .
Michael R. Garey, David S. Johnson. Computere og intraktabilitet: En guide til teorien om NP-fuldstændighed . - W.H. Freeman, 1979. - ISBN 0-7167-1045-5 . A6: MP2, s.245.
Nicholas I.M. Gould, Philippe L. Toint. En kvadratisk programmeringsbibliografi (PDF). RAL Numerisk Analysegruppe Intern rapport 2000-1 (2000). (ubestemt)