Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Semialgebraic problems, those that can be expressed with a finite number of polynomial inequalities and inequalities, are ubiquitous in many different engineering and applied math disciplines. A few concrete exSemialgebraic problems, those that can be expressed with a finite number of polynomial inequalities and inequalities, are ubiquitous in many different engineering and applied math disciplines. A few concrete examples are given by polynomial optimization problems, analysis of uncertain systems, graph theoretic problems, and issues of network survivability and reliability. In general, this class of problems are NP-hard, and therefore exact algorithms to solve them are usually computationally infeasible. amples are given by polynomial optimization problems, analysis of uncertain systems, graph theoretic problems, and issues of network survivability and reliability. In general, this class of problems are NP-hard, and therefore exact algorithms to solve them are usually computationally infeasible. As a consequence, considerable research efforts have been directed towards the efficient computation of approximate solutions (or bounds) for this class of problems. In this talk, we present a new convex optimization framework for semialgebraic problems. The key element is the interaction of concepts from real algebra and convex optimization, in particular a semidefinite programming formulation for the sums of squares decomposition for multivariable polynomials. These results are used to construct a hierarchy of progressively stronger convex tests, based on the Positivstellensatz, to prove that a given semialgebraic set is empty. The search for such certificates can be efficiently carried out, in polynomial time. The developed techniques unify and generalize many well-known existing results. The computational complexity implications are discussed. We describe the application of the results to some problems in continuous and combinatorial optimization. These include MAX CUT, Lyapunov stability of nonlinear systems described by polynomial vector fields, matrix copositivity, and enhanced semidefinite relaxations for quadratic programming. The ideas and algorithms will be illustrated with examples from a broad range of application domains.