Introduction: what is this course about?TopicsReview: convexityReview: linear programmingMIT 6.972 Algebraic techniques and semidefinite optimization February 7, 2006 Lecture 1 Lecturer: Pablo A . Parrilo Scribe: Pablo A. Parrilo 1 Introduction: what is this course about? In this course we aim to understand the properties, both mathematical and computational, of sets defined by polynomial equations and inequalities. In particular, we want to work towards methods that will enable the solution (either exact or approximate) of optimization problems with feasible sets that are defined through polynomial systems. Needless to say (is it?), many problems in estimation, control, signal processing, etc., admit simple formulations in terms of polynomial equations and inequalities. However, these formulations can be tremendously difficult to solve, and thus our methods should try to exploit as many structural properties as possible. The computational aspects of these sets are not very well understood at the moment. In the well-known case of polyhedra, for instance, there is a well defined relationship b etween the geometrical prop e rties of the set (e.g., the number of facets, or the number of extreme points) and its algebraic representation. Furthermore, polyhedral sets are preserved by natural operations (e.g., projections). None of this will generally be true for (basic) semialgebraic sets, and this causes a very interesting interaction between their geometry and algebraic descriptions. 2 Topics To understand better what is going on, we will embark in a journey to learn a wide variety of methods used to approach these problems. Some of our stops along the way will include: • Linear optimization, second order cones, semidefinite programming • Algebra: groups, fields, rings • Univariate polynomials Resultants and discriminants • • Hyperb olic polynomials • Sum of squares • Ideals, varieties, Groebner bases, Nullstellensatz • Quantifier elimination Real Nullstellensatz • And much more. . . • We are interested in computational methods, and want to emphasize efficiency. Throughout, appli-cations will play an important role, both as motivation and illustration of the techniques. 1-1�3 Review: convexity A very important notion in modern optimization is that of convexity. To a large extent, m odulo some (important) technicalities, there is a huge gap between the theoretical and practical solvability of opti-mization problems where the feasible set is convex, versus those where this property fails. Recommended presentations of convex optimization from a modern viewp oint are [BV04, BTN01, BNO03], with [Roc70] being the classical treatment of convex analysis. Here are some relevant definitions: Definition 1 A set S is convex if x1, x2 ∈ S implies λx1 + (1 − λ)x2 ∈ S for all 0 ≤ λ ≤ 1. Definition 2 A set S ⊆ Rn is a cone if λ ≥ 0, x ∈ S ⇒ λx ∈ S. Definition 3 The dual of a set S is S∗ = {y ∈ Rn : x ∈ S ⇒ �x, y� ≥ 0}. A c one K is pointed if K ∩ (−K) = {0}, and solid if the interior of K is not empty. A cone that is convex, closed, pointed and solid is called a proper cone. The dual set of a proper cone is also a proper cone, called the dual cone. An element x is in the interior of the cone K if and only if �x, y� > 0, ∀y ∈ K∗, y = 0. A proper cone induces a partial order in the space, via x � y if and only if y − x ∈ K. We also use x � y if y − x is in the interior of K. Important examples of proper cones are the nonnegative orthant, given by {x ∈ Rn, xi ≥ 0}, and the set of symme tric positive semidefinite matrices. 4 Review: linear programming Linear programming (LP) is the problem of minimizing a linear function, subject to linear inequality constraints. An LP in s tandard form is written as: � min c T x s.t. Ax x = b ≥ 0 (P) Every LP problem has a corresponding dual problem, which in this case is: max bT y s.t. c − AT y ≥ 0. (D) There are many important features of LP. Among them, we mention the following ones: Geometry of the feasible set: The feasible set of linear programs are polyhedra. The geometry of polyhedra is quite well understood. In particular, the Minkowski-Weyl theorem (e.g., [BT 97, Zie95]) states that every polyhedron P can be written as P = conv(u1, . . . , ur ) + cone(v1, . . . , vs), where the ui, vi are the extreme points and extreme rays of P , respectively. Weak duality: For any feasible solutions x, y of (P) and (D), respectively, it always holds that: T T c x − bT y = x c − (Ax)T y = x T (c − AT y) ≥ 0. In other words, from any feasible dual solution we can obtain a lower bound on the primal. Conversely, primal feasible solutions give upper bounds on the value of the dual. Strong duality: If both primal and dual are feasible, then they achieve exactly the same value, and T x� = bT y�.there exist optimal feasible solutions x�, y� such that c1-2Some of these properties (which ones ?) will break down as soon as we leave LP and go the more general case of conic or se midefinite programming. These will cause s ome difficulties, although with the right assumptions, the resulting theory will closely parallel the LP case. Remark The software codes cdd (Komei Fukuda, http://www.ifor.math.ethz.ch/~fukuda/cdd_ home/index.html) and lrs (David Avis, http://cgm.cs.mcgill.ca/~avis/C/lrs.html) are very use-ful for polyhedral computations. In particular, both of them allow to convert an inequality representation of a polyhedron (usually called an H-representation) into extreme points/rays (V-representation), and viceversa. References [BNO03] D.P. Bertsekas, A. Nedic, and A.E. Ozdaglar. Convex analysis and optimization. Athena Scientific, Belmont, MA, 2003. [BT97] D. Bertsimas and J. N. Tsitsiklis. Introduction to Linear Optimization. Athena Scientific, 1997. [BTN01] A. Ben-Tal and A. Nemirovski. Lectures on modern convex o ptimization. MPS/SIAM Series on Optimization. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2001. [BV04] S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, 2004. [Roc70] R. T. Rockafellar. Convex Analysis. Princeton University