Solution refinement at regular points of conic problems
From MaRDI portal
Publication:2282811
DOI10.1007/S10589-019-00122-9zbMATH Open1434.90132arXiv1811.02157OpenAlexW2971228012MaRDI QIDQ2282811FDOQ2282811
Authors: Enzo Busseti, Walaa M. Moursi, Stephen Boyd 
Publication date: 19 December 2019
Published in: Computational Optimization and Applications (Search for Journal in Brave)
Abstract: Most numerical methods for conic problems use the homogenous primal-dual embedding, which yields a primal-dual solution or a certificate establishing primal or dual infeasibility. Following Patrinos (and others, 2018), we express the embedding as the problem of finding a zero of a mapping containing a skew-symmetric linear function and projections onto cones and their duals. We focus on the special case when this mapping is regular, i.e., differentiable with nonsingular derivative matrix, at a solution point. While this is not always the case, it is a very common occurrence in practice. We propose a simple method that uses LSQR, a variant of conjugate gradients for least squares problems, and the derivative of the residual mapping to refine an approximate solution, i.e., to increase its accuracy. LSQR is a matrix-free method, i.e., requires only the evaluation of the derivative mapping and its adjoint, and so avoids forming or storing large matrices, which makes it efficient even for cone problems in which the data matrices are given and dense, and also allows the method to extend to cone programs in which the data are given as abstract linear operators. Numerical examples show that the method almost always improves an approximate solution of a conic program, and often dramatically, at a computational cost that is typically small compared to the cost of obtaining the original approximate solution. For completeness we describe methods for computing the derivative of the projection onto the cones commonly used in practice: nonnegative, second-order, semidefinite, and exponential cones. The paper is accompanied by an open source implementation.
Full work available at URL: https://arxiv.org/abs/1811.02157
Recommendations
- Gradient methods and conic least-squares problems
- Conic optimization via operator splitting and homogeneous self-dual embedding
- An Augmented Primal-Dual Method for Linear Conic Programs
- Operator splitting for a homogeneous embedding of the linear complementarity problem
- Projection Methods in Conic Optimization
Numerical mathematical programming methods (65K05) Convex programming (90C25) Semidefinite programming (90C22) Computational methods for problems pertaining to operations research and mathematical programming (90-08) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33)
Cites Work
- LSQR: An Algorithm for Sparse Linear Equations and Sparse Least Squares
- Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
- CVXPY: a Python-embedded modeling language for convex optimization
- OSQP: an operator splitting solver for quadratic programs
- Title not available (Why is that?)
- Conic optimization via operator splitting and homogeneous self-dual embedding
- Variational Analysis
- Title not available (Why is that?)
- Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
- A nonsmooth version of Newton's method
- Graph implementations for nonsmooth convex programs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Robust Solutions to Least-Squares Problems with Uncertain Data
- Proximité et dualité dans un espace hilbertien
- Convergence theorems for sequences of nonlinear operators in Banach spaces
- An O(√nL)-Iteration Homogeneous and Self-Dual Linear Programming Algorithm
- Solution of the Sylvester matrix equation AXB T + CXD T = E
- Clarke generalized Jacobian of the projection onto the cone of positive semidefinite matrices
- Solving conic optimization problems via self-dual embedding and facial reduction: A unified approach
- Convex analysis and monotone operator theory in Hilbert spaces
- On the local convergence of semismooth Newton methods for linear and nonlinear second-order cone programs without strict complementarity
- Löwner's Operator and Spectral Functions in Euclidean Jordan Algebras
- Analysis of Nonsmooth Symmetric-Matrix-Valued Functions with Applications to Semidefinite Complementarity Problems
- A survey of truncated-Newton methods
- Title not available (Why is that?)
- Global Convergence Analysis of the Generalized Newton and Gauss-Newton Methods of the Fischer-Burmeister Equation for the Complementarity Problem
- An inexact Levenberg-Marquardt method for large sparse nonlinear least squres
- Introduction to applied linear algebra. Vectors, matrices, and least squares
- SuperMann: A Superlinearly Convergent Algorithm for Finding Fixed Points of Nonexpansive Operators
Cited In (3)
Uses Software
This page was built for publication: Solution refinement at regular points of conic problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2282811)
