245documents trouvés
Moment matrices, border bases and real radical computation
J.B.LASSERRE, M.LAURENT, B.MOURRAIN, P.ROSTALSKI, P.TREBUCHET
MAC, CWI, Amsterdam, INRIA Sophia, ACL Zurich, Institut für Mathematik, LIP6-CNRS
Revue Scientifique : Journal of Symbolic Computation, Vol.51, pp.63-85, Avril 2013 , N° 11845
Diffusable
Plus d'informations
Abstract
In this paper, we describe new methods to compute the radical (resp. real radical) of an ideal, assuming it complex (resp. real) variety is finite. The aim is to combine approaches for solving a system of polynomial equations with dual methods which involve moment matrices and semi-definite programming. While the border basis algorithms of [17] are efficient and numerically stable for computing complex roots, algorithms based on moment matrices [12] allow the incorporation of additional polynomials, e.g., to re- strict the computation to real roots or to eliminate multiple solutions. The proposed algorithm can be used to compute a border basis of the input ideal and, as opposed to other approaches, it can also compute the quotient structure of the (real) radical ideal directly, i.e., without prior algebraic techniques such as Gr ̈obner bases. It thus combines the strength of existing algorithms and provides a unified treatment for the computation of border bases for the ideal, the radical ideal and the real radical ideal.
The truncated K-Moment problem for closure of open sets
G.BLEKHERMAN, J.B.LASSERRE
Georgia Institute, MAC
Revue Scientifique : Journal of Functional Analysis, Vol.263, N°11, pp.3612-3616, Décembre 2012 , N° 11843
Lien : http://hal.archives-ouvertes.fr/hal-00613043
Diffusable
Plus d'informations
Abstract
We solve the truncated K-moment problem when $K\subseteq R^n$ is the closure of a, not necessarily bounded, open set (which includes the important cases $K=R^n$ and $K=R^n_+$). That is, we completely characterize the interior of the convex cone of finite sequences that have a representing measure on $K\subseteq R^n$. It is in fact the domain of the Legendre-Fenchel transform associated with a certain convex function. And so in this context, detecting whether a sequence is in the interior of this cone reduces to solving a finite-dimensional convex optimization problem. This latter problem is related to maximum entropy methods for approximating an unknown density from knowing only finitely many of its moments. Interestingly, the proposed approach is essentially geometric and of independent interest, as it also addresses the abstract problem of characterizing the interior of a convex cone C which is the conical hull of a set continuously parametrized by a compact set $M\subset R^n$ or $M \subseteq S^{n-1}$, where $M$ is the closure of an open subset of $R^n$ (resp. $S^{n-1}$). As a by-product we also obtain a barrier function for the cone C.
Rank-constrained fundamental matrix estimation by polynomial global optimization versus the eight-point algorithm
F.BUGARIN, A.BARTOLI, D.HENRION, J.B.LASSERRE, J.J.ORTEU, T.SENTENAC
MAC, Université d’Auvergne, CROMeP , RAP
Rapport LAAS N°12489, Septembre 2012, 23p.
Lien : http://hal.archives-ouvertes.fr/hal-00723015
Diffusable
Plus d'informations
Abstract
The fundamental matrix can be estimated from point matches. The current gold standard is to bootstrap the eight-point algorithm and two-view projective bundle adjustment. The eight-point algorithm first computes a simple linear least squares solution by minimizing an algebraic cost and then computes the closest rank-deficient matrix. This article proposes a single-step method that solves both steps of the eight-point algorithm. Using recent result from polynomial global optimization, our method finds the rank-deficient matrix that exactly minimizes the algebraic cost. The current gold standard is known to be extremely effective but is nonetheless outperformed by our rank-constrained method boostrapping bundle adjustment. This is here demonstrated on simulated and standard real datasets. With our initialization, bundle adjustment consistently finds a better local minimum (achieves a lower reprojection error) and takes less iterations to converge
Mean squared error minimization for inverse moment problems
D.HENRION, J.B.LASSERRE, M.MEVISSEN
MAC, IBM Research
Rapport LAAS N°12487, Septembre 2012, 27p.
Lien : http://hal.archives-ouvertes.fr/hal-00725977
Diffusable
Plus d'informations
Abstract
We consider the problem of approximating the unknown density $u\in L^2(\Omega,\lambda)$ of a measure $\mu$ on $\Omega\subset\R^n$, absolutely continuous with respect to some given reference measure $\lambda$, from the only knowledge of finitely many moments of $\mu$. Given $d\in\N$ and moments of order $d$, we provide a polynomial $p_d$ which minimizes the mean square error $\int (u-p)^2d\lambda$ over all polynomials $p$ of degree at most $d$. If there is no additional requirement, $p_d$ is obtained as solution of a linear system. In addition, if $p_d$ is expressed in the basis of polynomials that are orthonormal with respect to $\lambda$, its vector of coefficients is just the vector of given moments and no computation is needed. Moreover $p_d\to u$ in $L^2(\Omega,\lambda)$ as $d\to\infty$. In general nonnegativity of $p_d$ is not guaranteed even though $u$ is nonnegative. However, with this additional nonnegativity requirement one obtains analogous results but computing $p_d\geq0$ that minimizes $\int (u-p)^2d\lambda$ now requires solving an appropriate semidefinite program. We have tested the approach on some applications arising from the reconstruction of geometrical objects and the approximation of solutions of nonlinear differential equations. In all cases our results are significantly better than those obtained with the maximum entropy technique for estimating $u$.
Recovering an homogeneous polynomial from moments of its level set
J.B.LASSERRE
MAC
Rapport LAAS N°12486, Septembre 2012, 4p.
Lien : http://hal.archives-ouvertes.fr/hal-00725422
Diffusable
Plus d'informations
Abstract
Let $K:=\{x: g(x)\leq 1\}$ be the compact sub-level set of some homogeneous polynomial $g$. Assume that the only knowledge about $K$ is the degree of $g$ as well as the moments of the Lebesgue measure on $K$ up to order $2d$. Then the vector of coefficients of $g$ is solution of a simple linear system whose associated matrix is nonsingular. In other words, the moments up to order $2d$ of the Lebesgue measure on $K$ encode all information on the homogeneous polynomial $g$ that defines $K$ (in fact, only moments of order $d$ and $2d$ are needed).
Semidefinite programming for Min-Max problems and games
R.LARAKI, J.B.LASSERRE
LEEP, MAC
Revue Scientifique : Mathematical Programming, Vol.131, N°1-2, pp.305-332, Juillet 2012 , N° 08582
Lien : http://hal.archives-ouvertes.fr/hal-00331529/fr/
Diffusable
Plus d'informations
Abstract
We introduce two min-max problems: the first problem is to minimize the supremum of finitely many rational functions over a compact basic semi-algebraic set whereas the second problem is a 2-player zero-sum polynomial game in randomized strategies and with compact basic semi-algebraic pure strategy sets. It is proved that their optimal solution can be approximated by solving a hierarchy of semidefinite relaxations, in the spirit of the moment approach developed in Lasserre. This provides a unified approach and a class of algorithms to approximate all Nash equilibria and min-max strategies of many static and dynamic games. Each semidefinite relaxation can be solved in time which is polynomial in its input size and practice from global optimization suggests that very often few relaxations are needed for a good approximation (and sometimes even finite convergence). In many cases (e.g. for Nash equilibria) the error of a relaxation can be computed.
Measures and LMI for impulsive optimal control with applications to space rendezvous problems
M.CLAEYS, D.ARZELIER, D.HENRION, J.B.LASSERRE
MAC
Manifestation avec acte : American Control Conference (ACC 2012), Montréal (Canada), 27-29 Juin 2012, pp.161-166 , N° 11554
Lien : http://hal.archives-ouvertes.fr/hal-00633138/fr/
Diffusable
Plus d'informations
Abstract
This paper shows how to find lower bounds on, and sometimes solve globally, a large class of nonlinear optimal control problems with impulsive controls using semi-definite programming (SDP). This is done by relaxing an optimal control problem into a measure differential problem. The manipulation of the measures by their moments reduces the problem to a convergent series of standard linear matrix inequality (LMI) relaxations. After providing numerous academic examples, we apply the method to the impulsive rendezvous of two orbiting spacecrafts. As the method provides lower bounds on the global infimum, global optimality of the solutions can be guaranteed numerically by a posteriori simulations, and we can recover simultaneously the optimal impulse time and amplitudes by simple linear algebra.
Inner approximations for polynomial matrix inequalities and robust stability regions
D.HENRION, J.B.LASSERRE
MAC
Revue Scientifique : IEEE Transactions on Automatic Control, Vol.57, N°6, pp.1456-1467, Juin 2012 , N° 11210
Lien : http://hal.archives-ouvertes.fr/hal-00588754/fr/
Diffusable
Plus d'informations
Abstract
Following a polynomial approach, many robust fixed-order controller design problems can be formulated as optimization problems whose set of feasible solutions is modelled by parametrized polynomial matrix inequalities (PMI). These feasibility sets are typically nonconvex. Given a parametrized PMI set, we provide a hierarchy of linear matrix inequality (LMI) problems whose optimal solutions generate inner approximations modelled by a single polynomial sublevel set. Those inner approximations converge in a strong analytic sense to the nonconvex original feasible set, with asymptotically vanishing conservatism. One may also impose the hierarchy of inner approximations to be nested or convex. In the latter case they do not converge any more to the feasible set, but they can be used in a convex optimization framework at the price of some conservatism. Finally, we show that the specific geometry of nonconvex polynomial stability regions can be exploited to improve convergence of the hierarchy of inner approximations.
The existence of Gaussian cubature formulas
J.B.LASSERRE
MAC
Revue Scientifique : Journal of Approximation Theory, Vol.164, N°5, pp.572-582, Mai 2012 , N° 11274
Lien : http://hal.archives-ouvertes.fr/hal-00595007/fr/
Diffusable
Plus d'informations
Abstract
We provide a necessary and sufficient condition for existence of Gaussian cubature formulas. It consists of checking whether some overdetermined linear system has a solution and so complements Mysovskikh's theorem which requires computing common zeros of orthonormal polynomials. Moreover, the size of the linear system shows that existence of a cubature formula imposes severe restrictions on the associated linear functional. For fixed precision (or degree), the larger the number of variables the worse it gets. And for fixed number of variables, the larger the precision the worse it gets. Finally, we also provide an interpretation of the necessary and sufficient condition in terms of existence of a polynomial with very specific properties.
An algorithm for semi-infinite polynomial optimization
J.B.LASSERRE
MAC
Revue Scientifique : TOP, Vol.20, N°1, pp.119-129, Avril 2012 , N° 11011
Lien : http://hal.archives-ouvertes.fr/hal-00558159/fr/
Diffusable
126978