Kvadratikus programozás

A másodfokú programozás ( angolul quadratic programming , QP ) egy speciális típusú optimalizálási probléma megoldásának folyamata, nevezetesen több változó másodfokú függvényének optimalizálási problémája (minimalizálása vagy maximalizálása) , ezekre a változókra vonatkozó lineáris megszorítások mellett. A kvadratikus programozás a nemlineáris programozás speciális esete .

Problémafelvetés

Az n változós és m kényszerű másodfokú programozás problémája a következőképpen fogalmazható meg [1] .

Adott:

valós n - dimenziós c vektor ,
n × n -dimenziós valós szimmetrikus mátrix Q ,
m × n -dimenziós valós mátrix A
valós m - dimenziós b vektor ,

A másodfokú programozási feladat célja egy n -dimenziós x vektor megtalálása

minimalizálja	${\tfrac {1}{2}}\mathbf {x} ^{\mathrm {T} }Q\mathbf {x} +\mathbf {c} ^{\mathrm {T} }\mathbf {x }$
feltételek mellett	$A\mathbf {x} \leq \mathbf {b} ,$

ahol x T jelöli a transzponált vektort. Az A x ≤ b jelölés azt jelenti, hogy az A x vektor egyetlen eleme sem haladja meg a b vektor megfelelő elemét .

Egy kapcsolódó programozási probléma, a Quadratic Problem with Quadratic Constraints másodfokú kényszereket tartalmaz a változókra.

Megoldási módszerek

A közös értékekre különféle módszereket alkalmaznak, többek között

Belső pont módszer
Aktív beállítási módszer [2]
Általánosított Lagrange-módszer [3]
konjugált gradiens módszer
Gradiens vetítési módszer
A szimplex módszer módosítása [2] [4]

Abban az esetben, ha Q pozitív definit , a probléma az általánosabb konvex optimalizálási probléma speciális esete .

Megszorítások - Egyenlőség

A másodfokú programozás problémája valamivel egyszerűbb, ha Q pozitív határozott és minden kényszer egyenlő (nincs egyenlőtlenség), mivel ebben az esetben a feladatot le lehet redukálni egy lineáris egyenletrendszer megoldására. Ha Lagrange-szorzókat használunk , és a Lagrange-féle szélsőértéket keressük, könnyen megmutathatjuk, hogy a probléma megoldása

minimalizálni	${\tfrac {1}{2}}\mathbf {x} ^{\mathrm {T} }Q\mathbf {x} +\mathbf {c} ^{\mathrm {T} }\mathbf {x }$
feltételek mellett	$B\mathbf {x} =\mathbf {d}$

lineáris egyenletrendszer határozza meg

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

ahol a megoldással együtt megjelenő Lagrange-szorzók halmaza . $\lambda$ ${\mathbf x}$

Ezt a rendszert a legegyszerűbben direkt módszerekkel lehet megoldani (például LU dekompozíció használatával , ami nagyon kényelmes kis problémák esetén). Nagy problémák esetén szokatlan nehézségek merülnek fel, leginkább akkor, ha a probléma nem pozitív határozott (még akkor is, ha pozitív határozott), ami potenciálisan nagyon megnehezíti a jó matematikai megközelítés megtalálását, és sok problémafüggő megközelítés létezik. $K$ .

Ha a megszorítások száma nem egyenlő a változók számával, akkor egy viszonylag egyszerű támadást meg lehet próbálni a változók oly módon történő cseréjével, hogy a megszorítások feltétel nélkül teljesüljenek. Tegyük fel például, hogy (a nem nulla értékekre való átállás elég egyszerű). Vegye figyelembe a korlátozásokat $\mathbf {d} =0$

B\mathbf {x} =0

Bevezetünk egy új vektort , amelyet az egyenlőség határoz meg ${\mathbf y}$

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

ahol a dimenzió mínusz a kényszerek száma. Akkor ${\mathbf y}$ ${\mathbf x}$

BZ\mathbf {y} =0

és ha a mátrixot úgy választjuk meg, hogy a megszorítások egyenlőségei mindig érvényben maradnak. A mátrix megtalálása azt jelenti, hogy megtaláljuk a mátrix magját , ami többé-kevésbé egyszerű, a mátrix szerkezetétől függően . Az új vektort a kezdeti feltételekbe behelyettesítve egy korlátok nélküli másodfokú feladatot kapunk: $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 }

a megoldást pedig az egyenlet megoldásával találhatjuk meg

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

A redukált mátrixra vonatkozó bizonyos korlátozások mellett pozitív határozott lesz. Megírhatja a konjugált gradiens módszer változatát , amelyben nincs szükség a mátrix explicit kiszámítására [5] . $K$ $Z^{T}QZ$ $Z$

Lagrangi kettősség

A másodfokú programozás kettős Lagrange-problémája egyben másodfokú programozási probléma is. Ennek megértéséhez nézzünk meg egy Q pozitív határozott mátrixú esetet. Írjuk ki a függvény Lagrange-szorzóit $c=0$

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

Ha a (Lagrange-féle) duális függvényt így definiáljuk , akkor a Q mátrix pozitív meghatározottságának felhasználásával alsó korlátot keresünk : $g(\lambda )$ $g(\lambda )=\inf _{x}L(x,\lambda )$ $L$ $\nabla _{x}L(x,\lambda )=0$

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

Ezért a kettős függvény egyenlő

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

és az eredeti probléma kettős Lagrange-problémája az

minimalizálni	$-{\tfrac {1}{2}}\lambda ^{T}AQ^{-1}A^{T}\lambda -\lambda ^{T}b$
feltételek mellett	$\lambda \geqslant 0$ .

A Lagrange-dualitás-elmélet mellett más duális problémapárok is léteznek (például Wolfe dualitás ).

Nehézség

Pozitív határozott Q mátrix esetén az ellipszoid módszer polinomiális időben oldja meg a problémát [6] . Ha viszont Q nem pozitív határozott, akkor a probléma NP-nehéz lesz [7] . Valójában még akkor is, ha Q -nak egyetlen negatív sajátértéke van, a probléma NP-nehéz [8] .

Megoldáscsomagok és szkriptnyelvek

Név	Leírás
CÉLKITŰZÉS	Optimalizációs és ütemezési problémák modellezésére és megoldására szolgáló rendszer
ALGLIB	Programkönyvtár (C++, .NET) numerikus elemzéshez kettős licenccel (GPL/tulajdonos).
AMPL	Népszerű modellező nyelv nagyszabású matematikai optimalizáláshoz.
APMonitor	Modellezés és optimalizálás LP (lineáris programozás), QP (kvadratikus programozás), NLP (nemlineáris programozás), MILP (egészszámú programozás), MINLP (kevert egészszámú nemlineáris programozás) és DAE (differenciálalgebrai egyenletek) problémákhoz MATLAB és Piton.
CGAL	Nyílt forráskódú geometriai számítástechnikai csomag, amely másodfokú programozási problémák megoldására szolgáló rendszert tartalmaz.
CPLEX	Népszerű problémamegoldó rendszer API-kkal (C, C++, Java, .Net, Python, Matlab és R). Tanulmányi használatra ingyenes.
Megoldáskereső Excelben	Táblázatokhoz adaptált nemlineáris problémamegoldó rendszer, amelyben a függvényszámítások a cellák értékén alapulnak. Az alapverzió az Excel szabványos kiegészítőjeként érhető el.
GAMS	Magas szintű szimulációs rendszer a matematikai optimalizáláshoz
Gurobi_	Nagyméretű lineáris programozási feladatok, másodfokú programozási feladatok és vegyes egészszámú feladatok párhuzamos algoritmusokkal történő problémák megoldására szolgáló rendszer. Tanulmányi használatra ingyenes.
IMSL_	Matematikai és statisztikai függvények halmaza, amelyeket a programozó beépíthet az alkalmazásába.
IPOPT	Az IPOPT (Interior Point OPTimizer) csomag egy programcsomag nagy nemlineáris problémákhoz.
Artelys	Kereskedelmi integrált csomag nemlineáris optimalizáláshoz
juharfa	Általános célú programozási nyelv matematikához. A Maple a QPSolve parancsot használja a kvadratikus problémák megoldására . Archiválva : 2021. május 12. a Wayback Machine -en .
MATLAB	Mátrix-orientált általános célú programozási nyelv numerikus számításokhoz. A MATLAB másodfokú programozási problémáinak megoldásához az alap MATLAB terméken kívül szükség van az „Optimization Toolbox” kiegészítőre
Mathematica	Általános célú programozási nyelv matematikához, szimbolikus és numerikus képességekkel.
MOSEK_	Rendszer nagyszabású optimalizálási problémák megoldására, API-t tartalmaz több nyelvhez (C++, Java, .Net, Matlab és Python)
NAG Numerical Library	A Numerical Algorithms Group által kifejlesztett matematikai és statisztikai eljárások készlete több programozási nyelvhez (C, C++, Fortran, Visual Basic, Java és C#) és csomagokhoz (MATLAB, Excel, R, LabVIEW). A NAG-könyvtár optimalizálási szekciója másodfokú programozási problémákat tartalmaz ritka és sűrű kényszermátrixokkal, valamint eljárásokat lineáris és nemlineáris függvények, lineáris és nemlineáris függvények négyzetösszegei optimalizálására. A NAG könyvtár mind a lokális, mind a globális optimalizáláshoz, valamint az egész számok programozási problémáihoz tartalmaz eljárásokat.
OptimJ_	Egy szabadon terjesztett, Java alapú optimalizálási modellező nyelv, amely több céldöntési rendszert is támogat. Van egy bővítmény az Eclipse-hez [9] [10]
R	GPL -licenccel rendelkező, általános célú, többplatformos számítástechnikai csomag (lásd a quadprog szakaszt, archiválva 2017. június 19-én a csomag Wayback Machine -jén ). Lefordítva javascriptre Archiválva 2017. április 11-én a Wayback Machine -nél az MIT licence alatt . Lefordítva C# nyelvre, archiválva 2015. április 8-án a Wayback Machine -nél LGPL alatt .
SAS /VAGY	Lineáris, egészszámú, kombinatorikus, nemlineáris, nem differenciálható problémák, hálózatok problémáinak és kényszerű optimalizálásnak megoldására szolgáló rendszer. Algebrai modellező nyelv OPTMODEL Archiválva : 2016. szeptember 8. a Wayback Machine -nél , és számos konkrét feladatokat célzó vertikális megoldás teljes mértékben integrálva van a \|SAS/ rendszerrel.
Megoldó	Termelési szabályokon alapuló deklaratív nyelven alapuló matematikai modellezés és problémamegoldó rendszer. A rendszert a Universal Technical Systems, Inc. forgalmazza. Archiválva : 2022. április 1. a Wayback Machine -nél .
TOMLAB	Támogatja a globális optimalizálást, az egész számok programozását, a legkisebb négyzetek minden típusát, a lineáris másodfokú programozást a MATLAB számára . A TOMLAB támogatja a Gurobi, CPLEX , SNOPT és KNITRO megoldási rendszereket .

Lásd még

Jegyzetek

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

Irodalom

G.P. Künzi, W. Crelle. Nemlineáris programozás. - Moszkva: "Szovjet Rádió", 1965.
Jorge Nocedal, Stephen J. Wright. Numerikus optimalizálás . — 2. - Berlin, New York: Springer-Verlag , 2006. - 449. o . - ISBN 978-0-387-30303-1 .
Katta G Murty. Lineáris komplementaritás, lineáris és nemlineáris programozás . - Berlin: Heldermann Verlag, 1988. - V. 3. - C. xlviii + 629 pp.. - (Sigma Series in Applied Mathematics). — ISBN 3-88538-403-5 .
F. Delbos, J. Ch. Gilbert. Egy kiterjesztett Lagrange-algoritmus globális lineáris konvergenciája konvex kvadratikus optimalizálási problémák megoldására // Journal of Convex Analysis. - 2005. - T. 12 . - S. 45-69 .
Felix Zesch, Bernd Hellingrath. Optimalizációs modell vegyes modell összeszerelő sorokhoz // Integrált termelés-elosztás tervezés. – 2010.
Andrij Burkov, Brahim Chaibdraa. A huszonnegyedik AAAI Mesterséges Intelligencia Konferencia (AAAI-10) anyaga. – Atlanta, USA: AAAI Press, 2010.
Nicholas IM Gould, Mary E. Hribar, Jorge Nocedal. Az optimalizálás során felmerülő egyenlőség-korlátozott másodfokú programozási problémák megoldásáról. - SIAM Journal of Scientific Computing, 2001. - V. 23 , no. 4 . - S. 1376-1395 .
M. K. Kozlov, S. P. Tarasov, L. G. Khachiyan. Konvex kvadratikus programozás polinomiális megoldhatósága, Zh. Vychisl. matematika. és mat. fizika - 1980. - T. 20, , sz. 5 .
S. Sahni. Számítással kapcsolatos problémák // SIAM Journal on Computing. - 1974. - T. 3 . - S. 262-279 . - doi : 10.1137/0203021 .
Panos M. Pardalos, Stephen A. Vavasis. Az egy negatív sajátértékkel rendelkező kvadratikus programozás NP-kemény // Journal of Global Optimization. - 1991. - 1. évf. , szám. 1 . - S. 15-22 . - doi : 10.1007/bf00120662 .
Richard W. Cottle, Jong-Shi Pang, Richard E. Stone. A lineáris komplementaritás probléma. - 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. Számítógépek és kezelhetetlenség: Útmutató az NP-teljesség elméletéhez . - W. H. Freeman, 1979. - ISBN 0-7167-1045-5 . A6: MP2, 245. oldal.
Nicholas I. M. Gould, Philippe L. Toint. Kvadratikus programozási bibliográfia (PDF). RAL Numerical Analysis Group belső jelentés 2000-1 (2000). (határozatlan)

Linkek

Egy oldal a QP -ről Archiválva : 2011. június 7. a Wayback Machine -nél
NEOS optimalizálási útmutató: Kvadratikus programozás archiválva 2017. június 18-án a Wayback Machine -nél
Példa kvadratikus programozási (QP) probléma megoldása Archivált : 2015. május 10. a Wayback Machine -nél