The DOI matches its OpenAlex record; 28 of the 28 references it cites were found in a registry or an index.
Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization
Abstract
In the first part of this thesis, we introduce a specific class of Linear Matrix Inequalities (LMI) whose optimal solution can be characterized exactly. This family corresponds to the case where the associated linear operator maps the cone of positive semidefinite matrices onto itself. In this case, the optimal value equals the spectral radius of the operator. It is shown that some rank minimization problems, as well as generalizations of the structured singular value ($\\mu$) LMIs, have exactly this property. In the same spirit of exploiting structure to achieve computational efficiency, an algorithm for the numerical solution of a special class of frequency-dependent LMIs is presented. These optimization problems arise from robustness analysis questions, via the Kalman-Yakubovich-Popov lemma. The procedure is an outer approximation method based on the algorithms used in the computation of \\hinf\\ norms for linear, time invariant systems. The result is especially useful for systems with large state dimension. The other main contribution in this thesis is the formulation of a convex optimization framework for semialgebraic problems, i.e., those that can be expressed by polynomial equalities and inequalities. The key element is the interaction of concepts in real algebraic geometry (Positivstellensatz) and semidefinite programming. To this end, an LMI formulation for the sums of squares decomposition for multivariable polynomials is presented. Based on this, it is shown how to construct sufficient Positivstellensatz-based convex tests to prove that certain sets are empty. Among other applications, this leads to a nonlinear extension of many LMI based results in uncertain linear system analysis. Within the same framework, we develop stronger criteria for matrix copositivity, and generalizations of the well-known standard semidefinite relaxations for quadratic programming. Some applications to new and previously studied problems are presented. A few examples are Lyapunov function computation, robust bifurcation analysis, structured singular values, etc. It is shown that the proposed methods allow for improved solutions for very diverse questions in continuous and combinatorial optimization.
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
(1979) · Cited by 43,841
Horn, R. A., & Johnson, C. R. (1985) · Cited by 22,203
Nonlinear Oscillations, Dynamical Systems, and Bifurcations of Vector Fields
Guckenheimer, J., & Holmes, P. (1983) · Applied Mathematical Sciences · doi:10.1007/978-1-4612-1140-2 · Cited by 16,144
Nonlinear and adaptive control design
Krstić, M., Kokotović, P. V., & Kanellakopoulos, I. (1995) · Cited by 10,421
Combinatorial Optimization: Algorithms and Complexity.
Johnson, D. S., Papadimitriou, C. H., & Steiglitz, K. (1984) · The American Mathematical Monthly · doi:10.2307/2322374 · Cited by 5,942
Nonnegative Matrices in the Mathematical Sciences
(1979) · Elsevier eBooks · doi:10.1016/c2013-0-10361-3 · Cited by 5,451
(2012) · SpringerReference · doi:10.1007/springerreference_117570 · Cited by 4,486
Introduction to Applied Nonlinear Dynamical Systems and Chaos
Wiggins, S., & Mazel, D. S. (1990) · Computers in Physics · doi:10.1063/1.4822950 · Cited by 3,780
Goemans, M. X., & Williamson, D. P. (1995) · Journal of the ACM · doi:10.1145/227683.227684 · Cited by 3,587
A linear matrix inequality approach to H∞control
Gahinet, P., & Apkarian, P. (1994) · International Journal of Robust and Nonlinear Control · doi:10.1002/rnc.4590040403 · Cited by 3,237
Cited by
Semidefinite programming relaxations for semialgebraic problems
Parrilo, P. A. (2003) · Mathematical Programming · doi:10.1007/s10107-003-0387-5 · Cited by 1,527
Self-citationPredictive Control for Linear and Hybrid Systems
Borrelli, F., Bemporad, A., & Morari, M. (2017) · Cambridge University Press eBooks · doi:10.1017/9781139061759 · Cited by 1,443
Solving Systems of Polynomial Equations
Sturmfels, B. (2002) · CBMS Regional Conference Series in Mathematics · doi:10.1090/cbms/097 · Cited by 792
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
Safety Verification of Hybrid Systems Using Barrier Certificates
Prajna, S., & Jadbabaie, A. (2004) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-24743-2_32 · Cited by 642
Semidefinite programming for optimal power flow problems
Bai, X., Wei, H., Fujisawa, K., & Wang, Y. (2008) · International Journal of Electrical Power & Energy Systems · doi:10.1016/j.ijepes.2007.12.003 · Cited by 573
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
Self-citationHamilton-Jacobi reachability: A brief overview and recent advances
Bansal, S., Chen, M., Herbert, S., & Tomlin, C. J. (2017) · 2017 IEEE 56th Annual Conference on Decision and Control (CDC) · doi:10.1109/cdc.2017.8263977 · Cited by 471
On the construction of Lyapunov functions using the sum of squares decomposition
Papachristodoulou, A., & Prajna, S. (2003) · Proceedings of the 41st IEEE Conference on Decision and Control, 2002. · doi:10.1109/cdc.2002.1184414 · Cited by 461
Optimal Inequalities in Probability Theory: A Convex Optimization Approach
Bertsimas, D., & Popescu, I. (2005) · SIAM Journal on Optimization · doi:10.1137/s1052623401399903 · Cited by 428
Geometric Programming for Communication Systems
Chiang, M. (2005) · now publishers, Inc. eBooks · doi:10.1561/9781933019574 · Cited by 423
LQR-trees: Feedback Motion Planning via Sums-of-Squares Verification
Tedrake, R., Manchester, I. R., Tobenkin, M., & Roberts, J. W. (2010) · The International Journal of Robotics Research · doi:10.1177/0278364910369189 · Cited by 409
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
Funnel libraries for real-time robust feedback motion planning
Majumdar, A., & Tedrake, R. (2017) · The International Journal of Robotics Research · doi:10.1177/0278364917712421 · Cited by 350
Feedback control of quantum state reduction
van Handel, R., Stockton, J. K., & Mabuchi, H. (2005) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2005.849193 · Cited by 320
LMI Relaxations in Robust Control
Scherer, C. W. (2006) · European Journal of Control · doi:10.3166/ejc.12.3-29 · Cited by 312
Briat, C. (2013) · Automatica · doi:10.1016/j.automatica.2013.08.022 · Cited by 268
An Introduction to Polynomial and Semi-Algebraic Optimization
Lasserre, J. B. (2015) · Cambridge University Press eBooks · doi:10.1017/cbo9781107447226 · Cited by 260
Mélykúti, B., August, E., Papachristodoulou, A., & El-Samad, H. (2010) · BMC Systems Biology · doi:10.1186/1752-0509-4-38 · Cited by 58
Learning dynamic polynomial proofs
Fawzi, A., Malinowski, M., Fawzi, H., & Fawzi, O. (2019) · arXiv · doi:10.48550/arxiv.1906.01681 · Cited by 8
Metadata
- Authors
- Parrilo, P. A.
- Published
- 2000-01-01
- OpenAlex
- W2133404041
- Cited by
- 1,802
- References
- 28
- FWCI
- 18.36
- 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.