Error Bounds for Conic Feasibility Problems: Case Studies on the Exponential Cone

Ting Kei Pong, Hong Kong Polytechnic University, Applied Mathematics
June 27, 2023 12:30 pm LSK 306

Pizza lunch will be served preceding the talk, starting at 12:00.

A linear conic programming problem aims at minimizing a linear objective over the intersection of an affine set and a closed convex cone. The conic feasibility problems that we study in this work arise naturally from the optimality conditions of linear conic programs, which amount to finding a point in the intersection of an affine set and a closed convex cone. Although the distance to the intersection gives a precise measure of proximity of a point to being feasible, this distance can be much harder to compute than the distances to the affine set and the cone respectively. Thus, establishing bounds on the distance to the intersection based on the latter two distances (a.k.a. the error-bound problem) is instrumental in the design of termination criteria for conic solvers and the study of convergence rate of algorithms.

     In this talk, we present a general framework for deriving error bounds for conic feasibility problems. Our framework is based on the classical concept of facial reduction, which is a fundamental tool for handling degeneracy in conic programs, and a new object called one-step facial residual function. We illustrate how our framework can be applied to obtain error bounds for the exponential cone, which is a recent addition to the MOSEK commercial conic solver that allows the modeling of optimization problems involving power, exponential, logarithmic, and entropy functions in the objective or constraint set. If time permits, we will also discuss the tools we developed to compute these facial residual functions, which are applicable even when the projections onto the cones under study are not easy to analyze.

This is joint work with Scott B. Lindstrom and Bruno F. Lourenço.