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.

We describe a major update of our Matlab freeware GloptiPoly for parsing generalized problems of moments and solving them numerically with semidefinite programming.

We consider the class of nonlinear optimal control problems (OCPs) with polynomial data, i.e., the differential equation, state and control constraints, and cost are all described by polynomials, and more generally for OCPs with smooth data. In addition, state constraints as well as state and/or action constraints are allowed. We provide a simple hierarchy of LMI- (linear matrix inequality)-relaxations whose optimal values form a nondecreasing sequence of lower bounds on the optimal value. Under some convexity assumptions, the sequence converges to the optimal value of the OCP. Preliminary results show that good approximations are obtained with few moments.

This is the first comprehensive introduction to the powerful moment approach for solving global optimization problems (and some related problems) described by polynomials (and even semi-algebraic functions). In particular, the author explains how to use relatively recent results from real algebraic geometry to provide a systematic numerical scheme for computing the optimal value and global minimizers. Indeed, among other things, powerful positivity certificates from real algebraic geometry allow one to define an appropriate hierarchy of semidefinite (SOS) relaxations or LP relaxations whose optimal values converge to the global minimum. Several extensions to related optimization problems are also described. Graduate students, engineers and researchers entering the field can use this book to understand, experiment with and master this new approach through the simple worked examples provided.

We consider a polynomial programming problem $\P$ on a compact basic semialgebraic set $\K\subset\R^n$, described by m polynomial inequalities $g_j(X)\geq0$, and with criterion $f\in\R[X]$. We propose a hierarchy of semidefinite relaxations in the spirit of those of Waki et al. [SIAM J. Optim., 17 (2006), pp. 218–242]. In particular, the SDP‐relaxation of order r has the following two features: (a) The number of variables is $O(\kappa^{2r})$, where $\kappa=\max[\kappa_1,\kappa_2]$ with $\kappa_1$ (resp., $\kappa_2$) being the maximum number of variables appearing in the monomials of f (resp., appearing in a single constraint $g_j(X)\geq0$). (b) The largest size of the linear matrix inequalities (LMIs) is $O(\kappa^r)$. This is to compare with the respective number of variables $O(n^{2r})$ and LMI size $O(n^r)$ in the original SDP‐relaxations defined in [J. B. Lasserre, SIAM J. Optim., 11 (2001), pp. 796–817]. Therefore, great computational savings are expected in case of sparsity in the data $\{g_j,f\}$, ...

GloptiPoly is a Matlab/SeDuMi add-on to build and solve convex linear matrix inequality relaxations of the (generally nonconvex) global optimization problem of minimizing a multivariable polynomial function subject to polynomial inequality, equality, or integer constraints. It generates a series of lower bounds monotonically converging to the global optimum without any problem splitting. Global optimality is detected and isolated optimal solutions are extracted automatically. Numerical experiments show that for most of the small-scale problems described in the literature, the global optimum is reached at low computational cost.