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

• 成果类型: Article
• 署名作者: Lindstrom, Scott B.; Lourenco, Bruno F.; Pong, Ting Kei
• 署名单位: Curtin University; Research Organization of Information & Systems (ROIS); Institute of Statistical Mathematics (ISM) - Japan; Hong Kong Polytechnic University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-022-01883-8
• 发表日期: 2023
• 页码: 229-278
• 关键词: projection methods; descent methods; convex; optimization; INEQUALITY; algorithms; reduction; systems

摘要

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 Holderian error bound holds but the supremum of the set of admissible exponents is not itself an admissible exponent.