On implementing a primal-dual interior-point method for conic quadratic optimization

E. D. Andersen, C. Roos, and T. Terlaky

Conic quadratic optimization is the problem of minimizing a linear function subject to the intersection of an affine set and the product of quadratic cones. The problem is a convex optimization problem and has numerous applications in engineering, economics, and other areas of science. Indeed, linear and convex quadratic optimization is a special case. Conic quadratic optimization problems can in theory be solved efficiently using interior-point methods. In particular it has been shown by Nesterov and Todd that primal-dual interior-point methods developed for linear optimization can be generalized to the conic quadratic case while maintaining their efficiency. Therefore, based on the work of Nesterov and Todd, we discuss an implementation of a primal-dual interior-point method for solution of large-scale sparse conic quadratic optimization problems. The main features of the implementation are it is based on a homogeneous and self-dual model, handles the rotated quadratic cone directly, employs a Mehrotra type predictor-corrector extension, and sparse linear algebra to improve the computational efficiency. Computational results are also presented which documents that the implementation is capable of solving very large problems robustly and efficiently.

Helsinki School of Economics and Business Administration, Working papers, W-274, December 2000

Contact: e.d.andersen@mosek.com