An extension of Karmarkar's projective algorithm for convex quadratic programming (Q1121792): Difference between revisions

The paper uses Karmarkar's polynomial-time LP algorithm as a base on which to develop a polynomial-time algorithm for convex quadratic programs. Using the interior ellipsoid method, the following sub- optimization problem is solved: \[ \min f(\hat x)=\hat x[n]^ T\hat Q\hat x[n]/2\hat x_{n+1}-\hat c\hat x[n] \] subject to: \(\hat A\hat x=\hat b\), \(\| \hat x-e\| \leq \beta <1\), where \[ \hat Q=DQD\quad (D=diag(x^ k)),\quad \hat c=cD,\quad \hat A=\left( \begin{matrix} AD-b\\ e^ T\end{matrix} \right),\quad \hat b=\left( \begin{matrix} 0\\ n+1\end{matrix} \right),\quad and \] \^x[n] is the vector of the first n components of \(\hat x\in R^{n+1}\). The authors show that this problem can be solved in \(O(Ln^ 3)\) operations and that \(O(Ln)\) iterates are required. While no computational results are presented, the authors claim an efficient implementation is possible and cite a Ph.D. thesis as a source of some such testing.