Optimization Online


On Implementing a Homogeneous Interior-Point Algorithm for Nonsymmetric Conic Optimization

Anders Skajaa (andsk***at***imm.dtu.dk)
John Bagterp Jørgensen (jbj***at***imm.dtu.dk)
Per Christian Hansen (pch***at***imm.dtu.dk)

Abstract: Based on earlier work by Nesterov, an implementation of a homogeneous infeasible-start interior-point algorithm for solving nonsymmetric conic optimization problems is presented. Starting each iteration from (the vicinity of) the central path, the method computes (nearly) primal-dual symmetric approximate tangent directions followed by a purely primal centering procedure to locate the next central 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. The method further employs quasi-Newton updating both to generate (pseudo) higher order directions and to reduce the number of factorizations needed in the centering process while still retaining the ability to exploit sparsity. Extensive and promising computational results are presented for the p-cone problem, the facility location problem, entropy problems and geometric programs; all formulated as nonsymmetric conic optimization problems.

Keywords: convex optimization, nonsymmetric, conic optimization, homogeneous model, infeasiblestart, interior-point algorithm

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Linear, Cone and Semidefinite Programming

Category 3: Nonlinear Optimization

Citation: On Implementing a Homogeneous Interior-Point Algorithm for Nonsymmetric Conic Optimization. IMM-Technical Report 2011-02. January 2011. Technical University of Denmark.

Download: [PDF]

Entry Submitted: 01/25/2011
Entry Accepted: 01/25/2011
Entry Last Modified: 03/29/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society