222documents trouvés
Semidefinite characterisation of invariant measures for one-dimensional discrete dynamical systems
D.HENRION
MAC
Revue Scientifique : Kybernetika, Vol.48, N°6, pp.1089-1099, Décembre 2012 , N° 12052
Lien : http://hal.archives-ouvertes.fr/hal-00666098
Diffusable
Plus d'informations
Abstract
Using recent results on measure theory and algebraic geometry, we show how semidefinite programming can be used to construct invariant measures of one-dimensional discrete dynamical systems (iterated maps on a real interval). In particular we show that both discrete measures (corresponding to finite cycles) and continuous measures (corresponding to chaotic behavior) can be recovered using standard software, paving the way for a numerical study of probabilistic properties of dynamical systems.
Minimum volume semialgebraic sets for robust estimation
F.DABBENE, D.HENRION
Politecnico Torino, MAC
Rapport LAAS N°12636, Novembre 2012, 11p.
Lien : http://hal.archives-ouvertes.fr/hal-00740794
Diffusable
Plus d'informations
Abstract
Motivated by problems of uncertainty propagation and robust estimation we are interested in computing a polynomial sublevel set of fixed degree and minimum volume that contains a given semialgebraic set K. At this level of generality this problem is not tractable, even though it becomes convex e.g. when restricted to nonnegative homogeneous polynomials. Our contribution is to describe and justify a tractable L^1-norm or trace heuristic for this problem, relying upon hierarchies of linear matrix inequality (LMI) relaxations when K is semialgebraic, and simplifying to linear programming (LP) when K is a collection of samples, a discrete union of points.
Inner approximations of the region of attraction for polynomial dynamical systems
M.KORDA, D.HENRION, C.N.JONES
EPFL, MAC
Rapport LAAS N°12635, Novembre 2012, 15p.
Lien : http://hal.archives-ouvertes.fr/hal-00740798
Diffusable
Plus d'informations
Abstract
In a previous work we developed a convex infinite dimensional linear programming (LP) approach to approximating the region of attraction (ROA) of polynomial dynamical systems subject to compact basic semialgebraic state constraints. Finite dimensional relaxations to the infinite-dimensional LP lead to a truncated moment problem in the primal and a polynomial sum-of-squares problem in the dual. This primal-dual linear matrix inequality (LMI) problem can be solved numerically with standard semidefinite programming solvers, producing a hierarchy of outer (i.e. exterior) approximations of the ROA by polynomial sublevel sets, with a guarantee of almost uniform and set-wise convergence. In this companion paper, we show that our approach is flexible enough to be modified so as to generate a hierarchy of polynomial inner (i.e.\,interior) approximations of the ROA with similar convergence guarantees.
Measures and LMIs for optimal control of piecewise-affine systems
M.R.ADBALMOATI, D.HENRION, L.RODRIGUES
ASTRIUM, MAC, Univ de Concordia
Rapport LAAS N°12633, Novembre 2012, 18p.
Lien : http://hal.archives-ouvertes.fr/hal-00751917
Diffusable
Plus d'informations
Abstract
This paper considers the class of deterministic continuous-time optimal control problems (OCPs) with piecewise-affine (PWA) vector field, polynomial Lagrangian and semialgebraic input and state constraints. The OCP is first relaxed as an infinite-dimensional linear program (LP) over a space of occupation measures. This LP, a particular instance of the generalized moment problem, is then approached by an asymptotically converging hierarchy of linear matrix inequality (LMI) relaxations. The relaxed dual of the original LP returns a polynomial approximation of the value function that solves the Hamilton-Jacobi-Bellman (HJB) equation of the OCP. Based on this polynomial approximation, a suboptimal policy is developed to construct a state feedback in a sample-and-hold manner. The results show that the suboptimal policy succeeds in providing a stabilizing suboptimal state feedback law that drives the system relatively close to the optimal trajectories and respects the given constraints.
Convex computation of the region of attraction of polynomial control systems
D.HENRION, M.KORDA
MAC, EPFL
Rapport LAAS N°12488, Septembre 2012, 29p.
Lien : http://hal.archives-ouvertes.fr/hal-00723019
Diffusable
Plus d'informations
Abstract
We address the long-standing problem of computing the region of attraction (ROA) of a target set (typically a neighborhood of an equilibrium point) of a controlled nonlinear system with polynomial dynamics and semialgebraic state and input constraints. We show that the ROA can be computed by solving a convex linear programming (LP) problem over the space of measures. In turn, this problem can be solved approximately via a classical converging hierarchy of convex finite-dimensional linear matrix inequalities (LMIs). Our approach is genuinely primal in the sense that convexity of the problem of computing the ROA is an outcome of optimizing directly over system trajectories. The dual LP on nonnegative continuous functions (approximated by polynomial sum-of-squares) allows us to generate a hierarchy of semialgebraic outer approximations of the ROA at the price of solving a sequence of LMI problems with asymptotically vanishing conservatism. This sharply contrasts with the existing literature which follows an exclusively dual Lyapunov approach yielding either nonconvex bilinear matrix inequalities or conservative LMI conditions.
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$.
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
Positive trigonometric polynomials for strong stability of difference equations
D.HENRION, T.VYHLIDAL
MAC, CTU
Revue Scientifique : Automatica , Vol.48, N°9, pp.2207-2212, Septembre 2012 , N° 10677
Lien : http://hal.archives-ouvertes.fr/hal-00532796/fr/
Diffusable
Plus d'informations
Abstract
We follow a polynomial approach to analyse strong stability of linear difference equations with rationally independent delays. Upon application of the Hermite stability criterion on the discrete-time homogeneous characteristic polynomial, assessing strong stability amounts to deciding positive definiteness of a multivariate trigonometric polynomial matrix. This latter problem is addressed with a converging hierarchy of linear matrix inequalities (LMIs). Numerical experiments indicate that certificates of strong stability can be obtained at a reasonable computational cost for state dimension and number of delays not exceeding 4 or 5.
Convex inner approximations of nonconvex semialgebraic sets applied to fixed-order controller design
D.HENRION, C.LOUEMBET
MAC
Revue Scientifique : International Journal of Control, Vol.85, N°8, pp.1083-1092, Août 2012 , N° 11213
Lien : http://hal.archives-ouvertes.fr/hal-00585633/fr/
Diffusable
Plus d'informations
Abstract
We describe an elementary algorithm to build convex inner approximations of nonconvex sets. Both input and output sets are basic semialgebraic sets given as lists of defining multivariate polynomials. Even though no optimality guarantees can be given (e.g. in terms of volume maximization for bounded sets), the algorithm is designed to preserve convex boundaries as much as possible, while removing regions with concave boundaries. In particular, the algorithm leaves invariant a given convex set. The algorithm is based on Gloptipoly 3, a public-domain Matlab package solving nonconvex polynomial optimization problems with the help of convex semidefinite programming (optimization over linear matrix inequalities, or LMIs). We illustrate how the algorithm can be used to design fixed-order controllers for linear systems, following a polynomial approach.
Semidefinite programming for optimizing convex bodies under width constraints
T.BAYEN, D.HENRION
I3M, MAC
Revue Scientifique : Optimization Methods and Software, Vol.27, N°6, pp.1073-1099, Août 2012 , N° 10481
Lien : http://hal.archives-ouvertes.fr/hal-00495031/fr/
Diffusable
Plus d'informations
Abstract
We consider the problem of minimizing a functional (like the area, perimeter, surface) within the class of convex bodies whose support functions are trigonometric polynomials. The convexity constraint is transformed via the Fejer-Riesz theorem on positive trigonometric polynomials into a semidefinite programming problem. Several problems such as the minimization of the area in the class of constant width planar bodies, rotors and space bodies of revolution are revisited. The approach seems promising to investigate more difficult optimization problems in the class of three-dimensional convex bodies.