zbMATH — the first resource for mathematics

An extension of Karmarkar’s projective algorithm for convex quadratic programming. (English) Zbl 0674.90077
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.
Reviewer: J.J.Dinkel

MSC:
 90C25 Convex programming 90C20 Quadratic programming 68Q25 Analysis of algorithms and problem complexity 90C05 Linear programming 65K05 Numerical mathematical programming methods
Full Text: