An extension of Karmarkar's projective algorithm for convex quadratic programming (Q1121792): Difference between revisions
From MaRDI portal
Removed claim: author (P16): Item:Q173845 |
Changed an Item |
||
Property / author | |||
Property / author: Yinyu Ye / rank | |||
Normal rank |
Revision as of 06:23, 10 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An extension of Karmarkar's projective algorithm for convex quadratic programming |
scientific article |
Statements
An extension of Karmarkar's projective algorithm for convex quadratic programming (English)
0 references
1989
0 references
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.
0 references
Karmarkar's projective algorithm
0 references
polynomial-time algorithm
0 references
convex quadratic
0 references
interior ellipsoid method
0 references
sub-optimization
0 references