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

References

• [1] Abernethy J, Hazan E (2016) Faster convex optimization: Simulated annealing with an efficient universal barrier. Balcan MF, Weinberger KQ, eds. Proc. 33rd Internat. Conf. on Machine Learning, vol. 48 (PMLR), 2520–2528.Google Scholar
• [2] Badenbroek R, de Klerk E (2019) Simulated annealing with hit-and-run for convex optimization: rigorous complexity analysis and practical perspectives for copositive programming. Preprint, submitted July 4, https://arxiv.org/abs/1907.02368.Google Scholar
• [3] Bélisle CJ, Romeijn HE, Smith RL (1993) Hit-and-run algorithms for generating multivariate distributions. Math. Oper. Res. 18(2):255–266.Link, Google Scholar
• [4] Boyd S, Vandenberghe L (2004) Convex Optimization (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [5] Bubeck S, Eldan R (2018) The entropic barrier: Exponential families, log-concave geometry, and self-concordance. Math. Oper. Res. 44(1):264–276.Google Scholar
• [6] de Klerk E, Glineur F, Taylor A (2020) Worst-case convergence analysis of iexact gradient and Newton methods through semidefinite programming performance estimation. SIAM J. Optim. 30(3):2053–2082.Crossref, Google Scholar
• [7] Güler O (1996) Barrier functions in interior point methods. Math. Oper. Res. 21(4):860–885.Link, Google Scholar
• [8] Kalai AT, Vempala S (2006) Simulated annealing for convex optimization. Math. Oper. Res. 31(2):253–266.Link, Google Scholar
• [9] Kannan R, Lovász L, Simonovits M (1995) Isoperimetric problems for convex bodies and a localization lemma. Discrete Comput. Geometry 13(1):541–559.Crossref, Google Scholar
• [10] Kannan R, Lovász L, Simonovits M (1997) Random walks and an O*(n5) volume algorithm for convex bodies. Random Structures Algorithms 11(1):1–50.Crossref, Google Scholar
• [11] Kaufman DE, Smith RL (1998) Direction choice for accelerated convergence in hit-and-run sampling. Oper. Res. 46(1):84–95.Link, Google Scholar
• [12] Kirkpatrick S, Gelatt CD, Vecchi MP (1983) Optimization by simulated annealing. Sci. 220(4598):671–680.Crossref, Google Scholar
• [13] Klartag B (2006) On convex perturbations with a bounded isotropic constant. Geometric Functional Analysis GAFA 16(6):1274–1290.Crossref, Google Scholar
• [14] Lee YT, Sidford A, Vempala SS (2018) Efficient convex optimization with membership oracles. Proc. Machine Learning Res. 75:1292–1294.Google Scholar
• [15] Lee YT, Sidford A, Wong SCW (2015) A faster cutting plane method and its implications for combinatorial and convex optimization. Proc. IEEE 56th Annual Sympos. on Foundations of Computer Science (IEEE, New York), 1049–1065.Google Scholar
• [16] Levin DA, Peres Y, Wilmer EL (2017) Markov Chains and Mixing Times, vol. 107 (American Mathematical Society, Providence, RI).Crossref, Google Scholar
• [17] Lovász L, Vempala S (2006) Fast algorithms for logconcave functions: Sampling, rounding, integration and optimization. Proc. 47th Annual IEEE Sympos. on Foundations of Computer Science (IEEE, New York), 57–68.Google Scholar
• [18] Lovász L, Vempala S (2006) Hit-and-run from a corner. SIAM J. Comput. 35(4):985–1005.Crossref, Google Scholar
• [19] Lovász L, Vempala S (2006) Simulated annealing in convex bodies and an O*(n4) volume algorithm. J. Comput. System Sci. 72(2):392–417.Crossref, Google Scholar
• [20] Lovász L, Vempala S (2007) The geometry of logconcave functions and sampling algorithms. Random Structures Algorithms 30(3):307–358.Crossref, Google Scholar
• [21] MOSEK ApS (2017) The MOSEK optimization toolbox for MATLAB manual. Version 8.1. http://docs.mosek.com/8.1/toolbox/index.html.Google Scholar
• [22] Nesterov Y, Nemirovskii A (1994) Interior-Point Polynomial Algorithms in Convex Programming (SIAM, Philadelphia).Crossref, Google Scholar
• [23] Papp D, Yildiz S (2018) alfonso: ALgorithm FOr Non-Symmetric Optimization. https://github.com/dpapp-github/alfonso.Google Scholar
• [24] Papp D, Yildiz S (2018) On “a homogeneous interior-point algorithm for non-symmetric convex conic optimization.” Preprint, revised June 14, https://arxiv.org/abs/1712.00492v2.Google Scholar
• [25] Renegar J (2001) A Mathematical View of Interior-Point Methods in Convex Optimization (SIAM, Philadelphia).Crossref, Google Scholar
• [26] Skajaa A, Ye Y (2015) A homogeneous interior-point algorithm for nonsymmetric convex conic optimization. Math. Programming 150(2):391–422.Crossref, Google Scholar
• [27] Smith RL (1984) Efficient Monte Carlo procedures for generating points uniformly distributed over bounded regions. Oper. Res. 32(6):1296–1308.Link, Google Scholar
• [28] Sturm JF (1999) Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optim. Methods Software 11(1-4):625–653.Crossref, Google Scholar
• [29] Toh KC, Todd MJ, Tütüncü RH (1999) SDPT3: A MATLAB software package for semidefinite programming, version 1.3. Optim. Methods Software 11(1-4):545–581.Crossref, Google Scholar
• [30] Wright MH (2005) The interior-point revolution in optimization: History, recent developments, and lasting consequences. Bull. Amer. Math. Soc. (New Series) 42(1):39–56.Crossref, Google Scholar