The DOI matches its Crossref record; 22 of the 22 references it cites were found in a registry or an index.
Sums of Squares and Semidefinite Program Relaxations for Polynomial Optimization Problems with Structured Sparsity
Abstract
Unconstrained and inequality constrained sparse polynomial optimization problems (POPs) are considered. A correlative sparsity pattern graph is defined to find a certain sparse structure in the objective and constraint polynomials of a POP. Based on this graph, sets of the supports for sums of squares (SOS) polynomials that lead to efficient SOS and semidefinite program (SDP) relaxations are obtained. Numerical results from various test problems are included to show the improved performance of the SOS and SDP relaxations.
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
Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
Sturm, J. F. (1999) · Optimization Methods and Software · doi:10.1080/10556789908805766 · Cited by 7,377
Algorithmic Graph Theory and Perfect Graphs
(2004) · Annals of Discrete Mathematics · doi:10.1016/s0167-5060(04)x8001-8 · Cited by 3,729
Goemans, M. X., & Williamson, D. P. (1995) · Journal of the ACM · doi:10.1145/227683.227684 · Cited by 3,587
Convex Bodies: The Brunn–Minkowski Theory
Schneider, R. (1993) · Cambridge University Press eBooks · doi:10.1017/cbo9780511526282 · Cited by 3,345
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
Semidefinite programming relaxations for semialgebraic problems
Parrilo, P. A. (2003) · Mathematical Programming · doi:10.1007/s10107-003-0387-5 · Cited by 1,527
Testing Unconstrained Optimization Software
Morè, J. J., Garbow, B. S., & Hillstrom, K. E. (1981) · ACM Transactions on Mathematical Software · doi:10.1145/355934.355936 · Cited by 1,527
Incidence matrices and interval graphs
Fulkerson, D., & Gross, O. (1965) · Pacific Journal of Mathematics · doi:10.2140/pjm.1965.15.835 · Cited by 1,262
Karypis, G., & Kumar, V. (1997) · University of Minnesota Digital Conservancy (University of Minnesota) · Cited by 1,215
Handbook of Test Problems in Local and Global Optimization
Floudas, C. A., Pardalos, P. M., Adjiman, C. S., Esposito, W. R., Gümüş, Z. H., Harding, S. T., Klepeis, J. L., Meyer, C. A., & Schweiger, C. A. (1999) · Nonconvex Optimization and Its Applications · doi:10.1007/978-1-4757-3040-1 · Cited by 636
LOQO:an interior point code for quadratic programming
Vanderbei, R. J. (1999) · Optimization Methods and Software · doi:10.1080/10556789908805759 · Cited by 471
An Introduction to Chordal Graphs and Clique Trees
Blair, J. R. S., & Peyton, B. (1993) · The IMA Volumes in Mathematics and its Applications · doi:10.1007/978-1-4613-8369-7_1 · Cited by 377
A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
Laurent, M. (2003) · Mathematics of Operations Research · doi:10.1287/moor.28.3.470.16391 · Cited by 373
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
Newton-Type Minimization via the Lanczos Method
Nash, S. G. (1984) · SIAM Journal on Numerical Analysis · doi:10.1137/0721052 · Cited by 338
Minimizing polynomial functions
Parrilo, P. A., & Sturmfels, B. (2003) · DIMACS series in discrete mathematics and theoretical computer science · doi:10.1090/dimacs/060/08 · Cited by 316
Detecting 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
Testing a class of methods for solving minimization problems with simple bounds on the variables
Conn, A. R., Gould, N. I. M., & Toint, P. L. (1988) · Mathematics of Computation · doi:10.1090/s0025-5718-1988-0929544-3 · Cited by 206
Implementation and evaluation of SDPA 6.0 (Semidefinite Programming Algorithm 6.0)
Yamashita, M., Fujisawa, K., & Kojima, M. (2003) · Optimization Methods and Software · doi:10.1080/1055678031000118482 · Cited by 160
Self-citationSemidefinite Programming Relaxation for Nonconvex Quadratic Programs
Fujie, T., & Kojima, M. (1997) · Journal of Global Optimization · doi:10.1023/a:1008282830093 · Cited by 130
Self-citationA GENERAL FRAMEWORK FOR CONVEX RELAXATION OF POLYNOMIAL OPTIMIZATION PROBLEMS OVER CONES
Kojima, M., Kim, S., & Waki, H. (2003) · Journal of the Operations Research Society of Japan · doi:10.15807/jorsj.46.125 · Cited by 37
Self-citationA NEW SECOND-ORDER CONE PROGRAMMING RELAXATION FOR MAX-CUT PROBLEMS
Muramatsu, M., & Suzuki, T. (2003) · Journal of the Operations Research Society of Japan · doi:10.15807/jorsj.46.164 · Cited by 29
Self-citation
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
Convex Relaxation of Optimal Power Flow—Part II: Exactness
Low, S. H. (2014) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2014.2323634 · Cited by 523
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
Convergent SDP‐Relaxations in Polynomial Optimization with Sparsity
Lasserre, J. B. (2006) · SIAM Journal on Optimization · doi:10.1137/05064504x · Cited by 281
A Survey of Relaxations and Approximations of the Power Flow Equations
Molzahn, D. K., & Hiskens, I. A. (2019) · Foundations and Trends® in Electric Energy Systems · doi:10.1561/3100000012 · Cited by 272
Metadata
- Authors
- Waki, H., Kim, S., Kojima, M., & Muramatsu, M.
- Venue
- SIAM Journal on Optimization
- Published
- 2006-01
- Volume
- 17
- Issue
- 1
- Pages
- 218-242
- ISSN
- 1052-6234 (ISSN-L)
- 1095-7189
- OpenAlex
- W2166798101
- Cited by
- 439
- References
- 22
- FWCI
- 20.90
- 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
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.