A survey of the S-lemma
---
paper_title: Topics in matrix analysis

paper_content:

1. The field of values 2. Stable matrices and inertia 3. Singular value inequalities 4. Matrix equations and Kronecker products 5. Hadamard products 6. Matrices and functions.
---
paper_title: Trust Region Methods

paper_content:

Preface 1. Introduction Part I. Preliminaries: 2. Basic Concepts 3. Basic Analysis and Optimality Conditions 4. Basic Linear Algebra 5. Krylov Subspace Methods Part II. Trust-Region Methods for Unconstrained Optimization: 6. Global Convergence of the Basic Algorithm 7.The Trust-Region Subproblem 8. Further Convergence Theory Issues 9. Conditional Models 10. Algorithmic Extensions 11. Nonsmooth Problems Part III. Trust-Region Methods for Constrained Optimization with Convex Constraints: 12. Projection Methods for Convex Constraints 13. Barrier Methods for Inequality Constraints Part IV. Trust-Region Mewthods for General Constained Optimization and Systems of Nonlinear Equations: 14. Penalty-Function Methods 15. Sequential Quadratic Programming Methods 16. Nonlinear Equations and Nonlinear Fitting Part V. Final Considerations: Practicalities Afterword Appendix: A Summary of Assumptions Annotated Bibliography Subject and Notation Index Author Index.
---
paper_title: On Cones of Nonnegative Quadratic Functions

paper_content:

We derive linear matrix inequality (LMI) characterizations and dual decomposition algorithms for certain matrix cones which are generated by a given set using generalized co-positivity. These matrix cones are in fact cones of nonconvex quadratic functions that are nonnegative on a certain domain. As a domain, we consider for instance the intersection of a (upper) level-set of a quadratic function and a half-plane. Consequently, we arrive at a generalization of Yakubovich's S-procedure result. Although the primary concern of this paper is to characterize the matrix cones by LMIs, we show, as an application of our results, that optimizing a general quadratic function over the intersection of an ellipsoid and a half-plane can be formulated as semidefinite programming (SDP), thus proving the polynomiality of this class of optimization problems, which arise, e.g., from the application of the trust region method for nonlinear programming. Other applications are in control theory and robust optimization.
---
paper_title: On a subproblem of trust region algorithms for constrained optimization

paper_content:

We study a subproblem that arises in some trust region algorithms for equality constrained optimization. It is the minimization of a general quadratic function with two special quadratic constraints. Properties of such subproblems are given. It is proved that the Hessian of the Lagrangian has at most one negative eigenvalue, and an example is presented to show that the Hessian may have a negative eigenvalue when one constraint is inactive at the solution.
---
paper_title: Multivariate nonnegative quadratic mappings

paper_content:

In this paper, we study several issues related to the characterization of specific classes of multivariate quadratic mappings that are nonnegative over a given domain, with nonnegativity defined by a prespecified conic order. In particular, we consider the set (cone) of nonnegative quadratic mappings, defined with respect to the positive semidefinite matrix cone, and study when it can be represented by linear matrix inequalities. We also discuss the applications of the results in robust optimization, especially the robust quadratic matrix inequalities and the robust linear programming models. In the latter application the implementational errors of the solution are taken into account, and the problem is formulated as a semidefinite program.
---
paper_title: On Cones of Nonnegative Quadratic Functions

paper_content:

We derive linear matrix inequality (LMI) characterizations and dual decomposition algorithms for certain matrix cones which are generated by a given set using generalized co-positivity. These matrix cones are in fact cones of nonconvex quadratic functions that are nonnegative on a certain domain. As a domain, we consider for instance the intersection of a (upper) level-set of a quadratic function and a half-plane. Consequently, we arrive at a generalization of Yakubovich's S-procedure result. Although the primary concern of this paper is to characterize the matrix cones by LMIs, we show, as an application of our results, that optimizing a general quadratic function over the intersection of an ellipsoid and a half-plane can be formulated as semidefinite programming (SDP), thus proving the polynomiality of this class of optimization problems, which arise, e.g., from the application of the trust region method for nonlinear programming. Other applications are in control theory and robust optimization.
---
paper_title: On Cones of Nonnegative Quadratic Functions

paper_content:

We derive linear matrix inequality (LMI) characterizations and dual decomposition algorithms for certain matrix cones which are generated by a given set using generalized co-positivity. These matrix cones are in fact cones of nonconvex quadratic functions that are nonnegative on a certain domain. As a domain, we consider for instance the intersection of a (upper) level-set of a quadratic function and a half-plane. Consequently, we arrive at a generalization of Yakubovich's S-procedure result. Although the primary concern of this paper is to characterize the matrix cones by LMIs, we show, as an application of our results, that optimizing a general quadratic function over the intersection of an ellipsoid and a half-plane can be formulated as semidefinite programming (SDP), thus proving the polynomiality of this class of optimization problems, which arise, e.g., from the application of the trust region method for nonlinear programming. Other applications are in control theory and robust optimization.
---
paper_title: Convexity of quadratic transformations and its use in control and optimization

paper_content:

Quadratic transformations have the hidden convexity property which allows one to deal with them as if they were convex functions. This phenomenon was encountered in various optimization and control problems, but it was not always recognized as consequence of some general property. We present a theory on convexity and closedness of a 3D quadratic image of ℝn, n≥3, which explains many disjoint known results and provides some new ones.
---
paper_title: Degenerate Nonlinear Programming with a Quadratic Growth Condition

paper_content:

We show that the quadratic growth condition and the Mangasarian--Fromovitz constraint qualification (MFCQ) imply that local minima of nonlinear programs are isolated stationary points. As a result, when started sufficiently close to such points, an $L_\infty$ exact penalty sequential quadratic programming algorithm will induce at least R-linear convergence of the iterates to such a local minimum. We construct an example of a degenerate nonlinear program with a unique local minimum satisfying the quadratic growth and the MFCQ but for which no positive semidefinite augmented Lagrangian exists. We present numerical results obtained using several nonlinear programming packages on this example and discuss its implications for some algorithms.
---
paper_title: An Energy Amplification Condition for Decentralized Adaptive Stabilization

paper_content:

The author is interested here in the problem of global decentralized adaptive regulation (of the plant output to zero) of square multivariable linear time-invariant systems without any restrictions on relative degrees or matching assumptions. The first solution to this problem was recently reported by the author using Morse's new dynamic certainty equivalent adaptive controller to prove that global stabilization is possible if the unmodeled interconnections do not induce "amplification of the energy of the signals in all channels". In this paper the author shows that to preserve global convergence, it is actually enough to have only one "nonamplifying channel". Instrumental for the establishment of the authors' result is the fundamental S-procedure losslessness theorem of Megretsky and Treil, together with some basic loop transformations and D-scalings.
---
paper_title: A Remark On The Rank Of Positive Semidefinite Matrices Subject To Affine Constraints

paper_content:

Let K n be the cone of positive semidefinite n X n matrices and let A be an affine subspace of the space of symmetric matrices such that the intersection K n ?A is nonempty and bounded. Suppose that n ? 3 and that \codim A = r+2 \choose 2 for some 1 ≤ r ≤ n-2 . Then there is a matrix X ? K n ?A such that rank X ≤ r . We give a short geometric proof of this result, use it to improve a bound on realizability of weighted graphs as graphs of distances between points in Euclidean space, and describe its relation to theorems of Bohnenblust, Friedland and Loewy, and Au-Yeung and Poon.
---
paper_title: Ridge regression: biased estimation for nonorthogonal problems

paper_content:

In multiple regression it is shown that parameter estimates based on minimum residual sum of squares have a high probability of being unsatisfactory, if not incorrect, if the prediction vectors are not orthogonal. Proposed is an estimation procedure based on adding small positive quantities to the diagonal of X′X. Introduced is the ridge trace, a method for showing in two dimensions the effects of nonorthogonality. It is then shown how to augment X′X to obtain biased estimates with smaller mean square error.
---
paper_title: A Superlinearly Convergent Sequential Quadratically Constrained Quadratic Programming Algorithm For Degenerate Nonlinear Programming

paper_content:

We present an algorithm that achieves superlinear convergence for nonlinear programs satisfying the Mangasarian--Fromovitz constraint qualification and the quadratic growth condition. This convergence result is obtained despite the potential lack of a locally convex augmented Lagrangian. The algorithm solves a succession of subproblems that have quadratic objectives and quadratic constraints, both possibly nonconvex. By the use of a trust-region constraint we guarantee that any stationary point of the subproblem induces superlinear convergence, which avoids the problem of computing a global minimum. We compare this algorithm with sequential quadratic programming algorithms on several degenerate nonlinear programs.
---
paper_title: Robust Portfolio Selection Problems

paper_content:

In this paper we show how to formulate and solve robust portfolio selection problems. The objective of these robust formulations is to systematically combat the sensitivity of the optimal portfolio to statistical and modeling errors in the estimates of the relevant market parameters. We introduce "uncertainty structures" for the market parameters and show that the robust portfolio selection problems corresponding to these uncertainty structures can be reformulated as second-order cone programs and, therefore, the computational effort required to solve them is comparable to that required for solving convex quadratic programs. Moreover, we show that these uncertainty structures correspond to confidence regions associated with the statistical procedures employed to estimate the market parameters. Finally, we demonstrate a simple recipe for efficiently computing robust portfolios given raw market data and a desired level of confidence.
---
paper_title: On some generalizations of convex sets and convex functions

paper_content:

A set $C$ in a topological vector space is said to be weakly convex if for any $x,y$ in $C$ there exists $p$ in $(0,1)$ such that $(1-p)x+py\in C$. If the same holds with $p$ independent of $x,y$, then $C$ is said to be $p$-convex. Some basic results are established for such sets, for instance: any weakly convex closed set is convex.
---
paper_title: ON THE RANK OF EXTREME MATRICES IN SEMIDEFINITE PROGRAMS AND THE MULTIPLICITY OF OPTIMAL EIGENVALUES

paper_content:

We derive some basic results on the geometry of semidefinite programming (SDP) and eigenvalue-optimization, i.e., the minimization of the sum of the k largest eigenvalues of a smooth matrix-valued function. We provide upper bounds on the rank of extreme matrices in SDPs, and the first theoretically solid explanation of a phenomenon of intrinsic interest in eigenvalue-optimization. In the spectrum of an optimal matrix, the kth and (k + 1)st largest eigenvalues tend to be equal and frequently have multiplicity greater than two. This clustering is intuitively plausible and has been observed as early as 1975. When the matrix-valued function is affine, we prove that clustering must occur at extreme points of the set of optimal solutions, if the number of variables is sufficiently large. We also give a lower bound on the multiplicity of the critical eigenvalue. These results generalize to the case of a general matrix-valued function under appropriate conditions.
---
paper_title: Convexity of the joint numerical range

paper_content:

Let A=(A1, . . ., Am) be an m-tuple of n × n Hermitian matrices. For $1 \le k \le n$, the $k${\rm th} joint numerical range of A is defined by $$W_k(A) = \{ ({\rm \tr}(X^*A_1X), \dots, {\rm \tr}(X^*A_mX) ): X \in {\bf C}^{n\times k}, X^*X = I_k \}.$$ We consider linearly independent families of Hermitian matrices {A1, . . . , Am} so that Wk(A) is convex. It is shown that m can reach the upper bound 2k(n-k)+1. A key idea in our study is relating the convexity of Wk(A) to the problem of constructing rank k orthogonal projections under linear constraints determined by A. The techniques are extended to study the convexity of other generalized numerical ranges and the corresponding matrix construction problems.
---
paper_title: Convexity of quadratic transformations and its use in control and optimization

paper_content:

Quadratic transformations have the hidden convexity property which allows one to deal with them as if they were convex functions. This phenomenon was encountered in various optimization and control problems, but it was not always recognized as consequence of some general property. We present a theory on convexity and closedness of a 3D quadratic image of ℝn, n≥3, which explains many disjoint known results and provides some new ones.
---
paper_title: ON THE FIELD OF VALUES OF A MATRIX

paper_content:

W is clearly a compact and connected set. Toeplitz showed in [3] that W has a convex outer boundary, and a short time later F. Hausdorff [1] proved that W itself is convex. Since then several investigations have been made concerning the geometry of W. An example of a recent one is the dissertation of R. Kippenhahn [2] in which W is described as the convex hull of a certain algebraic curve of degree n obtainable from C. Writing
---
paper_title: Convexity of the joint numerical range

paper_content:

Let A=(A1, . . ., Am) be an m-tuple of n × n Hermitian matrices. For $1 \le k \le n$, the $k${\rm th} joint numerical range of A is defined by $$W_k(A) = \{ ({\rm \tr}(X^*A_1X), \dots, {\rm \tr}(X^*A_mX) ): X \in {\bf C}^{n\times k}, X^*X = I_k \}.$$ We consider linearly independent families of Hermitian matrices {A1, . . . , Am} so that Wk(A) is convex. It is shown that m can reach the upper bound 2k(n-k)+1. A key idea in our study is relating the convexity of Wk(A) to the problem of constructing rank k orthogonal projections under linear constraints determined by A. The techniques are extended to study the convexity of other generalized numerical ranges and the corresponding matrix construction problems.
---
paper_title: ON THE FIELD OF VALUES OF A MATRIX

paper_content:

W is clearly a compact and connected set. Toeplitz showed in [3] that W has a convex outer boundary, and a short time later F. Hausdorff [1] proved that W itself is convex. Since then several investigations have been made concerning the geometry of W. An example of a recent one is the dissertation of R. Kippenhahn [2] in which W is described as the convex hull of a certain algebraic curve of degree n obtainable from C. Writing
---
paper_title: A Superlinearly Convergent Sequential Quadratically Constrained Quadratic Programming Algorithm For Degenerate Nonlinear Programming

paper_content:

We present an algorithm that achieves superlinear convergence for nonlinear programs satisfying the Mangasarian--Fromovitz constraint qualification and the quadratic growth condition. This convergence result is obtained despite the potential lack of a locally convex augmented Lagrangian. The algorithm solves a succession of subproblems that have quadratic objectives and quadratic constraints, both possibly nonconvex. By the use of a trust-region constraint we guarantee that any stationary point of the subproblem induces superlinear convergence, which avoids the problem of computing a global minimum. We compare this algorithm with sequential quadratic programming algorithms on several degenerate nonlinear programs.
---
paper_title: Convexity of the joint numerical range

paper_content:

Let A=(A1, . . ., Am) be an m-tuple of n × n Hermitian matrices. For $1 \le k \le n$, the $k${\rm th} joint numerical range of A is defined by $$W_k(A) = \{ ({\rm \tr}(X^*A_1X), \dots, {\rm \tr}(X^*A_mX) ): X \in {\bf C}^{n\times k}, X^*X = I_k \}.$$ We consider linearly independent families of Hermitian matrices {A1, . . . , Am} so that Wk(A) is convex. It is shown that m can reach the upper bound 2k(n-k)+1. A key idea in our study is relating the convexity of Wk(A) to the problem of constructing rank k orthogonal projections under linear constraints determined by A. The techniques are extended to study the convexity of other generalized numerical ranges and the corresponding matrix construction problems.
---
paper_title: Jordan‐Algebraic Approach to Convexity Theorems for Quadratic Mappings

paper_content:

We describe a Jordan-algebraic version of results related to convexity of images of quadratic mappings as well as related results on exactness of symmetric relaxations of certain classes of nonconvex optimization problems. The exactness of relaxations is proved based on rank estimates. Our approach provides a unifying viewpoint on a large number of classical results related to cones of Hermitian matrices over real and complex numbers. We describe (apparently new) results related to cones of Hermitian matrices with quaternion entries and to the exceptional 27-dimensional Euclidean Jordan algebra.
---
paper_title: On Cones of Nonnegative Quadratic Functions

paper_content:

We derive linear matrix inequality (LMI) characterizations and dual decomposition algorithms for certain matrix cones which are generated by a given set using generalized co-positivity. These matrix cones are in fact cones of nonconvex quadratic functions that are nonnegative on a certain domain. As a domain, we consider for instance the intersection of a (upper) level-set of a quadratic function and a half-plane. Consequently, we arrive at a generalization of Yakubovich's S-procedure result. Although the primary concern of this paper is to characterize the matrix cones by LMIs, we show, as an application of our results, that optimizing a general quadratic function over the intersection of an ellipsoid and a half-plane can be formulated as semidefinite programming (SDP), thus proving the polynomiality of this class of optimization problems, which arise, e.g., from the application of the trust region method for nonlinear programming. Other applications are in control theory and robust optimization.
---
paper_title: On Cones of Nonnegative Quadratic Functions

paper_content:

We derive linear matrix inequality (LMI) characterizations and dual decomposition algorithms for certain matrix cones which are generated by a given set using generalized co-positivity. These matrix cones are in fact cones of nonconvex quadratic functions that are nonnegative on a certain domain. As a domain, we consider for instance the intersection of a (upper) level-set of a quadratic function and a half-plane. Consequently, we arrive at a generalization of Yakubovich's S-procedure result. Although the primary concern of this paper is to characterize the matrix cones by LMIs, we show, as an application of our results, that optimizing a general quadratic function over the intersection of an ellipsoid and a half-plane can be formulated as semidefinite programming (SDP), thus proving the polynomiality of this class of optimization problems, which arise, e.g., from the application of the trust region method for nonlinear programming. Other applications are in control theory and robust optimization.
---
paper_title: Jordan‐Algebraic Approach to Convexity Theorems for Quadratic Mappings

paper_content:

We describe a Jordan-algebraic version of results related to convexity of images of quadratic mappings as well as related results on exactness of symmetric relaxations of certain classes of nonconvex optimization problems. The exactness of relaxations is proved based on rank estimates. Our approach provides a unifying viewpoint on a large number of classical results related to cones of Hermitian matrices over real and complex numbers. We describe (apparently new) results related to cones of Hermitian matrices with quaternion entries and to the exceptional 27-dimensional Euclidean Jordan algebra.
---
paper_title: A Remark On The Rank Of Positive Semidefinite Matrices Subject To Affine Constraints

paper_content:

Let K n be the cone of positive semidefinite n X n matrices and let A be an affine subspace of the space of symmetric matrices such that the intersection K n ?A is nonempty and bounded. Suppose that n ? 3 and that \codim A = r+2 \choose 2 for some 1 ≤ r ≤ n-2 . Then there is a matrix X ? K n ?A such that rank X ≤ r . We give a short geometric proof of this result, use it to improve a bound on realizability of weighted graphs as graphs of distances between points in Euclidean space, and describe its relation to theorems of Bohnenblust, Friedland and Loewy, and Au-Yeung and Poon.
---
paper_title: Hidden convexity in some nonconvex quadratically constrained quadratic programming

paper_content:

We consider the problem of minimizing an indefinite quadratic objective function subject to twosided indefinite quadratic constraints. Under a suitable simultaneous diagonalization assumption (which trivially holds for trust region type problems), we prove that the original problem is equivalent to a convex minimization problem with simple linear constraints. We then consider a special problem of minimizing a concave quadratic function subject to finitely many convex quadratic constraints, which is also shown to be equivalent to a minimax convex problem. In both cases we derive the explicit nonlinear transformations which allow for recovering the optimal solution of the nonconvex problems via their equivalent convex counterparts. Special cases and applications are also discussed. We outline interior-point polynomial-time algorithms for the solution of the equivalent convex programs.
---
paper_title: Trust Region Methods

paper_content:

Preface 1. Introduction Part I. Preliminaries: 2. Basic Concepts 3. Basic Analysis and Optimality Conditions 4. Basic Linear Algebra 5. Krylov Subspace Methods Part II. Trust-Region Methods for Unconstrained Optimization: 6. Global Convergence of the Basic Algorithm 7.The Trust-Region Subproblem 8. Further Convergence Theory Issues 9. Conditional Models 10. Algorithmic Extensions 11. Nonsmooth Problems Part III. Trust-Region Methods for Constrained Optimization with Convex Constraints: 12. Projection Methods for Convex Constraints 13. Barrier Methods for Inequality Constraints Part IV. Trust-Region Mewthods for General Constained Optimization and Systems of Nonlinear Equations: 14. Penalty-Function Methods 15. Sequential Quadratic Programming Methods 16. Nonlinear Equations and Nonlinear Fitting Part V. Final Considerations: Practicalities Afterword Appendix: A Summary of Assumptions Annotated Bibliography Subject and Notation Index Author Index.
---
paper_title: Optimality Conditions for the Minimization of a Quadratic with Two Quadratic Constraints

paper_content:

The trust region method has been proven to be very successful in both unconstrained and constrained optimization. It requires the global minimum of a general quadratic function subject to ellipsoid constraints. In this paper, we generalize the trust region subproblem by allowing two general quadratic constraints. Conditions and properties of its solution are discussed.
---
paper_title: Indefinite Trust Region Subproblems And Nonsymmetric Eigenvalue Perturbations

paper_content:

This paper extends the theory of trust region subproblems in two ways: (i) it allows indefinite inner products in the quadratic constraint, and (ii) it uses a two-sided (upper and lower bound) quadratic constraint. Characterizations of optimality are presented that have no gap between necessity and sufficiency. Conditions for the existence of solutions are given in terms of the definiteness of a matrix pencil. A simple dual program is introduced that involves the maximization of a strictly concave function on an interval. This dual program simplifies the theory and algorithms for trust region subproblems. It also illustrates that the trust region subproblems are implicit convex programming problems, and thus explains why they are so tractable.The duality theory also provides connections to eigenvalue perturbation theory. Trust region subproblems with zero linear term in the objective function correspond to eigenvalue problems, and adding a linear term in the objective function is seen to correspond to a p...
---
paper_title: On a subproblem of trust region algorithms for constrained optimization

paper_content:

We study a subproblem that arises in some trust region algorithms for equality constrained optimization. It is the minimization of a general quadratic function with two special quadratic constraints. Properties of such subproblems are given. It is proved that the Hessian of the Lagrangian has at most one negative eigenvalue, and an example is presented to show that the Hessian may have a negative eigenvalue when one constraint is inactive at the solution.
---
paper_title: Global optimality conditions in maximizing a convex quadratic function under convex quadratic constraints

paper_content:

For the problem of maximizing a convex quadratic function under convex quadratic constraints, we derive conditions characterizing a globally optimal solution. The method consists in exploiting the global optimality conditions, expressed in terms of e-subdifferentials of convex functions and e-normal directions, to convex sets. By specializing the problem of maximizing a convex function over a convex set, we find explicit conditions for optimality.
---
paper_title: Conditions for Global Optimality 2

paper_content:

In this paper bearing the same title as our earlier survey-paper [11] we pursue the goal of characterizing the global solutions of an optimization problem, i.e. getting at necessary and sufficient conditions for a feasible point to be a global minimizer (or maximizer) of the objective function. We emphasize nonconvex optimization problems presenting some specific structures like ‘convex-anticonvex’ ones or quadratic ones.
---
paper_title: On the finite convergence of successive SDP relaxation methods

paper_content:

Abstract Let F be a subset of the n -dimensional Euclidean space R n represented in terms of a compact convex subset of R n and a set of finitely or infinitely many quadratic inequalities. This paper investigates some fundamental properties related to the finite convergence of the successive semidefinite programming relaxation method proposed by the authors for approximating the convex hull of F .
---
paper_title: Semidefinite Programming Relaxation for NonconvexQuadratic Programs

paper_content:

This paper applies the SDP (semidefinite programming) relaxation originally developed for a 0-1 integer program to a general nonconvex QP (quadratic program) having a linear objective function and quadratic inequality constraints, and presents some fundamental characterizations of the SDP relaxation including its equivalence to a relaxation using convex-quadratic valid inequalities for the feasible region of the QP.
---
paper_title: On Semidefinite Bounds for Maximization of a Non-convex Quadratic Objective over the L1-Unit Ball

paper_content:

We consider the non-convex quadratic maximization problem subject ::: to the l 1 unit ball constraint. The nature of the l 1 norm ::: structure makes this problem extremely hard to analyze, and as a ::: consequence, the same difficulties are encountered when trying to ::: build suitable approximations for this problem by some tractable ::: convex counterpart formulations. We explore some properties of ::: this problem, derive SDP-like relaxations and raise open ::: questions.
---
paper_title: New Results on Quadratic Minimization

paper_content:

In this paper we present several new results on minimizing an indefinite quadratic function under quadratic/linear constraints. The emphasis is placed on the case in which the constraints are two quadratic inequalities. This formulation is termed the extended trust region subproblem in this paper, to distinguish it from the ordinary trust region subproblem, in which the constraint is a single ellipsoid. The computational complexity of the extended trust region subproblem in general is still unknown. In this paper we consider several interesting cases related to this problem and show that for those cases the corresponding semidefinite programming relaxation admits no gap with the true optimal value, and consequently we obtain polynomial-time procedures for solving those special cases of quadratic optimization. For the extended trust region subproblem itself, we introduce a parameterized problem and prove the existence of a trajectory that will lead to an optimal solution. Combining this with a result obtained in the first part of the paper, we propose a polynomial-time solution procedure for the extended trust region subproblem arising from solving nonlinear programs with a single equality constraint.
---
paper_title: Recent improvements in the complexity of the effective Nullstellensatz

paper_content:

Abstract We bring up to date the estimates on the complexity of the effective Nullstellensatz and the membership problem.
---
paper_title: On the intrinsic complexity of the arithmetic Nullstellensatz

paper_content:

We show several arithmetic estimates for Hilbert's Nullstellensatz. This includes an algorithmic procedure computing the polynomials and constants occurring in a Bezout identity, whose complexity is polynomial in the geometric degree of the system. Moreover, we show for the first time height estimates of intrinsic type for the polynomials and constants appearing, again polynomial in the geometric degree and linear in the height of the system. These results are based on a suitable representation of polynomials by straight-line programs and duality techniques using the Trace Formula for Gorenstein algebras. As an application we show more precise upper bounds for the function πS(x) counting the number of primes yielding an inconsistent modular polynomial equation system. We also give a computationally interesting lower bound for the density of small prime numbers of controlled bit length for the reduction to positive characteristic of inconsistent systems. Again, this bound is given in terms of intrinsic parameters.
---
paper_title: Algorithms in Real Algebraic Geometry

paper_content:

Algebraically Closed Fields.- Real Closed Fields.- Semi-Algebraic Sets.- Algebra.- Decomposition of Semi-Algebraic Sets.- Elements of Topology.- Quantitative Semi-algebraic Geometry.- Complexity of Basic Algorithms.- Cauchy Index and Applications.- Real Roots.- Cylindrical Decomposition Algorithm.- Polynomial System Solving.- Existential Theory of the Reals.- Quantifier Elimination.- Computing Roadmaps and Connected Components of Algebraic Sets.- Computing Roadmaps and Connected Components of Semi-algebraic Sets.
---
paper_title: Principles of Algebraic Geometry

paper_content:

A comprehensive, self-contained treatment presenting general results of the theory. Establishes a geometric intuition and a working facility with specific geometric practices. Emphasizes applications through the study of interesting examples and the development of computational tools. Coverage ranges from analytic to geometric. Treats basic techniques and results of complex manifold theory, focusing on results applicable to projective varieties, and includes discussion of the theory of Riemann surfaces and algebraic curves, algebraic surfaces and the quadric line complex as well as special topics in complex manifolds.
---
paper_title: Real Algebraic Geometry

paper_content:

1. Ordered Fields, Real Closed Fields.- 2. Semi-algebraic Sets.- 3. Real Algebraic Varieties.- 4. Real Algebra.- 5. The Tarski-Seidenberg Principle as a Transfer Tool.- 6. Hilbert's 17th Problem. Quadratic Forms.- 7. Real Spectrum.- 8. Nash Functions.- 9. Stratifications.- 10. Real Places.- 11. Topology of Real Algebraic Varieties.- 12. Algebraic Vector Bundles.- 13. Polynomial or Regular Mappings with Values in Spheres.- 14. Algebraic Models of C? Manifolds.- 15. Witt Rings in Real Algebraic Geometry.- Index of Notation.
---
paper_title: Feasibility Testing for Systems of Real Quadratic Equations

paper_content:

We consider the problem of deciding whether a given system of quadratic homogeneous equations over the reals has nontrivial solution. We design an algorithm which, for a fixed number of equations, uses a number of arithmetic operations bounded by a polynomial in the number of variables only.
---
paper_title: ON THE S-PROCEDURE AND SOME VARIANTS

paper_content:

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.
---
paper_title: Polynomial-time computing over quadratic maps I: sampling in real algebraic sets

paper_content:

Given a quadratic map $$Q:\mathbb{K}^n \to \mathbb{K}^k $$ defined over a computable subring D of a real closed field $$\mathbb{K},$$ and p ?D[Y1,...,Yk] of degree d, we consider the zero set $$Z = Z(p(Q(X)), \mathbb{K}^n) \subseteq \mathbb{K}^n$$ of p(Q(X1,...,Xn)) ?D[X1,...,Xn]. We present a procedure that computes, in (dn)O(k) arithmetic operations in D, a set $$\mathcal{S}$$ of (real univariate representations of) sampling points in $$\mathbb{K}^n$$ that intersects nontrivially each connected component of Z. As soon as k=o(n), this is faster than the known methods that all have exponential dependence on n in the complexity. In particular, our procedure is polynomial-time for constant k. In contrast, the best previously known procedure is only capable of deciding in $$n^{O(k^2 )} $$ operations the nonemptiness (rather than constructing sampling points) of the set Z in the case of p(Y)=?iYi2 and homogeneous Q. ::: ::: A by-product of our procedure is a bound (dn)O(k) on the number of connected components of Z. ::: ::: The procedure consists of exact symbolic computations in D and outputs vectors of algebraic numbers. It involves extending $$\mathbb{K}$$ by infinitesimals and subsequent limit computation by a novel procedure that utilizes knowledge of an explicit isomorphism between real algebraic sets.
---

Title: A Survey of the S-Lemma

Section 1: Proofs for the Basic S-Lemma
Description 1: In this section, we present three proofs for the basic S-lemma. The proofs include the original proof of Yakubovich, a modern proof based on LMIs, and an elementary analytic proof.

Section 2: The Two Faces of the S-Lemma
Description 2: Here, the central result of the theory is presented, showing the main directions of the rest of the survey. This includes both the logical consequence and feasibility problem perspectives.

Section 3: The Traditional Approach
Description 3: This section elucidates the traditional proof of the S-lemma using convexity results and associated propositions.

Section 4: A Modern Approach
Description 4: We present a modern proof which extends the classical proof to nonhomogeneous cases using advanced linear algebra techniques.

Section 5: An Elementary Proof
Description 5: This section delivers an elementary proof based on simpler concepts and direct verifications, applicable in specific settings.

Section 6: Special Results and Counterexamples
Description 6: This section contains related results, counterexamples, and showcases the limitations and scope of the S-lemma under various conditions.

Section 7: Other Variants
Description 7: In this part, we enumerate and discuss various useful forms of the basic S-lemma which arise from slight modifications in the original reasoning.

Section 8: General Results
Description 8: This section discusses known results on the system solvability and dual vector existence, with a focus on the failures and limitations in a general setting.

Section 9: Counterexamples
Description 9: Specific counterexamples are provided to illustrate the failure of the S-lemma under certain general conditions and assumptions.

Section 10: Stability Analysis
Description 10: Real-world applications of the S-lemma in stability analysis are presented, demonstrating its utility in practical problems.

Section 11: Sum of Two Ellipsoids
Description 11: This section describes the application of the S-lemma to the problem of finding an ellipsoid that contains the sum of two other ellipsoids.

Section 12: Convexity of the Joint Numerical Range
Description 12: We investigate the theory and the general convexity results related to the joint numerical range, highlighting its relevance to the S-lemma.

Section 13: Results over Real Numbers
Description 13: This section provides a deep dive into convexity results over real numbers and their implications for the S-lemma.

Section 14: Results over Complex Numbers
Description 14: An exploration of results over complex numbers, illustrating how these findings affect the applications and extensions of the S-lemma.

Section 15: Implications
Description 15: The implications of convexity results for practical problems and theoretical investigations are discussed here.

Section 16: Further Extensions
Description 16: We discuss the generalization of the S-lemma to more advanced and generalized forms, including polynomial systems and more complex transformations.

Section 17: Miscellaneous Topics
Description 17: Various related topics, such as trust region problems and SDP relaxation, are discussed to illustrate broader applications of the S-lemma.

Section 18: Summary
Description 18: A concise summary of the survey’s findings, emphasizing key points and insights derived from the in-depth analysis of the S-lemma.

Section 19: Future Research
Description 19: This section outlines open problems and suggests directions for future research in areas related to the S-lemma and its applications.