A Geodesic Interior-Point Method for Linear Optimization over Symmetric Cones
From MaRDI portal
Abstract: We develop a new interior-point method (IPM) for symmetric-cone optimization, a common generalization of linear, second-order-cone, and semidefinite programming. In contrast to classical IPMs, we update iterates with a geodesic of the cone instead of the kernel of the linear constraints. This approach yields a primal-dual-symmetric, scale-invariant, and line-search-free algorithm that uses just half the variables of a standard primal-dual IPM. With elementary arguments, we establish polynomial-time convergence matching the standard square-root-n bound. Finally, we prove global convergence of a long-step variant and provide an implementation that supports all symmetric cones. For linear programming, our algorithms reduce to central-path tracking in the log domain.
Recommendations
- An interior-point method for symmetric optimization based on a new wide neighborhood
- Interior-point methods based on kernel functions for symmetric optimization
- A new full Nesterov-Todd step primal-dual path-following interior-point algorithm for symmetric optimization
- A new full Nesterov-Todd step feasible interior-point method for convex quadratic symmetric cone optimization
- A primal-dual predictor-corrector interior-point method for symmetric cone programming with \(O (\sqrt{r} \log \epsilon^{-1})\) iteration complexity
Cites work
- A study of search directions in primal-dual interior-point methods for semidefinite programming
- An Interior-Point Method for Semidefinite Programming
- Conic geometric optimization on the manifold of positive definite matrices
- Euclidean Jordan algebras and interior-point algorithms
- Extension of primal-dual interior point algorithms to symmetric cones
- Full Nesterov-Todd step infeasible interior-point method for symmetric optimization
- Geodesic Convexity and Covariance Estimation
- Geometric means on symmetric cones
- Hessian barrier algorithms for linearly constrained optimization problems
- Hessian Riemannian Gradient Flows in Convex Programming
- scientific article; zbMATH DE number 4164543 (Why is no real title available?)
- scientific article; zbMATH DE number 52737 (Why is no real title available?)
- scientific article; zbMATH DE number 715155 (Why is no real title available?)
- scientific article; zbMATH DE number 1862745 (Why is no real title available?)
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- scientific article; zbMATH DE number 852525 (Why is no real title available?)
- scientific article; zbMATH DE number 4197739 (Why is no real title available?)
- scientific article; zbMATH DE number 5223994 (Why is no real title available?)
- scientific article; zbMATH DE number 964349 (Why is no real title available?)
- Implementation of interior point methods for mixed semidefinite and second order cone optimization problems
- Interior path following primal-dual algorithms. I: Linear programming
- Interior-Point Methods for the Monotone Semidefinite Linear Complementarity Problem in Symmetric Matrices
- Introductory lectures on convex optimization. A basic course.
- Linear systems in Jordan algebras and primal-dual interior-point algorithms
- Metric and spectral geometric means on symmetric cones
- Nineteen Dubious Ways to Compute the Exponential of a Matrix
- On the implementation and usage of SDPT3 -- a Matlab software package for semidefinite-quadratic-linear programming, version 4.0
- On the Nesterov--Todd Direction in Semidefinite Programming
- On the Riemannian geometry defined by self-concordant barriers and interior-point methods.
- Positive Definite Matrices
- Primal central paths and Riemannian distances for convex sets
- Primal--Dual Path-Following Algorithms for Semidefinite Programming
- Primal-Dual Interior-Point Methods for Self-Scaled Cones
- Primal-dual symmetry and scale invariance of interior-point algorithms for convex optimization
- Self-Scaled Barriers and Interior-Point Methods for Convex Programming
- Self-scaled barriers for irreducible symmetric cones
- Symmetric primal-dual path-following algorithms for semidefinite programming
- The Geometric Mean, Matrices, Metrics, and More
Cited in
(6)- Two wide neighborhood interior-point methods for symmetric cone optimization
- Information geometry and interior-point algorithms in semidefinite programs and symmetric cone programs
- scientific article; zbMATH DE number 1501278 (Why is no real title available?)
- Performance enhancements for a generic conic interior point algorithm
- Log-domain interior-point methods for convex quadratic programming
- Inexact log-domain interior-point methods for quadratic programming
This page was built for publication: A Geodesic Interior-Point Method for Linear Optimization over Symmetric Cones
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6161308)
