Projectively Self-Concordant Barriers

DOI10.1287/MOOR.2021.1215MaRDI QIDQ5868964zbMATH OpenOpenAlexFDO

Authors Roland Hildebrand

Publication date 26 September 2022

Published in Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1909.01883

zbMATH Keywords

interior-point methodsself-concordant barriers

Mathematics Subject Classification ID

Convex programming (90C25) Interior-point methods (90C51)

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 $Xsubset{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 $Ksubset{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.

Recommendations

• Barriers on projective convex sets
• Self-scaled barriers for irreducible symmetric cones
• Self-concordant barriers for hyperbolic means
• Recursive construction of optimal self-concordant barriers for homogeneous cones
• On self-concordant barriers for generalized power cones
• Self-concordant barriers for cones generated by Chebyshev systems
• Self-concordant barriers for convex approximations of structured convex sets
• Canonical barriers on convex cones
• On the Self-Concordance of the Universal Barrier Function
• Universal Barrier Is n-Self-Concordant

Cites work

• A mathematical view of interior-point methods in convex optimization
• Canonical barriers on convex cones
• Centro-affine hypersurface immersions with parallel cubic form
• scientific article; zbMATH DE number 729680 (Why is no real title available?)
• scientific article; zbMATH DE number 790016 (Why is no real title available?)
• Hyperbolic Polynomials and Interior Point Methods for Convex Programming
• Lectures on convex optimization
• On self-concordant barrier functions for conic hulls and fractional programming
• Self-Scaled Barriers and Interior-Point Methods for Convex Programming
• The entropic barrier: exponential families, log-concave geometry, and self-concordance

Cited in

(9)

• On self-concordant barrier functions for conic hulls and fractional programming
• On self-concordant barriers for generalized power cones
• Barriers on projective convex sets
• New self-concordant barrier for the hypercube
• The entropic barrier: exponential families, log-concave geometry, and self-concordance
• Self-concordant barriers for hyperbolic means
• Numerical analysis of the convex relaxation of the barrier parameter functional of self-concordant barriers
• Self-concordant barriers for convex approximations of structured convex sets
• Three different views on barrier functions in conic optimization

This page was built for publication: Projectively Self-Concordant Barriers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5868964)