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

Abstract

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.

arXiv comment39 pages, comments welcome. In this version, we simplified the error bound framework and also obtained a better error bound result for products of exponential cones

References in corpus (8)

• Calculus of the exponent of Kurdyka-Łojasiewicz inequality and its applications to linear convergence of first-order methods
• Lifts of convex sets and cone factorizations
• Convergence rate analysis for averaged fixed point iterations in the presence of Hölder regularity
• Amenable cones: error bounds without constraint qualifications
• Facial Reduction and Partial Polyhedrality
• Amenable cones are particularly nice
• Convergence analysis under consistent error bounds
• Proximal Averages for Minimization of Entropy Functionals

Cited by in corpus (2)

• Generalized power cones: optimal error bounds and automorphisms
• Concrete convergence rates for common fixed point problems under Karamata regularity