Vad är kvadratisk programmering?
Kvadratisk programmering är en metod som används för att optimera en multivariabel kvadratisk funktion som kan eller inte kan vara linjärt begränsad. Många verkliga problem, som att optimera ett företags portfölj eller minska en tillverkares kostnader, kan beskrivas med ett kvadratiskt program. Om objektivfunktionen är konvex kan en genomförbar lösning existera och kan lösas av kända algoritmer såsom den utvidgade Simplex -algoritmen. Det finns metoder för att lösa vissa icke-konvexa kvadratiska funktioner men de är komplicerade och inte lätt tillgängliga.
matematiska optimeringstekniker används i kvadratisk programmering för att minimera en objektiv funktion. Målfunktionen består av ett antal beslutsvariabler som kan eller inte kan begränsas. Beslutsvariablerna har befogenheter 0, 1 eller 2. Målfunktionen kan underkastas ett antal linjära jämlikhets- och ojämlikhetsbegränsningar för beslutsvariablerna. Ett exempel på kvadratisk programmering är:Minimera f (x, y) = x 2 + 3y 2 - 12y + 12 där x + y = 6 och x> 0 och y ≥ 0.
Det är ofta intressant att använda multivariata kvadratiska funktioner för att beskriva verkliga problem. Till exempel, med modern portföljteori, kommer en finansanalytiker att försöka optimera ett företags portfölj genom att välja andelen tillgångar som minimerar risken i samband med en given förväntad avkastning. En kvadratisk ekvation som består av tillgångsvikt och sambandet mellan tillgångar beskriver portföljvariansen som kan minimeras med kvadratisk programmering. Ett annat exempel kan vara en tillverkare som använder en kvadratisk ekvation för att beskriva förhållandet mellan olika kvalitetskomponenter och en produkts kostnad. Tillverkaren kan minimera kostnaderna samtidigt som vissa standarder upprätthåller genom att lägga till linjära begränsningar till det kvadratiska programmet.
en av de viktigaste konditionernaNS för att lösa ett kvadratiskt program är konvexiteten i den objektiva ekvationen. Konvexiteten hos en kvadratisk funktion bestäms av Hessian eller matrisen för dess andra derivat. Funktionen kallas konvex om den hessiska matrisen är antingen positiv bestämd eller positiv semidefinite, det vill säga om alla egenvärden är positiva respektive icke-negativa. Om Hessian är positiv och en genomförbar lösning finns, är det lokala minimumet unikt och är ett globalt minimum. Om Hessian är semi-positiv kanske en genomförbar lösning kanske inte är unik. Icke-konvexa kvadratiska funktioner kan ha lokala eller globala minimum, men de är svårare att bestämma.
Det finns många metoder för att lösa en konvex kvadratisk funktion med kvadratisk programmering. Det vanligaste tillvägagångssättet är en utvidgning av Simplex -algoritmen. Vissa andra metoder inkluderar den inre punkten eller barriärmetoden, Active Set -metoden och den konjugerade gradientmetoden. Dessa metoder är integrerade i CERTain -program som Mathematica® och Matlab® och de finns tillgängliga i bibliotek för många programmeringsspråk.