Homotopy Methods for Convex Optimization

Convex optimization encompasses a wide range of optimization problems that con-tain many efficiently solvable subclasses. Interior point methods are currently the state-of-the-artapproach for solving such problems, particularly effective for classes like semidefinite programming,quadratic programming, and geometric programming. However, their success hinges on the construc-tion of self-concordant barrier functions for feasible sets. In this work, we investigate and developa homotopy-based approach to solve convex optimization problems. While homotopy methods havebeen considered in optimization before, their potential for general convex programs remains under-explored. This approach gradually transforms the feasible set of a trivial optimization problem intothe target one while tracking solutions by solving a differential equation, in contrast to traditionalcentral path methods. We establish a criterion that ensures that the homotopy method correctlysolves the optimization problem and prove the existence of such homotopies for several importantclasses, including semidefinite and hyperbolic programs. Furthermore, we demonstrate that our ap-proach numerically outperforms state-of-the-art methods in hyperbolic programming, highlightingits practical advantages.