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

Riley Badenbroek () and Etienne de Klerk ()
Additional contact information
Riley Badenbroek: Econometric Institute, Erasmus University Rotterdam, Rotterdam 3062 PA, Netherlands
Etienne de Klerk: Department of Econometrics and Operations Research, Tilburg University, Tilburg 5037 AB, Netherlands

Mathematics of Operations Research, 2022, vol. 47, issue 1, 779-811

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 a sketch of a universal interior point method using the so-called entropic barrier. 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. The analysis of our algorithm uses properties of the entropic barrier, mixing times for hit-and-run random walks, approximation quality guarantees for the mean and covariance of a log-concave distribution, and results on inexact Newton-type methods.

Keywords: Primary: 90C25; interior point method; convex optimization; hit-and-run sampling; entropic barrier (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2021.1150 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:47:y:2022:i:1:p:779-811

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().