Abstract
We present a unified framework for solving linear and convex quadratic programs via interior point methods. At each iteration, this method solves an indefinite system whose matrix is {Mathematical expression} instead of reducing to obtain the usual AD2AT system. This methodology affords two advantages: (1) it avoids the fill created by explicitly forming the product AD2AT when A has dense columns; and (2) it can easily be used to solve nonseparable quadratic programs since it requires only that D be symmetric. We also present a procedure for converting nonseparable quadratic programs to separable ones which yields computational savings when the matrix of quadratic coefficients is dense.
Original language | English (US) |
---|---|
Pages (from-to) | 1-32 |
Number of pages | 32 |
Journal | Mathematical Programming |
Volume | 58 |
Issue number | 1-3 |
DOIs | |
State | Published - Jan 1993 |
All Science Journal Classification (ASJC) codes
- Software
- General Mathematics
Keywords
- Interior point method
- linear programming
- quadratic programming