A Survey of the S-Lemma

DOI10.1137/S003614450444614XzbMath1128.90046OpenAlexW2140214428WikidataQ124887919 ScholiaQ124887919MaRDI QIDQ5757476

Tamás Terlaky, Imre Pólik

Publication date: 7 September 2007

Published in: SIAM Review (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s003614450444614x

zbMATH Keywords

numerical rangecontrol theorysemidefinite optimizationS-procedureS-lemmarelaxation theorygeneralized convexitiesnonconvex theorem of alternatives

Mathematics Subject Classification ID

Semidefinite programming (90C22) Nonconvex programming, global optimization (90C26) Quadratic programming (90C20) Stability of solutions to ordinary differential equations (34D20) Convexity of real functions of several variables, generalizations (26B25) Numerical methods of relaxation type (49M20)

Related Items

On Local Minimizers of Nonconvex Homogeneous Quadratically Constrained Quadratic Optimization with at Most Two Constraints, Robust Network Design with Uncertain Outsourcing Cost, Solving a class of non-convex quadratic problems based on generalized KKT conditions and neurodynamic optimization technique, On Obtaining the Convex Hull of Quadratic Inequalities via Aggregations, Observer-based output feedback control of discrete-time Luré systems with sector-bounded slope-restricted nonlinearities, Interplay of non-convex quadratically constrained problems with adjustable robust optimization, Improved reachable set estimation for positive systems: a polyhedral approach, Improving the Performance of MIQP Solvers for Quadratic Programs with Cardinality and Minimum Threshold Constraints: A Semidefinite Program Approach, Probabilistic reachable and invariant sets for linear systems with correlated disturbance, Toward nonquadratic S-lemma: new theory and application in nonconvex optimization, Indefinite least squares with a quadratic constraint, A Second-Order Cone Based Approach for Solving the Trust-Region Subproblem and Its Variants, Quaternion matrix decomposition and its theoretical implications, Ellipsoidal load-domain shakedown analysis with von Mises yield criterion: A robust optimization approach, Optimization under uncertainty and risk: quadratic and copositive approaches, The smallest mono-unstable convex polyhedron with point masses has 8 faces and 11 vertices, Distributionally robust expected residual minimization for stochastic variational inequality problems, Implicit Regularity and Linear Convergence Rates for the Generalized Trust-Region Subproblem, Quadratic Matrix Inequalities with Applications to Data-Based Control, Invariance Conditions for Nonlinear Dynamical Systems, Separating disconnected quadratic level sets by other quadratic level sets, Reachable set estimation for positive linear discrete-time systems under the constrained disturbance, Aggregations of Quadratic Inequalities and Hidden Hyperplane Convexity, Extremality and rigidity for scalar curvature in dimension four, Polyak's theorem on Hilbert spaces, Computation of parameter dependent robust invariant sets for LPV models with guaranteed performance, Effective algorithms for separable nonconvex quadratic programming with one quadratic and box constraints, Quadratically adjustable robust linear optimization with inexact data via generalized S-lemma: exact second-order cone program reformulations, The Yakubovich S-Lemma Revisited: Stability and Contractivity in Non-Euclidean Norms, Exact SDP relaxations for quadratic programs with bipartite graph structures, Distributionally robust Weber problem with uncertain demand, Effective algorithms for optimal portfolio deleveraging problem with cross impact, Simultaneous Hollowization, Joint Numerical Range, and Stabilization by Noise, New bounds for nonconvex quadratically constrained quadratic programming, Calabi-Polyak convexity theorem, Yuan'S lemma and S-lemma: extensions and applications, Erratum: On The Aubin Property of Critical Points to Perturbed Second-Order Cone Programs, Linear pencils and quadratic programming problems with a quadratic constraint, Non-quadratic extension of homogeneous S-lemma and its applications in optimization, Optimal recovery from inaccurate data in Hilbert spaces: regularize, but what of the parameter?, Unnamed Item, Minimizing an indefinite quadratic function subject to a single indefinite quadratic constraint, An Iterative Scheme for Valid Polynomial Inequality Generation in Binary Polynomial Programming, A Note on Polynomial Solvability of the CDT Problem, Symmetry of convex sets and its applications to the extremal ellipsoids of convex bodies, On the global optimality of generalized trust region subproblems, Intersection cuts for nonlinear integer programming: convexification techniques for structured sets, Maximizing the sum of a generalized Rayleigh quotient and another Rayleigh quotient on the unit sphere via semidefinite programming, Complexity, exactness, and rationality in polynomial optimization, On Conic Relaxations of Generalization of the Extended Trust Region Subproblem, Solving a Type of the Tikhonov Regularization of the Total Least Squares by a New S-Lemma, Complexity, exactness, and rationality in polynomial optimization, Chebyshev Inequalities for Products of Random Variables, Risk-Averse Two-Stage Stochastic Program with Distributional Ambiguity, An SDP approach for quadratic fractional problems with a two-sided quadratic constraint, Novel Reformulations and Efficient Algorithms for the Generalized Trust Region Subproblem, Canonical Dual Solutions to Quadratic Optimization over One Quadratic Constraint, On minimizing the ratio of quadratic functions over an ellipsoid, Characterizing Convexity of Images for Quadratic-Linear Mappings with Applications in Nonconvex Quadratic Optimization, A Linear-Time Algorithm for Generalized Trust Region Subproblems, Connectivity of Quadratic Hypersurfaces and Its Applications in Optimization, Part I: General Theory, The distributionally robust complementarity problem, Stability and stabilisation of a class of networked dynamic systems, A tensor analogy of Yuan's theorem of the alternative and polynomial optimization with sign structure, Some applications of polynomial optimization in operations research and real-time decision making, Generalized Farkas' lemma and gap-free duality for minimax DC optimization with polynomials and robust quadratic optimization, A fresh geometrical look at the general S-procedure, Removing inessential points in \(c\)-and \(A\)-optimal design, On the spherical quasi-convexity of quadratic functions on spherically subdual convex sets, On distributional robust probability functions and their computations, Geometric properties for level sets of quadratic functions, Learning from non-random data in Hilbert spaces: an optimal recovery perspective, Robust chance-constrained support vector machines with second-order moment information, Quantum entanglement, symmetric nonnegative quadratic polynomials and moment problems, On the local stability of semidefinite relaxations, Reduction of joint \(c\)-numerical ranges, Distributionally robust optimization with matrix moment constraints: Lagrange duality and cutting plane methods, SOCP reformulation for the generalized trust region subproblem via a canonical form of two symmetric matrices, Generating cutting planes for the semidefinite relaxation of quadratic programs, Robust international portfolio optimization with worst-case mean-CVaR, Generalized S-lemma and strong duality in nonconvex quadratic programming, Theorems of the alternative revisited and some extensions of Yuan's lemma, Frameworks and results in distributionally robust optimization, On the set-semidefinite representation of nonconvex quadratic programs over arbitrary feasible sets, On Lagrangian duality gap of quadratic fractional programming with a two-sided quadratic constraint, Necessary and sufficient conditions for \(S\)-lemma and~nonconvex quadratic optimization, An extension of Yuan's lemma and its applications in optimization, A survey of hidden convex optimization, How to solve a design centering problem, Sum-of-squares methods for controlled invariant sets with applications to model-predictive control, Distributionally robust chance-constrained games: existence and characterization of Nash equilibrium, Positive operators on extended second order cones, Safety verification for distributed parameter systems using barrier functionals, Comments on ``On the indefinite quadratic fractional optimization with two quadratic constraints, Generalized positiveness of spatially interconnected systems over quadratically constrained frequency domains, Theorems of the alternative for multivalued mappings and applications to mixed convex \(\backslash\) concave systems of inequalities, Regularized Lagrangian duality for linearly constrained quadratic optimization and trust-region problems, A real nullstellensatz for free modules, Convex optimization approach to a single quadratically constrained quadratic minimization problem, Robust solutions of quadratic optimization over single quadratic constraint under interval uncertainty, Distributionally robust joint chance constraints with second-order moment information, On zero duality gap in nonconvex quadratic programming problems, Think co(mpletely)positive! Matrix properties, examples and a clustered bibliography on copositive optimization, An extension of the KYP-lemma for the design of state-dependent switching systems with uncertainty, Hidden conic quadratic representation of some nonconvex quadratic optimization problems, Application of a multiplier method to uncertain Lur'e-like systems, A Kalman-Yakubovich-Popov-type lemma for systems with certain state-dependent constraints, Maximum likelihood identification of stable linear dynamical systems, The generalized trust region subproblem, Semidefinite relaxation and new conditions for sign-definiteness of the quadratic form under quadratic constraints, Eigenvalue-based algorithm and analysis for nonconvex QCQP with one constraint, On weak conjugacy, augmented Lagrangians and duality in nonconvex optimization, Farkas' lemma: three decades of generalizations for mathematical optimization, Robust quadratic regression and its application to energy-growth consumption problem, Convexity of the image of a quadratic map via the relative entropy distance, Robust duality for generalized convex programming problems under data uncertainty, The distributionally robust optimization reformulation for stochastic complementarity problems, Finsler's lemma for matrix polynomials, Roofs and convexity, An extension of Yuan's lemma to fourth-order tensor system, A novel unified approach to invariance conditions for a linear dynamical system, On local convexity of quadratic transformations, Robust linear MIMO in the downlink: A worst-case optimization with ellipsoidal uncertainty regions, The complexity of optimizing over a simplex, hypercube or sphere: a short survey, Distributionally robust multi-item newsvendor problems with multimodal demand distributions, The sum-of-squares hierarchy on the sphere and applications in quantum information theory, Strong duality for generalized trust region subproblem: S-lemma with interval bounds, A survey of adjustable robust optimization, Extensions of the standard quadratic optimization problem: strong duality, optimality, hidden convexity and S-lemma, Distributionally robust chance constrained problems under general moments information, A linear-time algorithm for minimizing the ratio of quadratic functions with a quadratic constraint, How to convexify the intersection of a second order cone and a nonconvex quadratic, An efficient global optimization algorithm for maximizing the sum of two generalized Rayleigh quotients, Robust tracking error portfolio selection with worst-case downside risk measures, A geometric characterization of strong duality in nonconvex quadratic programming with linear and nonconvex quadratic constraints, A copositive approach for two-stage adjustable robust optimization with uncertain right-hand sides, All Models are Wrong, but Many are Useful: Learning a Variable's Importance by Studying an Entire Class of Prediction Models Simultaneously, Theorems of the alternative for inequality systems of real polynomials, New results on Hermitian matrix rank-one decomposition, A new algorithm for concave quadratic programming, Semidefinite relaxations for quadratically constrained quadratic programming: A review and comparisons, Maximizing perturbation radii for robust convex quadratically constrained quadratic programs, Lagrange multiplier necessary conditions for global optimality for non-convex minimization over a quadratic constraint via S-lemma, Global optimality condition for quadratic optimization problems under data uncertainty, Positive semidefinite rank, Strong duality in minimizing a quadratic form subject to two homogeneous quadratic inequalities over the unit sphere, Exact SDP reformulations of adjustable robust linear programs with box uncertainties under separable quadratic decision rules via SOS representations of non-negativity, On fractional quadratic optimization problem with two quadratic constraints, Convexity properties associated with nonconvex quadratic matrix functions and applications to quadratic programming, On the convexity for the range set of two quadratic functions, Matrix pencils and existence conditions for quadratic programming with a sign-indefinite quadratic equality constraint, Indefinite abstract splines with a quadratic constraint, Ricci flow does not preserve positive sectional curvature in dimension four, Novel results on robust control under structured uncertainties, On minimizing a quadratic function on Stiefel manifold, Narrowing the difficulty gap for the Celis-Dennis-Tapia problem, Exact SDP relaxations of quadratically constrained quadratic programs with forest structures, Review on computational methods for Lyapunov functions, Quantitative stability analysis for minimax distributionally robust risk optimization, The generalized trust region subproblem: solution complexity and convex hull results, A dynamic inequality generation scheme for polynomial programming, Generalized Gauss inequalities via semidefinite programming, S-lemma with equality and its applications