Optimal error bounds for conic linear feasibility problems and their applications

Abstract

Error bounds are a requisite for trusting or distrusting solutions in an informed way. Until recently, provable error bounds in the absence of constraint qualifications were unattainable for many classes of cones that do not admit projections with known succinct expressions. In this thesis, we apply a recently developed framework based on facial reduction algorithms and one-step facial residual functions to build up error bounds for two closed convex cones: the generalized power cones and the log-determinant cones. The generalized power cones admit direct modelling of certain problems and have found applications in geometric programs, generalized location problems, and portfolio optimization, etc. We propose a complete error bound analysis for the conic linear feasibility problems with the generalized power cones without requiring any constraint qualifications. All the error bounds are shown to be tight in the sense of that framework. Besides their utility for understanding solution reliability, the error bounds we discover have additional applications to the algebraic structure of the underlying cone. We then completely determine the automorphism group of the generalized power cones, which was unknown before our work. Based on the automorphism group, we also discuss some other theoretical questions related to homogeneity and perfectness, identifying a set of generalized power cones that are self-dual, irreducible, nonhomogeneous, and perfect. The log-determinant cone is the closure of the hypograph of the perspective function of the log-determinant function, which has both theoretical and practical importance. Specifically, a problem with a log-determinant term in its objective can be recast as a problem over the log-determinant cone, indicating the significance of the log-determinant cone. As a high-dimensional generalization of the exponential cone, whose error bounds were well studied, the derivation of the error bounds for the log-determinant cone is however not straightforward because of the higher dimension and the more involved facial structure. We establish tight error bounds for the log-determinant cone problem without requiring any constraint qualifications.