Neliöllinen ohjelmointi

Neliöllinen ohjelmointi ( englanniksi quadratic programming , QP ) on prosessi, jossa ratkaistaan erityinen optimointiongelma , nimittäin useiden muuttujien neliöfunktion optimointiongelma (minimointi tai maksimointi) näiden muuttujien lineaaristen rajoitusten alaisena . Neliöllinen ohjelmointi on epälineaarisen ohjelmoinnin erikoistapaus .

Ongelman kuvaus

Neliöllisen ohjelmoinnin ongelma n muuttujan ja m rajoitteen kanssa voidaan muotoilla seuraavasti [1] .

Annettu:

todellinen n - ulotteinen vektori c ,
n × n -ulotteinen reaalisymmetrinen matriisi Q ,
m × n -ulotteinen reaalimatriisi A
todellinen m -ulotteinen vektori b ,

Neliöllisen ohjelmointitehtävän tavoitteena on löytää n - ulotteinen vektori x , joka on

minimoi	${\tfrac {1}{2}}\mathbf {x} ^{\mathrm {T} }Q\mathbf {x} +\mathbf {c} ^{\mathrm {T} }\mathbf {x }$
olosuhteissa	$A\mathbf {x} \leq \mathbf {b} ,$

missä x T tarkoittaa transponoitua vektoria. Merkintä A x ≤ b tarkoittaa, että mikään vektorin A x alkio ei ylitä vektorin b vastaavaa alkiota .

Asiaan liittyvä ohjelmointiongelma, Quadratic Problem with Quadratic Constraints sisältää neliötason rajoituksia muuttujille.

Ratkaisumenetelmät

Yhteisille arvoille käytetään erilaisia menetelmiä mm

Sisäpistemenetelmä
Active Set Method [2]
Yleistetty Lagrangin menetelmä [3]
konjugaattigradienttimenetelmä
Gradienttiprojektiomenetelmä
Simpleksimenetelmän muunnos [ 2] [4]

Siinä tapauksessa, että Q on positiivinen definiitti , ongelma on yleisemmän konveksin optimointitehtävän erikoistapaus .

Rajoitukset - yhtäläisyydet

Neliöllisen ohjelmoinnin ongelma on hieman yksinkertaisempi, jos Q on positiivinen määrätty ja kaikki rajoitukset ovat yhtä suuret (ei epäyhtälöjä), koska tässä tapauksessa on mahdollista pelkistää ongelma lineaarisen yhtälöjärjestelmän ratkaisemiseksi. Jos käytämme Lagrangen kertoimia ja etsimme Lagrangenin ääripäätä, voimme helposti osoittaa, että ongelman ratkaisu

minimoida	${\tfrac {1}{2}}\mathbf {x} ^{\mathrm {T} }Q\mathbf {x} +\mathbf {c} ^{\mathrm {T} }\mathbf {x }$
olosuhteissa	$B\mathbf {x} =\mathbf {d}$

määritetään lineaarisen yhtälöjärjestelmän avulla

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

missä on ratkaisun mukana ilmestyvien Lagrange-kertoimien joukko . $\lambda$ ${\mathbf x}$

Helpoin tapa ratkaista tämä järjestelmä on ratkaista se suorilla menetelmillä (esimerkiksi käyttämällä LU-hajoamista , joka on erittäin kätevä pienille ongelmille). Suurissa ongelmissa esiintyy epätavallisia vaikeuksia, jotka ovat merkittävimpiä silloin, kun ongelma ei ole positiivinen (vaikka se olisi positiivinen), mikä tekee hyvän matemaattisen lähestymistavan löytämisen mahdollisesti erittäin vaikeaksi, ja ongelmariippuvaisia lähestymistapoja on monia. $K$ .

Jos rajoitusten määrä ei ole yhtä suuri kuin muuttujien lukumäärä, voidaan kokeilla suhteellisen yksinkertaista hyökkäystä korvaamalla muuttujat siten, että rajoitukset täyttyvät ehdoitta. Oletetaan esimerkiksi, että (ei-nolla-arvoihin siirtyminen on tarpeeksi helppoa). Harkitse rajoituksia $\mathbf {d} =0$

B\mathbf {x} =0

Esittelemme uuden tasa-arvon määrittelemän vektorin ${\mathbf y}$

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

missä on ulottuvuus miinus rajoitusten määrä. Sitten ${\mathbf y}$ ${\mathbf x}$

BZ\mathbf {y} =0

ja jos matriisi valitaan niin, että , yhtäläisyydet rajoituksissa pysyvät aina. Matriisin löytäminen tarkoittaa matriisin ytimen löytämistä , mikä on enemmän tai vähemmän helppoa matriisin rakenteesta riippuen . Korvaamalla uuden vektorin alkuehtoihin, saadaan neliöllinen ongelma ilman rajoituksia: $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 }

ja ratkaisu löytyy ratkaisemalla yhtälö

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

Joillakin pelkistetyn matriisin rajoituksilla se on positiivinen. Voit kirjoittaa muunnelman konjugaattigradienttimenetelmästä , jossa matriisia ei tarvitse erikseen laskea [5] . $K$ $Z^{T}QZ$ $Z$

Lagrangian kaksinaisuus

Kaksois -Lagrange-tehtävä neliöllisen ohjelmoinnin yhteydessä on myös neliöllisen ohjelmoinnin ongelma. Tämän ymmärtämiseksi tarkastellaan tapausta positiivisen määrätyn matriisin Q kanssa. Kirjoitetaan funktion Lagrange-kertoimet $c = 0$

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

Jos määritämme (Lagrangin) kaksoisfunktion muodossa , etsimme alarajaa käyttämällä matriisin Q positiivista määritystä: $g(\lambda )$ $g(\lambda )=\inf _{x}L(x,\lambda )$ $L$ $\nabla _{x}L(x,\lambda )=0$

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

Siksi kaksoisfunktio on yhtä suuri kuin

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

ja alkuperäisen ongelman kaksois-Lagrangen ongelma on

minimoida	$-{\tfrac {1}{2}}\lambda ^{T}AQ^{-1}A^{T}\lambda -\lambda ^{T}b$
olosuhteissa	$\lambda \geqslant 0$ .

Lagrangen duaalisuusteorian lisäksi on olemassa muita ongelmapareja (esim. Wolfe duality ).

Vaikeus

Positiiviselle määrätylle matriisille Q ellipsoidimenetelmä ratkaisee ongelman polynomiajassa [6] . Jos toisaalta Q ei ole positiivinen definiitti, niin ongelmasta tulee NP-kova [7] . Itse asiassa, vaikka Q :lla olisi yksi negatiivinen ominaisarvo , ongelma on NP-kova [8] .

Ratkaisupaketit ja komentosarjakielet

Nimi	Kuvaus
AIMMS	Järjestelmä optimointi- ja aikataulutusongelmien mallintamiseen ja ratkaisemiseen
ALGLIB	Ohjelmakirjasto (C++, .NET) numeerista analyysiä varten kaksoislisensoinnilla (GPL/omistettu).
AMPL	Suosittu mallinnuskieli laajamittaiseen matemaattiseen optimointiin.
APMonitor	Mallintaminen ja optimointi LP (Lineaarinen ohjelmointi), QP (Kvadraattinen ohjelmointi), NLP (Epälineaarinen Ohjelmointi), MILP (Integer Programming), MINLP (Mixed Integer Nonlinear Programming) ja DAE (differentiaalialgebralliset yhtälöt) -ongelmille MATLABissa ja Python.
CGAL	Avoimen lähdekoodin geometrialaskentapaketti, joka sisältää järjestelmän neliöllisen ohjelmoinnin ongelmien ratkaisemiseen.
CPLEX	Suosittu ongelmanratkaisujärjestelmä API:illa (C, C++, Java, .Net, Python, Matlab ja R). Ilmainen akateemiseen käyttöön.
Ratkaisuhaku Excelissä	Laskentataulukoihin sovitettu epälineaarinen ongelmanratkaisujärjestelmä, jossa funktiolaskelmat perustuvat solujen arvoon. Perusversio on saatavana Excelin vakiolisäosana.
GAMS	Korkean tason simulointijärjestelmä matemaattiseen optimointiin
Gurobi_	Järjestelmä ongelmien ratkaisemiseen rinnakkaisilla algoritmeilla suurissa lineaarisissa ohjelmointitehtävissä, neliöllisen ohjelmoinnin tehtävissä ja sekakokonaislukutehtävissä. Ilmainen akateemiseen käyttöön.
IMSL_	Joukko matemaattisia ja tilastollisia toimintoja, jotka ohjelmoija voi sisällyttää sovellukseensa.
IPOPT	IPOPT (Interior Point OPTimizer) -paketti on ohjelmointipaketti suuriin epälineaarisiin ongelmiin.
Artelys	Kaupallinen integroitu paketti epälineaariseen optimointiin
vaahtera	Yleiskäyttöinen ohjelmointikieli matematiikan tarpeisiin. Maple käyttää QPSolve- komentoa kvadraattisten ongelmien ratkaisemiseen . Arkistoitu 12. toukokuuta 2021 Wayback Machinessa .
MATLAB	Matriisisuuntautunut yleiskäyttöinen ohjelmointikieli numeerisia laskelmia varten. Kvadraattisten ohjelmointiongelmien ratkaisemiseksi MATLABissa tarvitaan MATLAB-perustuotteen lisäksi "Optimization Toolbox" -lisäosa.
Mathematica	Yleiskäyttöinen matematiikan ohjelmointikieli, joka sisältää symbolisia ja numeerisia ominaisuuksia.
MOSEK	Järjestelmä laajamittaisten optimointiongelmien ratkaisemiseen, sisältää API useille kielille (C++, Java, .Net, Matlab ja Python)
NAG Numerical Library	Numerical Algorithms Groupin kehittämä matemaattisten ja tilastollisten menettelyjen sarja useille ohjelmointikielille (C, C++, Fortran, Visual Basic, Java ja C#) ja paketeille (MATLAB, Excel, R, LabVIEW). NAG-kirjaston optimointiosio sisältää proseduurit toisen asteen ohjelmointiongelmiin, joissa on harvat ja tiheät rajoitematriisit, sekä menettelyt lineaaristen ja epälineaaristen funktioiden, lineaaristen ja epälineaaristen funktioiden neliösumman optimoimiseksi. NAG-kirjasto sisältää menettelyjä sekä paikallista että globaalia optimointia varten sekä kokonaislukuohjelmointiongelmia.
OptimJ_	Vapaasti jaettu Java-pohjainen optimointimallinnuskieli, joka tukee useita kohdepäätösjärjestelmiä. Eclipselle on lisäosa [9] [10]
R	GPL -lisensoitu yleiskäyttöinen cross-platform laskentapaketti (katso osa quadprog Arkistoitu 19. kesäkuuta 2017 tämän paketin Wayback Machinessa ). Käännetty javascriptiksi Arkistoitu 11. huhtikuuta 2017 Wayback Machinessa MIT -lisenssillä . Käännetty C#: ksi Arkistoitu 8. huhtikuuta 2015 Wayback Machinessa LGPL :n alla .
SAS /TAI	Järjestelmä lineaaristen, kokonaislukujen, kombinatoristen, epälineaaristen, ei-differentoivien ongelmien, verkkoongelmien ja rajoitetun optimoinnin ratkaisemiseen. Algebrallinen mallinnuskieli OPTMODEL Arkistoitu 8. syyskuuta 2016 Wayback Machinessa , ja joukko tiettyihin tehtäviin tarkoitettuja vertikaalisia ratkaisuja on täysin integroitu \|SAS/:n kanssa.
Ratkaisija	Matemaattisen mallinnuksen ja ongelmanratkaisun järjestelmä, joka perustuu tuotantosääntöihin perustuvaan deklaratiiviseen kieleen. Järjestelmän kaupallistaa Universal Technical Systems, Inc. Arkistoitu 1. huhtikuuta 2022 Wayback Machinessa .
TOMLAB	Tukee maailmanlaajuista optimointia, kokonaislukuohjelmointia, kaikentyyppisiä pienimmän neliösumman laskentaa, lineaarista neliöllistä ohjelmointia MATLABille . TOMLAB tukee Gurobi-, CPLEX- , SNOPT- [ - ja KNITRO- ratkaisujärjestelmiä .

Katso myös

Muistiinpanot

↑ 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 ja Vavasis, 1991 , s. 15–22.
↑ Zesch, Hellingrath, 2010 .
↑ Burkov, Chaibdraa, 2010 .

Kirjallisuus

G.P. Künzi, W. Crelle. Epälineaarinen ohjelmointi. - Moskova: "Neuvostoliiton radio", 1965.
Jorge Nocedal, Stephen J. Wright. Numeerinen optimointi . – 2. - Berliini, New York: Springer-Verlag , 2006. - S. 449 . - ISBN 978-0-387-30303-1 .
Katta G Murty. Lineaarinen täydentävyys, lineaarinen ja epälineaarinen ohjelmointi . - Berliini: Heldermann Verlag, 1988. - V. 3. - C. xlviii + 629 s.. - (Sigma-sarja Applied Mathematics). — ISBN 3-88538-403-5 .
F. Delbos, J. Ch. Gilbert. Lisätyn Lagrange-algoritmin globaali lineaarinen konvergenssi konveksin neliöllisen optimointiongelmien ratkaisemiseksi // Journal of Convex Analysis. - 2005. - T. 12 . - S. 45-69 .
Felix Zesch, Bernd Hellingrath. Sekamallien kokoonpanolinjojen optimointimalli // Integrated Production-Distribution Planning. – 2010.
Andriy Burkov, Brahim Chaibdraa. Tekoälyä käsittelevän 24. AAAI-konferenssin (AAAI-10) aineisto. - Atlanta, USA: AAAI Press, 2010.
Nicholas IM Gould, Mary E. Hribar, Jorge Nocedal. Optimoinnissa syntyvien tasa-arvorajoitteisten kvadratuuriohjelmointiongelmien ratkaisusta. - SIAM Journal of Scientific Computing, 2001. - V. 23 , no. 4 . - S. 1376-1395 .
M. K. Kozlov, S. P. Tarasov, L. G. Khachiyan. Konveksin toisen asteen ohjelmoinnin polynomiratkaistuvuus, Zh. Vychisl. matematiikka. ja matto. fysiikka - 1980. - T. 20, , no. 5 .
S. Sahni. Laskennalliset ongelmat // SIAM Journal on Computing. - 1974. - T. 3 . - S. 262-279 . - doi : 10.1137/0203021 .
Panos M. Pardalos, Stephen A. Vavasis. Toisen asteen ohjelmointi yhdellä negatiivisella ominaisarvolla on NP-hard // Journal of Global Optimization. - 1991. - Vol. 1 , numero. 1 . - S. 15-22 . - doi : 10.1007/bf00120662 .
Richard W. Cottle, Jong-Shi Pang, Richard E. Stone. Lineaarisen täydentävyyden ongelma. - 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. Tietokoneet ja hallitsemattomuus: opas NP-täydellisyyden teoriaan . - W.H. Freeman, 1979. - ISBN 0-7167-1045-5 . A6: MP2, s. 245.
Nicholas I.M. Gould, Philippe L. Toint. A Quadratic Programming Bibliography (PDF). RAL Numerical Analysis Groupin sisäinen raportti 2000-1 (2000). (määrätön)

Linkit

Sivu QP:stä Arkistoitu 7. kesäkuuta 2011 Wayback Machinessa
NEOS-optimointiopas: Quadratic Programming Arkistoitu 18. kesäkuuta 2017 Wayback Machinessa
Ratkaise esimerkki Quadratic Programming (QP) -ongelmasta Arkistoitu 10. toukokuuta 2015 Wayback Machinessa