Kvadratikus programozás

A Wikipédiából, a szabad enciklopédiából

A kvadratikus programozás 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; ehhez előbb vissza kell őket vezetni lineáris programozási feladatokra.

A kvadratikus programozás alapfeladata:

Ax \leq b, x \geq 0
p^Tx+x^TCx\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[szerkesztés | forrásszöveg szerkesztése]

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^Tu = p
x^Tv + y^Tu = 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[szerkesztés | forrásszöveg szerkesztése]

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^Tx'+p))e_j

3. Elkészíjük ezt a lineáris programot:

Ax + y = b,
x, y, v, u, z \geq 0
-Cx + v - A^Tu + 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[szerkesztés | forrásszöveg szerkesztése]