pith. sign in

arxiv: 1907.02368 · v1 · pith:7HEZJ7T5new · submitted 2019-07-04 · 🧮 math.OC

Simulated annealing with hit-and-run for convex optimization: rigorous complexity analysis and practical perspectives for copositive programming

Riley Badenbroek , Etienne de Klerk This is my paper

Pith reviewed 2026-05-25 09:18 UTC · model grok-4.3

classification 🧮 math.OC
keywords simulated annealinghit-and-run samplingconvex optimizationcopositive programmingmembership oraclepolynomial time complexitytemperature schedule
0
0 comments X

The pith

Simulated annealing with hit-and-run returns near-optimal solutions in polynomial time for convex problems using only a membership oracle.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper analyzes the simulated annealing algorithm originally proposed by Kalai and Vempala for convex optimization, incorporating the temperature update rule from Abernethy and Hazan. It proves that this method, which relies solely on a membership oracle for the feasible set, produces a near-optimal solution with high probability after a number of steps that is polynomial in the problem size. A sympathetic reader would care because this provides a theoretical foundation for applying the method to difficult convex programs, such as those arising in copositive programming, where direct access to the feasible set may not be available. The authors further suggest modifications to enhance practical performance and demonstrate them on numerical examples.

Core claim

The simulated annealing algorithm with hit-and-run sampling, equipped with the Abernethy-Hazan temperature schedule, returns a solution that is near-optimal with high probability and does so in polynomial time, when the feasible set is accessed only through a membership oracle.

What carries the argument

The hit-and-run sampler inside the simulated annealing loop combined with the specific temperature update rule, which together enable the rigorous polynomial-time bound.

If this is right

  • The algorithm applies to any convex feasible set that can be queried via membership oracle.
  • It yields a polynomial-time randomized algorithm for finding near-optimal solutions in copositive programming.
  • Practical modifications to the basic method can improve runtime on test instances from copositive programming.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the membership oracle model holds, the approach could be adapted to other oracles like separation oracles in convex optimization.
  • The numerical results on copositive programs indicate potential competitiveness with existing solvers in practice, though this requires further comparison.

Load-bearing premise

The polynomial-time guarantee holds only when the temperature is updated exactly according to the rule proposed by Abernethy and Hazan and the feasible set is accessed exclusively via membership queries.

What would settle it

Finding a convex body and objective where the algorithm requires super-polynomial steps to reach near-optimality despite using the specified temperature rule and membership oracle would disprove the claim.

Figures

Figures reproduced from arXiv: 1907.02368 by Etienne de Klerk, Riley Badenbroek.

Figure 1
Figure 1. Figure 1: Effect of sample size N and walk length ℓ on quality of uniform covariance approximation One major conclusion from [PITH_FULL_IMAGE:figures/full_fig_p011_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Running times required to find an approximation [PITH_FULL_IMAGE:figures/full_fig_p012_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Effect of sample size N and walk length ℓ on quality of uniform covariance matrix approximation over the hypercube in R n 5.3 Kalai-Vempala Algorithm The results from the previous two sections show that we should not hope to approximate the covariance matrix and sample mean with high accuracy in high dimensions. However, it is still insightful to verify if this is really required for Algorithm 2 to work in… view at source ↗
Figure 5
Figure 5. Figure 5: One can see that for practical sample sizes and walk length [PITH_FULL_IMAGE:figures/full_fig_p013_5.png] view at source ↗
Figure 4
Figure 4. Figure 4: Effect of sample size N and walk length ℓ on quality of uniform mean approximation 1. Use the (centered) samples generated in the previous iteration as directions for hit-and-run in the current iteration. This would eliminate the need to estimate the covariance matrix of a distribution, only to then draw samples from that same distribution. Instead, we can also draw directions directly from the centered sa… view at source ↗
Figure 5
Figure 5. Figure 5: Effect of sample size N and walk length ℓ on the final gap of Algorithm 2 objective value. We solve the problem from Section 5.3 with Algorithm 3. The results are given in [PITH_FULL_IMAGE:figures/full_fig_p015_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Effect of sample size N and walk length ℓ on the final gap of Algorithm 3 optimal solution Y of the doubly nonnegative relaxation from the completely positive cone. This is listed as an open (computational) problem by Berman et al. [4, Section 5], who note that the problem of generating such a cut has only been answered for specific structures of Y , including 5 × 5 matrices [8]. In general, such a cut cou… view at source ↗
Figure 7
Figure 7. Figure 7: Numerical approximation of hθ, H(θ)θi Bubeck and Eldan [6, Lemma 1(iii)] show that the gradient g ∗ of the entropic barrier is a bijection of Bn to R n. Therefore, ϑ = sup x∈Bn (kg ∗ x (x)k ∗ x ) 2 = sup x∈Bn hg ∗ (x), H∗ (x) −1 g ∗ (x)i = sup θ∈Rn hθ, H(θ)θi, where the final equality uses H∗ (x) −1 = H(θ(x)) (see [6, Lemma 1(iv)]). Recall that H(θ) is the covariance operator of the Boltzmann distribution … view at source ↗
read the original abstract

We give a rigorous complexity analysis of the simulated annealing algorithm by Kalai and Vempala [Math of OR 31.2 (2006): 253-266] using the type of temperature update suggested by Abernethy and Hazan [arXiv 1507.02528v2, 2015]. The algorithm only assumes a membership oracle of the feasible set, and we prove that it returns a solution in polynomial time which is near-optimal with high probability. Moreover, we propose a number of modifications to improve the practical performance of this method, and present some numerical results for test problems from copositive programming.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The paper gives a rigorous complexity analysis of the simulated annealing algorithm of Kalai and Vempala using the temperature-update rule suggested by Abernethy and Hazan. It assumes only a membership oracle for the feasible set and claims to prove that the procedure returns a near-optimal solution in polynomial time with high probability. The manuscript also proposes practical modifications to the method and reports numerical results on test problems from copositive programming.

Significance. If the claimed polynomial-time high-probability guarantee is established, the work would supply a theoretically grounded, oracle-efficient approach to approximate convex optimization that applies directly to copositive programs. The practical modifications and accompanying numerical experiments constitute an additional strength by addressing implementability.

major comments (1)
  1. [Complexity analysis (main theorem and its proof)] The central polynomial-time claim rests on transferring the Abernethy-Hazan cooling schedule to hit-and-run sampling under a pure membership oracle while preserving the conductance/isoperimetric bounds used in the Kalai-Vempala framework. No explicit re-derivation or verification of the required mixing-time or expected-hitting-time bounds for this specific combination appears in the analysis; without it the polynomial dependence on dimension cannot be confirmed.
minor comments (2)
  1. [Abstract and main theorem statement] The dependence of the running-time bound on the dimension and on the parameters of the temperature schedule should be stated explicitly (even if only in big-O notation) rather than left implicit in the citations.
  2. [Numerical experiments section] Numerical results would benefit from a clear statement of the stopping criterion used in the experiments and from reporting both success probability and wall-clock time alongside oracle counts.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the positive overall assessment and for identifying the need for greater explicitness in the complexity analysis. We address the major comment below and will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: [Complexity analysis (main theorem and its proof)] The central polynomial-time claim rests on transferring the Abernethy-Hazan cooling schedule to hit-and-run sampling under a pure membership oracle while preserving the conductance/isoperimetric bounds used in the Kalai-Vempala framework. No explicit re-derivation or verification of the required mixing-time or expected-hitting-time bounds for this specific combination appears in the analysis; without it the polynomial dependence on dimension cannot be confirmed.

    Authors: We agree that the manuscript does not contain a self-contained re-derivation of the mixing-time and hitting-time bounds for the precise combination of the Abernethy-Hazan schedule with hit-and-run under a membership oracle. The current proof sketch invokes the conductance bounds of Kalai-Vempala (which hold for any log-concave distribution generated by hit-and-run) and the per-phase step-count analysis of Abernethy-Hazan, but does not spell out why these results chain without additional factors that would destroy polynomiality. In the revised version we will insert a new subsection (approximately 1.5 pages) that (i) recalls the relevant conductance and isoperimetric lemmas from Kalai-Vempala, (ii) verifies that the membership-oracle hit-and-run walk satisfies the same geometric assumptions at every temperature, and (iii) confirms that the expected number of steps per temperature level remains polynomial under the Abernethy-Hazan schedule. This will make the polynomial dependence on dimension fully explicit. revision: yes

Circularity Check

0 steps flagged

No circularity; central bound derived from external theorems

full rationale

The paper proves a polynomial-time guarantee for simulated annealing with hit-and-run by invoking the Kalai-Vempala framework and the Abernethy-Hazan temperature schedule as external results. No step reduces a claimed prediction to a quantity defined inside the paper, no fitted parameter is relabeled as a prediction, and no self-citation chain is load-bearing. The analysis therefore remains self-contained against the cited external benchmarks rather than tautological.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Based solely on the abstract, the claim rests on the membership-oracle model and the external temperature-update rule; no free parameters, invented entities, or additional axioms are stated.

axioms (1)
  • domain assumption Feasible set is accessed exclusively via a membership oracle
    Stated explicitly in the abstract as the only information the algorithm requires.

pith-pipeline@v0.9.0 · 5638 in / 1144 out tokens · 17558 ms · 2026-05-25T09:18:26.841983+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

24 extracted references · 24 canonical work pages · 3 internal anchors

  1. [1]

    Faster Convex Optimization: Simulated Annealing with an Efficient Universal Barrier

    J. Abernethy and E. Hazan. Faster convex optimization: Simulat ed annealing with an efficient universal barrier. arXiv preprint arXiv:1507.02528 , 2015

    work page internal anchor Pith review Pith/arXiv arXiv 2015

  2. [2]

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

    R. Badenbroek and E. de Klerk. Complexity analysis of a sampling-b ased interior point method for convex optimization. arXiv preprint arXiv:1811.07677 , 2018

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  3. [3]

    C. J. B´ elisle, H. E. Romeijn, and R. L. Smith. Hit-and-run algorith ms for generating multivariate distributions. Mathematics of Operations Research , 18(2):255–266, 1993

    work page 1993

  4. [4]

    Berman, M

    A. Berman, M. Dur, and N. Shaked-Monderer. Open problems in t he theory of completely positive and copositive matrices. Electronic Journal of Linear Algebra , 29(1):46–58, 2015

    work page 2015

  5. [5]

    I. M. Bomze. Copositive optimization–recent developments and a pplications. European Journal of Operational Research, 216(3):509–520, 2012. 20

    work page 2012

  6. [6]

    Bubeck and R

    S. Bubeck and R. Eldan. The entropic barrier: Exponential familie s, log-concave geometry, and self- concordance. Mathematics of Operations Research , 44(1):264–276, 2018

    work page 2018

  7. [7]

    S. Burer. Optimizing a polyhedral-semidefinite relaxation of comple tely positive programs. Mathematical Programming Computation, 2(1):1–19, 2010

    work page 2010

  8. [8]

    Burer and H

    S. Burer and H. Dong. Separation and relaxation for cones of qu adratic forms. Mathematical Program- ming, 137(1-2):343–370, 2013

    work page 2013

  9. [9]

    de Klerk and M

    E. de Klerk and M. Laurent. Comparison of Laserre’s measure-b ased bounds for polynomial optimization to the bounds obtained by simulated annealing. Mathematics of Operations Research , 43(4):1051–1404, 2018

    work page 2018

  10. [10]

    A. T. Kalai and S. Vempala. Simulated annealing for convex optimiz ation. Mathematics of Operations Research, 31(2):253–266, 2006

    work page 2006

  11. [11]

    Y.T. Lee, A. Sidford, and S.C. Wong. A Faster Cutting Plane Meth od and its Implications for Com- binatorial and Convex Optimization. In 56th Annual Symposium on Foundations of Computer Science (FOCS 2015)

    work page 2015

  12. [12]

    Kannan, L

    R. Kannan, L. Lov´ asz, and M. Simonovits. Random walks and an O∗ (n5) volume algorithm for convex bodies. Random Structures and Algorithms , 11(1):1–50, 1997

    work page 1997

  13. [13]

    Kirkpatrick, C

    S. Kirkpatrick, C. D. Gelatt, M. P. Vecchi, et al. Optimization by s imulated annealing. Science, 220(4598):671–680, 1983

    work page 1983

  14. [14]

    D. A. Levin, Y. Peres, and E. L. Wilmer. Markov Chains and Mixing Times , volume 107. American Mathematical Society, 2017

    work page 2017

  15. [15]

    Lov´ asz and S

    L. Lov´ asz and S. Vempala. Simulated annealing in convex bodies a nd an O∗ (n4) volume algorithm. Journal of Computer and System Sciences , 72(2):392–417, 2006

    work page 2006

  16. [16]

    The MOSEK optimization toolbox for MATLAB manual

    MOSEK ApS. The MOSEK optimization toolbox for MATLAB manual. Version 8 .1., 2017

    work page 2017

  17. [17]

    K. G. Murty and S. N. Kabadi. Some NP-complete problems in quad ratic and nonlinear programming. Mathematical programming, 39(2):117–129, 1987

    work page 1987

  18. [18]

    Nesterov and A

    Y. Nesterov and A. Nemirovskii. Interior-Point Polynomial Algorithms in Convex Programmi ng. SIAM, 1994

    work page 1994

  19. [19]

    Rudelson

    M. Rudelson. Random vectors in the isotropic position. Journal of Functional Analysis , 164(1):60–72, 1999

    work page 1999

  20. [20]

    R. L. Smith. Efficient Monte Carlo procedures for generating po ints uniformly distributed over bounded regions. Operations Research, 32(6):1296–1308, 1984

    work page 1984

  21. [21]

    Tawarmalani and N

    M. Tawarmalani and N. V. Sahinidis. A polyhedral branch-and-c ut approach to global optimization. Mathematical Programming, 103(2):225–249, 2005

    work page 2005

  22. [22]

    W. Xia, J. Vera, and L. F. Zuluaga. Globally solving non-convex qu adratic programs via linear integer programming techniques. arXiv preprint arXiv:1511.02423 , 2015

    work page internal anchor Pith review Pith/arXiv arXiv 2015

  23. [23]

    B. Ycart. Extr´ emales du cˆ one des matrices de type non n´ egatif, ` a coefficients positifs ou nuls. Linear Algebra and its Applications , 48:317–330, 1982

    work page 1982

  24. [24]

    Yudin and A.S

    D. Yudin and A.S. Nemirovski, Informational complexity and effec tive methods of solution of convex extremal problems. Economics and Mathematical Methods , 12:357–369, 1976. 21

    work page 1976