An Introduction to Polynomial and Semi-Algebraic Optimization
The DOI matches its Crossref record; 83 of the 83 references it cites were found in a registry or an index.
Abstract
This is the first comprehensive introduction to the powerful moment approach for solving global optimization problems (and some related problems) described by polynomials (and even semi-algebraic functions). In particular, the author explains how to use relatively recent results from real algebraic geometry to provide a systematic numerical scheme for computing the optimal value and global minimizers. Indeed, among other things, powerful positivity certificates from real algebraic geometry allow one to define an appropriate hierarchy of semidefinite (SOS) relaxations or LP relaxations whose optimal values converge to the global minimum. Several extensions to related optimization problems are also described. Graduate students, engineers and researchers entering the field can use this book to understand, experiment with and master this new approach through the simple worked examples provided.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
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
Golub, G. (2012) · doi:10.56021/9781421407944 · Cited by 34,505
An introduction to probability theory and its applications
(1958) · Journal of the Franklin Institute · doi:10.1016/0016-0032(58)90688-4 · Cited by 29,269
YALMIP : a toolbox for modeling and optimization in MATLAB
Lofberg, J. (2005) · 2004 IEEE International Conference on Robotics and Automation (IEEE Cat. No.04CH37508) · doi:10.1109/cacsd.2004.1393890 · Cited by 9,149
Bertsimas, D., & Sim, M. (2004) · Operations Research · doi:10.1287/opre.1030.0065 · Cited by 4,557
Encyclopedia of Mathematics and its Applications.
L., Y. L., Jones, W. B., & Thron, W. J. (1982) · Mathematics of Computation · doi:10.2307/2007638 · Cited by 4,119
Vandenberghe, L., & Boyd, S. (1996) · SIAM Review · doi:10.1137/1038003 · Cited by 4,105
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
Self-citationPerturbation Analysis of Optimization Problems
Bonnans, J. F., & Shapiro, A. (2000) · Springer eBooks · doi:10.1007/978-1-4612-1394-9 · Cited by 2,400
Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization
Parrilo, P. A. (2000) · doi:10.7907/2k6y-ch43 · Cited by 1,802
Faraut, J., & Korányi, A. (1994) · doi:10.1093/oso/9780198534778.001.0001 · Cited by 1,656
Semidefinite programming relaxations for semialgebraic problems
Parrilo, P. A. (2003) · Mathematical Programming · doi:10.1007/s10107-003-0387-5 · Cited by 1,527
Mathematics and its applications
Yau, S. T. (2005) · The 2002 International Conference on Control and Automation, 2002. ICCA. Final Program and Book of Abstracts. · doi:10.1109/icca.2002.1229256 · Cited by 1,488
Problems and Theorems in Analysis
Pólya, G., & Szegö, G. (1972) · Springer eBooks · doi:10.1007/978-1-4757-1640-5 · Cited by 1,283
(2014) · Choice Reviews Online · doi:10.5860/choice.51-3296 · Cited by 1,260
A polyhedral branch-and-cut approach to global optimization
Tawarmalani, M., & Sahinidis, N. V. (2005) · Mathematical Programming · doi:10.1007/s10107-005-0581-8 · Cited by 1,225
Discrete-Time Markov Control Processes
Hernández-Lerma, O., & Lasserre, J. B. (1996) · Springer eBooks · doi:10.1007/978-1-4612-0729-0 · Cited by 1,082
Self-citationCones of Matrices and Set-Functions and 0–1 Optimization
Lovász, L., & Schrijver, A. (1991) · SIAM Journal on Optimization · doi:10.1137/0801013 · Cited by 1,008
Sherali, H. D., & Adams, W. P. (1990) · SIAM Journal on Discrete Mathematics · doi:10.1137/0403036 · Cited by 931
Minima of Functions of Several Variables with Inequalities as Side Conditions
Karush, W. (2014) · Traces and Emergence of Nonlinear Programming · doi:10.1007/978-3-0348-0439-4_10 · Cited by 848
Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications
Ben-Tal, A., & Nemirovski, A. (2001) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9780898718829 · Cited by 747
Real Analysis and Probability.
Ross, K. A., & Ash, R. B. (1975) · The American Mathematical Monthly · doi:10.2307/2319153 · Cited by 714
Barvinok, A. (2002) · Graduate Studies in Mathematics · doi:10.1090/gsm/054 · Cited by 660
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
Ahuja, R. K., & Orlin, J. B. (2001) · Operations Research · doi:10.1287/opre.49.5.771.10607 · Cited by 643
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
A reformulation-linearization technique for solving discrete and continuous nonconvex problems
(1999) · Computers & Mathematics with Applications · doi:10.1016/s0898-1221(99)91233-6 · Cited by 591
Handbook of semidefinite programming : theory, algorithms, and applications
Wolkowicz, H., Saigal, R., & Vandenberghe, L. (2000) · Cited by 568
Ali, M. M., Khompatraporn, C., & Zabinsky, Z. B. (2005) · Journal of Global Optimization · doi:10.1007/s10898-004-9972-2 · Cited by 565
Introducing SOSTOOLS: a general purpose sum of squares programming solver
Prajna, S., Papachristodoulou, A., & Parrilo, P. A. (2003) · Proceedings of the 41st IEEE Conference on Decision and Control, 2002. · doi:10.1109/cdc.2002.1184594 · Cited by 545
?BB: A global optimization method for general constrained nonconvex problems
Androulakis, I. P., Maranas, C. D., & Floudas, C. A. (1995) · Journal of Global Optimization · doi:10.1007/bf01099647 · Cited by 465
Deterministic global optimization: Theory, methods and applications
(2000) · Computers & Mathematics with Applications · doi:10.1016/s0898-1221(00)90165-2 · Cited by 451
Waki, H., Kim, S., Kojima, M., & Muramatsu, M. (2006) · SIAM Journal on Optimization · doi:10.1137/050623802 · Cited by 439
The Moment Problem on Compact Semi-Algebraic Sets
Schmüdgen, K. (2017) · Graduate texts in mathematics · doi:10.1007/978-3-319-64546-9_12 · Cited by 429
On the copositive representation of binary and continuous nonconvex quadratic programs
Burer, S. (2009) · Mathematical Programming · doi:10.1007/s10107-008-0223-z · Cited by 388
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
Self-citationApproximation of the Stability Number of a Graph via Copositive Programming
de Klerk, E., & Pasechnik, D. V. (2002) · SIAM Journal on Optimization · doi:10.1137/s1052623401383248 · Cited by 322
Tractable Approximations to Robust Conic Optimization Problems
Bertsimas, D., & Sim, M. (2006) · Mathematical Programming · doi:10.1007/s10107-005-0677-1 · Cited by 297
Nonlinear regulator theory and an inverse optimal control problem
Moylan, P., & Anderson, B. (1973) · IEEE Transactions on Automatic Control · doi:10.1109/tac.1973.1100365 · Cited by 283
Convergent SDP‐Relaxations in Polynomial Optimization with Sparsity
Lasserre, J. B. (2006) · SIAM Journal on Optimization · doi:10.1137/05064504x · Cited by 281
Self-citationLinear Level Lasserre Lower Bounds for Certain k-CSPs
Schoenebeck, G. (2008) · 2008 49th Annual IEEE Symposium on Foundations of Computer Science · doi:10.1109/focs.2008.74 · Cited by 261
Optimality conditions and finite convergence of Lasserre’s hierarchy
Nie, J. (2013) · Mathematical Programming · doi:10.1007/s10107-013-0680-x · Cited by 259
New Code Upper Bounds From the Terwilliger Algebra and Semidefinite Programming
Schrijver, A. (2005) · IEEE Transactions on Information Theory · doi:10.1109/tit.2005.851748 · Cited by 246
Solving Standard Quadratic Optimization Problems via Linear, Semidefinite and Copositive Programming
Bomze, I. M., & De Klerk, E. (2002) · Journal of Global Optimization · doi:10.1023/a:1020209017701 · Cited by 219
Extending Scope of Robust Optimization: Comprehensive Robust Counterparts of Uncertain Problems
Ben-Tal, A., Boyd, S., & Nemirovski, A. (2006) · Mathematical Programming · doi:10.1007/s10107-005-0679-z · Cited by 216
Copositive Programming – a Survey
Dür, M. (2010) · Springer eBooks · doi:10.1007/978-3-642-12598-0_1 · Cited by 209
On Copositive Programming and Standard Quadratic Optimization Problems
Bomze, I. M., Dür, M., de Klerk, E., Roos, C., Quist, A. J., & Terlaky, T. (2000) · Journal of Global Optimization · doi:10.1023/a:1026583532263 · Cited by 196
On the complexity of Putinar's Positivstellensatz
Nie, J., & Schweighofer, M. (2006) · Journal of Complexity · doi:10.1016/j.jco.2006.07.002 · Cited by 181
Semidefinite representation of convex sets
Helton, J. W., & Nie, J. (2008) · Mathematical Programming · doi:10.1007/s10107-008-0240-y · Cited by 180
Smooth Optimization with Approximate Gradient
d'Aspremont, A. (2008) · SIAM Journal on Optimization · doi:10.1137/060676386 · Cited by 168
Minimizing Polynomials via Sum of Squares over the Gradient Ideal
Nie, J., Demmel, J. W., & Sturmfels, B. (2005) · Mathematical Programming · doi:10.1007/s10107-005-0672-6 · Cited by 162
Copositive optimization – Recent developments and applications
Bomze, I. M. (2011) · European Journal of Operational Research · doi:10.1016/j.ejor.2011.04.026 · Cited by 154
Polynomials that are positive on an interval
Victoria Powers, A., & Reznick, B. A. (2000) · Transactions of the American Mathematical Society · doi:10.1090/s0002-9947-00-02595-2 · Cited by 131
Convex extensions and envelopes of lower semi-continuous functions
Tawarmalani, M., & Sahinidis, N. V. (2002) · Mathematical Programming · doi:10.1007/s10107-002-0308-z · Cited by 127
NP-hardness of deciding convexity of quartic polynomials and related problems
Ahmadi, A. A., Olshevsky, A., Parrilo, P. A., & Tsitsiklis, J. N. (2011) · Mathematical Programming · doi:10.1007/s10107-011-0499-2 · Cited by 126
Semidefinite Programs and Combinatorial Optimization
Lovász, L. (2003) · Springer eBooks · doi:10.1007/0-387-22444-0_6 · Cited by 109
Theta Bodies for Polynomial IdealsPreprint
Gouveia, J., Parrilo, P. A., & Thomas, R. R. (2009) · Cited by 106
Semidefinite Programming vs. LP Relaxations for Polynomial Programming
Lasserre, J. B. (2002) · Mathematics of Operations Research · doi:10.1287/moor.27.2.347.322 · Cited by 101
Self-citationComputing the Stability Number of a Graph Via Linear and Semidefinite Programming
Peña, J., Vera, J. C., & Zuluaga, L. F. (2007) · SIAM Journal on Optimization · doi:10.1137/05064401x · Cited by 100
Convex Relaxations and Integrality Gaps
Chlamtáč, E., & Tulsiani, M. (2011) · International series in management science/operations research/International series in operations research & management science · doi:10.1007/978-1-4614-0769-0_6 · Cited by 93
Revisiting 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
On the complexity of Schmüdgen's Positivstellensatz
Schweighofer, M. (2004) · Journal of Complexity · doi:10.1016/j.jco.2004.01.005 · Cited by 93
Convex Geometry and Functional Analysis
Ball, K. (2001) · Handbook of the geometry of Banach spaces · doi:10.1016/s1874-5849(01)80006-1 · Cited by 90
Semidefinite representations for finite varieties
Laurent, M. (2006) · Mathematical Programming · doi:10.1007/s10107-004-0561-4 · Cited by 89
Nonnegative polynomials and sums of squares
Blekherman, G. (2012) · Journal of the American Mathematical Society · doi:10.1090/s0894-0347-2012-00733-4 · Cited by 88
A Frank–Wolfe Type Theorem for Convex Polynomial Programs
Belousov, E. G., & Klatte, D. (2002) · Computational Optimization and Applications · doi:10.1023/a:1014813701864 · Cited by 85
Approximate Volume and Integration for Basic Semialgebraic Sets
Henrion, D., Lasserre, J. B., & Savorgnan, C. (2009) · SIAM Review · doi:10.1137/080730287 · Cited by 85
Self-citationBomze, I. M., Schachinger, W., & Uchida, G. (2011) · Journal of Global Optimization · doi:10.1007/s10898-011-9749-3 · Cited by 81
Variant quantifier elimination
Hong, H., & Din, M. S. E. (2011) · Journal of Symbolic Computation · doi:10.1016/j.jsc.2011.05.014 · Cited by 67
Global Minimization of a Multivariate Polynomial using Matrix Methods
Hanzon, B., & Jibetean, D. (2003) · Journal of Global Optimization · doi:10.1023/a:1024664432540 · Cited by 66
Representations of Non-Negative Polynomials, Degree Bounds and Applications to Optimization
Marshall, M. (2009) · Canadian Journal of Mathematics · doi:10.4153/cjm-2009-010-4 · Cited by 63
Improved Approximation Guarantees through Higher Levels of SDP Hierarchies
Chlamtáč, E., & Singh, G. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-85363-3_5 · Cited by 51
An analogue of the Riesz–Haviland theorem for the truncated moment problem
Curto, R. E., & Fialkow, L. A. (2008) · Journal of Functional Analysis · doi:10.1016/j.jfa.2008.09.003 · Cited by 50
Semidefinite Approximations for Global Unconstrained Polynomial Optimization
Jibetean, D., & Laurent, M. (2005) · SIAM Journal on Optimization · doi:10.1137/04060562x · Cited by 43
Gounaris, C. E., & Floudas, C. A. (2008) · Journal of Global Optimization · doi:10.1007/s10898-008-9288-8 · Cited by 42
Tractable approximations of sets defined with quantifiers
Lasserre, J. B. (2014) · Mathematical Programming · doi:10.1007/s10107-014-0838-1 · Cited by 27
Self-citationExposed Faces of Semidefinitely Representable Sets
Netzer, T., Plaumann, D., & Schweighofer, M. (2010) · SIAM Journal on Optimization · doi:10.1137/090750196 · Cited by 27
New Convex Relaxations for the Maximum Cut and VLSI Layout Problems
dos Anjos, F. F., & Nuno, M. (2001) · UWSpace (University of Waterloo) · Cited by 25
The Positivstellensatz for definable functions on o-minimal structures
Acquistapace, F., Andradas, C., & Broglia, F. (2002) · Illinois Journal of Mathematics · doi:10.1215/ijm/1258130979 · Cited by 8
0 CERTIFICATES OF CONVEXITY FOR BASIC SEMI-ALGEBRAIC SETSPreprint
Lasserre, J. B. (2010) · Cited by 5
Self-citationPositive polynomials on projective limits of real algebraic varieties
Kuhlmann, S., & Putinar, M. (2008) · Bulletin des Sciences Mathématiques · doi:10.1016/j.bulsci.2008.06.001 · Cited by 4
Metadata
- Authors
- Lasserre, J. B.
- Venue
- Cambridge University Press eBooks
- Publisher
- Cambridge University Press
- Published
- 2015-02-05
- OpenAlex
- W404764422
- Cited by
- 260
- References
- 83
- FWCI
- 2.74
- Type
- book
- 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.