Kvadratické programování - Quadratic programming

tento článek potřebuje pozornost odborníka na matematiku. Specifický problém je: Některé položky na této stránce vyžadují vysvětlení a / nebo odborné ověření. Viz diskusní stránka pro detaily. Matematika WikiProject může pomoci s náborem odborníka. (Února 2017)

Kvadratické programování (QP) je proces řešení speciálního typu matematická optimalizace problém —Konkrétně (lineárně omezený) problém kvadratické optimalizace, tj. Problém optimalizace (minimalizace nebo maximalizace) a kvadratická funkce několika proměnných podléhajících lineárnímu omezení na tyto proměnné. Kvadratické programování je zvláštní typ nelineární programování.

Formulace problému

Kvadratický problém programování s n proměnné a m omezení lze formulovat následovně.^[1]Dané:

• skutečnou hodnotu, n-dimenzionální vektor C,
• an n × n-dimenzionální skutečné symetrická matice Q,
• an m × n-dimenzionální skutečná matice A, a
• an m-dimenzionální reálný vektor b,

cílem kvadratického programování je najít n-dimenzionální vektor X, to bude

${displaystyle {ext {minimalizovat}}}$	${displaystyle {frac {1} {2}} mathbf {x} ^ {mathrm {T}} Qmathbf {x} + mathbf {c} ^ {mathrm {T}} mathbf {x}}$
${displaystyle {ext {předmět}}}$	${displaystyle Amathbf {x} preceq mathbf {b},}$

kde X^T označuje vektor přemístit z ${displaystyle mathbf {x}}$. Zápis AX ⪯ b znamená, že každá položka vektoru AX je menší než nebo se rovná odpovídajícímu vstupu vektoru b (nerovnost po částech).

Nejmenší čtverce

Jako zvláštní případ, když Q je symetrický pozitivní určitý, nákladová funkce se sníží na nejmenší čtverečky:

${displaystyle {ext {minimalizovat}}}$	${displaystyle {frac {1} {2}} | mathbf {R} mathbf {x} -mathbf {d} | ^ {2}}$
${displaystyle {ext {předmět}}}$	${displaystyle Amathbf {x} preceq mathbf {b},}$

kde Q = R^TR vyplývá z Choleský rozklad z Q a C = -R^T d. Naopak jakýkoli takto omezený program nejmenších čtverců lze ekvivalentně zarámovat jako QP, a to i pro generické nečtverečné R matice.

Zobecnění

Při minimalizaci funkce F v sousedství nějakého referenčního bodu X₀, Q je nastaven na jeho Hesenská matice H(F(X₀)) a C je nastaven na svůj gradient ∇F(X₀). Související problém s programováním, kvadraticky omezené kvadratické programování, lze představovat přidáním kvadratických omezení k proměnným.

Metody řešení

U obecných problémů se běžně používá řada metod, včetně

• vnitřní bod,
• aktivní sada,^[2]
• rozšířená Lagrangeova,^[3]
• konjugovaný gradient,
• gradientní projekce,
• rozšíření simplexní algoritmus.^[2]

V případě, že Q je pozitivní určitý, problémem je speciální případ obecnější oblasti konvexní optimalizace.

Omezení rovnosti

Kvadratické programování je obzvláště jednoduché, když Q je pozitivní určitý a existují pouze omezení rovnosti; konkrétně je proces řešení lineární. Používáním Lagrangeovy multiplikátory a při hledání extrému Lagrangeova, lze snadno ukázat, že řešení problému omezeného rovností

${displaystyle {ext {Minimize}} quad {frac {1} {2}} mathbf {x} ^ {mathrm {T}} Qmathbf {x} + mathbf {c} ^ {mathrm {T}} mathbf {x}}$

${displaystyle {ext {subject to}} quad Emathbf {x} = mathbf {d}}$

je dána lineárním systémem

${displaystyle {egin {bmatrix} Q & E ^ {T} E & 0end {bmatrix}} {egin {bmatrix} mathbf {x} lambda end {bmatrix}} = {egin {bmatrix} -mathbf {c} mathbf {d} konec {bmatrix}}}$

kde ${displaystyle lambda}$ je sada Lagrangeových multiplikátorů, které společně vycházejí z řešení ${displaystyle mathbf {x}}$.

Nejjednodušší způsob přístupu k tomuto systému je přímé řešení (například Faktorizace LU ), což je pro malé problémy velmi praktické. U velkých problémů systém představuje určité neobvyklé obtíže, zejména to, že problém není nikdy kladně definitivní (i když ${displaystyle Q}$ je), takže je potenciálně velmi obtížné najít dobrý numerický přístup a existuje mnoho přístupů, z nichž si můžete vybrat v závislosti na problému.^[4]

Pokud omezení nepropojují proměnné příliš těsně, relativně jednoduchým útokem je změna proměnných tak, aby byla omezení bezpodmínečně splněna. Předpokládejme například ${displaystyle mathbf {d} = 0}$ (zobecnění na nenulovou hodnotu je jednoduché). Podíváme-li se na omezující rovnice:

${displaystyle Emathbf {x} = 0}$

zavést novou proměnnou ${displaystyle mathbf {y}}$ definován

${displaystyle Zmathbf {y} = mathbf {x}}$

kde ${displaystyle mathbf {y}}$ má rozměr ${displaystyle mathbf {x}}$ minus počet omezení. Pak

${displaystyle EZmathbf {y} = 0}$

a pokud ${displaystyle Z}$ je vybrán tak, aby ${displaystyle EZ = 0}$ rovnice omezení bude vždy splněna. Nalezení takové ${displaystyle Z}$ znamená najít prázdný prostor z ${displaystyle E}$, což je víceméně jednoduché v závislosti na struktuře ${displaystyle E}$. Nahrazení do kvadratické formy dává neomezený problém s minimalizací:

${displaystyle {frac {1} {2}} mathbf {x} ^ {T} Qmathbf {x} + mathbf {c} ^ {T} mathbf {x} quad Rightarrow quad {frac {1} {2}} mathbf { y} ^ {T} Z ^ {T} QZmathbf {y} + (Z ^ {T} mathbf {c}) ^ {T} mathbf {y}}$

jehož řešení je dáno:

${displaystyle Z ^ {T} QZmathbf {y} = -Z ^ {T} mathbf {c}}$

Za určitých podmínek dne ${displaystyle Q}$, redukovaná matice ${displaystyle Z ^ {T} QZ}$ bude kladně definitivní. Je možné napsat variaci na metoda konjugovaného gradientu který se vyhýbá výslovnému výpočtu ${displaystyle Z}$.^[5]

Lagrangeova dualita

Lagrangian dvojí QP je také QP. Abychom to viděli, zaměřme se na případ, kdy ${displaystyle c = 0}$ a Q je kladně definitivní. Píšeme Lagrangian fungovat jako

${displaystyle L (x, lambda) = {frac {1} {2}} x ^ {T} Qx + lambda ^ {T} (Ax-b).}$

Definování (Lagrangeovy) duální funkce ${displaystyle g (lambda)}$ tak jako ${displaystyle g (lambda) = inf _ {x} L (x, lambda)}$, najdeme infimum z ${displaystyle L}$, použitím ${displaystyle abla _ {x} L (x, lambda) = 0}$ a pozitivní definitivnost Q:

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

Proto je duální funkce

${displaystyle g (lambda) = - {frac {1} {2}} lambda ^ {T} AQ ^ {- 1} A ^ {T} lambda -lambda ^ {T} b,}$

a tak Lagrangeova dvojka QP je

${displaystyle {ext {maximize}} _ {lambda geq 0} quad - {frac {1} {2}} lambda ^ {T} AQ ^ {- 1} A ^ {T} lambda -lambda ^ {T} b}$

Kromě Lagrangeovy teorie duality existují i ​​další dvojice dualit (např. Wolfe, atd.).

Složitost

Pro pozitivní určitý Q, elipsoidní metoda řeší problém v (slabě) polynomiální čas.^[6] Pokud na druhou stranu Q je neurčitý, pak je problém NP-tvrdé.^[7] Ve skutečnosti, i když Q má pouze jeden zápor vlastní číslo, problém je (silně) NP-tvrdé.^[8]

Omezení na celé číslo

Existují situace, kdy jeden nebo více prvků ${displaystyle xin mathbb {R} ^ {n}}$ vektor bude muset nabrat celočíselné hodnoty. To vede k formulaci problému se smíšeným celočíselným kvadratickým programováním (MIQP).^[9] Aplikace MIQP zahrnují vodní zdroje^[10] a výstavba indexových fondů.^[11]

Řešiče a skriptovací (programovací) jazyky

Viz také

• Podporujte vektorový stroj
• Sekvenční kvadratické programování
• Lineární programování
• Metoda kritické linky

Reference

Další čtení

• Cottle, Richard W .; Pang, Jong-Shi; Kámen, Richard E. (1992). Problém lineární komplementarity. Počítačová věda a vědecké výpočty. Boston, MA: Academic Press, Inc. s. Xxiv + 762 s. ISBN  978-0-12-192350-1. PAN  1150683.
• Garey, Michael R.; Johnson, David S. (1979). Počítače a neodolatelnost: Průvodce po teorii NP-úplnosti. W.H. Freemane. ISBN  978-0-7167-1045-5. A6: MP2, str. 245.
• Gould, Nicholas I. M .; Toint, Philippe L. (2000). „Kvadratická programovací bibliografie“ (PDF). Interní zpráva skupiny číselných analýz RAL 2000-1.

externí odkazy

• Stránka o QP
• Průvodce optimalizací NEOS: Kvadratické programování
• Kvadratické programování