Úloha kvadratického programovania

Úvod do nelineárneho programovania

Cieľom úlohy nelineárneho programovania (ďalej už z len \(\hbox{NLP}\)) je minimalizácia funkcie \(f(x_1,\dots,x_n)\)  za podmienok  \(g_i(x_1,\dots,x_n)\leq 0,\) pre \(i=1,\dots,m\) a \(h_k(x)=0\) pre \(k=1,\dots,p\), kde \(\mathbf{x}=(x_1,\dots,x_n)^T\in \mathbf{X}\subset \mathbb{R}^n\).  Pre ľahší popis označme \(I=\{1,\dots, m\}\) a \(J=\{1,\dots, p\}\). Predpokladom je však, že dané funkcie \(f,g_i,h_k\) pre \(i\in I\), \(k\in J\) sú definované na celom \(\mathbf{R}^n\) a majú hodnoty na rozšírenej reálnej priamke \(\mathbf{R}^{\ast}\). Nelinearita úlohy je podmienená tým, že aspoň jedna z uvedených funkcií  nie je lineárna. \(\mathbf{X}\) predstavuje napr. nezápornosť niektorých premenných.

Úlohu \(\hbox{NLP}\) v rovnicovom tvare na základe vyššie uvedeného  môžeme zapísať nasledovne: \[\min\{f(x): g(x)\leq 0;h(x)=0,x\in \mathbf{X}\},\]kde \(g(x)=(g_1(x),\dots, g_m(x))^T\) a \(h(x)=(h_1(x),\dots, h_p(x))^T\) sú vektorové funkcie. Množinu prípustných riešení našej úlohy budeme štandardne označovať \[M=\{x\in \mathbf{X}: g(x)\leq 0,h(x)=0\}.\]V špeciálnych prípadoch \(g_i(x)=0\) je možné previesť na dve nerovnosti v tvare \(g_i(x)\leq 0\) a \(-g_i(x)\leq 0\).

Úvod do kvadratického programovania

Na úvod je potrebné si zopakovať základné vlastnosti definitných matíc. Matica \(A\) je pozitívne definitná (pozitívne semidefinitná), ak \[(\forall x)\; x^TAx> 0\quad [(\forall x)\; x^TAx\geq 0].\] Matica \(A\) je symetrická, ak \(A^T=A\). Keďže pre symetrické matice platí \[x^TAx=x^T\left(\frac{1}{2}(A+A^T)x\right),\]stačí sa zaoberať len symetrickými maticami.

Vlastnosti symetrických matíc:

• Symetrická matica je pozitívne definitná (semidefinitná) práve vtedy, keď všetky jej vlastné  čísla sú kladné (nezáporné).
• Symetrická matica \(A\) rozmerov \(n\times n\) je pozitívne definitná práve vtedy, keď \[ det\left(\begin{matrix} a_{11} & a_{12} &\dots & a_{1k}\\a_{21} & a_{22} &\dots & a_{2k} \\ \dots & \dots &\dots & \dots \\ a_{k1} & a_{k2} &\dots & a_{kk} \end{matrix}\right)>0\] pre \(k=1,\dots,n\).

Špeciálnym prípadom úlohy nelineárneho programovania je úloha kvadratického programovnia (ďalej už len \(\hbox{KP}\)), t.j. účelová funkcia je kvadratická a podmienky sú lineárne: \[ f(\mathbf{x})=\mathbf{x}^T\mathbf{C}\mathbf{x}+\mathbf{p}^T\mathbf{x} \to \min \] pri ohraničeniach \(\mathbf{x}\in \mathbf{D}\), kde \(n\) - počet rozhodovacích premenných úlohy; \(\mathbf{x}\in \mathbb{R}^n\) - vektor rozhodovacích premenných; \(\mathbf{C}\) - symetrická pozitívne semidefinitná matica \(n\)-tého stupňa; \(\mathbf{p}\in \mathbb{R}^n\) - vektor koeficientov; \(\mathbf{D}\subset \mathbb{R}^n\) - konvexná polyedrálna množina v \(\mathbb{R}^n\). Budeme uvažovať len tri špeciálne prípady polyedrálnej množiny \(\mathbf{D}\), a to: \[\mathbf{D_1}=\{\mathbf{x}: A\mathbf{x}\leq b, \mathbf{x}\geq 0\}, \]\[\mathbf{D_2}=\{\mathbf{x}: A\mathbf{x}= b, \mathbf{x}\geq 0\}, \]\[\mathbf{D_3}=\{\mathbf{x}: A\mathbf{x}= b\}, \] kde \(A\) - matica rozmerov \(m\times n\) a \(b\in \mathbb{R}^m\) - vektor. Prípady množín \(\mathbf{D_2}\) a \(\mathbf{D_3}\) vieme vhodnými dodatočnými podmienkami (napr. \(A\mathbf{x}= b\) práve vtedy, keď \(A\mathbf{x}\leq b\) a \(-A\mathbf{x}\leq -b\)) previesť na problém množiny \(\mathbf{D_1}\), a tak sa stačí zaoberať len týmto prípadom. Keďže sústava ohraničení \(\hbox{KP}\) je tvorená lineárnymi t.j. konvexnými funkciami a navyše predpokladáme, že \(\mathbf{C}\) je pozitívne semidefinitná matica a  z tohoto dôvodu aj účelová funkcia konvexná, tak úloha kvadratického programovania je úlohou konvexného programovania. Na základe toho môžeme využiť niektoré metódy pre riešenie úloh na viazaný extrém.