Kvadratikus programozás

A kvadratikus programozás (QP) a nemlineáris programozás része, mivel a kvadratikus programozási feladatok célfüggvényei nem lineárisak, hanem másodfokúak. Ezek a feladatok közvetlenül nem oldhatók meg a szimplex módszerrel, mivel az optimum nem biztos, hogy csúcspont, így ehhez előbb vissza kell őket vezetni lineáris programozási feladatokra.

A kvadratikus programozás alapfeladata:

$Ax\leq b,$ $x\geq 0$

$p^{T}x+x^{T}Cx\rightarrow \mathrm {min} ,$

ahol a C mátrix pozitív szemidefinit. Feltehető, hogy szimmetrikus is, mivel a kvadratikus alak megegyezik a szimmetrikus résszel alkotott kvadratikus alakkal.

Visszavezetés a lineáris programozásra

A kvadratikus programozás alapfeladata a következő lineáris programra vezethető vissza:

$Ax+y=b,$ $x,y,v,u\geq 0$

$-Cx+v-A^{T}u=p$

$x^{T}v+y^{T}u=0$

Ha a kvadratikus alapfeladat megoldható, akkor ez a lineáris program is megoldható, és a belőle kapott x a kvadratikus alapfeladatnak is megoldása lesz.

A feladat megoldása

A lineáris programozási feladat nem tudja garantálni az optimumot, ezért azt bonyolultabb megkapni.

1. Megadunk egy lehetséges $x'$ megoldást szimplex módszerrel.

2. Elkészítjük az F mátrixot, aminek oszlopai

$f_{j}=\mathrm {sgn} (C(e_{j}^{T}x'+p))e_{j}$

3. Elkészítjük a következő lineáris programot:

$Ax+y=b,$

$x,y,v,u,z\geq 0$

$-Cx+v-A^{T}u+Fz=p$

$t=\sum z_{i}\rightarrow \mathrm {min}$ $(i=1\dots n)$

4. Keressük ennek egy olyan bázismegoldását, amiben u és v is nullvektor.

5. Innen elindulva megoldjuk ezt a rendszert úgy, hogy a bázisban egy j-re se legyen bent egyszerre $x_{j}$ és $v_{j}$, vagy $y_{j}$ és $u_{j}$.

6. Álljunk meg, ha a $t=\sum z_{i}\rightarrow \mathrm {min}$ célfüggvény értéke nulla. Ekkor x a kvadratikus alapfeladatnak is optimuma lesz.

Források

• Alkalmazott operációkutatás
• Kalmár János: Operációkutatás