Hvad er kvadratisk programmering?
Kvadratisk programmering er en metode, der bruges til at optimere en multivariabel kvadratisk funktion, der måske eller måske ikke begrænses lineært. Mange problemer i den virkelige verden, såsom at optimere en virksomheds portefølje eller reducere en producentens omkostninger, kan beskrives ved hjælp af et kvadratisk program. Hvis den objektive funktion er konveks, kan der eksistere en gennemførlig løsning og kan løses ved kendte algoritmer, såsom den udvidede simplex -algoritme. Der findes metoder til løsning af nogle ikke-konvekse kvadratiske funktioner, men de er komplicerede og ikke let tilgængelige.
Matematiske optimeringsteknikker bruges i kvadratisk programmering for at minimere en objektiv funktion. Den objektive funktion består af en række beslutningsvariabler, der måske eller måske ikke er afgrænset. Beslutningsvariablerne har beføjelser 0, 1 eller 2. 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 at bruge multivariate kvadratiske funktioner til at beskrive problemer i den virkelige verden. For eksempel ved hjælp af moderne porteføljeteori vil en finansanalytiker forsøge at optimere en virksomheds portefølje ved at vælge andelen af aktiver, der minimerer risikoen forbundet med et givet forventet afkast. En kvadratisk ligning, der består af aktivvægte og sammenhængen mellem aktiver, beskriver porteføljevariansen, der kan minimeres ved hjælp af kvadratisk programmering. Et andet eksempel kan være en producent, der bruger en kvadratisk ligning til at beskrive forholdet mellem forskellige kvalitetskomponenter og et produkts omkostninger. Producenten kan minimere omkostningerne og samtidig opretholde visse standarder ved at tilføje lineære begrænsninger til det kvadratiske program.
en af de vigtigste conditioNS til løsning af et kvadratisk program er konveksiteten i den objektive ligning. Konveksiteten af en kvadratisk funktion bestemmes af Hessian eller matrixen for dets andet derivater. Funktionen kaldes konveks, hvis den hessiske matrix enten er positiv bestemt eller positiv semi-definit, det er hvis alle egenværdier er henholdsvis positive eller ikke-negative. Hvis Hessian er positiv, og der findes en gennemførlig løsning, er det lokale minimum unikt og er et globalt minimum. Hvis Hessian er semi-positiv, er en mulig løsning muligvis ikke unik. Ikke-konvekse kvadratiske funktioner kan have lokale eller globale minimum, men de er vanskeligere at bestemme.
Der er mange tilgange til at løse en konveks kvadratisk funktion ved hjælp af kvadratisk programmering. Den mest almindelige tilgang er en udvidelse af simplex -algoritmen. Nogle andre metoder inkluderer interiørpunktet eller barriere -metoden, aktiv sætmetode og den konjugerede gradientmetode. Disse metoder er integreret i CERTain -programmer som Mathematica® og Matlab®, og de fås i biblioteker til mange programmeringssprog.