A moment approach to analyze zeros of triangular polynomial sets

Let $I=(g_1,…, g_n)$ be a zero-dimensional ideal of $ \R[x_1,…,x_n]$ such that its associated set $G$ of polynomial equations $g_i(x)=0$ for all $i=1,…,n$, is in triangular form. By introducing multivariate Newton sums we provide a numerical characterization of polynomials in the radical ideal of $I$. We also provide a necessary and sufficient (numerical) condition for … Read more

Generating functions and duality for integer programs

We consider the integer program P -> max {c’x | Ax=y; x\in N^n }. Using the generating function of an associated counting problem, and a generalized residue formula of Brion and Vergne, we explicitly relate P with its continuous linear programming (LP) analogue and provide a characterization of its optimal value. In particular, dual variables … Read more

Characterizing polynomials with roots in a semi-algebraic set

Consider a real polynomial $p$ and a semi-algebraic subset $S$ of the complex plane, defined by finitely many polynomial inequalities $g_k(z,\bar{z}) \geq 0$ for some complex polynomials $\{g_k\}$. We provide necessary and sufficient conditions on the coefficients of $p$ for the zeros of $p$ to be in $S$. Citation IEEE Trans. Automatic Control 49 (2004), … Read more

The integer hull of a convex rational polytope

Given $A\in Z^{m\times n}$ and $b\in Z^m$, we consider the integer program $\max \{c’x\vert Ax=b;x\in N^n\}$ and provide an equivalent and explicit linear program $\max \{\widehat{c}’q\vert M q=r;q\geq 0\}$, where $M,r,\widehat{c}$ are easily obtained from $A,b,c$ with no calculation. We also provide an explicit algebraic characterization of the integer hull of the convex polytope $P=\{x\in\R^n\vert … Read more

Duality and a Farkas lemma for integer programs

We consider the integer program $\max \{c’ x\,|\,Ax=b,x\in N^n\}$. A formal parallel between linear programming and continuous integration on one side, and discrete summation on the other side, shows that a natural duality for integer programs can be derived from the $Z$-transform and Brion and Vergne’s counting formula. Along the same lines, we also provide … Read more

On counting integral points in a convex rational polytope

Given a convex rational polytope $\Omega(b):=\{x\in\R^n_+\,|\,Ax=b\}$, we consider the function $b\mapsto f(b)$, which counts the nonnegative integral points of $\Omega(b)$. A closed form expression of its $\Z$-transform $z\mapsto \mathcal{F}(z)$ is easily obtained so that $f(b)$ can be computed as the inverse $\Z$-transform of $\mathcal{F}$. We then provide two variants of an inversion algorithm. As a … Read more

Solving the knapsack problem via Z-transform

Given vectors $a,c\in Z^n$ and $b\in Z$, we consider the (unbounded) knapsack optimization problem $P:\,\min\{c’x\,\vert\, a’x=b;\,x\in N^n\}$. We compute the minimum value $p^*$ using techniques from complex analysis, namely Cauchy residue technique to integrate a function in $C^2$, the $Z$-transform of an appropriate function related to $P$. The computational complexity depends on $s:=\sum_{a_j} a_j$, not … Read more

GloptiPoly – Global Optimization over Polynomials withMatlab and SeDuMi

GloptiPoly is a Matlab/SeDuMi add-on to build and solve convex linear matrix inequality relaxations of the (generally non-convex) global optimization problem of minimizing a multivariable polynomial function subject to polynomial inequality, equality or integer constraints. It generates a series of lower bounds monotonically converging to the global optimum. Numerical experiments show that for most of … Read more

Bounds on measures satisfying moment conditions

Given a semi algebraic set S of R^n we provide a numerical approximation procedure that yields upper and lower bounds on mu(S), for measures mu that satisfy some given moment conditions. The bounds are obtained as solutions of positive semidefinite programs that can be solved via standard software packages like the LMI MATLAB toolbox. Citation … Read more