{
  "id": "1302.1056",
  "version": "v4",
  "published": "2013-02-05T14:58:21.000Z",
  "updated": "2014-12-23T20:18:57.000Z",
  "title": "A generalization of Löwner-John's ellipsoid theorem",
  "authors": [
    "Jean-Bernard Lasserre"
  ],
  "comment": "To appear in Mathematical Programming",
  "categories": [
    "math.OC"
  ],
  "abstract": "We address the following generalization $P$ of the Lowner-John ellipsoid problem. Given a (non necessarily convex) compact set $K\\subset R^n$ and an even integer $d$, find an homogeneous polynomial $g$ of degree $d$ such that $K\\subset G:=\\{x:g(x)\\leq1\\}$ 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\\cap G$ is also provided. This is the analogue for $d\\textgreater{}2$ 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\\in R^n$ such that $K\\subset G\\_a:=\\{x:g(x-a)\\leq1\\}$ 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.",
  "revisions": [
    {
      "version": "v3",
      "updated": "2014-07-21T16:38:58.000Z",
      "title": "A generalization of the Löwner-John's ellipsoid theorem",
      "abstract": "We address the following generalization $P$ of the Lowner-John ellipsoid problem. Given a (non necessarily convex) compact set $K\\subset R^n$ and an even integer $d$, find an homogeneous polynomial $g$ of degree $d$ such that $K\\subset G:=\\{x:g(x)\\leq1\\}$ 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\\cap G$ is also provided. This is the analogue for $d>2$ 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\\in R^n$ such that $K\\subset G_a:=\\{x:g(x-a)\\leq1\\}$ 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.",
      "journal": null,
      "doi": null
    },
    {
      "version": "v4",
      "updated": "2014-12-23T20:18:57.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "löwner-johns ellipsoid theorem",
      "convex optimization problem",
      "generalization",
      "minimum volume",
      "unique optimal solution"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1302.1056L"
    }
  }
}