Wat is kwadratisch programmeren?
kwadratische programmering is een methode die wordt gebruikt om een multivariabele kwadratische functie te optimaliseren die al dan niet lineair beperkt is. Veel problemen in de echte wereld, zoals het optimaliseren van de portefeuille van een bedrijf of het verlagen van de kosten van een fabrikant, kunnen worden beschreven met behulp van een kwadratisch programma. Als de objectieve functie convex is, kan een haalbare oplossing bestaan en kan worden opgelost door bekende algoritmen zoals het uitgebreide simplex -algoritme. Methoden bestaan voor het oplossen van enkele niet-convexe kwadratische functies, maar ze zijn ingewikkeld en niet direct beschikbaar.
Wiskundige optimalisatietechnieken worden gebruikt in kwadratische programmering om een objectieve functie te minimaliseren. De objectieve functie bestaat uit een aantal beslissingsvariabelen die al dan niet worden begrensd. De beslissingsvariabelen hebben bevoegdheden 0, 1 of 2. De objectieve functie kan worden onderworpen aan een aantal lineaire gelijkheid en ongelijkheidsbeperkingen met betrekking tot de beslissingsvariabelen. Een voorbeeld van kwadratische programmering is:Minimaliseer f (x, y) = x 2 + 3y 2 - 12y + 12 waarbij x + y = 6 en x> 0 en y ≥ 0.
Het is vaak interessant om multivariate kwadratische functies te gebruiken om problemen in de echte wereld te beschrijven. Met behulp van de moderne portefeuilletheorie zal een financiële analist bijvoorbeeld proberen de portefeuille van een bedrijf te optimaliseren door het aandeel activa te kiezen dat het risico van een bepaald verwacht rendement minimaliseert. Een kwadratische vergelijking die bestaat uit activagewichten en de correlatie tussen activa beschrijft de portfolio -variantie die kan worden geminimaliseerd met behulp van kwadratische programmering. Een ander voorbeeld kan een fabrikant zijn die een kwadratische vergelijking gebruikt om de relatie tussen verschillende kwaliteitscomponenten en de kosten van een product te beschrijven. De fabrikant kan de kosten minimaliseren met behoud van bepaalde normen door lineaire beperkingen toe te voegen aan het kwadratische programma.
Een van de belangrijkste conditioNS bij het oplossen van een kwadratisch programma is de convexiteit van de objectieve vergelijking. De convexiteit van een kwadratische functie wordt bepaald door de Hessian of de matrix van zijn tweede derivaten. De functie wordt convex genoemd als de Hessiaanse matrix positief definitief of positief semi-definitief is, dat wil zeggen als de alle eigenwaarden respectievelijk positief of niet-negatief zijn. Als de Hessiaan positief is en er een haalbare oplossing bestaat, is dat lokale minimum uniek en is een wereldwijd minimum. Als de Hessian semi-positief is, is een haalbare oplossing mogelijk niet uniek. Niet-convexe kwadratische functies kunnen lokale of globale minima hebben, maar ze zijn moeilijker te bepalen.
Er zijn veel benaderingen om een convexe kwadratische functie op te lossen met behulp van kwadratische programmering. De meest voorkomende aanpak is een uitbreiding van het simplex -algoritme. Sommige andere methoden omvatten de interieurpunt- of barrièresmethode, de actieve set -methode en de conjugaatgradiëntmethode. Deze methoden zijn geïntegreerd in cerTain -programma's zoals Mathematica® en MATLAB® en ze zijn beschikbaar in bibliotheken voor veel programmeertalen.