Complexity Analysis of a Sampling-Based Interior Point Method for Convex Optimization

Research output: Working paperOther research output

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
Place of PublicationIthaca
PublisherCornell University Library
Number of pages38
Publication statusSubmitted - 2018

Publication series

NamearXiv
Volume1811.07677

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