Kvadratické programování

Kvadratické programování je odvětví optimalizace a speciálním typem konvexního programování.

Úloha

Úlohou kvadratického programování je následující optimalizační úloha

$\underset{x\in M}{\min }1/2x^{T}Cx+p^{T}x,$

přičemž:

• p, x jsou n-rozměrné vektory
• C je pozitivně definitní matice rozměru n × n
• $p^{T}x$ označuje skalární součin vektorů p, x
• Součin x^T C x označuje součin matic
• množina přípustných řešení M je popsána soustavou

$Ax\le b,x\ge 0,$

kde A je matice rozměru m × n, b je m-rozměrný vektor.

Metody řešení

Na řešení úlohy kvadratického programování se používají komplementární algoritmy, např. Wolfeho metoda nebo Lemkeho algoritmus.

Reference

1. Milan Hamala: Nelineárne programovanie, ALFA, Bratislava 1972, 1. vydání.
2. Miroslav Maňas: Optimalizační metody, Státní nakladatelství technické literatury, Praha 1979, 1. vydání.

Externí odkazy

• Petr Lachout: Matematické programování. Učební text MFF UK