The DOI matches its Crossref record; 7 of the 7 references it cites were found in a registry or an index.
Convergent SDP‐Relaxations in Polynomial Optimization with Sparsity
Abstract
We consider a polynomial programming problem $\P$ on a compact basic semialgebraic set $\K\subset\R^n$, described by m polynomial inequalities $g_j(X)\geq0$, and with criterion $f\in\R[X]$. We propose a hierarchy of semidefinite relaxations in the spirit of those of Waki et al. [SIAM J. Optim., 17 (2006), pp. 218–242]. In particular, the SDP‐relaxation of order r has the following two features: (a) The number of variables is $O(\kappa^{2r})$, where $\kappa=\max[\kappa_1,\kappa_2]$ with $\kappa_1$ (resp., $\kappa_2$) being the maximum number of variables appearing in the monomials of f (resp., appearing in a single constraint $g_j(X)\geq0$). (b) The largest size of the linear matrix inequalities (LMIs) is $O(\kappa^r)$. This is to compare with the respective number of variables $O(n^{2r})$ and LMI size $O(n^r)$ in the original SDP‐relaxations defined in [J. B. Lasserre, SIAM J. Optim., 11 (2001), pp. 796–817]. Therefore, great computational savings are expected in case of sparsity in the data $\{g_j,f\}$, i.e., when κ is small, a frequent case in practical applications of interest. The novelty with respect to [H. Waki, S. Kim, M. Kojima, and M. Maramatsu, SIAM J. Optim., 17 (2006), pp. 218–242] is that we prove convergence to the global optimum of $\P$ when the sparsity pattern satisfies a condition often encountered in large size problems of practical applications, and known as the running intersection property in graph theory. In such cases, and as a by‐product, we also obtain a new representation result for polynomials positive on a compact basic semialgebraic set, a sparse version of Putinar’s Positivstellensatz [M. Putinar, Indiana Univ. Math. J., 42 (1993), pp. 969–984].
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Global Optimization with Polynomials and the Problem of Moments
Lasserre, J. B. (2001) · SIAM Journal on Optimization · doi:10.1137/s1052623400366802 · Cited by 2,474
Self-citation(1972) · Elsevier eBooks · doi:10.1016/c2013-0-06164-6 · Cited by 1,728
Stochastic optimal control : the discrete time case
Bertsekas, D. P., & Shreve, S. E. (2007) · Cited by 1,654
Waki, H., Kim, S., Kojima, M., & Muramatsu, M. (2006) · SIAM Journal on Optimization · doi:10.1137/050623802 · Cited by 439
GloptiPoly: Global optimization over polynomials with Matlab and SeDuMi
Henrion, D., & Lasserre, J.-B. (2003) · ACM Transactions on Mathematical Software · doi:10.1145/779359.779363 · Cited by 369
Self-citationDetecting Global Optimality and Extracting Solutions in GloptiPoly
Henrion, D., & Lasserre, J. B. (2005) · Lecture notes in control and information sciences · doi:10.1007/10997703_15 · Cited by 289
Self-citationRevisiting two theorems of Curto and Fialkow on moment matrices
Laurent, M. (2005) · Proceedings of the American Mathematical Society · doi:10.1090/s0002-9939-05-08133-5 · Cited by 93
Cited by
Sums of Squares, Moment Matrices and Optimization Over Polynomials
Laurent, M. (2009) · The IMA Volumes in Mathematics and its Applications · doi:10.1007/978-0-387-09686-5_7 · Cited by 648
SE-Sync: A certifiably correct algorithm for synchronization over the special Euclidean group
Rosen, D. M., Carlone, L., Bandeira, A. S., & Leonard, J. J. (2019) · The International Journal of Robotics Research · doi:10.1177/0278364918784361 · Cited by 282
Warm-starting quantum optimization
Egger, D. J., Mareček, J., & Woerner, S. (2021) · Quantum · doi:10.22331/q-2021-06-17-479 · Cited by 269
An Introduction to Polynomial and Semi-Algebraic Optimization
Lasserre, J. B. (2015) · Cambridge University Press eBooks · doi:10.1017/cbo9781107447226 · Cited by 260
Self-citation
Metadata
- Authors
- Lasserre, J. B.
- Venue
- SIAM Journal on Optimization
- Published
- 2006-01
- Volume
- 17
- Issue
- 3
- Pages
- 822-843
- ISSN
- 1052-6234 (ISSN-L)
- 1095-7189
- OpenAlex
- W2071550336
- Cited by
- 281
- References
- 7
- FWCI
- 11.61
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Convergent SDP‐Relaxations in Polynomial Optimization with Sparsity. https://app.cochat.ai/papers/10.1137/05064504x
- The paper
- Lasserre, J. B. (2006). Convergent SDP‐Relaxations in Polynomial Optimization with Sparsity. SIAM Journal on Optimization. https://doi.org/10.1137/05064504x
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.