Complexity analysis of a sampling-based interior point method for convex optimization

Riley Badenbroek, Etienne de Klerk

Research output: Contribution to journalArticleScientificpeer-review

133 Downloads (Pure)

Abstract

We develop a short-step interior point method to optimize a linear function over a convex body assuming that one only knows a membership oracle for this body. The approach is based on Abernethy and Hazan's sketch of a universal interior point method using the so-called entropic barrier [arXiv 1507.02528v2, 2015]. It is well-known that the gradient and Hessian of the entropic barrier can be approximated by sampling from Boltzmann-Gibbs distributions, and the entropic barrier was shown to be self-concordant by Bubeck and Eldan [arXiv 1412.1587v3, 2015]. The analysis of our algorithm uses properties of the entropic barrier, mixing times for hit-and-run random walks by Lovász and Vempala [Foundations of Computer Science, 2006], approximation quality guarantees for the mean and covariance of a log-concave distribution, and results from De Klerk, Glineur and Taylor on inexact Newton-type methods [arXiv 1709.0519, 2017].
Original languageEnglish
Pages (from-to)779-811
JournalMathematics of Operations Research
Volume47
Issue number1
DOIs
Publication statusPublished - Feb 2022

Keywords

  • copositive optimization
  • analytic center cutting plane method
  • completely positive matrices

Fingerprint

Dive into the research topics of 'Complexity analysis of a sampling-based interior point method for convex optimization'. Together they form a unique fingerprint.

Cite this