Retour au site du LAAS-CNRS

Abstract

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.

Mots-Clés / Keywords

Mots-Clés / Keywords

Abstract

We consider the classical problem of estimating a density on [0,1] via some maximum entropy criterion. For solving this convex optimization problem with algorithms using first-order or second-order methods, at each iteration one has to compute (or at least approximate) moments of some measure with a density on [0,1], to obtain gradient and Hessian data. We propose a numerical scheme based on semidefinite programming that avoids computing quadrature formula for this gradient and Hessian computation.

Abstract

We provide explicit sufficient conditions for a polynomial f to be a sum of squares (s.o.s.), linear in the coefficients of f. All conditions are simple and provide an explicit description of a convex polyhedral subcone of the cone of s.o.s. polynomials of degree at most 2d. We also provide a simple condition to ensure that f is s.o.s., possibly after adding a constant.

Mots-Clés / Keywords

Abstract

Given z  n and A  $m×n, we provide an explicit expression and an algorithm for evaluating the counting function h(y;z): =  { zx | x  $n;Ax=y,x e 0}. The algorithm only involves simple (but possibly numerous) calculations. In addition, we exhibit finitely many fixed convex cones of n explicitly and exclusively defined by A, such that for any y  $m, h(y;z) is obtained by a simple formula that evaluates  zx over the integral points of those cones only. At last, we also provide an alternative (and different) formula from a decomposition of the generating function into simpler rational fractions, easy to invert.

Abstract

We show that every real polynomial f nonnegative on [1,1] n can be approximated in the l 1-norm of coefficients, by a sequence of polynomials that are sums of squares (s.o.s). This complements the existence of s.o.s. approximations in the denseness result of Berg, Christensen and Ressel, as we provide a very simple and explicit approximation sequence. Then we show that if the moment problem holds for a basic closed semi-algebraic set with nonempty interior, then every polynomial nonnegative on K S can be approximated in a similar fashion by elements from the corresponding preordering. Finally, we show that the degree of the perturbation in the approximating sequence depends on as well as the degree and the size of coefficients of the nonnegative polynomial f, but not on the specific values of its coefficients.

Abstract

We show that every real nonnegative polynomial $f$ can be approximated as closely as desired (in the $l_1$-norm of its coefficient vector) by a sequence of polynomials $\{f_\epsilon\}$ that are sums of squares. The novelty is that each $f_\epsilon$ has a simple and explicit form in terms of $f$ and $\epsilon$.

Mots-Clés / Keywords

Abstract

We consider the global minimization of a multivariate polynomial on a variety K ‚ R n. We present two new hierarchies of SDP-relaxations in the same spirit but simpler than those defined in \cite{lasserre1}, which are valid for an arbitrary variety K (not necessarily compact). In particular, (a) the sequence of optimal values converges monotonically to the global optimum and (b), every accumulation point of an associated sequence of moment sequences converges to a moment sequence of a moment-determinate probability measure, supported on the global minimizers of the original problem. Preliminary computational results are presented.