Kas ir kvadrātiskā programmēšana?

Kvadrātiskajā programmēšanā tiek izmantotas matemātiskās optimizācijas metodes, lai samazinātu mērķa funkciju. Mērķa funkcija sastāv no vairākiem lēmuma mainīgajiem lielumiem, kas var būt vai nevar būt ierobežoti. Lēmuma mainīgajiem ir pilnvaras 0, 1 vai 2. Mērķa funkcija var tikt pakļauta vairākiem lineārās vienlīdzības un nevienlīdzības ierobežojumiem attiecībā uz lēmuma mainīgajiem. Kvadrātiskās programmēšanas piemērs ir: minimizējiet f(x,y) = x2 + 3y2 – 12y + 12, kur x + y = 6 un x > 0 un y ≥ 0.

Bieži vien ir interesanti izmantot daudzfaktoru kvadrātiskās funkcijas, lai aprakstītu reālās pasaules problēmas. Piemēram, izmantojot moderno portfeļa teoriju, finanšu analītiķis mēģinās optimizēt uzņēmuma portfeli, izvēloties tādu aktīvu īpatsvaru, kas samazina risku, kas saistīts ar doto paredzamo atdevi. Kvadrātvienādojums, ko veido aktīvu svari un korelācija starp aktīviem, apraksta portfeļa dispersiju, ko var samazināt, izmantojot kvadrātisko programmēšanu. Cits piemērs varētu būt ražotājs, kas izmanto kvadrātvienādojumu, lai aprakstītu saistību starp dažādām kvalitātes sastāvdaļām un produkta izmaksām. Ražotājs var samazināt izmaksas, vienlaikus saglabājot noteiktus standartus, pievienojot kvadrātveida programmai lineārus ierobežojumus.

Viens no svarīgākajiem nosacījumiem kvadrātprogrammas risināšanā ir objektīvā vienādojuma izliekums. Kvadrātfunkcijas izliekumu nosaka Hesa ​​vai tās otro atvasinājumu matrica. Funkciju sauc par izliektu, ja Hesa ​​matrica ir pozitīva noteikta vai pozitīva daļēji noteikta, tas ir, ja visas īpašvērtības ir attiecīgi pozitīvas vai nenegatīvas. Ja Hesens ir pozitīvs un ir iespējams risinājums, tad šis vietējais minimums ir unikāls un ir globāls minimums. Ja Hesens ir daļēji pozitīvs, iespējamais risinājums var nebūt unikāls. Neizliektām kvadrātiskām funkcijām var būt lokāli vai globāli minimumi, taču tos ir grūtāk noteikt.

Ir daudzas pieejas, kā atrisināt izliektu kvadrātfunkciju, izmantojot kvadrātisko programmēšanu. Visizplatītākā pieeja ir simpleksa algoritma paplašināšana. Dažas citas metodes ietver iekšējā punkta vai barjeras metodi, aktīvās kopas metodi un konjugētā gradienta metodi. Šīs metodes ir integrētas noteiktās programmās, piemēram, Mathematica® un Matlab®, un tās ir pieejamas daudzu programmēšanas valodu bibliotēkās.