pith. sign in

arxiv: 2605.18620 · v1 · pith:6RNH3ZY2new · submitted 2026-05-18 · 🧮 math.OC

Singleton Optimality in Standard Quadratic Programs with the GOE

Xin Chen This is my paper

Pith reviewed 2026-05-20 08:30 UTC · model grok-4.3

classification 🧮 math.OC
keywords standard quadratic programmingGaussian Orthogonal Ensemblesimplex optimizationsupport sizeasymptotic probabilityglobal optimalityrandom matricesboundary layer estimates
0
0 comments X

The pith

For GOE quadratic programs over the simplex the probability that the global optimum has support larger than one is asymptotically 2 sqrt(2 pi) sqrt(log n) over n.

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

The paper shows that when the objective matrix of a standard quadratic program over the simplex is drawn from the Gaussian Orthogonal Ensemble, the support size kappa_n of the almost surely unique global optimizer satisfies Prob(kappa_n greater than 1) asymptotically equal to 2 sqrt(2 pi) times sqrt(log n) divided by n. This implies that the vertex with the smallest diagonal entry is the global optimum with probability tending to one, up to an explicit first-order correction term. A reader would care because the result gives precise control over the typical location of optima in random quadratic programs that appear in combinatorial optimization and related fields.

Core claim

We prove Prob(kappa_n greater than 1) is asymptotically 2 sqrt(2 pi) sqrt(log n) over n, where kappa_n is the support size of the global optimizer. The argument uses an exact two-coordinate condition for when an edge can improve the objective, combined with a product formula obtained by conditioning on the order statistics of the diagonal entries. Boundary-layer estimates isolate the leading contribution from two-support configurations and show that supports of size three or larger contribute negligibly.

What carries the argument

Boundary-layer estimates combined with a product formula from conditioning on diagonal order statistics that isolate the leading probability contribution from two-coordinate edge improvements.

If this is right

  • The vertex with the minimal diagonal entry solves the problem with probability one minus a term of order sqrt(log n) over n.
  • Supports of size three or more become vanishingly rare for large n under the GOE model.
  • Optimality can be verified in practice by checking only pairwise edge improvements against the candidate vertex.

Where Pith is reading between the lines

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

  • The same conditioning-plus-boundary-layer technique may apply to other random-matrix ensembles with comparable tail behavior on the off-diagonals.
  • For very large n the result suggests that simple vertex selection followed by a cheap pairwise check suffices for near-optimal solutions in random quadratic programs.
  • The explicit rate could be used to calibrate the sample size needed for Monte-Carlo studies of quadratic programs that rely on the singleton solution.

Load-bearing premise

The boundary-layer estimates correctly isolate the leading contribution from two-support cases while showing that all higher-support configurations remain negligible at the same order.

What would settle it

Generate many independent GOE matrices of size n equals 500 or larger, solve the quadratic program exactly for each, and check whether the empirical fraction of instances with optimal support size greater than one matches the predicted asymptotic within sampling error.

read the original abstract

We study the standard quadratic optimization problem over the simplex when the objective matrix is drawn from the Gaussian Orthogonal Ensemble (GOE). Let \(\kappa_n\) denote the support size of the almost surely unique global optimizer. We prove \[ \Prob(\kappa_n>1)\sim 2\sqrt{2\pi}\,\frac{\sqrt{\log n}}{n}. \] The proof combines an exact two-coordinate condition for edge improvement with a product formula obtained by conditioning on the diagonal order statistics. Boundary-layer estimates identify the leading contribution and show that supports of size at least three are negligible. Consequently, the minimum-diagonal vertex is globally optimal with probability tending to one, with an explicit first-order correction.

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 analyzes the standard quadratic program over the simplex with a GOE objective matrix. It proves that the probability the (almost surely unique) global optimizer has support size κ_n > 1 satisfies Prob(κ_n > 1) ∼ 2√(2π) √(log n)/n. The argument proceeds by deriving an exact two-coordinate edge-improvement condition, conditioning on the ordered diagonal entries to obtain a product formula, and applying boundary-layer estimates to show that configurations with support size at least three contribute only lower-order terms. As a consequence, the minimum-diagonal vertex is globally optimal with probability tending to one, up to the stated first-order correction.

Significance. If the claimed asymptotic holds, the result supplies a sharp, explicit characterization of the typical optimality of vertices in random quadratic programs on the simplex. This has direct implications for the design and analysis of algorithms that rely on vertex or low-support solutions, and the conditioning-plus-boundary-layer technique may extend to other random optimization problems on polytopes. The derivation of a parameter-free leading constant from the GOE law is a notable technical strength.

major comments (1)
  1. [Boundary-layer estimates (proof of the asymptotic)] The central claim that Prob(support size ≥ 3) = o(√(log n)/n) rests on the boundary-layer estimates that declare higher-support configurations negligible after conditioning on the three smallest diagonals lying within O(1/√(log n)) of the minimum. A more explicit bound on the measure of off-diagonal realizations for which the KKT conditions hold on a 3-face (under this conditioning) would strengthen the argument; without it, it remains possible that the 3×3 principal submatrix contributes at the same order.
minor comments (2)
  1. [Introduction / proof outline] The abstract refers to an 'exact two-coordinate condition for edge improvement'; a brief statement of this condition (perhaps as a displayed equation) would improve readability before the conditioning argument begins.
  2. [Conditioning on diagonal order statistics] Notation for the ordered diagonal statistics and the scaling of the boundary layer should be introduced with explicit definitions (e.g., the precise meaning of 'O(1/√(log n))' in the conditioning event) to avoid ambiguity when the product formula is stated.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and constructive feedback on our manuscript. We address the major comment below.

read point-by-point responses

  1. Referee: The central claim that Prob(support size ≥ 3) = o(√(log n)/n) rests on the boundary-layer estimates that declare higher-support configurations negligible after conditioning on the three smallest diagonals lying within O(1/√(log n)) of the minimum. A more explicit bound on the measure of off-diagonal realizations for which the KKT conditions hold on a 3-face (under this conditioning) would strengthen the argument; without it, it remains possible that the 3×3 principal submatrix contributes at the same order.

    Authors: We appreciate the referee's suggestion to strengthen the boundary-layer analysis with a more explicit bound. The estimates in Section 4 of the manuscript already control the contribution from support size ≥3 by showing that, after conditioning on the three smallest diagonals lying in an O(1/√(log n)) neighborhood of the global minimum, the GOE off-diagonal entries make the KKT conditions on any 3-face hold only on a set whose measure integrates to a lower-order term. To address the concern directly and improve clarity, we will revise the manuscript to include an explicit upper bound on the (conditional) measure of off-diagonal realizations satisfying the 3-face KKT conditions; this bound is O((log n)^{-1}) and confirms the total contribution remains o(√(log n)/n). revision: yes

Circularity Check

0 steps flagged

No circularity: derivation uses independent conditioning and estimates on GOE order statistics

full rationale

The paper establishes the asymptotic Prob(κ_n>1)∼2√(2π)√(log n)/n by combining an exact two-coordinate edge-improvement condition with a product formula obtained via conditioning on the diagonal order statistics of the GOE matrix, then applying boundary-layer estimates to control the contribution of supports of size ≥3. These steps are explicit probabilistic calculations and tail bounds that operate directly on the joint law of the GOE entries and do not reduce to any fitted parameter, self-definition, or load-bearing self-citation. The central claim therefore remains independent of its own outputs and is self-contained against the stated GOE model.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Based solely on the abstract, the paper relies on standard properties of the GOE and the simplex but introduces no new free parameters, axioms, or invented entities beyond the usual random-matrix setup.

pith-pipeline@v0.9.0 · 5631 in / 1273 out tokens · 63946 ms · 2026-05-20T08:30:26.509702+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

20 extracted references · 20 canonical work pages · 1 internal anchor

  1. [1]

    Abramowitz and I

    M. Abramowitz and I. A. Stegun.Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables. National Bureau of Standards, Washington, DC, 1964

    work page 1964

  2. [2]

    Bai and J

    Z. Bai and J. W. Silverstein.Spectral Analysis of Large Dimensional Random Matrices. 2nd ed., Springer, New York, 2010. 40

    work page 2010

  3. [3]

    Ben Arous and A

    G. Ben Arous and A. Guionnet. The spectrum of heavy tailed random matrices.Communications in Mathematical Physics278 (2008), 715–751

    work page 2008

  4. [4]

    Billingsley.Probability and Measure

    P. Billingsley.Probability and Measure. 3rd ed., Wiley, New York, 1995

    work page 1995

  5. [5]

    I. M. Bomze. On standard quadratic optimization problems.Journal of Global Optimization 13 (1998), 369–387

    work page 1998

  6. [6]

    I. M. Bomze and E. de Klerk. Solving standard quadratic optimization problems via linear, semidefinite and copositive programming.Journal of Global Optimization24 (2002), 163–185

    work page 2002

  7. [7]

    I. M. Bomze and D. de Vicente. Uncertain standard quadratic optimization under distributional assumptions: a chance-constrained epigraphic approach.Operations Research Letters62 (2025), Article 107310

    work page 2025

  8. [8]

    I. M. Bomze, B. Peng, Y. Qiu, and E. A. Yildirim. Tighter yet more tractable relaxations and nontrivial instance generation for sparse standard quadratic optimization.Mathematical Programming Computation17 (2025), 617–651

    work page 2025

  9. [9]

    I. M. Bomze, W. Schachinger, and R. Ullrich. The complexity of simple models: A study of worst and typical hard cases for the standard quadratic optimization problem.Mathematics of Operations Research43 (2018), 651–674

    work page 2018

  10. [10]

    Bourgade, L

    P. Bourgade, L. Erdos, H.-T. Yau, and J. Yin. Universality for a class of random band matrices. Advances in Theoretical and Mathematical Physics21 (2017), 739–800

    work page 2017

  11. [11]

    X. Chen. Exactness of the DNN relaxation for random standard quadratic programs. arXiv preprint arXiv:2605.11456, 2026

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  12. [12]

    Chen and J

    X. Chen and J. Peng. New analysis on sparse solutions to random standard quadratic optimization problems and extensions.Mathematics of Operations Research40 (2015), 725–738

    work page 2015

  13. [13]

    X. Chen, J. Peng, and S. Zhang. Sparse solutions to random standard quadratic optimization problems.Mathematical Programming141 (2013), 273–293

    work page 2013

  14. [14]

    Chen and B

    X. Chen and B. Pittel. On sparsity of the solution to a random quadratic optimization problem. Mathematical Programming186 (2021), 309–336

    work page 2021

  15. [15]

    H. A. David and H. N. Nagaraja.Order Statistics. 3rd ed., Wiley, Hoboken, NJ, 2003

    work page 2003

  16. [16]

    N. G. de Bruijn.Asymptotic Methods in Analysis. Dover, New York, 1981

    work page 1981

  17. [17]

    Feller.An Introduction to Probability Theory and Its Applications, Vol

    W. Feller.An Introduction to Probability Theory and Its Applications, Vol. 1. 3rd ed., Wiley, New York, 1968

    work page 1968

  18. [18]

    M. R. Leadbetter, G. Lindgren, and H. Rootzen.Extremes and Related Properties of Random Sequences and Processes. Springer, New York, 1983

    work page 1983

  19. [19]

    M. L. Mehta.Random Matrices. 3rd ed., Elsevier/Academic Press, Amsterdam, 2004

    work page 2004

  20. [20]

    Tao.Topics in Random Matrix Theory

    T. Tao.Topics in Random Matrix Theory. Graduate Studies in Mathematics, Vol. 132, American Mathematical Society, Providence, RI, 2012. 41

    work page 2012