ALGORITHMS IN REAL ALGEBRAIC GEOMETRY: A SURVEY <s> 4.1. <s> Written for specialists working in optimization, mathematical programming, or control theory. The general theory of path-following and potential reduction interior point polynomial time methods, interior point methods, interior point methods for linear and quadratic programming, polynomial time methods for nonlinear convex programming, efficient computation methods for control problems and variational inequalities, and acceleration of path-following methods are covered. In this book, the authors describe the first unified theory of polynomial-time interior-point methods. Their approach provides a simple and elegant framework in which all known polynomial-time interior-point methods can be explained and analyzed; this approach yields polynomial-time interior-point methods for a wide variety of problems beyond the traditional linear and quadratic programs. The book contains new and important results in the general theory of convex programming, e.g., their "conic" problem formulation in which duality theory is completely symmetric. For each algorithm described, the authors carefully derive precise bounds on the computational effort required to solve a given family of problems to a given precision. In several cases they obtain better problem complexity estimates than were previously known. Several of the new algorithms described in this book, e.g., the projective method, have been implemented, tested on "real world" problems, and found to be extremely efficient in practice. Contents : Chapter 1: Self-Concordant Functions and Newton Method; Chapter 2: Path-Following Interior-Point Methods; Chapter 3: Potential Reduction Interior-Point Methods; Chapter 4: How to Construct Self- Concordant Barriers; Chapter 5: Applications in Convex Optimization; Chapter 6: Variational Inequalities with Monotone Operators; Chapter 7: Acceleration for Linear and Linearly Constrained Quadratic Problems <s> BIB001 </s> ALGORITHMS IN REAL ALGEBRAIC GEOMETRY: A SURVEY <s> 4.1. <s> We consider the problem of finding the unconstrained global minimum of a real-valued polynomial p(x): {\mathbb{R}}^n\to {\mathbb{R}}$, as well as the global minimum of p(x), in a compact set K defined by polynomial inequalities. It is shown that this problem reduces to solving an (often finite) sequence of convex linear matrix inequality (LMI) problems. A notion of Karush--Kuhn--Tucker polynomials is introduced in a global optimality condition. Some illustrative examples are provided. <s> BIB002 </s> ALGORITHMS IN REAL ALGEBRAIC GEOMETRY: A SURVEY <s> 4.1. <s> A hierarchy of convex relaxations for semialgebraic problems is introduced. For questions reducible to a finite number of polynomial equalities and inequalities, it is shown how to construct a complete family of polynomially sized semidefinite programming conditions that prove infeasibility. The main tools employed are a semidefinite programming formulation of the sum of squares decomposition for multivariate polynomials, and some results from real algebraic geometry. The techniques provide a constructive approach for finding bounded degree solutions to the Positivstellensatz, and are illustrated with examples from diverse application fields. <s> BIB003 </s> ALGORITHMS IN REAL ALGEBRAIC GEOMETRY: A SURVEY <s> 4.1. <s> We show that every real nonnegative polynomial $f$ can be approximated as closely as desired by a sequence of polynomials $\{f_\epsilon\}$ that are sums of squares. Each $f_\epsilon$ has a simple et explicit form in terms of $f$ and $\epsilon$. A special representation is also obtained for convex polynomials, nonnegative on a convex semi-algebraic set. <s> BIB004 </s> ALGORITHMS IN REAL ALGEBRAIC GEOMETRY: A SURVEY <s> 4.1. <s> We consider a polynomial programming problem P on a compact basic semi-algebraic set K⊂ℝn, described by m polynomial inequalities gj(X)≥0, and with criterion f∈ℝ[X]. We propose a hierarchy of semidefinite relaxations that take sparsity of the original data into account, in the spirit of those of Waki et al. [7]. The novelty with respect to [7] is that we prove convergence to the global optimum of P when the sparsity pattern satisfies a condition often encountered in large size problems of practical applications, and known as the running intersection property in graph theory. <s> BIB005 </s> ALGORITHMS IN REAL ALGEBRAIC GEOMETRY: A SURVEY <s> 4.1. <s> We consider the problem of minimizing a polynomial over a semialgebraic set defined by polynomial equations and inequalities, which is NP-hard in general. Hierarchies of semidefinite relaxations have been proposed in the literature, involving positive semidefinite moment matrices and the dual theory of sums of squares of polynomials. We present these hierarchies of approximations and their main properties: asymptotic/finite convergence, optimality certificate, and extraction of global optimum solutions. We review the mathematical tools underlying these properties, in particular, some sums of squares representation results for positive polynomials, some results about moment matrices (in particular, of Curto and Fialkow), and the algebraic eigenvalue method for solving zero-dimensional systems of polynomial equations. We try whenever possible to provide detailed proofs and background. <s> BIB006
Deciding non-negativity of polynomials using sums-of-squares. The problem is to decide whether a given polynomial P ∈ R[X 1 , . . . , X k ] is non-negative in R k . More generally, the problem is to decide whether a given polynomial P ∈ R[X 1 , . . . , X k ] is non-negative over a given basic, semi-algebraic subset K ⊂ R k . There are also optimization versions of these problems namely. More generally, Given P ∈ R[X 1 , . . . , X k ] and K ⊂ R k a basic semi-algebraic set, compute For purposes of exposition we concentrate on the first versions of these problems. Let the degree of P be 2d and let Pos k,d (resp. Σ k,d ) denote the cone of nonnegative polynomials (resp. cone of sum of squares) in R[X 1 , . . . , X k ] of degree at most 2d. Clearly Σ k,d ⊂ Pos k,d and as known since Hilbert, the inclusion is strict Chapter 6] . Note that the cones Pos k,d are in general not understood very well (for instance, their face structure, extreme rays etc.) and testing membership in them is clearly an NP-hard problem. On the other hand, the cones Σ k,d are relatively well understood and membership in Σ k,d can be tested via semi-definite programming as a result of the following theorem. For any symmetric, square matrix X ∈ R k×k , we let X 0 denote that X is positive, semi-definite. For each k, d ≥ 0, we denote by M k,d the set of exponent The following are equivalent. ( (2) The following system in matrix variables X = (X α,β ) α,β∈M k,d is feasible: The feasibility problem in the above theorem is an instance of the feasibility problem in the theory of semi-definite programming . Semi-definite programming (or semi-definite optimization) is a generalization of linear programming, where the problem is to optimize a linear functional over some affine section of the cone of real symmetric positive semi-definite matrices in the space of k × k real symmetric matrices. Because of its wide ranging applicability, semi-definite programming has been the focus of intense effort on the part of researchers in optimization for developing efficient algorithms for solving semi-definite programming problems. As a result very efficient algorithms based on "interior point methods" (see BIB001 ) have been developed for solving semi-definite optimization problems such as the one in Theorem 4.1. These algorithms are very efficient in practice, but there seems to be no definitive mathematical result which states that the running time is polynomial (in the bit-size of the input) (unlike in the case of linear programming). Note that the polynomial optimization problems can also be "approximated" using the sum of squares cone just like above. For example, in order to compute p min := inf x∈R k P (x) = sup{ρ ∈ R | P − ρ ∈ Pos k,d }, one computes p sos := sup{ρ ∈ R | P − ρ ∈ Σ k,d }. Since, this latter problem is an example of semi-definite optimization problem and can be solved in practice using efficient interior points methods. Also note that since the latter problem involves optimization over a smaller cone we have that p sos ≤ p min . The idea of "relaxing" polynomial optimization problems to semi-definite programming has been utilized by Lasserre BIB002 BIB004 BIB005 , Parrilo BIB003 and others to obtain algorithms for performing polynomial optimization which perform well in practice (but see Remark 4.2 below). Remark 4.2. While the idea of approximating the cone of non-negative polynomials by the smaller cone of sums of square seems to work well in practice for solving or approximating well solutions of polynomial optimization problems, one should be aware of certain negative results. Blekherman  proved that the ratio of the volumes of certain fixed sections of the cones Σ k,d and Pos k,d goes to 0 with k exponentially fast. This seems to indicate that the approximation of Pos k,d by Σ k,d is very inaccurate as k grows (with d fixed). We refer the reader to the excellent survey article by Laurent BIB006 for more detailed information about the sums-of-squares methods in algorithmic real algebraic geometry.