A homogeneous interior-point algorithm for nonsymmetric convex conic optimization

• 成果类型: Article
• 署名作者: Skajaa, Anders; Ye, Yinyu
• 署名单位: Technical University of Denmark; Stanford University; Nanjing University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-014-0773-1
• 发表日期: 2015
• 页码: 391-422
• 关键词: Implementation

摘要

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 -accuracy in 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 -cone problem, the facility location problem, entropy maximization problems and geometric programs; all formulated as nonsymmetric convex conic optimization problems.