Name
Title | ||
|---|---|---|
Interior path following primal-dual algorithms. Part II: Convex quadratic programming |
Abstract | ||
|---|---|---|
We describe a primal-dual interior point algorithm for convex quadratic programming problems which requires a total of
<img src="/fulltext-image.asp?format=htmlnonpaginated&src=K733514G345G7831_html\10107_2005_Article_BF01587076_TeX2GIFIE1.gif" border="0" alt="
$$O\left( {\sqrt n L} \right)$$
" /> number of iterations, whereL is the input size. Each iteration updates a penalty parameter and finds an approximate Newton direction associated with the Karush-Kuhn-Tucker system of equations which characterizes a solution of the logarithmic barrier function problem. The algorithm is based on the path following idea. The total number of arithmetic operations is shown to be of the order of O(n3L). |
Year | DOI | Venue |
|---|---|---|
1989 | 10.1007/BF01587076 | Math. Program. |
Keywords | Field | DocType |
polynomial-time algorithms,logarithmic barrier function,path following.,primal-dual algorithm,part ii,interior-point methods,interior path,convex quadratic programming,karmarkar's algorithm,karush kuhn tucker,system of equations,barrier function,interior point method | Path following,Quadratic programming,Logarithm,Time complexity,Karmarkar's algorithm,Discrete mathematics,Mathematical optimization,Combinatorics,System of linear equations,Algorithm,Interior point method,Convex optimization,Mathematics | Journal |
Volume | Issue | ISSN |
44 | 1 | 0025-5610 |
Citations | PageRank | References |
115 | 33.15 | 4 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Renato D.C. Monteiro | 1 | 271 | 57.90 |
| Ilan Adler | 2 | 674 | 155.98 |