# zbMATH — the first resource for mathematics

A generalization of Löwner-John’s ellipsoid theorem. (English) Zbl 1337.90049
In this remarkable work, the author considers the following geometric problem. Given a compact set $$K$$ of $${\mathbb R}^n$$ and an even integer $$d$$, find a homogeneous polynomial $$g$$ of degree $$d$$ such that its unit sublevel set $$G:=\{x \in {\mathbb R}^n : g(x) \leq 1\}$$ contains $$K$$ and has minimal volume (i.e. Lebesgue measure). This turns out to be a finite-dimensional convex optimization problem, even though $$K$$ is not assumed to be convex or connected. This follows from the observation that the volume of $$G$$ is proportional to the integral $$\int_{{\mathbb R}^n} \exp(-g(x))dx$$. Using first-order optimal conditions, the author then shows that this optimization problem has a unique optimal solution, and a tight upper bound on the number of contact points of $$K$$ and $$G$$ is also provided.
Whereas finding the optimal set $$G$$ boils down to solving a finite-dimensional convex optimization problem (whose decision variable is the homogeneous polynomial $$g$$), solving this optimization problem seems to be a challenge, the main difficulty being evaluation of integrals of exponentials of polynomials. Numerically, the optimal set $$G$$ can however be approximated as closely as desired with a hierarchy of finite-dimensional semidefinite programming problems for which efficient interior-point algorithms are available.
This work can be considered as a significant extension of the Löwner-John ellipsoid theorem stating that there exists a minimum volume ellipsoid $$G$$ containing a given convex compact set $$K$$. The extension is twofold. First, $$K$$ is not assumed to be convex or connected. Second, $$G$$ is not restricted to be the unit sublevel set of a degree $$2$$ polynomial.

##### MSC:
 90C22 Semidefinite programming 65K10 Numerical optimization and variational techniques
##### Software:
GloptiPoly; Polynomial Toolbox
Full Text:
##### References:
  Anastassiou, G.A.: Moments in Probability Approximation Theory. Longman Scientific & Technical, UK (1993) · Zbl 0847.41001  d’Aspremont, A, Smooth optimization with approximate gradient, SIAM J. Optim., 19, 1171-1183, (2008) · Zbl 1180.90378  Ash, R.B.: Real Analysis and Probability. Academic Press Inc., Boston (1972) · Zbl 1381.28001  Ball, K, Ellipsoids of maximal volume in convex bodies, Geom. Dedicata, 41, 241-250, (1992) · Zbl 0747.52007  Ball, K; Johnson, WB (ed.); Lindenstrauss, J (ed.), Convex geometry and functional analysis, 161-194, (2001), Amsterdam · Zbl 1017.46004  Barvinok, AI, Computing the volume, counting integral points, and exponential sums, Discrete Comput. Geom., 10, 123-141, (1993) · Zbl 0774.68054  Bastero, J; Romance, M, John’s decomposition of the identity in the non-convex case, Positivity, 6, 1-16, (2002) · Zbl 1018.52004  Bayer, C; Teichmann, J, The proof of tchakaloff’s theorem, Proc. Am. Math. Soc., 134, 303-3040, (2006) · Zbl 1093.41016  Bookstein, FL, Fitting conic sections to scattered data, Comp. Graph. Image. Process., 9, 56-71, (1979)  Calafiore, G, Approximation of $$n$$-dimnsional data using spherical and ellipsoidal primitives, IEEE Trans. Syst. Man. Cyb., 32, 269-276, (2002)  Chernousko, FL, Guaranteed estimates of undetermined quantities by means of ellipsoids, Sov. Math. Dodkl., 21, 396-399, (1980) · Zbl 0454.93010  Croux, C; Haesbroeck, G; Rousseeuw, PJ, Location adjustment for the minimum volume ellipsoid estimator, Stat. Comput., 12, 191-200, (2002)  Giannopoulos, A; Perissinaki, I; Tsolomitis, A, A john’s theorem for an arbitrary pair of convex bodies, Geom. Dedicata, 84, 63-79, (2001) · Zbl 0989.52004  Dyer, ME; Frieze, AM; Kannan, R, A random polynomial-time algorithm for approximating the volume of convex bodies, J. ACM, 38, 1-17, (1991) · Zbl 0799.68107  Faraut, J., Korányi, A.: Analysis on Symmetric Cones. Clarendon Press, Oxford (1994) · Zbl 0841.43002  Freitag, E., Busam, R.: Complex Analysis, 2nd edn. Springer, Berlin (2009) · Zbl 1167.30001  Gander, W; Golub, GH; Strebel, R, Least-squares Fitting of circles and ellipses, BIT, 34, 558-578, (1994) · Zbl 0817.65008  Helton, JW; Nie, J, A semidefinite approach for truncated K-moment problems, Fond. Comput. Math., 12, 851-881, (2012) · Zbl 1259.44005  Henk, M.: Löwner-John ellipsoids. Documenta Math. 95-106 (2012) (extra volume: optimization stories)  Henrion, D; Lasserre, JB; Lofberg, J, Gloptipoly 3: moments, optimization and semidefinite programming, Optim. Method. Softw., 24, 761-779, (2009) · Zbl 1178.90277  Henrion, D; Lasserre, JB; Savorgnan, C, Approximate volume and integration of basic semi-algebraic sets, SIAM Rev., 51, 722-743, (2009) · Zbl 1179.14037  Henrion, D; Peaucelle, D; Arzelier, D; Sebek, M, Ellipsoidal approximation of the stability domain of a polynomial, IEEE Trans. Autom. Control, 48, 2255-2259, (2003) · Zbl 1364.93568  Henrion, D; Lasserre, JB, Inner approximations for polynomial matrix inequalities and robust stability regions, IEEE Trans. Autom. Control, 57, 1456-1467, (2012) · Zbl 1369.93460  Henrion, D; Sebek, M; Kucera, V, Positive polynomials and and robust stabilization with fixed-order controllers, IEEE Trans. Autom. Control, 48, 1178-1186, (2003) · Zbl 1364.93707  Hiriart-Urruty, J.B., Lemarechal, C.: Convex Analysis and Minimization Algorithms I. Springer, Berlin (1993) · Zbl 0795.49001  Hiriart-Urruty, J.B., Lemarechal, C.: Convex Analysis and Minimization Algorithms II. Springer, Berlin (1993) · Zbl 0795.49002  Karimi, A; Khatibi, H; Longchamp, R, Robust control of polytopic systems by convex optimization, Automatica, 43, 1395-1402, (2007) · Zbl 1130.93339  Kemperman, J.H.B.: Geometry of the moment problem. In: H.J. Landau (Ed.) Moments in Mathematics. Proceedings of Symposia in Applied Mathematics, vol. 37 pp. 16-53 (1987) · Zbl 0632.60015  Kemperman, JHB, The general moment problem, a geometric approach, Annals Math. Stat., 39, 93-122, (1968) · Zbl 0162.49501  Lasserre, JB, Global optimization with polynomials and the problem of moments, SIAM J. Optim., 11, 796-817, (2001) · Zbl 1010.90061  Lasserre, J.B.: Moments, Positive Polynomials and Their Applications. Imperial College, London (2009)  Lasserre, JB, Recovering an homogeneous polynomial from moments of its level set, Discrete Comput. Geom., 50, 673-678, (2013) · Zbl 1311.44009  Morosov, A; Shakirov, S, New and old results in resultant theory, Theor. Math. Phys., 163, 587-617, (2010) · Zbl 1254.15011  Morosov, A., Shakirov, S.: Introduction to integral discriminants, J. High Energy Phys. 12 (2009). arXiv:0911.5278v1  Nurges, U, Robust pole assignment via reflection coefficientsof polynomials, Automatica, 42, 1223-1230, (2006) · Zbl 1122.93033  O’Rourke, J; Badler, NI, Decomposition of three-dimensional objets into spheres, IEEE Trans. Pattern Anal. Machine Intell., 1, 295-305, (1979)  Pratt, V.: Direct least squares fitting of algebraic surfaces. ACM J. Comp. Graph. 21, 145-152 (1987)  Putinar, M, Positive polynomials on compact semi-algebraic sets, Indiana Univ. Math. J., 42, 969-984, (1993) · Zbl 0796.12002  Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton, NJ (1970) · Zbl 0193.18401  Rosen, JB, Pattern separation by convex programming techniques, J. Math. Anal. Appl., 10, 123-134, (1965) · Zbl 0134.37503  Rosin, PL, A note on the least squares Fitting of ellipses, Pattern Recog. Lett., 14, 799-808, (1993) · Zbl 0802.68155  Rosin, PL; West, GA, Nonparametric segmentation of curves into various representations, IEEE Trans. Pattern Anal. Machine Intell., 17, 1140-1153, (1995)  Rousseeuw, P.J., Leroy, A.M.: Robust Regression and Outlier Detection. John Wiley, New York (1987) · Zbl 0711.62030  Royden, H.L.: Real Analysis. Macmillan, New York (1968) · Zbl 0197.03501  Sun, P; Freund, R, Computation of minimum-volume covering ellipsoids, Oper. Res., 52, 690-706, (2004) · Zbl 1165.90571  Taubin, G, Estimation of planar curves, surfaces and nonplanar space curves defined by implicit equations, with applications to to edge and range image segmentation, IEEE Trans. Pattern Anal. Machine Intell., 13, 1115-1138, (1991)  Vandenberghe, L; Boyd, S, Semidefinite programming, SIAM Rev., 38, 49-95, (1996) · Zbl 0845.65023  Widder, D.V.: The Laplace Transform. Princeton University Press, Princeton (1946) · Zbl 0060.24801
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.