Hva er kvadratisk programmering?

Kvadratisk programmering er en metode som brukes for å optimalisere en multivariabel kvadratisk funksjon som kanskje ikke er lineært begrenset. Mange problemer i den virkelige verden, som å optimalisere et selskaps portefølje eller redusere produsentens kostnader, kan beskrives ved hjelp av et kvadratisk program. Hvis den objektive funksjonen er konveks, kan en gjennomførbar løsning eksistere og kan løses av kjente algoritmer som den utvidede simplex -algoritmen. Det finnes metoder for å løse noen ikke-konvekse kvadratiske funksjoner, men de er kompliserte og ikke lett tilgjengelige.

Matematisk optimaliseringsteknikker brukes i kvadratisk programmering for å minimere en objektiv funksjon. Den objektive funksjonen består av en rekke beslutningsvariabler som kanskje ikke er avgrenset. Beslutningsvariablene har krefter 0, 1 eller 2.. Målfunksjonen kan bli utsatt for en rekke lineære likestilling og ulikhetsbegrensninger angående beslutningsvariablene. Et eksempel på kvadratisk programmering er:Minimer F (x, y) = x ^{2 + 3y 2 - 12y + 12 hvor x + y = 6 og x> 0 og y ≥ 0.}

Det er ofte interessant å bruke multivariate kvadratiske funksjoner for å beskrive problemer i den virkelige verden. For eksempel ved å bruke moderne porteføljeteori, vil en finansanalytiker prøve å optimalisere et selskaps portefølje ved å velge andelen av eiendeler som minimerer risikoen forbundet med en gitt forventet avkastning. En kvadratisk ligning som består av eiendelsvekter og sammenhengen mellom eiendeler beskriver porteføljevariansen som kan minimeres ved hjelp av kvadratisk programmering. Et annet eksempel kan være en produsent som bruker en kvadratisk ligning for å beskrive forholdet mellom forskjellige kvalitetskomponenter og et produkts kostnad. Produsenten kan minimere kostnadene mens de opprettholder visse standarder ved å legge til lineære begrensninger til det kvadratiske programmet.

En av de viktigste forholdeneNS for å løse et kvadratisk program er konveksiteten til objektivligningen. Konveksiteten til en kvadratisk funksjon bestemmes av Hessian eller matrisen til dens andre derivater. Funksjonen kalles konveks hvis den hessiske matrisen er enten positiv definitiv eller positiv semi-definisjon, det vil si hvis alle egenverdiene er henholdsvis positive eller ikke-negative. Hvis Hessian er positiv og en gjennomførbar løsning eksisterer, er det lokale minimum unikt og er et globalt minimum. Hvis hessianen er semi-positiv, kan det hende at en gjennomførbar løsning ikke er unik. Ikke-konvekse kvadratiske funksjoner kan ha lokale eller globale minimum, men de er vanskeligere å bestemme.

Det er mange tilnærminger til å løse en konveks kvadratisk funksjon ved bruk av kvadratisk programmering. Den vanligste tilnærmingen er en utvidelse av simplex -algoritmen. Noen andre metoder inkluderer interiørpunkt eller barriere -metode, aktiv settmetode og konjugatgradientmetoden. Disse metodene er integrert i CERTain -programmer som Mathematica® og Matlab®, og de er tilgjengelige i biblioteker for mange programmeringsspråk.