Uncertain standard quadratic optimization under distributional assumptions: a chance-constrained epigraphic approach

Daniel de Vicente; Immanuel M. Bomze

REVIEW 2 major objections 4 minor 19 references

Uncertain standard quadratic optimization under distributional assumptions: a chance-constrained epigraphic approach

T0 review · 2 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A chance-constrained formulation of the uncertain standard quadratic problem reduces, under a location-scale condition, to an ordinary deterministic StQP.

desk verdict Main equivalence is correct and clean, but a localized sqrt(2) error in the GOE verification of Property 5 needs fixing before the bridge from the model to Theorem 7 is sound. read the letter →

arxiv 2411.14884 v3 pith:EKISSDT6 submitted 2024-11-22 math.OC

Immanuel M. Bomze , Daniel de Vicente This is my paper · ORCID

classification math.OC MSC 90C2090C1590C26

keywords standardquadraticoptimizationchance-constrainedepigraphicformulationGaussianOrthogonalEnsemblerandommatricesvalue-at-riskrobustlocation-scaledistributions

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper studies standard quadratic optimization (minimizing $x^\top Q x$ over the simplex) when the matrix $Q$ is random with known distribution. It introduces a chance-constrained epigraphic version: find the smallest $t$ such that, with probability at least $\alpha$, the realized quadratic form $x^\top \tilde Q x$ does not exceed $t$. The central result is that if the random matrix satisfies a location-scale property for every simplex point, then this stochastic problem is exactly an ordinary StQP with data matrix $Q = M + F^{-1}(\alpha) S$. This matters because the decision-maker stays in the same problem class and can use existing StQP algorithms; for Gaussian-orthogonal-ensemble perturbations the matrix becomes explicit, and moderate confidence levels give solutions less conservative than a robust box approach.

What carries the argument

The machinery is the epigraphic variable $t$ combined with Property 5, a location-scale assumption on the uncertain quadratic forms. Property 5 asserts that there are fixed symmetric matrices $M$ and $S$, with $x^\top S x > 0$ on $\Delta$, and a continuous, strictly increasing cdf $F$ such that $P[x^\top \tilde Q x \le t] = F((t - x^\top M x)/(x^\top S x))$ for every $x\in\Delta$. Because $F$ is invertible at $\alpha$, the chance constraint is equivalent to $x^\top M x + F^{-1}(\alpha)x^\top S x \le t$, so the whole CCEStQP reduces to $\min_{x\in\Delta} x^\top [M + F^{-1}(\alpha)S] x$. The GOE perturbation model and shifted Wishart model are shown to satisfy Property 5, giving explicit $M$, $S$, and $F$.

What would settle it

Take a random symmetric matrix whose entries are independent but non-Gaussian, for instance shifted exponential entries, and check whether the empirical distributions of $x^\top \tilde Q x$ for different $x$ are all of the form $F((t - x^\top M x)/(x^\top S x))$ with fixed $M$, $S$, $F$. If they are not, solve the CCEStQP by sampling and compare its value with $\min_{x\in\Delta} x^\top(M + F^{-1}(\alpha)S)x$; a mismatch for some $\alpha$ would show the deterministic reduction relies on Property 5 and does not hold generally.

Watch

Extended reading notes

Core claim

On its own terms, the paper claims Theorem 7: for a random symmetric matrix $\tilde Q$ with distribution $P$ obeying Property 5, the CCEStQP value equals $\min_{x\in\Delta} x^\top Q x$ with $Q = M + F^{-1}(\alpha) S$. The proof inverts the strictly increasing cdf $F$, turning the chance constraint $P[x^\top \tilde Q x \le t] \ge \alpha$ into the deterministic quadratic inequality $x^\top Q x \le t$, so the epigraphic lift collapses to a deterministic StQP. For the GOE perturbation model $\tilde Q = Q^{(\mathrm{nom})} + \beta \tilde G$, this gives $Q^{(\mathrm{cce})} = Q^{(\mathrm{nom})} + \sqrt{2}\beta \Phi^{-1}(\alpha) I_n$, and the solution coincides with the robust StQP over a Frobenius ball of radius $\sqrt{2}\beta \Phi^{-1}(\alpha)$. The paper also characterizes when the reformulation becomes convex (Proposition 10) and reports numerical experiments in which the chance-constrained solutions achieve near-$\alpha$ empirical coverage and, for $\alpha$ below about 0.72 to 0.79, are less conservative than box-robust solutions.

Load-bearing premise

The result rests on Property 5: every quadratic form $x^\top \tilde Q x$ must follow the same baseline distribution after shifting by $x^\top M x$ and scaling by $x^\top S x$, with a single cdf $F$ valid for all $x$ in the simplex.

Editorial extensions

If this is right

A decision-maker facing an uncertain StQP whose distribution satisfies Property 5 can solve one deterministic StQP; the chance constraint adds no new computational complexity.
In the GOE perturbation model, raising the confidence level $\alpha$ only shifts the data matrix by $\sqrt{2}\beta \Phi^{-1}(\alpha) I_n$, and the problem becomes convex once $\alpha \ge \Phi(|\lambda_{\min}|/(\sqrt{2}\beta))$ even when the nominal matrix is indefinite.
The CCEStQP for GOE perturbations coincides with the robust StQP over a Frobenius-ball uncertainty set of radius $\sqrt{2}\beta \Phi^{-1}(\alpha)$, giving a probabilistic meaning to that robust radius.
Numerical experiments show the chance-constrained solutions attain empirical coverage close to $\alpha$ and are less conservative than box-robust solutions for $\alpha \le 0.72$ in the nominal comparison and $\alpha \le 0.79$ against realized instances.
For shifted Wishart models the deterministic reformulation still applies, but the paper argues the robust-ball characterization does not carry over because the location matrix is negative.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The mechanism suggests a general template: whenever a random objective is affine in the random parameter and its distribution at each decision point is location-scale with parameters that are themselves quadratic in $x$, a chance constraint can be collapsed to a deterministic problem; this may extend to other elliptically contoured ensembles.
Since only $F^{-1}(\alpha)$ enters the reformulation, the whole trade-off curve in $\alpha$ can be traced by a one-dimensional root find on $F$, and Proposition 10's threshold provides a simple convexity certificate for tuning $\alpha$ adaptively.
A testable extension would construct synthetic distributions that satisfy Property 5 but are neither GOE nor Wishart, and verify whether the deterministic formula holds exactly or only approximately.
Conversely, because Property 5 fails for general distributions, one could perturb the assumed distribution and measure how much the optimal value and empirical coverage of the CCE solution degrade, quantifying the price of the location-scale assumption.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Dear colleague,

The paper's main equivalence (Theorem 7) is correct and the proof is complete. The CCEStQP model is new for this problem class, and the reduction to a deterministic StQP under a location-scale property is a legitimate contribution. The link to Frobenius-ball robustness via Bomze et al. is a nice touch, and the numerical experiments do verify that the empirical probability tracks alpha, with a sensible comparison against a robust formulation.

The stress-test note is right. Proposition 4 states the GOE scale as S = beta I_n, but the variance of x^T beta G x is 2 beta^2 ||x||^4, so the scale should be sqrt(2) beta I_n. The paper itself uses sqrt(2) beta in Corollary 8 and Theorem 9, so the proposition is internally inconsistent with the rest of the paper. As written, a reader who follows Proposition 4 literally would obtain a deterministic matrix off by sqrt(2). This is a load-bearing step in the bridge from the motivating model to Theorem 7, but it is a one-line fix. The conditional statement in Theorem 7 stands.

Two smaller soft spots. The phrase "apparently for the first time" is not supported by a literature search; a quick check would verify it or soften it. And the numerical experiments are not packaged with code or data, which limits reproducibility. Both are minor.

None of this is fatal. Theorem 7 is a solid conditional result, and the paper is written in the same problem class it studies, which is elegant. The paper deserves a serious referee; a referee should ask for the Proposition 4 correction and a cleaner novelty claim, but not much else.

For whom: anyone working on uncertain quadratic optimization, robust StQP, or chance-constrained optimization. I would cite Theorem 7 after the scale issue is fixed and would bring the paper to a reading group, mostly to discuss the location-scale property and its limits.

Referee Report

2 major / 4 minor

Summary. The paper proposes a chance-constrained epigraphic reformulation of standard quadratic optimization problems with a random data matrix. For a fixed decision vector x, the objective x^T Q̃ x is a random variable, and the authors minimize its value-at-risk at confidence level α subject to x lying in the standard simplex. The central mathematical contribution is Theorem 7, which shows that if the random quadratic forms satisfy a location-scale property (Property 5) with location x^T M x and scale x^T S x, then the chance-constrained epigraphic problem is exactly equivalent to the deterministic StQP with matrix M + F^{-1}(α) S. The paper verifies Property 5 for two families of indefinite random matrices: the GOE perturbation model and the shifted Wishart model. It then specializes the deterministic reformulation to the GOE case, relates it to a Frobenius-ball robust counterpart, and reports numerical experiments comparing the chance-constrained solutions with nominal and robust solutions.

Significance. If the stated results hold, the paper provides a clean and useful observation: under a distributional location-scale assumption, an uncertain StQP with chance constraints can be solved by a single deterministic StQP in the same problem class. The proof of Theorem 7 is a direct and sound quantile-inversion argument, and the numerical experiments provide a falsifiable check of the GOE model by comparing empirical coverage frequencies with the nominal confidence level. The connection with Frobenius-ball robust optimization is also instructive. The main weakness is that the GOE verification in Proposition 4 contains a scale-factor error: the variance calculation and the claimed scale matrix S = β I_n are inconsistent, although Corollary 8 and Theorem 9 use the correct factor √2 β. This error is local and easily corrected, but it is load-bearing for the paper's validation of Property 5 for the flagship GOE model.

major comments (2)

[§2.2, Proposition 4] The GOE case of Proposition 4 is internally inconsistent. The proof correctly states that x^T eG x ∼ N(0, 2||x||^4) and hence, for eQ = Q(nom) + β eG, that x^T eQ x has standard deviation √2 β ||x||^2. But the proof then sets S = β I_n, which would give, under Property 5, the quantile shift β Φ^{-1}(α)||x||^2. The correct scale matrix is S = √2 β I_n, yielding the deterministic matrix Q = Q(nom) + √2 β Φ^{-1}(α) I_n. This is exactly the formula used in Corollary 8 and Theorem 9, which confirms the intended statement. As written, however, Proposition 4 cannot be combined with Theorem 7 to obtain Corollary 8; a reader following the proof literally would obtain the wrong factor. Please correct the scale matrix in Proposition 4 and its proof, and state explicitly that β > 0 there.
[§4.3] The empirical coverage check is reported only as a rough approximation (# counts divided by 100 ≈ α, with one interval cited for α = 0.70). Since this is the main numerical validation of the chance-constrained model, the paper should report the full range over all α or a table of empirical frequencies, and ideally a confidence interval for the binomial proportion. This is not a correctness issue for Theorem 7, but it would make the experimental claim more precise.

minor comments (4)

[§2.2(i)] The formula for the GOE perturbation generation appears to contain a typographical error: 'eQ := Q(nom) + β√2 (eR + eR⊤)' should presumably read 'eQ := Q(nom) + (β/√2)(eR + eR⊤)' to match Definition 2 and Corollary 8.
[Abstract and introduction] There are several small language slips: 'ranging portfolio optimization' should be 'ranging from portfolio optimization', 'suppossed' should be 'supposed', and 'familiar interpretation familiar' should be 'familiar interpretation'.
[Corollary 8] The statement should explicitly assume β > 0 (as in Proposition 4) because the formula σ(x) = √2 β x^T I_n x is otherwise ambiguous for negative β.
[Theorem 9] The proof relies on [6, Theorem 4] without stating the mapping of notation. A brief sentence explaining how C = I, the definition of L, and the sign convention in [6] translate to the current uncertainty set would improve readability.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: Theorem 7 is a direct conditional equivalence from an explicit location-scale assumption, with no fitted parameter renamed as prediction.

full rationale

The central result, Theorem 7, is a conditional statement: if Property 5 holds with given (F, M, S), then the chance constraint P[x^T Q̃x ≤ t] ≥ α is, by definition of a quantile, equivalent to x^T(M + F^{-1}(α)S)x ≤ t. The quantile F^{-1}(α) is not fitted to data; it is a fixed parameter of the assumed distribution, and the theorem is an algebraic reformulation rather than a prediction forced by an earlier fit. Proposition 4 verifies Property 5 for the GOE and shifted Wishart models by substituting explicit (F, M, S) obtained from known distributional facts, so it provides independent content rather than restating the conclusion. The only self-citation is the use of [6, Theorem 4 and Remark 5] in Theorem 9 to connect the GOE CCEStQP to a Frobenius-ball robust StQP; that is a secondary interpretation result, the cited theorem is a published peer-reviewed statement, and the main equivalence in Corollary 8 is already established without it. No step reduces to its own input by construction. I note separately that Proposition 4 sets S = β I_n for the GOE while Corollary 8 correctly uses scale √2 β I_n; this is a local scaling error, not a circularity, and it does not affect the conditional validity of Theorem 7.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central theorem relies on Property 5 as a domain assumption, plus standard properties of normal and gamma distributions. No parameters are fitted to data; α and β are user-provided inputs. No new physical or mathematical entities are introduced.

assumptions (4)

domain assumption Property 5: location-scale form of quadratic form distributions
Central assumption; holds for GOE and shifted Wishart models, but is not true for general distributions.
standard math Properties of normal and gamma distributions for GOE and Wishart quadratic forms
Used to derive location-scale representations in Proposition 4.
standard math Known equivalence between chance constraints and quantile (VaR) constraints
Used in defining CCEStQP and in Theorem 7's proof.
domain assumption Robust StQP counterpart from Bomze et al. [6, Theorem 4]
External result used in Theorem 9 to connect to Frobenius ball robustness.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Uncertain standard quadratic optimization under distributional assumptions: a chance-constrained epigraphic approach." pith.science (2026). https://pith.science/paper/EKISSDT6

@misc{pith2026241114884,
  author       = {Pith},
  title        = {Pith review of: Uncertain standard quadratic optimization under distributional assumptions: a chance-constrained epigraphic approach},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/EKISSDT6}},
  note         = {Machine review of arXiv:2411.14884}
}

read the original abstract

The standard quadratic optimization problem (StQP) consists of minimizing a quadratic form over the standard simplex. Without convexity or concavity of the quadratic form, the StQP is NP-hard. This problem has many relevant real-life applications ranging portfolio optimization to pairwise clustering and replicator dynamics. Sometimes, the data matrix is uncertain. We investigate models where the distribution of the data matrix is known but where both the StQP after realization of the data matrix and the here-and-now problem are indefinite. We test the performance of a chance-constrained epigraphic StQP to the uncertain StQP.

Figures

Figures reproduced from arXiv: 2411.14884 by the authors.

**Figure 3.** |ℓ (nom) cce,α − ℓ (nom)| vs |ℓ (nom) rob − ℓ (nom)| [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

19 extracted references · 17 canonical work pages

[1]

Aizenman, R

M. Aizenman, R. Peled, J. Schenker, M. Shamis, and S. Sodin. Matrix regularizing effects of Gaussian perturbations. Communications in Contemporary Mathematics , 19(3):1750028, 2017

work page 2017
[2]

Ben-Tal, L

A. Ben-Tal, L. El Ghaoui, and A. Nemirovski. Robust optimization . Princeton University Press, 2009

work page 2009
[3]

Bertsimas, D

D. Bertsimas, D. B. Brown, and C. Caramanis. Theory and applications of robust optimization. SIAM review, 53(3):464–501, 2011

2011
[4]

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

work page 1998
[5]

I. M. Bomze, M. Gabl, F. Maggioni, and G. C. Pflug. Two-stage stochastic standard quadratic optimization. European Journal of Operational Research, 299(1):21–34, 2022

work page 2022
[6]

I. M. Bomze, M. Kahr, and M. Leitner. Trust your data or not – StQP remains StQP: Community Detection via Robust Standard Quadratic Optimization. Mathematics of Operations Research , 46:301–316, 2021

work page 2021
[7]

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 Research, 43(2):651–674, 2018

work page 2018
[8]

El Ghaoui, M

L. El Ghaoui, M. Oks, and F. Oustry. Worst-Case Value-At-Risk and Robust Portfolio Optimization: A Conic Programming Approach. Operations Research, 51(4):543–556, 2003

work page 2003

Show all 19 references

[9]

S. Geman. A limit theorem for the norm of random matrices. The Annals of Probability , 8(2):252– 261, 1980

1980
[10]

B. L. Gorissen, I. Yanıkoglu, and D. Den Hertog. A practical guide to robust optimization. Omega, 53:124–137, 2015

2015
[11]

J. Hull. Risk management and financial institutions, volume 733. John Wiley & Sons, Inc., Hoboken, NJ, 3 edition, 2012

2012
[12]

Larsen, H

N. Larsen, H. Mausser, and S. Uryasev. Algorithms for Optimization of Value-at-Risk. In P. M. Pardalos and V. K. Tsitsiringos, editors, Financial Engineering, E-commerce and Supply Chain , pages 19–46. Springer US, Boston, MA, 2002

2002
[13]

V. A. Marchenko and L. A. Pastur. Distribution of eigenvalues for some sets of random matrices. Mathematics of the USSR-Sbornik , 1(4):457–483, 1967

1967
[14]

Markowitz

H. Markowitz. Portfolio selection. The Journal of Finance , 7(1):77–91, 1952

1952
[15]

T. S. Motzkin and E. G. Straus. Maxima for Graphs and a New Proof of a Theorem of Tur´ an. Canadian Journal of Mathematics , 17:533–540, 1965

1965
[16]

Pavan and M

M. Pavan and M. Pelillo. Dominant sets and hierarchical clustering. In Proceedings Ninth IEEE International Conference on Computer Vision , volume 1, pages 362–369. IEEE, 2003. 11

2003
[17]

Shaked-Monderer and A

N. Shaked-Monderer and A. Berman. Copositive and completely positive matrices . World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ, 2021

2021
[18]

Shapiro and K

B. Shapiro and K. Zarembo. Level crossing in random matrices: I. Random perturbation of a fixed matrix. Journal of Physics A: Mathematical and Theoretical , 50(4):045201, 2016

2016
[19]

J. W. Silverstein. The smallest eigenvalue of a large dimensional Wishart matrix. The Annals of Probability, 13(4):1364–1368, 1985. 12

1985

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.

[1] [1]

Aizenman, R

M. Aizenman, R. Peled, J. Schenker, M. Shamis, and S. Sodin. Matrix regularizing effects of Gaussian perturbations. Communications in Contemporary Mathematics , 19(3):1750028, 2017

work page 2017

[2] [2]

Ben-Tal, L

A. Ben-Tal, L. El Ghaoui, and A. Nemirovski. Robust optimization . Princeton University Press, 2009

work page 2009

[3] [3]

Bertsimas, D

D. Bertsimas, D. B. Brown, and C. Caramanis. Theory and applications of robust optimization. SIAM review, 53(3):464–501, 2011

2011

[4] [4]

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

work page 1998

[5] [5]

I. M. Bomze, M. Gabl, F. Maggioni, and G. C. Pflug. Two-stage stochastic standard quadratic optimization. European Journal of Operational Research, 299(1):21–34, 2022

work page 2022

[6] [6]

I. M. Bomze, M. Kahr, and M. Leitner. Trust your data or not – StQP remains StQP: Community Detection via Robust Standard Quadratic Optimization. Mathematics of Operations Research , 46:301–316, 2021

work page 2021

[7] [7]

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 Research, 43(2):651–674, 2018

work page 2018

[8] [8]

El Ghaoui, M

L. El Ghaoui, M. Oks, and F. Oustry. Worst-Case Value-At-Risk and Robust Portfolio Optimization: A Conic Programming Approach. Operations Research, 51(4):543–556, 2003

work page 2003