Retour au site du LAAS-CNRS

Abstract

We consider integer programming and the semi-group membership problem. We provide the following theorem of the alternative: the system Ax=b has no nonnegative integral solution x if and only if p(b) <0 for some given polynomial p whose vector of coefficients lies in a convex cone that we characterize. We also provide a hierarchy of linear programming relaxations, where the continuous case Ax=b with x real and nonnegative, describes the first relaxation in the hierarchy.

Mots-Clés / Keywords

Discrete optimization; Integer linear programming; discrete Farkas lemma;

Abstract

We review several (and provide new) results on the theory of moments, sums of squares, and basic semialgebraic sets when convexity is present. In particular, we show that, under convexity, the hierarchy of semidefinite relaxations for polynomial optimization simplifies and has finite convergence, a highly desirable feature as convex problems are in principle easier to solve. In addition, if a basic semialgebraic set $\mathbf{K}$ is convex but its defining polynomials are not, we provide two algebraic certificates of convexity which can be checked numerically. The second is simpler and holds if a sufficient (and almost necessary) condition is satisfied; it also provides a new condition for $\mathbf{K}$ to have semidefinite representation. For this we use (and extend) some of the recent results from the author and Helton and Nie [Math. Program., to appear]. Finally, we show that, when restricting to a certain class of convex polynomials, the celebrated Jensen's inequality in convex analysis can be extended to linear functionals that are not necessarily probability measures.

Abstract

Given a compact basic semi-algebraic set , a rational fraction , and a sequence of scalars y = (y ±), we investigate when holds for all , i.e., when y is the moment sequence of some measure fd¼, supported on K. This yields a set of (convex) linear matrix inequalities (LMI). We also use semidefinite programming to develop a converging approximation scheme to evaluate the integral + fd¼ when the moments of ¼ are known and f is a given rational fraction. Numerical expreriments are also provided. We finally provide (again LMI) conditions on the moments of two measures with support contained in K, to have for some rational fraction f.

Mots-Clés / Keywords

Problem of moments; Semidefinite programming; Relaxation;

Abstract

We consider nonlinear optimal control problems (OCPs) for which all problem data are polynomial. In the first part of the paper, we review how occupation measures can be used to approximate pointwise the optimal value function of a given OCP, using a hierarchy of linear matrix inequality (LMI) relaxations. In the second part, we extend the methodology to approximate the optimal value function on a given set and we use such a function to constructively and computationally derive an almost optimal control law. Numerical examples show the effectiveness of the approach.

Abstract

We consider the generalized problem of moments (GPM) from a computational point of view and provide a hierarchy of semidefinite programming relaxations whose sequence of optimal values converges to the optimal value of the GPM. We then investigate in detail various examples of applications in optimization, probability, financial economics and optimal control, which all can be viewed as particular instances of the GPM.

Mots-Clés / Keywords

Semidefinite programming; Relaxations; Problem of moments;

Abstract

We provide a specific representation of convex polynomials nonnegative on a convex (not necessarily compact) basic closed semi-algebraic set K C Rn. Namely, they belong to a specific subset of the quadratic module generated by the concave polynomials that define K.

Mots-Clés / Keywords

Positive polynomials; Sum-of-squares; Quadratic modules; Convex sets;

Abstract

We investigate and discuss when the inverse of a multivariate truncated moment matrix of a measure ¼ has zeros in some prescribed entries. We describe precisely which pattern of these zeroes corresponds to independence, namely, the measure having a product structure. A more refined finding is that the key factor forcing a zero entry in this inverse matrix is a certain conditional triangularity property of the orthogonal polynomials associated with ¼.

Mots-Clés / Keywords

Moment matrix; Orthogonal polynomials;

Résumé

Nous établissons une procédure numérique pour approcher uniformément par une suite de fonctions convexes., l'enveloppe convexe d'une fraction rationnelle ayant pour domaine, D, un ensemble de dimension finie supposée compacte et semi-algébrique. Calculer la valeur d'une approximation en un point donné de K=co(D) se résume à résoudre un programme semi-défini. En suite, nous caractérisons K=co(D) comme projection d'un LMI semi-infini, et en plus nous approximons K par une suite décroissante d'ensembles convexes. Tester si un point donné n'est pas dans K se résume à résoudre un nombre fini de programmes semi-définis.

Abstract

We provide a numerical procedure to compute uniform (convex) approximations {f_{r}} of the convex envelope f of a rational fraction f, on a compact semi-algebraic set D. At each point x in K=co(D), computing f_{r}(x) reduces to solving a semidefinite program. We next characterize the convex hull K=co(D) in terms of the projection of a semi-infinite LMI, and provide outer convex approximations {K_{r}}«K. Testing whether x is not in K reduces to solving finitely many semidefinite programs.

Mots-Clés / Keywords

Enveloppe convexe; Programme semi-défini; Ensemble semi-algébrique; Dualité; Convex envelope; Semi-definite program; Semi-algbraic set; Duality;