Kvadraticky omezený kvadratický program - Quadratically constrained quadratic program - Wikipedia

v matematická optimalizace, a kvadraticky omezený kvadratický program (QCQP) je optimalizační problém ve kterém oba Objektivní funkce a omezení jsou kvadratické funkce. Má to formu

${ displaystyle { begin {aligned} & { text {minimal}} && { tfrac {1} {2}} x ^ { mathrm {T}} P_ {0} x + q_ {0} ^ { mathrm {T}} x & { text {subject to}} && { tfrac {1} {2}} x ^ { mathrm {T}} P_ {i} x + q_ {i} ^ { mathrm {T}} x + r_ {i} leq 0 quad { text {for}} i = 1, dots, m, &&& Ax = b, end {zarovnáno}}}$

kde P₀, …, P_m jsou n-podle-n matice a X ∈ Rⁿ je optimalizační proměnná.

Li P₀, …, P_m všichni jsou pozitivní semidefinit, pak je problém konvexní. Pokud tyto matice nejsou ani pozitivní, ani negativní semidefinitní, problém není nekonvexní. Li P₁, … ,P_m jsou všechny nulové, pak jsou omezení ve skutečnosti lineární a problém je kvadratický program.

Tvrdost

Řešení obecného případu je NP-tvrdé problém. Chcete-li to vidět, všimněte si, že dvě omezení X₁(X₁ - 1) ≤ 0 a X₁(X₁ - 1) ≥ 0 jsou ekvivalentní omezení X₁(X₁ - 1) = 0, což je zase ekvivalentní omezení X₁ ∈ {0, 1}. Proto jakýkoli 0–1 celočíselný program (ve kterém všechny proměnné musí být buď 0 nebo 1) lze formulovat jako kvadraticky omezený kvadratický program. Protože programování celých čísel 0–1 je obecně NP-tvrdé, je QCQP také NP-tvrdé.

Relaxace

Existují dvě hlavní relaxace QCQP: používání semidefinitní programování (SDP) a pomocí technika přeformulování-linearizace (RLT). U některých tříd problémů QCQP (přesně QCQP s prvky s nulovou úhlopříčkou v datových maticích), programování kuželů druhého řádu (SOCP) a lineární programování K dispozici jsou relaxace (LP) poskytující stejnou objektivní hodnotu jako relaxace SDP.^[1]

Nekonvexní QCQP s pozitivními off-diagonálními prvky lze přesně vyřešit relaxací SDP nebo SOCP,^[2] a existují polynomiálně-časově kontrolovatelné dostatečné podmínky pro přesnost relaxace SDP obecných QCQP.^[3] Kromě toho se ukázalo, že třída náhodných obecných QCQP má přesné semidefinitní relaxace s vysokou pravděpodobností, pokud počet omezení roste ne rychleji než pevný polynom v počtu proměnných.^[3]

Semidefinitní programování

Když P₀, …, P_m všichni jsou pozitivně definitivní matice, problém je konvexní a lze je snadno vyřešit pomocí vnitřní bodové metody, jak je to u semidefinitní programování.

Příklad

Max. Řez je problém v teorii grafů, který je NP-tvrdý. Vzhledem k grafu je problém rozdělit vrcholy na dvě sady, aby co nejvíce hran přešlo z jedné sady do druhé. Max Cut lze formulovat jako QCQP a uvolnění SDP duální poskytuje dobré dolní hranice.

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

Reference

• Boyd, Stephen; Lieven Vandenberghe (2004). Konvexní optimalizace. Cambridge: Cambridge University Press. ISBN  978-0-521-83378-3.

Další čtení

Ve statistikách

• Albers C. J., Critchley F., Gower, J. C. (2011). „Kvadratické minimalizační problémy ve statistice“ (PDF). Journal of Multivariate Analysis. 102 (3): 698–713. doi:10.1016 / j.jmva.2009.12.018.CS1 maint: více jmen: seznam autorů (odkaz)

externí odkazy

• Průvodce optimalizací NEOS: Kvadratické omezené kvadratické programování