245documents trouvés
A new look at nonnegativity on closed sets and polynomial optimization
J.B.LASSERRE
MAC
Revue Scientifique : SIAM Journal on Optimization, Vol.21, N°3, pp.864-885, Juillet 2011 , N° 10492
Lien : http://hal.archives-ouvertes.fr/hal-00512560/fr/
Diffusable
Plus d'informations
Abstract
We first show that a continuous function f is nonnegative on a closed set $K\subseteq R^n$ if and only if (countably many) moment matrices of some signed measure $d\nu =fd\mu$ with support equal to K, are all positive semidefinite (if $K$ is compact $\mu$ is an arbitrary finite Borel measure with support equal to K. In particular, we obtain a convergent explicit hierarchy of semidefinite (outer) approximations with {\it no} lifting, of the cone of nonnegative polynomials of degree at most $d$. Wen used in polynomial optimization on certain simple closed sets $\K$ (like e.g., the whole space $\R^n$, the positive orthant, a box, a simplex, or the vertices of the hypercube), it provides a nonincreasing sequence of upper bounds which converges to the global minimum by solving a hierarchy of semidefinite programs with only one variable. This convergent sequence of upper bounds complements the convergent sequence of lower bounds obtained by solving a hierarchy of semidefinite relaxations.
A new look at nonnegativity on closed sets
J.B.LASSERRE
MAC
Revue Scientifique : SIAM Journal on Optimization, Vol.21, N°3, pp.864-885, Juillet 2011 , N° 10920
Diffusable
126364The K-moment problem for continuous linear functionals
J.B.LASSERRE
MAC
Rapport LAAS N°11102, Mars 2011, 15p.
Lien : http://hal.archives-ouvertes.fr/hal-00570653/fr/
Diffusable
Plus d'informations
Abstract
Given a closed (and non necessarily compact) basic semi-algebraic set $K\subseteq R^n$, we solve the $K$-moment problem for continuous linear functionals. Namely, we introduce a weighted $\ell_1$-norm $\ell_w$ on $R[x]$, and show that the $\ell_w$-closures of the preordering $P$ and quadratic module $Q$ (associated with the generators of $K$) is the cone $psd(K)$ of polynomials nonnegative on $K$. We also prove that $P$ an $Q$ solve the $K$-moment problem for $\ell_w$-continuous linear functionals and completely characterize those $\ell_w$-continuous linear functionals positive on $P$ and $Q$ (hence on $psd(K)$). When $K$ has a nonempty interior we also provide an explicit form of the $\ell_w$-projection $g^w_f$ of a given polynomial $f$ on the (degree-truncated) preordering or quadratic module. Remarkably, the support of $g^w_f$ is very sparse and does not depend on $K$! This enables us to provide an explicit Positivstellensatz on $K$. At last but not least, we provide a simple characterization of polynomials positive on $K$, which is crucial in proving the above results.
Minimizing the sum of many rational functions
F.BUGARIN, D.HENRION, J.B.LASSERRE
CROMeP , MAC
Rapport LAAS N°11100, Mars 2011, 16p.
Lien : http://hal.archives-ouvertes.fr/hal-00569067/fr/
Diffusable
Plus d'informations
Abstract
We consider the problem of globally minimizing the sum of many rational functions over a given compact semialgebraic set. The number of terms can be large (10 to 100), the degree of each term should be small (up to 10), and the number of variables can be large (10 to 100) provided some kind of sparsity is present. We describe a formulation of the rational optimization problem as a generalized moment problem and its hierarchy of convex semidefinite relaxations. Under some conditions we prove that the sequence of optimal values converges to the globally optimal value. We show how public-domain software can be used to model and solve such problems.
New approximations for the cone of copositive matrices and its dual
J.B.LASSERRE
MAC
Rapport LAAS N°10796, Janvier 2011, 8p.
Lien : http://hal.archives-ouvertes.fr/hal-00545755/fr/
Diffusable
Plus d'informations
Abstract
We provide convergent hierarchies for the cone C of copositive matrices and its dual, the cone of completely positive matrices. In both cases the corresponding hierarchy consists of nested spectrahedra and provide outer (resp. inner) approximations for C (resp. for its dual), thus complementing previous inner (resp. outer) approximations for C (for the dual). In particular, both inner and outer approximations have a very simple interpretation. Finally, extension to K-copositivity and K-complete positivity for a closed convex cone K, is straightforward.
Best $\ell_1$-approximation of nonnegative polynomials by sums of squares
J.B.LASSERRE
MAC
Rapport LAAS N°10794, Janvier 2011, 4p.
Lien : http://hal.archives-ouvertes.fr/hal-00546660/fr/
Diffusable
Plus d'informations
Abstract
Given a nonnegative polynomial f, we provide an explicit expression for its best $\ell_1$-norm approximation by a sum of squares of given degree.
The "joint+marginal" approach in optimization
J.B.LASSERRE
MAC
Conférence invitée : International Conference on Optimization: techniques and Application (ICOTA8), Shanghai (Chine), 10-13 Décembre 2010, 2p. (Résumé) , N° 10915
Diffusable
124326A "joint+marginal" algorithm in 0/1 programming
J.B.LASSERRE
MAC
Conférence invitée : Exploratory Workshop on Non-Linear Integer Programming, Séville (Espagne), 1-3 Décembre 2010 , N° 10917
Diffusion restreinte
124330Positivity and optimization for semi-algebraic functions
J.B.LASSERRE, M.PUTINAR
MAC, Santa Barbara
Revue Scientifique : SIAM Journal on Optimization, Vol.20, N°6, pp.3364-3383, Décembre 2010 , N° 10899
Non diffusable
124185A new look at nonnegativity on closed sets
J.B.LASSERRE
MAC
Conférence invitée : Colloque JBHU 2010, Bayonne (France), 15-17 Octobre 2010 , N° 10920
Diffusable
124336