Conic Optimization via Operator Splitting and Homogeneous Self-Dual Embedding

• DOI: 10.48550/arxiv.1312.3039
• Publication Date: 2013-01-01
• Authors: Brendan O’Donoghue; Eric Chu; Neal S. Parikh; Stephen Boyd
• Keywords: Conic optimization; Interior point method; Second-order cone programming; Cone (formal languages); Conic section; Operator (biology)

We introduce a first order method for solving very large convex cone programs. The uses an operator splitting method, the alternating directions of multipliers, to solve homogeneous self-dual embedding, equivalent feasibility problem involving finding nonzero point in intersection subspace and cone. This approach has several favorable properties. Compared interior-point methods, first-order methods scale problems, at cost requiring more time reach high accuracy. other programs, our finds both primal dual solutions when available or certificate infeasibility unboundedness otherwise, is parameter-free, per-iteration same as applying alone. discuss efficient implementation detail, including direct indirect computing projection onto subspace, scaling original data, stopping criteria. describe open-source implementation, which handles usual (symmetric) non-negative, second-order, semidefinite cones well (non-self-dual) exponential power their duals. report numerical results that show speedups over solvers general