Improving Interior Point Algorithms for Semidefinite Programs

Carson Kent, Stanford University

Photo of Carson Kent

One of the greatest triumphs in the field of optimization has been the development of fast interior point algorithms for solving linear programming. Indeed, in both theory and practice, such algorithms have, for many years, been considered to be the de facto methods for solving linear programs. Moreover, reasonable structural similarity between linear and semidefinite optimization suggests that an analogous level of efficacy could exist for semidefinite interior point algorithms. Currently, however, the most efficient algorithms for semidefinite optimization rely on separating hyperplane techniques – methods whose theoretical and practical efficiency for solving linear programs were surpassed by interior point methods decades ago. To remedy this, we explore the application of recent advances in numerical linear algebra for improving the efficiency of semidefinite interior point methods. We show that, for certain regimes, interior point methods are able to compete with or outperform current, state-of-the-art cutting-hyperplane techniques.

Abstract Author(s): Carson Kent, Aaron Sidford