Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2508.21327

Some Applications and Limitations of Convex Optimization Hierarchies for Discrete and Continuous Optimization Problems

Ghosh, Mrinalkanti

Published Aug 29, 2025• 0 citations
arXivHTMLPDF

Abstract

This thesis explores algorithmic applications and limitations of convex relaxation hierarchies for approximating some discrete and continuous optimization problems. - We show a dichotomy of approximability of constraint satisfaction problems (CSPs) by linear programming (LP) relaxations: for every CSP, the approximation obtained by a basic LP relaxation, is no weaker than the approximation obtained using relaxations given by super-constant levels of the Sherali-Adams hierarchy on instances of size $n$. - For the problem of approximating the absolute maximum of an n-variate degree-d homogeneous polynomial f with real coefficients over the unit sphere, we analyze the optimum value of the level-t sum-of-squares (SoS) SDP relaxation of the problem. Our results offer a trade-off between the approximation ratio and running time, which can take advantage of additional structure in the polynomial, such as non-negativity or sparsity of the coefficients. - We study the problem of approximating the $p \to q$-norm of a matrix $A$, and prove the first NP-hardness result for approximating norms in the hypercontractive case $1< p < q < \infty$. We also prove almost tight algorithmic results for the case when $p \geq q$ (with $2 \in [q,p]$) where constant factor approximations for the matrix norms are possible. A common theme for these results is their connection to geometry. For the discrete optimization problem of CSP, geometry appears as a crucial tool for our lower bound proof. For the problem of polynomial optimization, we show that SDPs capture and extend earlier algorithms based on diameter estimation for convex bodies. For the matrix (operator) norm problem, the definition itself is geometric in nature and embedding theorems play a crucial role in our proofs.

DOI
10.48550/arxiv.2508.21327

Related papers

Rounding Sum-of-Squares Relaxations

Boaz Barak, Jonathan A. Kelner, David Steurer

We present a general approach to rounding semidefinite programming relaxations obtained by the Sum-of-Squares method (Lasserre hierarchy). Our approach is based on using the connection between these relaxations and the Sum-of-Squares proof system to transform a *combining algorithm* -- an algorithm that maps a distribution over solutions into a (possibly weaker) solution -- into a *rounding algorithm* that maps a solution of the relaxation to a solution of the original problem. Using this approach, we obtain algorithms that yield improved results for natural variants of three well-known problems: 1) We give a quasipolynomial-time algorithm that approximates the maximum of a low degree multivariate polynomial with non-negative coefficients over the Euclidean unit sphere. Beyond being of interest in its own right, this is related to an open question in quantum information theory, and our techniques have already led to improved results in this area (Brandão and Harrow, STOC '13). 2) We give a polynomial-time algorithm that, given a d dimensional subspace of R^n that (almost) contains the characteristic function of a set of size n/k, finds a vector $v$ in the subspace satisfying $|v|_4^4 > c(k/d^{1/3}) |v|_2^2$, where $|v|_p = (E_i v_i^p)^{1/p}$. Aside from being a natural relaxation, this is also motivated by a connection to the Small Set Expansion problem shown by Barak et al. (STOC 2012) and our results yield a certain improvement for that problem. 3) We use this notion of L_4 vs. L_2 sparsity to obtain a polynomial-time algorithm with substantially improved guarantees for recovering a planted $μ$-sparse vector v in a random d-dimensional subspace of R^n. If v has mu n nonzero coordinates, we can recover it with high probability whenever $μ< O(\min(1,n/d^2))$, improving for $d < n^{2/3}$ prior methods which intrinsically required $μ< O(1/\sqrt(d))$.

arXiv:1312.6652•Electronic colloquium on computational complexity•Dec 23, 2013•0 citations

On the $Ω(n)$ SDP relaxation gap for Submodular Box-Constrained Quadratic Programming

Junyu Zhang, Guanyi Wang

Continuous submodular optimization is an important class of nonconvex problems with global guarantees, for which the submodular box-constrained quadratic programming (BCQP) forms a fundamental subclass. It arises naturally as quadratic subproblems of general twice-differentiable submodular problems and also has direct business and management applications such as pricing. This paper studies the worst-case relaxation gap of semidefinite programming (SDP) relaxations with a finite family of valid linear cuts for submodular BCQP. We show that in dimension $n\geq4$, for any SDP relaxation formulated with a finite family of linear cuts, there always exists a submodular BCQP instance with a strictly positive relaxation gap. By restricting to the normalized BCQP instances that remove the problem's scaling factor, we further quantify this limitation with explicit lower bounds. In general dimension $n\geq4$, when the SDP relaxation is formulated with only Boolean-quadric-polytope (BQP) valid cuts, including the commonly used McCormick and triangle inequalities, we establish an $Ω(n)$ relaxation gap lower bound. For an arbitrary family of $m$ valid linear cuts, we establish an $Ω(n/m^2)$ lower bound. These results capture the fundamental limitations of SDP relaxations, especially SDP with BQP valid cuts, and provide guidance on what additional constraints may be needed for more effective convex approximations of submodular BCQP.

arXiv:2609.03617•Sep 3, 2026•0 citations

An Argmax Principle for Sum-of-Squares Relaxations on the Sphere

Fernando Jeronimo Granha, Pei Wu, Haochen Xu

We develop an argmax principle for analyzing sum-of-squares relaxations of optimization problems over the unit sphere. Given a feasible pseudo-expectation, we form a polynomial of high-order pseudo-moments, such as $Φ_k(u)=\widetilde{\mathbb E}\langle x,u\rangle^{2k}$. Our guiding principle is that its maximizers are rounding candidates: their local and global optimality conditions reveal the reweighed pseudo-expectation inequalities governing SoS convergence. This viewpoint unifies several problems previously analyzed by rather different techniques. We obtain three results. First, for Best Separable State, we give a degree-$O(\sqrt{n/ε})$ SoS analysis for approximating $h_{\mathrm{sep}}(P)$ in the perfect-completeness regime, improving and simplifying Barak, Kothari and Steurer (STOC'17). The dependence is essentially tight for inverse-linear gap under the Exponential-Time Hypothesis, matching hardness from $\mathrm{QMA}(2)$ protocols. Second, for the matrix $2\to4$ norm, degree-$O(\sqrt n/ε)$ SoS gives a multiplicative $(1+ε)$ approximation. Barak et al. (STOC'12) previously gave a comparable-time constant-gap decision algorithm; our result gives a multiplicative guarantee and extends to a family of $p\to q$ norms with even $q$. Finally, for degree-$d$ polynomial optimization, we recover the convergence theorem of Bhattiprolu et al. (FOCS'17) with a shorter, more direct proof: degree-$k$ SoS gives approximation ratio $O_d((n/k)^{d/2-1})$. The paper introduces no new relaxation. Instead, the high-moment argmax gives a common way to read an SoS solution, unifying previously separate convergence analyses and yielding sharper bounds or simpler proofs.

cs.CCCross-listedarXiv:2608.02594•Aug 4, 2026•0 citations

The polarization hierarchy for polynomial optimization over convex bodies, with applications to nonnegative matrix rank

Martin Plávala, Laurens T. Ligthart, David Gross

We construct a convergent family of outer approximations for the problem of optimizing polynomial functions over convex bodies subject to polynomial constraints. This is achieved by generalizing the polarization hierarchy , which has previously been introduced for the study of polynomial optimization problems over state spaces of C ⁎ ⁎ -algebras, to convex cones in finite dimensions. If the convex bodies can be characterized by linear or semidefinite programs, then the same is true for our hierarchy. Convergence is proven by relating the problem to a certain de Finetti theorem for general probabilistic theories , which are studied as possible generalizations of quantum mechanics . We apply the method to the problem of nonnegative matrix factorization, and in particular to the nested rectangles problem . A numerical implementation of the third level of the hierarchy is shown to give rise to a very tight approximation for this problem.

arXiv:2406.09506•Linear Algebra and its Applications•May 22, 2025•1 citation

New approximation methods for solving binary quadratic programming problem

Rui Yang

In this thesis, we consider a special class of binary quadratic programming problem (BQP) where the number of nonzero elements is fixed. Such problems arise frequently from various applications and have been proved to be NP-hard. After a brief review of the quadratic programming problem, several optimization algorithms are presented. In Chapter 3, we propose a new simple second order conic relaxation of the BQP problem. We derive some additional constraints based on the information from the data matrix. The algorithm will be compared with the existing SDP relaxation algorithm in terms of their numerical performances. In Chapter 4, we use the convex quadratic relaxation as a geometric embedding tool to reformulate the underlying BQP as a clustering problem, where the target is to find a single cluster of fixed size. This connection allows us to employ many effective clustering algorithm developed in the data mining field. A 2-approximation algorithm for the clustering problem is presented. Numerical results based on the new relaxation model and the proposed algorithm are reported. The last Chapter mainly discusses some theoretical results we put forward on the derived clustering problem. Core-set technique is used to derive a new algorithm, which can provide a (1+\epsilon) approximation ratio to the reformulated clustering problem.

•Jun 22, 2010•2 citations

Quantum speed-ups for solving semidefinite relaxations of polynomial optimization

Daniel Stilck França, Ngoc Hoang Anh Mai

We study quantum algorithms for approximating Lasserre's hierarchy values for polynomial optimization. Let $f,g_1,\ldots,g_m$ be real polynomials in $n$ variables and $f^\star$ the infimum of $f$ over the semialgebraic set $S(g)=\{x: g_i(x)\ge 0\}$. Let $λ_k$ be the value of the order-$k$ Lasserre relaxation. Assume either (i) $f^\star=λ_k$ and the optimum is attained in the $\ell_1$-ball of radius $1/2$, or (ii) $S(g)$ lies in the simplex $\{x\ge 0: \sum_j x_j\le 1/2\}$, and the constraints define this simplex. After an appropriate coefficient rescaling, we give a quantum algorithm based on matrix multiplicative weights that approximates $λ_k$ to accuracy $\varepsilon>0$ with runtime, for fixed $k$, \[ O(n^k\varepsilon^{-4}+n^{k/2}\varepsilon^{-5}),\qquad O\!\left(s_g\!\left[n^k\varepsilon^{-4}+\!\left(n^{k}+\!\sum_{i=1}^m n^{k-d_i}\right)^{1/2}\!\varepsilon^{-5}\right]\right), \] where $s_g$ bounds the sparsity of the coefficient-matching matrices associated with the constraints. Classical matrix multiplicative-weights methods scale as $O(n^{3k}\mathrm{poly}(1/\varepsilon))$ even in the unconstrained case. As an example, we obtain an $O(n\varepsilon^{-4}+\sqrt{n}\varepsilon^{-5})$ quantum algorithm for portfolio optimization, improving over the classical $O(n^{ω+1}\log(1/\varepsilon))$ bound with $ω\approx2.373$. Our approach builds on and sharpens the analysis of Apeldoorn and Gilyén for the SDPs arising in polynomial optimization. We also show how to implement the required block encodings without QRAM. Under the stated assumptions, our method achieves a super-quadratic speedup in the problem dimension for computing Lasserre relaxations.

quant-pharXiv:2511.14389•Nov 19, 2025•0 citations
This thesis explores algorithmic applications and limitations of convex relaxation hierarchies for approximating some discrete and continuous optimization problems. - We show a dichotomy of approximability of constraint satisfaction problems (CSPs) by linear programming (LP) relaxations: for every CSP, the approximation obtained by a basic LP relaxation, is no weaker than the approximation obtained using relaxations given by super-constant levels of the Sherali-Adams hierarchy on instances of size nnn. - For the problem of approximating the absolute maximum of an n-variate degree-d homogeneous polynomial f with real coefficients over the unit sphere, we analyze the optimum value of the level-t sum-of-squares (SoS) SDP relaxation of the problem. Our results offer a trade-off between the approximation ratio and running time, which can take advantage of additional structure in the polynomial, such as non-negativity or sparsity of the coefficients. - We study the problem of approximating the p→qp \to qp→q-norm of a matrix AAA, and prove the first NP-hardness result for approximating norms in the hypercontractive case 1<p<q<∞1< p < q < \infty1<p<q<∞. We also prove almost tight algorithmic results for the case when p≥qp \geq qp≥q (with 2∈[q,p]2 \in [q,p]2∈[q,p]) where constant factor approximations for the matrix norms are possible. A common theme for these results is their connection to geometry. For the discrete optimization problem of CSP, geometry appears as a crucial tool for our lower bound proof. For the problem of polynomial optimization, we show that SDPs capture and extend earlier algorithms based on diameter estimation for convex bodies. For the matrix (operator) norm problem, the definition itself is geometric in nature and embedding theorems play a crucial role in our proofs.
We present a general approach to rounding semidefinite programming relaxations obtained by the Sum-of-Squares method (Lasserre hierarchy). Our approach is based on using the connection between these relaxations and the Sum-of-Squares proof system to transform a *combining algorithm* -- an algorithm that maps a distribution over solutions into a (possibly weaker) solution -- into a *rounding algorithm* that maps a solution of the relaxation to a solution of the original problem. Using this approach, we obtain algorithms that yield improved results for natural variants of three well-known problems: 1) We give a quasipolynomial-time algorithm that approximates the maximum of a low degree multivariate polynomial with non-negative coefficients over the Euclidean unit sphere. Beyond being of interest in its own right, this is related to an open question in quantum information theory, and our techniques have already led to improved results in this area (Brandão and Harrow, STOC '13). 2) We give a polynomial-time algorithm that, given a d dimensional subspace of R^n that (almost) contains the characteristic function of a set of size n/k, finds a vector vvv in the subspace satisfying ∣v∣44>c(k/d1/3)∣v∣22|v|_4^4 > c(k/d^{1/3}) |v|_2^2∣v∣44​>c(k/d1/3)∣v∣22​, where ∣v∣p=(Eivip)1/p|v|_p = (E_i v_i^p)^{1/p}∣v∣p​=(Ei​vip​)1/p. Aside from being a natural relaxation, this is also motivated by a connection to the Small Set Expansion problem shown by Barak et al. (STOC 2012) and our results yield a certain improvement for that problem. 3) We use this notion of L_4 vs. L_2 sparsity to obtain a polynomial-time algorithm with substantially improved guarantees for recovering a planted μμμ-sparse vector v in a random d-dimensional subspace of R^n. If v has mu n nonzero coordinates, we can recover it with high probability whenever μ<O(min⁡(1,n/d2))μ< O(\min(1,n/d^2))μ<O(min(1,n/d2)), improving for d<n2/3d < n^{2/3}d<n2/3 prior methods which intrinsically required μ<O(1/(d))μ< O(1/\sqrt(d))μ<O(1/(​d)).
On the Ω(n)Ω(n)Ω(n) SDP relaxation gap for Submodular Box-Constrained Quadratic Programming
Continuous submodular optimization is an important class of nonconvex problems with global guarantees, for which the submodular box-constrained quadratic programming (BCQP) forms a fundamental subclass. It arises naturally as quadratic subproblems of general twice-differentiable submodular problems and also has direct business and management applications such as pricing. This paper studies the worst-case relaxation gap of semidefinite programming (SDP) relaxations with a finite family of valid linear cuts for submodular BCQP. We show that in dimension n≥4n\geq4n≥4, for any SDP relaxation formulated with a finite family of linear cuts, there always exists a submodular BCQP instance with a strictly positive relaxation gap. By restricting to the normalized BCQP instances that remove the problem's scaling factor, we further quantify this limitation with explicit lower bounds. In general dimension n≥4n\geq4n≥4, when the SDP relaxation is formulated with only Boolean-quadric-polytope (BQP) valid cuts, including the commonly used McCormick and triangle inequalities, we establish an Ω(n)Ω(n)Ω(n) relaxation gap lower bound. For an arbitrary family of mmm valid linear cuts, we establish an Ω(n/m2)Ω(n/m^2)Ω(n/m2) lower bound. These results capture the fundamental limitations of SDP relaxations, especially SDP with BQP valid cuts, and provide guidance on what additional constraints may be needed for more effective convex approximations of submodular BCQP.
We develop an argmax principle for analyzing sum-of-squares relaxations of optimization problems over the unit sphere. Given a feasible pseudo-expectation, we form a polynomial of high-order pseudo-moments, such as Φk(u)=E~⟨x,u⟩2kΦ_k(u)=\widetilde{\mathbb E}\langle x,u\rangle^{2k}Φk​(u)=E⟨x,u⟩2k. Our guiding principle is that its maximizers are rounding candidates: their local and global optimality conditions reveal the reweighed pseudo-expectation inequalities governing SoS convergence. This viewpoint unifies several problems previously analyzed by rather different techniques. We obtain three results. First, for Best Separable State, we give a degree-O(n/ε)O(\sqrt{n/ε})O(n/ε​) SoS analysis for approximating hsep(P)h_{\mathrm{sep}}(P)hsep​(P) in the perfect-completeness regime, improving and simplifying Barak, Kothari and Steurer (STOC'17). The dependence is essentially tight for inverse-linear gap under the Exponential-Time Hypothesis, matching hardness from QMA(2)\mathrm{QMA}(2)QMA(2) protocols. Second, for the matrix 2→42\to42→4 norm, degree-O(n/ε)O(\sqrt n/ε)O(n​/ε) SoS gives a multiplicative (1+ε)(1+ε)(1+ε) approximation. Barak et al. (STOC'12) previously gave a comparable-time constant-gap decision algorithm; our result gives a multiplicative guarantee and extends to a family of p→qp\to qp→q norms with even qqq. Finally, for degree-ddd polynomial optimization, we recover the convergence theorem of Bhattiprolu et al. (FOCS'17) with a shorter, more direct proof: degree-kkk SoS gives approximation ratio Od((n/k)d/2−1)O_d((n/k)^{d/2-1})Od​((n/k)d/2−1). The paper introduces no new relaxation. Instead, the high-moment argmax gives a common way to read an SoS solution, unifying previously separate convergence analyses and yielding sharper bounds or simpler proofs.
We construct a convergent family of outer approximations for the problem of optimizing polynomial functions over convex bodies subject to polynomial constraints. This is achieved by generalizing the polarization hierarchy , which has previously been introduced for the study of polynomial optimization problems over state spaces of C ⁎ ⁎ -algebras, to convex cones in finite dimensions. If the convex bodies can be characterized by linear or semidefinite programs, then the same is true for our hierarchy. Convergence is proven by relating the problem to a certain de Finetti theorem for general probabilistic theories , which are studied as possible generalizations of quantum mechanics . We apply the method to the problem of nonnegative matrix factorization, and in particular to the nested rectangles problem . A numerical implementation of the third level of the hierarchy is shown to give rise to a very tight approximation for this problem.
In this thesis, we consider a special class of binary quadratic programming problem (BQP) where the number of nonzero elements is fixed. Such problems arise frequently from various applications and have been proved to be NP-hard. After a brief review of the quadratic programming problem, several optimization algorithms are presented. In Chapter 3, we propose a new simple second order conic relaxation of the BQP problem. We derive some additional constraints based on the information from the data matrix. The algorithm will be compared with the existing SDP relaxation algorithm in terms of their numerical performances. In Chapter 4, we use the convex quadratic relaxation as a geometric embedding tool to reformulate the underlying BQP as a clustering problem, where the target is to find a single cluster of fixed size. This connection allows us to employ many effective clustering algorithm developed in the data mining field. A 2-approximation algorithm for the clustering problem is presented. Numerical results based on the new relaxation model and the proposed algorithm are reported. The last Chapter mainly discusses some theoretical results we put forward on the derived clustering problem. Core-set technique is used to derive a new algorithm, which can provide a (1+\epsilon) approximation ratio to the reformulated clustering problem.
We study quantum algorithms for approximating Lasserre's hierarchy values for polynomial optimization. Let f,g1,…,gmf,g_1,\ldots,g_mf,g1​,…,gm​ be real polynomials in nnn variables and f⋆f^\starf⋆ the infimum of fff over the semialgebraic set S(g)={x:gi(x)≥0}S(g)=\{x: g_i(x)\ge 0\}S(g)={x:gi​(x)≥0}. Let λkλ_kλk​ be the value of the order-kkk Lasserre relaxation. Assume either (i) f⋆=λkf^\star=λ_kf⋆=λk​ and the optimum is attained in the ℓ1\ell_1ℓ1​-ball of radius 1/21/21/2, or (ii) S(g)S(g)S(g) lies in the simplex {x≥0:∑jxj≤1/2}\{x\ge 0: \sum_j x_j\le 1/2\}{x≥0:∑j​xj​≤1/2}, and the constraints define this simplex. After an appropriate coefficient rescaling, we give a quantum algorithm based on matrix multiplicative weights that approximates λkλ_kλk​ to accuracy ε>0\varepsilon>0ε>0 with runtime, for fixed kkk, O(nkε−4+nk/2ε−5),O ⁣(sg ⁣[nkε−4+ ⁣(nk+ ⁣∑i=1mnk−di)1/2 ⁣ε−5]), O(n^k\varepsilon^{-4}+n^{k/2}\varepsilon^{-5}),\qquad O\!\left(s_g\!\left[n^k\varepsilon^{-4}+\!\left(n^{k}+\!\sum_{i=1}^m n^{k-d_i}\right)^{1/2}\!\varepsilon^{-5}\right]\right), O(nkε−4+nk/2ε−5),O(sg​[nkε−4+(nk+∑i=1m​nk−di​)1/2ε−5]), where sgs_gsg​ bounds the sparsity of the coefficient-matching matrices associated with the constraints. Classical matrix multiplicative-weights methods scale as O(n3kpoly(1/ε))O(n^{3k}\mathrm{poly}(1/\varepsilon))O(n3kpoly(1/ε)) even in the unconstrained case. As an example, we obtain an O(nε−4+nε−5)O(n\varepsilon^{-4}+\sqrt{n}\varepsilon^{-5})O(nε−4+n​ε−5) quantum algorithm for portfolio optimization, improving over the classical O(nω+1log⁡(1/ε))O(n^{ω+1}\log(1/\varepsilon))O(nω+1log(1/ε)) bound with ω≈2.373ω\approx2.373ω≈2.373. Our approach builds on and sharpens the analysis of Apeldoorn and Gilyén for the SDPs arising in polynomial optimization. We also show how to implement the required block encodings without QRAM. Under the stated assumptions, our method achieves a super-quadratic speedup in the problem dimension for computing Lasserre relaxations.