Error bounds for conic feasibility problems: case studies on the exponential cone

报告摘要：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 talk naturally arise 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. Hence, deriving bounds on the distance to the intersection based on the latter two distances (a.k.a. the error-bound problem) is crucial 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.

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

报告人简介：Dr Ting Kei Pong is currently an associate professor at the Hong Kong Polytechnic University. His research area is continuous optimization. He obtained his PhD degree from University of Washington in 2011. He then worked as a postdoctoral fellow at University of Waterloo (from 2011 to 2013) and later as a PIMS postdoctoral fellow at University of British Columbia in Vancouver (from 2013 to 2014), prior to joining the Hong Kong Polytechnic University in 2014. He now serves as an associate editor of Mathematics of Operations Research and the Open Journal of Mathematical Optimization, and is a member of the editorial board of Computational Optimization and Applications and the Pacific Journal of Optimization.