A strict complementarity approach to error bound and sensitivity of solution of conic programs

In this paper, we provide an elementary, geometric, and unified framework to analyze conic programs that we call the strict complementarity approach. This framework allows us to establish error bounds and quantify the sensitivity of the solution. The framework uses three classical ideas from convex...

Full description

Saved in:
Bibliographic Details
Published in:Optimization letters 2023-09, Vol.17 (7), p.1551-1574
Main Authors: Ding, Lijun, Udell, Madeleine
Format: Article
Language:English
Subjects:
Computational Intelligence
Mathematics
Mathematics and Statistics
Numerical and Computational Physics
Operations Research/Decision Theory
Optimization
Original Paper
Simulation
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper, we provide an elementary, geometric, and unified framework to analyze conic programs that we call the strict complementarity approach. This framework allows us to establish error bounds and quantify the sensitivity of the solution. The framework uses three classical ideas from convex geometry and linear algebra: linear regularity of convex sets, facial reduction, and orthogonal decomposition. We show how to use this framework to derive error bounds for linear programming, second order cone programming, and semidefinite programming.
ISSN:1862-4472
1862-4480
DOI:10.1007/s11590-022-01942-1