Solution refinement at regular points of conic problems
From MaRDI portal
Publication:2282811
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)
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.
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
Cites work
- scientific article; zbMATH DE number 410743 (Why is no real title available?)
- scientific article; zbMATH DE number 1266748 (Why is no real title available?)
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- scientific article; zbMATH DE number 1421091 (Why is no real title available?)
- scientific article; zbMATH DE number 5060482 (Why is no real title available?)
- A nonsmooth version of Newton's method
- A survey of truncated-Newton methods
- An O(√nL)-Iteration Homogeneous and Self-Dual Linear Programming Algorithm
- An inexact Levenberg-Marquardt method for large sparse nonlinear least squres
- Analysis of Nonsmooth Symmetric-Matrix-Valued Functions with Applications to Semidefinite Complementarity Problems
- CVXPY: a Python-embedded modeling language for convex optimization
- Clarke generalized Jacobian of the projection onto the cone of positive semidefinite matrices
- Conic optimization via operator splitting and homogeneous self-dual embedding
- Convergence theorems for sequences of nonlinear operators in Banach spaces
- Convex analysis and monotone operator theory in Hilbert spaces
- Global Convergence Analysis of the Generalized Newton and Gauss-Newton Methods of the Fischer-Burmeister Equation for the Complementarity Problem
- Graph implementations for nonsmooth convex programs
- Introduction to applied linear algebra. Vectors, matrices, and least squares
- LSQR: An Algorithm for Sparse Linear Equations and Sparse Least Squares
- Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
- Löwner's Operator and Spectral Functions in Euclidean Jordan Algebras
- OSQP: an operator splitting solver for quadratic programs
- On the local convergence of semismooth Newton methods for linear and nonlinear second-order cone programs without strict complementarity
- Proximité et dualité dans un espace hilbertien
- Robust Solutions to Least-Squares Problems with Uncertain Data
- Solution of the Sylvester matrix equation AXB T + CXD T = E
- Solving conic optimization problems via self-dual embedding and facial reduction: A unified approach
- SuperMann: A Superlinearly Convergent Algorithm for Finding Fixed Points of Nonexpansive Operators
- Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
- Variational Analysis
Cited in
(3)
Describes a project that uses
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)
