Error bounds, facial residual functions and applications to the exponential cone

We construct a general framework for deriving error bounds for conic feasibility problems. In particular, our approach allows one to work with cones that fail to be amenable or even to have computable projections, two previously challenging barriers. For the purpose, we first show how error bounds m...

Full description

Saved in:
Bibliographic Details
Published in:Mathematical programming 2023-06, Vol.200 (1), p.229-278
Main Authors: Lindstrom, Scott B., Lourenço, Bruno F., Pong, Ting Kei
Format: Article
Language:English
Subjects:
Calculus of Variations and Optimal Control
Optimization
Combinatorics
Cones
Entropy (Information theory)
Feasibility
Full Length Paper
Mathematical and Computational Physics
Mathematical Methods in Physics
Mathematics
Mathematics and Statistics
Mathematics of Computing
Numerical Analysis
Theoretical
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We construct a general framework for deriving error bounds for conic feasibility problems. In particular, our approach allows one to work with cones that fail to be amenable or even to have computable projections, two previously challenging barriers. For the purpose, we first show how error bounds may be constructed using objects called one-step facial residual functions . Then, we develop several tools to compute these facial residual functions even in the absence of closed form expressions for the projections onto the cones. We demonstrate the use and power of our results by computing tight error bounds for the exponential cone feasibility problem. Interestingly, we discover a natural example for which the tightest error bound is related to the Boltzmann–Shannon entropy. We were also able to produce an example of sets for which a Hölderian error bound holds but the supremum of the set of admissible exponents is not itself an admissible exponent.
ISSN:0025-5610
1436-4646
DOI:10.1007/s10107-022-01883-8