A homogeneous interior-point algorithm for nonsymmetric convex conic optimization

Anders Skajaa, Yinyu Ye

Research output: Contribution to journalJournal articleResearchpeer-review

646 Downloads (Pure)

Abstract

A homogeneous interior-point algorithm for solving nonsymmetric convex conic optimization problems is presented. Starting each iteration from the vicinity of the central path, the method steps in the approximate tangent direction and then applies a correction phase to locate the next well-centered primal–dual point. Features of the algorithm include that it makes use only of the primal barrier function, that it is able to detect infeasibilities in the problem and that no phase-I method is needed. We prove convergence to TeX -accuracy in TeX iterations. To improve performance, the algorithm employs a new Runge–Kutta type second order search direction suitable for the general nonsymmetric conic problem. Moreover, quasi-Newton updating is used to reduce the number of factorizations needed, implemented so that data sparsity can still be exploited. Extensive and promising computational results are presented for the TeX -cone problem, the facility location problem, entropy maximization problems and geometric programs; all formulated as nonsymmetric convex conic optimization problems.
Original languageEnglish
JournalMathematical Programming
Volume150
Issue number2
Pages (from-to)391-422
ISSN0025-5610
DOIs
Publication statusPublished - 2014

Fingerprint

Dive into the research topics of 'A homogeneous interior-point algorithm for nonsymmetric convex conic optimization'. Together they form a unique fingerprint.

Cite this