ref_LMI_and_SDP.bib

@book{blekhermanSemidefiniteOptimizationConvex2013,
  title = {Semidefinite {{Optimization}} and {{Convex Algebraic Geometry}}},
  editor = {Blekherman, Grigoriy and Parrilo, Pablo A. and Thomas, Rekha},
  year = {2013},
  month = mar,
  publisher = {{Society for Industrial and Applied Mathematics}},
  address = {Philadelphia},
  url = {http://www.mit.edu/~parrilo/sdocag/},
  isbn = {978-1-61197-228-3},
  langid = {english}
}

@techreport{boydEE363ReviewSession2008,
  type = {Lecture Notes for {{EE363}}},
  title = {{{EE363 Review Session}} 4: {{Linear Matrix Inequalities}}},
  author = {Boyd, Stephen},
  year = {2008},
  address = {Stanford, CA},
  institution = {Stanford University},
  url = {https://stanford.edu/class/ee363/sessions/s4notes.pdf},
  urldate = {2024-08-22}
}

@book{boydLinearMatrixInequalities1994,
  title = {Linear {{Matrix Inequalities}} in {{System}} and {{Control Theory}}},
  author = {Boyd, Stephen and El Ghaoui, Laurent and Feron, Eric and Balakrishnan, Venkataramanan},
  year = {1994},
  month = jan,
  series = {Studies in {{Applied}} and {{Numerical Mathematics}}},
  publisher = {{Society for Industrial and Applied Mathematics}},
  url = {https://web.stanford.edu/~boyd/lmibook/},
  urldate = {2021-04-16},
  abstract = {The basic topic of this book is solving problems from system and control theory using convex optimization. We show that a wide variety of problems arising in system and control theory can be reduced to a handful of standard convex and quasiconvex optimization problems that involve matrix inequalities. For a few special cases there are ``analytic solutions'' to these problems, but our main point is that they can be solved numerically in all cases. These standard problems can be solved in polynomial-time (by, e.g., the ellipsoid algorithm of Shor, Nemirovskii, and Yudin), and so are tractable, at least in a theoretical sense. Recently developed interior-point methods for these standard problems have been found to be extremely efficient in practice. Therefore, we consider the original problems from system and control theory as solved. This book is primarily intended for the researcher in system and control theory, but can also serve as a source of application problems for researchers in convex optimization. Although we believe that the methods described in this book have great practical value, we should warn the reader whose primary interest is applied control engineering. This is a research monograph: We present no specific examples or numerical results, and we make only brief comments about the implications of the results for practical control engineering. To put it in a more positive light, we hope that this book will later be considered as the first book on the topic, not the most readable or accessible. The background required of the reader is knowledge of basic system and control theory and an exposure to optimization. Sontag's book Mathematical Control Theory [Son90] is an excellent survey. Further background material is covered in the texts Linear Systems [Kai80] by Kailath, Nonlinear Systems Analysis [Vid92] by Vidyasagar, Optimal Control: Linear Quadratic Methods [AM90] by Anderson and Moore, and Convex Analysis and Minimization Algorithms I [HUL93] by Hiriart-Urruty and Lemar{\'e}chal. We also highly recommend the book Interior-point Polynomial Algorithms in Convex Programming [NN94] by Nesterov and Nemirovskii as a companion to this book. The reader will soon see that their ideas and methods play a critical role in the basic idea presented in this book.},
  isbn = {978-0-89871-485-2}
}

@techreport{boydSolvingSemidefinitePrograms,
  type = {Lecture Notes for {{EE363}}},
  title = {Solving Semidefinite Programs Using Cvx},
  author = {Boyd, Stephen},
  year = {2008},
  address = {Stanford, CA},
  institution = {Stanford University},
  url = {https://stanford.edu/class/ee363/notes/lmi-cvx.pdf},
  urldate = {2024-08-22}
}

@article{derinkuyuSprocedureVariants2006,
  title = {On the {{S-procedure}} and {{Some Variants}}},
  author = {Derinkuyu, K{\"u}r{\c s}ad and P{\i}nar, Mustafa {\c C}.},
  year = {2006},
  month = aug,
  journal = {Mathematical Methods of Operations Research},
  volume = {64},
  number = {1},
  pages = {55--77},
  issn = {1432-5217},
  doi = {10.1007/s00186-006-0070-8},
  url = {https://doi.org/10.1007/s00186-006-0070-8},
  urldate = {2022-07-28},
  abstract = {We give a concise review and extension of S-procedure that is an instrumental tool in control theory and robust optimization analysis. We also discuss the approximate S-Lemma as well as its applications in robust optimization.},
  langid = {english}
}

@book{elghaouiAdvancesLinearMatrix2000,
  title = {Advances in {{Linear Matrix Inequality Methods}} in {{Control}}},
  editor = {El Ghaoui, Laurent and Niculescu, Silviu-lulian},
  year = {2000},
  month = jan,
  series = {Advances in {{Design}} and {{Control}}},
  publisher = {{Society for Industrial and Applied Mathematics}},
  url = {http://epubs.siam.org/doi/book/10.1137/1.9780898719833},
  urldate = {2016-05-24},
  abstract = {Linear matrix inequalities (LMIs) have emerged recently as a useful tool for solving a number of control problems. The basic idea of the LMI method in control is to interpret a given control problem as a semidefinite programming (SDP) problem, i.e., an optimization problem with linear objective and positive semidefinite constraints involving symmetric matrices that are affine in the decision variables. The LMI formalism is relevant for many reasons. First, writing a given problem in this form brings an efficient, numerical solution. Also, the approach is particularly suited to problems with ``uncertain'' data and multiple (possibly conflicting) specifications. Finally, this approach seems to be widely applicable, not only in control, but also in other areas where uncertainty arises. Purpose and intended audience Since the early 1990s, with the developement of interior-point methods for solving SDP problems, the LMI approach has witnessed considerable attention in the control area (see the regularity of the invited sessions in the control conferences and workshops). Up to now, two self-contained books related to this subject have appeared. The book Interior Point Polynomial Methods in Convex Programming: Theory and Applications, by Nesterov and Nemirovskii, revolutionarized the field of optimization by showing that a large class of nonlinear convex programming problems (including SDP) can be solved very efficiently. A second book, also published by SIAM in 1994, Linear Matrix Inequalities in System and Control Theory, by Boyd, El Ghaoui, Feron, and Balakrishnan, shows that the advances in convex optimization can be successfully applied to a wide variety of difficult control problems. At this point, a natural question arises: Why another book on LMIs? One aim of this book is to describe, for the researcher in the control area, several important advances made both in algorithms and software and in the important issues in LMI control pertaining to analysis, design, and applications. Another aim is to identify several important issues, both in control and optimization, that need to be addressed in the future. We feel that these challenging issues require an interdisciplinary research effort, which we sought to foster. For example, Chapter 1 uses an optimization formalism, in the hope of encouraging researchers in optimization to look at some of the important ideas in LMI control (e.g., deterministic uncertainty, robustness) and seek nonclassical applications and challenges in the control area. Bridges go both ways, of course: for example, the ``primal-dual'' point of view that is so successful in optimization is also important in control.},
  isbn = {978-0-89871-438-8},
  annotation = {00397}
}

@article{heltonLinearMatrixInequality2003,
  title = {Linear {{Matrix Inequality Representation}} of {{Sets}}},
  author = {Helton, J. William and Vinnikov, Victor},
  year = {2003},
  month = jun,
  journal = {math/0306180},
  eprint = {math/0306180},
  url = {http://arxiv.org/abs/math/0306180},
  urldate = {2010-04-21},
  abstract = {This article concerns the question: which subsets of \$\{{\textbackslash}mathbb R\}{\textasciicircum}m\$ can be represented with Linear Matrix Inequalities, LMIs? This gives some perspective on the scope and limitations of one of the most powerful techniques commonly used in control theory. Also before having much hope of representing engineering problems as LMIs by automatic methods one needs a good idea of which problems can and cannot be represented by LMIs. Little is currently known about such problems. In this article we give a necessary condition, we call "rigid convexity", which must hold for a set \$\{{\textbackslash}cC\} {\textbackslash}in \{{\textbackslash}mathbb R\}{\textasciicircum}m\$ in order for \$\{{\textbackslash}cC\}\$ to have an LMI representation. Rigid convexity is proved to be necessary and sufficient when \$m=2\$. This settles a question formally stated by Pablo Parrilo and Berndt Sturmfels in [PSprep].},
  archiveprefix = {arXiv}
}

@article{henrionLinearMatrixInequalities2002,
  title = {Linear Matrix Inequalities for Robust Strictly Positive Real Design},
  author = {Henrion, D.},
  year = {2002},
  journal = {Circuits and Systems I: Fundamental Theory and Applications, IEEE Transactions on},
  volume = {49},
  number = {7},
  pages = {1017--1020},
  issn = {1057-7122},
  doi = {10.1109/TCSI.2002.800838},
  abstract = {A necessary and sufficient condition is proposed for the existence of a polynomial p(s) such that the rational function p(s)/q(s) is robustly strictly positive real when q(s) is a given Hurwitz polynomial with polytopic uncertainty. It turns out that the whole set of candidates p(s) is a convex subset of the cone of positive semidefinite matrices, resulting in a straightforward strictly positive real design algorithm based on linear matrix inequalities}
}

@phdthesis{henrionMeasuresLinearMatrix2012,
  type = {Czech Professorship Inaugural Lecture Manuscript},
  title = {Measures and Linear Matrix Inequalities in Polynomial Optimal Control},
  author = {Henrion, Didier},
  year = {2012},
  address = {Prague},
  url = {http://homepages.laas.fr/henrion/Papers/henrionprof.pdf},
  urldate = {2014-04-18},
  school = {Czech Technical University in Prague}
}

@misc{lofbergSemidefiniteProgramming2016,
  title = {Semidefinite Programming},
  author = {Lofberg, Johan},
  year = {2016},
  month = sep,
  url = {https://yalmip.github.io/tutorial/semidefiniteprogramming/},
  urldate = {2024-08-22},
  abstract = {Who wudda thought? Optimization over positive definite symmetric matrices is easy.}
}

@misc{majumdarSurveyRecentScalability2019,
  title = {A {{Survey}} of {{Recent Scalability Improvements}} for {{Semidefinite Programming}} with {{Applications}} in {{Machine Learning}}, {{Control}}, and {{Robotics}}},
  author = {Majumdar, Anirudha and Hall, Georgina and Ahmadi, Amir Ali},
  year = {2019},
  month = dec,
  number = {arXiv:1908.05209},
  eprint = {1908.05209},
  primaryclass = {cs, eess, math},
  publisher = {arXiv},
  doi = {10.48550/arXiv.1908.05209},
  url = {http://arxiv.org/abs/1908.05209},
  urldate = {2023-09-15},
  abstract = {Historically, scalability has been a major challenge to the successful application of semidefinite programming in fields such as machine learning, control, and robotics. In this paper, we survey recent approaches for addressing this challenge including (i) approaches for exploiting structure (e.g., sparsity and symmetry) in a problem, (ii) approaches that produce low-rank approximate solutions to semidefinite programs, (iii) more scalable algorithms that rely on augmented Lagrangian techniques and the alternating direction method of multipliers, and (iv) approaches that trade off scalability with conservatism (e.g., by approximating semidefinite programs with linear and second-order cone programs). For each class of approaches we provide a high-level exposition, an entry-point to the corresponding literature, and examples drawn from machine learning, control, or robotics. We also present a list of software packages that implement many of the techniques discussed in the paper. Our hope is that this paper will serve as a gateway to the rich and exciting literature on scalable semidefinite programming for both theorists and practitioners.},
  archiveprefix = {arXiv}
}

@article{polikSurveySLemma2007,
  title = {A {{Survey}} of the {{S-Lemma}}},
  author = {P{\'o}lik, Imre and Terlaky, Tam{\'a}s},
  year = {2007},
  month = jan,
  journal = {SIAM Review},
  volume = {49},
  number = {3},
  pages = {371--418},
  publisher = {{Society for Industrial and Applied Mathematics}},
  issn = {0036-1445},
  doi = {10.1137/S003614450444614X},
  url = {https://epubs.siam.org/doi/abs/10.1137/S003614450444614X},
  urldate = {2022-07-28},
  abstract = {In this survey we review the many faces of the S-lemma, a result about the correctness of the S-procedure. The basic idea of this widely used method came from control theory but it has important consequences in quadratic and semidefinite optimization, convex geometry, and linear algebra as well. These were all active research areas, but as there was little interaction between researchers in these different areas, their results remained mainly isolated. Here we give a unified analysis of the theory by providing three different proofs for the S-lemma and revealing hidden connections with various areas of mathematics. We prove some new duality results and present applications from control theory, error estimation, and computational geometry.}
}

@unpublished{schererLinearMatrixInequalities2015,
  type = {Lecture Notes},
  title = {Linear Matrix Inequalities in Control},
  author = {Scherer, Carsten W. and Weiland, Siep},
  year = {2015},
  month = jan,
  url = {https://www.imng.uni-stuttgart.de/mst/files/LectureNotes.pdf},
  urldate = {2021-04-16},
  annotation = {00492}
}

@article{uhligRecurringTheoremPairs1979,
  title = {A Recurring Theorem about Pairs of Quadratic Forms and Extensions: A Survey},
  shorttitle = {A Recurring Theorem about Pairs of Quadratic Forms and Extensions},
  author = {Uhlig, Frank},
  year = {1979},
  month = jun,
  journal = {Linear Algebra and its Applications},
  volume = {25},
  pages = {219--237},
  issn = {0024-3795},
  doi = {10.1016/0024-3795(79)90020-X},
  url = {https://www.sciencedirect.com/science/article/pii/002437957990020X},
  urldate = {2022-07-28},
  abstract = {This is a historical and mathematical survey of work on necessary and sufficient conditions for a pair of quadratic forms to admit a positive definite linear combination and various extensions thereof.},
  langid = {english}
}

@article{vanantwerpTutorialLinearBilinear2000,
  title = {A Tutorial on Linear and Bilinear Matrix Inequalities},
  author = {VanAntwerp, Jeremy G. and Braatz, Richard D.},
  year = {2000},
  month = aug,
  journal = {Journal of Process Control},
  volume = {10},
  number = {4},
  pages = {363--385},
  issn = {0959-1524},
  doi = {10.1016/S0959-1524(99)00056-6},
  url = {http://www.sciencedirect.com/science/article/pii/S0959152499000566},
  urldate = {2016-05-24},
  abstract = {This is a tutorial on the mathematical theory and process control applications of linear matrix inequalities (LMIs) and bilinear matrix inequalities (BMIs). Many convex inequalities common in process control applications are shown to be LMIs. Proofs are included to familiarize the reader with the mathematics of LMIs and BMIs. LMIs and BMIs are applied to several important process control applications including control structure selection, robust controller analysis and design, and optimal design of experiments. Software for solving LMI and BMI problems is reviewed.},
  annotation = {00368}
}

@article{vandenbergheSemidefiniteProgramming1996,
  title = {Semidefinite {{Programming}}},
  author = {Vandenberghe, Lieven and Boyd, Stephen},
  year = {1996},
  month = mar,
  journal = {SIAM Review},
  volume = {38},
  number = {1},
  pages = {49--95},
  publisher = {{Society for Industrial and Applied Mathematics}},
  issn = {0036-1445},
  doi = {10.1137/1038003},
  url = {https://epubs.siam.org/doi/abs/10.1137/1038003},
  urldate = {2024-09-06},
  abstract = {This paper studies the semidefinite programming SDP problem, i.e., the optimization problem of a linear function of a symmetric matrix subject to linear equality constraints and the additional condition that the matrix be positive semidefinite. First the classical cone duality is reviewed as it is specialized to SDP is reviewed. Next an interior point algorithm is presented that converges to the optimal solution in polynomial time. The approach is a direct extension of Ye's projective method for linear programming. It is also argued that many known interior point methods for linear programs can be transformed in a mechanical way to algorithms for SDP with proofs of convergence and polynomial time complexity carrying over in a similar fashion. Finally, the significance of these results is studied in a variety of combinatorial optimization problems including the general 0-1 integer programs, the maximum clique and maximum stable set problems in perfect graphs, the maximum k-partite subgraph problem in graphs, and various graph partitioning and cut problems. As a result, barrier oracles are presented for certain combinatorial optimization problems (in particular, clique and stable set problem for perfect graphs) whose linear programming formulation requires exponentially many inequalities. Existence of such barrier oracles refutes the commonly believed notion that to solve a combinatorial optimization problem with interior point methods, its linear programming formulation is eeded explicitly.}
}