Convex Optimization & Parsimony of L_p-balls Representation

Thursday, January 28, 2016 - 9:00am - 9:50am
Keller 3-180
Jean Lasserre (Centre National de la Recherche Scientifique (CNRS))
We consider the family of nonnegative homogeneous polynomials of even degree p whose sublevel set G = {x : g(x) ≤ 1} (a unit ball) has same fixed volume and want to find in this family the one that minimizes either the parsimony-inducing ell_1-norm or the ell_2-norm of its vector of coefficients. We first show that in both cases this is a convex optimization problem with a unique optimal solution. In the former case, the unique solution is the polynomial associated with the L_p-ball, thus recovering a parsimony property of its representation via ell_1-minimization. We also show that the solution of the ell_2-norm problem is an appropriate power of the polynomial associated with the Euclidean ball. We also characterize the unique optimal solution of the same problem where one searches for an SOS homogeneous polynomial that minimizes the (parsimony-inducing) nuclear norm of its associated (psd) Gram matrix. Again the Euclidean ball shows up.
MSC Code: