2013/02/05 by Lasserre, Jean-Bernard · 2 citations
#FOS: Mathematics #Optimization and Control (math.OC)
paper · doi:10.48550/arxiv.1302.1056
We address the following generalization P of the Lowner-John ellipsoid problem. Given a (non necessarily convex) compact set K⊂ Rn and an even integer d, find an homogeneous polynomial g of degree d such that K⊂ G:=\x:g(x)≤1\ and G has minimum volume among all such sets. We show that P is a convex optimization problem even if neither K nor G are convex! We next show that P has a unique optimal solution and a characterization with at most n+d-1\choose d contacts points in K∩ G is also provided. This is the analogue for d\textgreater2 of the Lowner-John's theorem in the quadratic case d=2, but importantly, we neither require the set K nor the sublevel set G to be convex. More generally, there is also an homogeneous polynomial g of even degree d and a point a∈ Rn such that K⊂ G_a:=\x:g(x-a)≤1\ and G_a has minimum volume among all such sets (but uniqueness is not guaranteed). Finally, we also outline a numerical scheme to approximate as closely as desired the optimal value and an optimal solution. It consists of solving a hierarchy of convex optimization problems with strictly convex objective function and Linear Matrix Inequality (LMI) constraints.