Kvadratické programování

Tento článek se bude zabývat tématem Kvadratické programování, které vyvolalo zájem a diskusi v různých oblastech společnosti. Kvadratické programování upoutal pozornost výzkumníků, odborníků a dokonce i běžných občanů díky své relevanci a dopadu na různé aspekty každodenního života. V průběhu let byl Kvadratické programování předmětem analýz, diskuzí a úvah, což dalo vzniknout různým názorům a pohledům na toto téma. V tomto smyslu je velmi důležité prohloubit znalosti a porozumění Kvadratické programování s cílem obohatit diskusi a podpořit komplexní a kritickou vizi v tomto ohledu. Proto budou v následujících řádcích prozkoumány různé dimenze Kvadratické programování s cílem nabídnout úplný a objektivní pohled na toto téma důležité pro dnešní společnost.

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

\min _{x\in M}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\leq b,\quad x\geq 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

Milan Hamala: Nelineárne programovanie, ALFA, Bratislava 1972, 1. vydání.
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