^{1} Department of Applied Mathematics and Computer Science, Technical University of Denmark^{2} Department of Informatics and Mathematical Modeling, Technical University of Denmark^{3} Stanford University

DOI:

10.1007/s10107-014-0773-1

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.

Type:

Journal article

Language:

English

Published in:

Mathematical Programming, 2014, Vol 150, Issue 2, p. 391-422