1. Projectively self-concordant barriers
- Author
-
Roland Hildebrand, Données, Apprentissage et Optimisation (DAO), Laboratoire Jean Kuntzmann (LJK), Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), and Université Grenoble Alpes (UGA)
- Subjects
Optimization and Control (math.OC) ,General Mathematics ,FOS: Mathematics ,90C51, 90C25 ,[MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC] ,Management Science and Operations Research ,Mathematics - Optimization and Control ,Mathematics::Geometric Topology ,Computer Science Applications - Abstract
Self-concordance is the most important property required for barriers in convex programming. It is intrinsically linked to the affine structure of the underlying space. Here we introduce an alternative notion of self-concordance which is linked to the projective structure. A function on a set $X \subset A^n$ in an $n$-dimensional affine space is projectively self-concordant if and only if it can be extended to an affinely self-concordant logarithmically homogeneous function on the conic extension $K \subset V^{n+1}$ of $X$ in the $(n+1)$-dimensional vector space obtained by homogenization of $A^n$. The feasible sets in conic programs, notably linear and semi-definite programs, are naturally equipped with projectively self-concordant barriers. However, the interior-point methods used to solve these programs employ only affine self-concordance. We show that estimates used in the analysis of interior-point methods are tighter for projective self-concordance, in particular inner and outer approximations of the set. This opens the way to a better tuning of parameters in interior-points algorithms to allow larger steps and hence faster convergence. Projective self-concordance is also a useful tool in the theoretical analysis of logarithmically homogeneous barriers on cones.
- Published
- 2022
- Full Text
- View/download PDF