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:

${\displaystyle Ax\leq b,}$ ${\displaystyle x\geq 0}$

${\displaystyle 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.

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

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

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

${\displaystyle 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 lineáris programozási feladat nem tudja garantálni az optimumot, ezért azt bonyolultabb megkapni.

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

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

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

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

${\displaystyle Ax+y=b,}$

${\displaystyle x,y,v,u,z\geq 0}$

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

${\displaystyle t=\sum z_{i}\rightarrow \mathrm {min} }$ ${\displaystyle (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 ${\displaystyle x_{j))$ és ${\displaystyle v_{j))$, vagy ${\displaystyle y_{j))$ és ${\displaystyle u_{j))$.

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

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