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.
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
(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
Approximation Algorithms for NP-Hard Problems
(1997) · ACM SIGACT News · doi:10.1145/261342.571216 · Cited by 3,103
The Linear Complementarity Problem
Cottle, R. W., Pang, J.-S., & Stone, R. E. (2009) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9780898719000 · Cited by 2,788
(1993) · Choice Reviews Online · doi:10.5860/choice.30-5053 · Cited by 2,034
System analysis via integral quadratic constraints
Megretski, A., & Rantzer, A. (1997) · IEEE Transactions on Automatic Control · doi:10.1109/9.587335 · Cited by 1,521
Olmsted, J. M. H., Kolmogorov, A. N., Fomin, S. V., & Silverman, R. A. (1971) · The American Mathematical Monthly · doi:10.2307/2316932 · Cited by 1,397
(2014) · Choice Reviews Online · doi:10.5860/choice.51-3296 · Cited by 1,260
Computation of piecewise quadratic Lyapunov functions for hybrid systems
Johansson, M., & Rantzer, A. (1998) · IEEE Transactions on Automatic Control · doi:10.1109/9.664157 · Cited by 1,222
Cones 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
Some NP-complete problems in quadratic and nonlinear programming
Murty, K. G., & Kabadi, S. N. (1987) · Mathematical Programming · doi:10.1007/bf02592948 · Cited by 1,003
Sherali, H. D., & Adams, W. P. (1990) · SIAM Journal on Discrete Mathematics · doi:10.1137/0403036 · Cited by 931
On the Kalman—Yakubovich—Popov lemma
Rantzer, A. (1996) · Systems & Control Letters · doi:10.1016/0167-6911(95)00063-1 · Cited by 927
A bisection method for computing the H∞ norm of a transfer matrix and related problems
Boyd, S., Balakrishnan, V., & Kabamba, P. T. (1989) · Mathematics of Control Signals and Systems · doi:10.1007/bf02551385 · Cited by 443
Mishra, B. (1993) · Springer eBooks · doi:10.1007/978-1-4612-4344-1 · Cited by 310
On the rank minimization problem over a positive semidefinite linear matrix inequality
Mesbahi, M., & Papavassilopoulos, G. P. (1997) · IEEE Transactions on Automatic Control · doi:10.1109/9.554402 · Cited by 187
A new bound for Pólya's Theorem with applications to polynomials positive on polyhedra
Powers, V., & Reznick, B. (2001) · Journal of Pure and Applied Algebra · doi:10.1016/s0022-4049(00)00155-9 · Cited by 179
Computing a closest bifurcation instability in multidimensional parameter space
Dobson, I. (1993) · Journal of Nonlinear Science · doi:10.1007/bf02429868 · Cited by 123
Polynomial Equations and Convex Polytopes
Sturmfels, B. (1998) · American Mathematical Monthly · doi:10.1080/00029890.1998.12004987 · Cited by 92
Copositive realxation for genera quadratic programming
Quist, A. J., de Klerk, E., Roos, C., & Tamás Terlaky, B. (1998) · Optimization methods & software · doi:10.1080/10556789808805692 · Cited by 65
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
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.