The Experts below are selected from a list of 76596 Experts worldwide ranked by ideXlab platform
Didier Henrion - One of the best experts on this subject based on the ideXlab platform.
-
real root finding for low rank linear matrices
Applicable Algebra in Engineering Communication and Computing, 2020Co-Authors: Didier Henrion, Simone Naldi, Mohab Safey El DinAbstract:We consider \(m \times s\) matrices (with \(m\ge s\)) in a real affine subspace of dimension n. The problem of finding elements of low rank in such spaces finds many applications in information and systems theory, where low rank is synonymous of structure and parsimony. We design computer algebra algorithms, based on advanced methods for polynomial system solving, to solve this problem efficiently and exactly: the input are the rational coefficients of the matrices spanning the affine subspace as well as the expected maximum rank, and the output is a rational parametrization encoding a finite Set of points that intersects each connected component of the low rank real Algebraic Set. The complexity of our algorithm is studied thoroughly. It is polynomial in \(\left( {\begin{array}{c}n+m(s-r)\\ n\end{array}}\right) \). It improves on the state-of-the-art in computer algebra and effective real Algebraic geometry. Moreover, computer experiments show the practical efficiency of our approach.
-
Approximating regions of attraction of a sparse polynomial differential system *
2019Co-Authors: Didier Henrion, Matteo Tacchi, Carmen Cardozo, Jean LasserreAbstract:Motivated by stability analysis of large scale power systems, we describe how the Lasserre (moment-sums of squares, SOS) hierarchy can be used to generate outer approximations of the region of attraction (ROA) of sparse polynomial differential systems, at the price of solving linear matrix inequalities (LMI) of increasing size. We identify specific sparsity structures for which we can provide numerically certified outer approximations of the region of attraction in high dimension. For this purpose, we combine previous results on non-sparse ROA approximations with sparse semi-Algebraic Set volume computation.
-
strong duality in lasserre s hierarchy for polynomial optimization
Optimization Letters, 2016Co-Authors: Cedric Josz, Didier HenrionAbstract:A polynomial optimization problem (POP) consists of minimizing a multivariate real polynomial on a semi-Algebraic Set \(K\) described by polynomial inequalities and equations. In its full generality it is a non-convex, multi-extremal, difficult global optimization problem. More than an decade ago, J. B. Lasserre proposed to solve POPs by a hierarchy of convex semidefinite programming (SDP) relaxations of increasing size. Each problem in the hierarchy has a primal SDP formulation (a relaxation of a moment problem) and a dual SDP formulation (a sum-of-squares representation of a polynomial Lagrangian of the POP). In this note, we show that there is no duality gap between each primal and dual SDP problem in Lasserre’s hierarchy, provided one of the constraints in the description of Set \(K\) is a ball constraint. Our proof uses elementary results on SDP duality, and it does not assume that \(K\) has a strictly feasible point.
-
real root finding for low rank linear matrices
arXiv: Symbolic Computation, 2015Co-Authors: Didier Henrion, Simone Naldi, Mohab Safey El DinAbstract:We consider $m \times s$ matrices (with $m\geq s$) in a real affine subspace of dimension $n$. The problem of finding elements of low rank in such spaces finds many applications in information and systems theory, where low rank is synonymous of structure and parsimony. We design computer algebra algorithms, based on advanced methods for polynomial system solving, to solve this problem efficiently and exactly: the input are the rational coefficients of the matrices spanning the affine subspace as well as the expected maximum rank, and the output is a rational parametrization encoding a finite Set of points that intersects each connected component of the low rank real Algebraic Set. The complexity of our algorithm is studied thoroughly. It is polynomial in $\binom{n+m(s-r)}{n}$. It improves on the state-of-the-art in computer algebra and effective real Algebraic geometry. Moreover, computer experiments show the practical efficiency of our approach.
-
strong duality in lasserre s hierarchy for polynomial optimization
arXiv: Optimization and Control, 2014Co-Authors: Cedric Josz, Didier HenrionAbstract:A polynomial optimization problem (POP) consists of minimizing a multivariate real polynomial on a semi-Algebraic Set $K$ described by polynomial inequalities and equations. In its full generality it is a non-convex, multi-extremal, difficult global optimization problem. More than an decade ago, J.~B.~Lasserre proposed to solve POPs by a hierarchy of convex semidefinite programming (SDP) relaxations of increasing size. Each problem in the hierarchy has a primal SDP formulation (a relaxation of a moment problem) and a dual SDP formulation (a sum-of-squares representation of a polynomial Lagrangian of the POP). In this note, when the POP feasibility Set $K$ is compact, we show that there is no duality gap between each primal and dual SDP problem in Lasserre's hierarchy, provided a redundant ball constraint is added to the description of Set $K$. Our proof uses elementary results on SDP duality, and it does not assume that $K$ has an interior point.
Jean B Lasserre - One of the best experts on this subject based on the ideXlab platform.
-
a bounded degree sos hierarchy for polynomial optimization
EURO Journal on Computational Optimization, 2017Co-Authors: Jean B Lasserre, Shouguang YangAbstract:We consider a new hierarchy of semidefinite relaxations for the general polynomial optimization problem $(P):\:f^{\ast}=\min \{\,f(x):x\in K\,\}$ on a compact basic semi-Algebraic Set $K\subSet\R^n$. This hierarchy combines some advantages of the standard LP-relaxations associated with Krivine's positivity certificate and some advantages of the standard SOS-hierarchy. In particular it has the following attractive features: (a) In contrast to the standard SOS-hierarchy, for each relaxation in the hierarchy, the size of the matrix associated with the semidefinite constraint is the same and fixed in advance by the user. (b) In contrast to the LP-hierarchy, finite convergence occurs at the first step of the hierarchy for an important class of convex problems. Finally (c) some important techniques related to the use of point evaluations for declaring a polynomial to be zero and to the use of rank-one matrices make an efficient implementation possible. Preliminary results on a sample of non convex problems are encouraging.
-
borel measures with a density on a compact semi Algebraic Set
Archiv der Mathematik, 2013Co-Authors: Jean B LasserreAbstract:Let \({\mathbf{K} \subSet \mathbb{R}^n}\) be a compact basic semi-Algebraic Set. We provide a necessary and sufficient condition (with no a priori bounding parameter) for a real sequence y = (yα), \({\alpha \in \mathbb{N}^n}\) , to have a finite representing Borel measure absolutely continuous w.r.t. the Lebesgue measure on K, and with a density in \({\cap_{p \geq 1} L_p(\mathbf{K})}\) . With an additional condition involving a bounding parameter, the condition is necessary and sufficient for the existence of a density in L∞(K). Moreover, nonexistence of such a density can be detected by solving finitely many of a hierarchy of semidefinite programs. In particular, if the semidefinite program at step d of the hierarchy has no solution, then the sequence cannot have a representing measure on K with a density in Lp(K) for any p ≥ 2d.
-
borel measures with a density on a compact semi Algebraic Set
arXiv: Optimization and Control, 2013Co-Authors: Jean B LasserreAbstract:Let $K\subSet R^n$ be a compact basic semi-Algebraic Set. We provide a necessary and sufficient condition (with no a priori bounding parameter) for a real sequence $y=(y_\alpha)$, $\alpha\in N^n$, to have a finite representing Borel measure absolutely continuous w.r.t. the Lebesgue measure on $K$, and with a density in $\cap_{p=1}^\infty L_p(K)$. With an additional condition involving a bounding parameter, the condition is necessary and sufficient for existence of a density in $L_\infty(K)$. Moreover, nonexistence of such a density can be detected by solving finitely many of a hierarchy of semidefinite programs. In particular, if the semidefinite program at step $d$ of the hierarchy has no solution then the sequence cannot have a representing measure on $K$ with a density in $L_p(K)$ for any $p\geq 2d$.
-
the mathbf k moment problem for continuous linear functionals
Transactions of the American Mathematical Society, 2012Co-Authors: Jean B LasserreAbstract: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 nonnegative on $P$ and $Q$ (hence on $psd(K)$). When $K$ has a nonempty interior we also provide in explicit form a canonical $\ell_w$-projection $g^w_f$ for any 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 nonnegative on $K$, which is crucial in proving the above results.
-
approximate volume and integration for basic semi Algebraic Sets
arXiv: Optimization and Control, 2008Co-Authors: Didier Henrion, Jean B Lasserre, Carlo SavorgnanAbstract:Given a basic compact semi-Algebraic Set $\K\subSet\R^n$, we introduce a methodology that generates a sequence converging to the volume of $\K$. This sequence is obtained from optimal values of a hierarchy of either semidefinite or linear programs. Not only the volume but also every finite vector of moments of the probability measure that is uniformly distributed on $\K$ can be approximated as closely as desired, and so permits to approximate the integral on $\K$ of any given polynomial; extension to integration against some weight functions is also provided. Finally, some numerical issues associated with the algorithms involved are briefly discussed.
Scott Mccullough - One of the best experts on this subject based on the ideXlab platform.
-
every convex free basic semi Algebraic Set has an lmi representation
Annals of Mathematics, 2012Co-Authors: William J Helton, Scott McculloughAbstract:The (matricial) solution Set of a Linear Matrix Inequality (LMI) is a convex free basic open semi-Algebraic Set. The main theorem of this paper is a converse, each such Set arises from some LMI. The result has implications for semi-definite programming and systems engineering as well as for free semi-Algebraic geometry.
-
every free basic convex semi Algebraic Set has an lmi representation
arXiv: Functional Analysis, 2009Co-Authors: William J Helton, Scott McculloughAbstract:The (matricial) solution Set of a Linear Matrix Inequality (LMI) is a convex basic non-commutative semi-Algebraic Set. The main theorem of this paper is a converse, a result which has implications for both semidefinite programming and systems engineering. For p(x) a non-commutative polynomial in free variables x= (x1, ... xg) we can substitute a tuple of symmetric matrices X= (X1, ... Xg) for x and obtain a matrix p(X). Assume p is symmetric with p(0) invertible, let Ip denote the Set {X: p(X) is an invertible matrix}, and let Dp denote the component of Ip containing 0. THEOREM: If the Set Dp is uniformly bounded independent of the size of the matrix tuples, then Dp has an LMI representation if and only if it is convex. Linear engineering systems problems are called "dimension free" if they can be stated purely in terms of a signal flow diagram with L2 performance measures, e.g., H-infinity control. Conjecture: A dimension free problem can be made convex if and only it can be made into an LMI. The theorem here Settles the core case affirmatively.
William J Helton - One of the best experts on this subject based on the ideXlab platform.
-
every convex free basic semi Algebraic Set has an lmi representation
Annals of Mathematics, 2012Co-Authors: William J Helton, Scott McculloughAbstract:The (matricial) solution Set of a Linear Matrix Inequality (LMI) is a convex free basic open semi-Algebraic Set. The main theorem of this paper is a converse, each such Set arises from some LMI. The result has implications for semi-definite programming and systems engineering as well as for free semi-Algebraic geometry.
-
every free basic convex semi Algebraic Set has an lmi representation
arXiv: Functional Analysis, 2009Co-Authors: William J Helton, Scott McculloughAbstract:The (matricial) solution Set of a Linear Matrix Inequality (LMI) is a convex basic non-commutative semi-Algebraic Set. The main theorem of this paper is a converse, a result which has implications for both semidefinite programming and systems engineering. For p(x) a non-commutative polynomial in free variables x= (x1, ... xg) we can substitute a tuple of symmetric matrices X= (X1, ... Xg) for x and obtain a matrix p(X). Assume p is symmetric with p(0) invertible, let Ip denote the Set {X: p(X) is an invertible matrix}, and let Dp denote the component of Ip containing 0. THEOREM: If the Set Dp is uniformly bounded independent of the size of the matrix tuples, then Dp has an LMI representation if and only if it is convex. Linear engineering systems problems are called "dimension free" if they can be stated purely in terms of a signal flow diagram with L2 performance measures, e.g., H-infinity control. Conjecture: A dimension free problem can be made convex if and only it can be made into an LMI. The theorem here Settles the core case affirmatively.
Lihong Zhi - One of the best experts on this subject based on the ideXlab platform.
-
computing real radicals and s radicals of polynomial systems
Journal of Symbolic Computation, 2021Co-Authors: Mohab Safey El Din, Zhi-hong Yang, Lihong ZhiAbstract:Abstract Let f = ( f 1 , … , f s ) be a sequence of polynomials in Q [ X 1 , … , X n ] of maximal degree D and V ⊂ C n be the Algebraic Set defined by f and r be its dimension. The real radical 〈 f 〉 r e associated to f is the largest ideal which defines the real trace of V. When V is smooth, we show that 〈 f 〉 r e , has a finite Set of generators with degrees bounded by deg V . Moreover, we present a probabilistic algorithm of complexity ( s n D n ) O ( 1 ) to compute the minimal primes of 〈 f 〉 r e . When V is not smooth, we give a probabilistic algorithm of complexity s O ( 1 ) ( n D ) O ( n r 2 r ) to compute rational parametrizations for all irreducible components of the real Algebraic Set V ∩ R n . Let ( g 1 , … , g p ) in Q [ X 1 , … , X n ] and S be the basic closed semi-Algebraic Set defined by g 1 ≥ 0 , … , g p ≥ 0 . The S-radical of 〈 f 〉 , which is denoted by 〈 f 〉 S , is the ideal associated to the Zariski closure of V ∩ S . We give a probabilistic algorithm to compute rational parametrizations of all irreducible components of that Zariski closure, hence encoding 〈 f 〉 S . Assuming now that D is the maximum of the degrees of the f i 's and the g i 's, this algorithm runs in time 2 p ( s + p ) O ( 1 ) ( n D ) O ( r n 2 r ) . Experiments are performed to illustrate and show the efficiency of our approaches on computing real radicals.
-
On the complexity of computing real radicals of polynomial systems
2018Co-Authors: Mohab Safey El Din, Zhi-hong Yang, Lihong ZhiAbstract:Let f= (f1, ..., fs) be a sequence of polynomials in Q[X1,...,Xn] of maximal degree D and V⊂ Cn be the Algebraic Set defined by f and r be its dimension. The real radical re < f > associated to f is the largest ideal which defines the real trace of V . When V is smooth, we show that re < f >, has a finite Set of generators with degrees bounded by V. Moreover, we present a probabilistic algorithm of complexity (snDn )O(1) to compute the minimal primes of re < f >. When V is not smooth, we give a probabilistic algorithm of complexity sO(1) (nD)O(nr2r) to compute rational parametrizations for all irreducible components of the real Algebraic Set V ∩ Rn. Experiments are given to show the efficiency of our approaches.
-
Optimizing a Parametric Linear Function over a Non-compact Real Algebraic Variety
2015Co-Authors: Feng Guo, Mohab Safey El Din, Wang Chu, Lihong ZhiAbstract:We consider the problem of optimizing a parametric linear function over a non-compact real trace of an Algebraic Set. Our goal is to compute a representing polynomial which defines a hypersurface containing the graph of the optimal value function. Rostalski and Sturmfels showed that when the Algebraic Set is irreducible and smooth with a compact real trace, then the least degree representing polynomial is given by the defining polynomial of the irreducible hypersurface dual to the projective closure of the Algebraic Set. First, we generalize this approach to non-compact situations. We prove that the graph of the opposite of the optimal value function is still contained in the affine cone over a dual variety similar to the one considered in compact case. In consequence, we present an algorithm for solving the considered parametric optimization problem for generic parameters' values. For some special parameters' values, the representing polynomials of the dual variety can be identically zero, which give no information on the optimal value. We design a dedicated algorithm that identifies those regions of the parameters' space and computes for each of these regions a new polynomial defining the optimal value over the considered region.
-
computing real solutions of polynomial systems via low rank moment matrix completion
International Symposium on Symbolic and Algebraic Computation, 2012Co-Authors: Lihong ZhiAbstract:In this paper, we propose a new algorithm for computing real roots of polynomial equations or a subSet of real roots in a given semi-Algebraic Set described by additional polynomial inequalities. The algorithm is based on using modified fixed point continuation method for solving Lasserre's hierarchy of moment relaxations. We establish convergence properties for our algorithm. For a large-scale polynomial system with only few real solutions in a given area, we can extract them quickly. Moreover, for a polynomial system with an infinite number of real solutions, our algorithm can also be used to find some isolated real solutions or real solutions on the manifolds.
