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

• 成果类型: Article
• 署名作者: Badenbroek, Riley; de Klerk, Etienne
• 署名单位: Erasmus University Rotterdam - Excl Erasmus MC; Erasmus University Rotterdam; Tilburg University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2021.1150
• 发表日期: 2022
• 页码: 779-811
• 关键词: hit-and-run; logconcave functions; CONVERGENCE; algorithms; bodies

摘要

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.