A geodesic interior-point method for linear optimization over symmetric cones

We develop a new interior-point method for symmetric-cone optimization, a common generalization of linear, second-order-cone, and semidefinite programming. Our key idea is updating 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 method. 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 compare the approaches computationally. For linear programming, our algorithms reduce to central-path tracking in the log domain.

Article

Download

View A geodesic interior-point method for linear optimization over symmetric cones