Co je kvadratické programování?
Kvadratické programování je metoda používaná k optimalizaci multivariabilní kvadratické funkce, která může nebo nemusí být lineárně omezena. Mnoho problémů skutečného světa, jako je optimalizace portfolia společnosti nebo snížení nákladů výrobce, lze popsat pomocí kvadratického programu. Pokud je objektivní funkce konvexní, může existovat proveditelné řešení a může být vyřešeno známými algoritmy, jako je rozšířený simplexní algoritmus. Existují metody pro řešení některých nekonvexních kvadratických funkcí, ale jsou komplikované a snadno dostupné.
techniky matematické optimalizace se používají v kvadratickém programování k minimalizaci objektivní funkce. Objektivní funkce se skládá z řady rozhodovacích proměnných, které mohou nebo nemusí být ohraničeny. Proměnné rozhodování mají pravomoci 0, 1 nebo 2. Objektivní funkce může být podrobena řadě omezení lineární rovnosti a nerovnosti týkající se proměnných rozhodování. Příkladem kvadratického programování je:Minimalizujte f (x, y) = x 2 + 3y 2 - 12y + 12, kde x + y = 6 a x> 0 a y ≥ 0.
Často je zajímavé používat vícerozměrné kvadratické funkce k popisu problémů v reálném světě. Například pomocí moderní teorie portfolia se finanční analytik pokusí optimalizovat portfolio společnosti výběrem podílu aktiv, které minimalizují riziko spojené s daným očekávaným výnosem. Kvadratická rovnice složená z hmotností aktiv a korelace mezi aktivy popisuje rozptyl portfolia, který lze minimalizovat pomocí kvadratického programování. Dalším příkladem může být výrobce, který používá kvadratickou rovnici k popisu vztahu mezi různými komponenty kvality a náklady na produkt. Výrobce může minimalizovat náklady při zachování určitých standardů přidáním lineárních omezení do kvadratického programu.
jeden z nejdůležitějších podmínekns při řešení kvadratického programu je konvexity objektivní rovnice. Konvexita kvadratické funkce je určena Hessian nebo maticí jejích druhých derivátů. Tato funkce se nazývá konvexní, pokud je hessiánská matice buď pozitivní nebo pozitivní polo-definita, to je, pokud jsou všechny vlastní hodnoty pozitivní nebo negativní. Pokud je Hessian pozitivní a existuje proveditelné řešení, pak je toto místní minimum jedinečné a je globální minimum. Pokud je Hessian polo-pozitivní, nemusí být proveditelné řešení jedinečné. Nekonvexní kvadratické funkce mohou mít místní nebo globální minimum, ale je obtížnější je určit.
Existuje mnoho přístupů k řešení konvexní kvadratické funkce pomocí kvadratického programování. Nejběžnějším přístupem je rozšíření algoritmu Simplex. Některé další metody zahrnují metodu vnitřního bodu nebo bariéry, metoda aktivní sady a metoda konjugovaného gradientu. Tyto metody jsou integrovány do CERTain programy jako Mathematica® a Matlab® a jsou k dispozici v knihovnách pro mnoho programovacích jazyků.