Recent Scalability Improvements for Semidefinite Programming with Applications in Machine Learning, Control, and Robotics

Research output: Contribution to journalReview articlepeer-review

18 Scopus citations

Abstract

Historically, scalability has been a major challenge for the successful application of semidefinite programming in fields such as machine learning, control, and robotics. In this article, we survey recent approaches to this challenge, including those that exploit structure (e.g., sparsity and symmetry) in a problem, those that produce low-rank approximate solutions to semidefinite programs, those that use more scalable algorithms that rely on augmented Lagrangian techniques and the alternating-direction method of multipliers, and those that trade off scalability with conservatism (e.g., by approximating semidefinite programs with linear and second-order cone programs). For each class of approaches, we provide a high-level exposition, an entry point to the corresponding literature, and examples drawn from machine learning, control, or robotics. We also present a list of software packages that implement many of the techniques discussed in the review. Our hope is that this article will serve as a gateway to the rich and exciting literature on scalable semidefinite programming for both theorists and practitioners.

Original languageEnglish (US)
Pages (from-to)331-360
Number of pages30
JournalAnnual Review of Control, Robotics, and Autonomous Systems
Volume3
DOIs
StatePublished - May 3 2020

All Science Journal Classification (ASJC) codes

  • Artificial Intelligence
  • Human-Computer Interaction
  • Control and Systems Engineering
  • Engineering (miscellaneous)

Keywords

  • Control
  • Machine learning
  • Robotics
  • Semidefinite programming
  • Sum of squares programming

Fingerprint

Dive into the research topics of 'Recent Scalability Improvements for Semidefinite Programming with Applications in Machine Learning, Control, and Robotics'. Together they form a unique fingerprint.

Cite this