×

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
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Anastassiou, G.A.: Moments in Probability Approximation Theory. Longman Scientific & Technical, UK (1993) · Zbl 0847.41001
[2] d’Aspremont, A, Smooth optimization with approximate gradient, SIAM J. Optim., 19, 1171-1183, (2008) · Zbl 1180.90378
[3] Ash, R.B.: Real Analysis and Probability. Academic Press Inc., Boston (1972) · Zbl 1381.28001
[4] Ball, K, Ellipsoids of maximal volume in convex bodies, Geom. Dedicata, 41, 241-250, (1992) · Zbl 0747.52007
[5] Ball, K; Johnson, WB (ed.); Lindenstrauss, J (ed.), Convex geometry and functional analysis, 161-194, (2001), Amsterdam · Zbl 1017.46004
[6] Barvinok, AI, Computing the volume, counting integral points, and exponential sums, Discrete Comput. Geom., 10, 123-141, (1993) · Zbl 0774.68054
[7] Bastero, J; Romance, M, John’s decomposition of the identity in the non-convex case, Positivity, 6, 1-16, (2002) · Zbl 1018.52004
[8] Bayer, C; Teichmann, J, The proof of tchakaloff’s theorem, Proc. Am. Math. Soc., 134, 303-3040, (2006) · Zbl 1093.41016
[9] Bookstein, FL, Fitting conic sections to scattered data, Comp. Graph. Image. Process., 9, 56-71, (1979)
[10] Calafiore, G, Approximation of \(n\)-dimnsional data using spherical and ellipsoidal primitives, IEEE Trans. Syst. Man. Cyb., 32, 269-276, (2002)
[11] Chernousko, FL, Guaranteed estimates of undetermined quantities by means of ellipsoids, Sov. Math. Dodkl., 21, 396-399, (1980) · Zbl 0454.93010
[12] Croux, C; Haesbroeck, G; Rousseeuw, PJ, Location adjustment for the minimum volume ellipsoid estimator, Stat. Comput., 12, 191-200, (2002)
[13] 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
[14] 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
[15] Faraut, J., Korányi, A.: Analysis on Symmetric Cones. Clarendon Press, Oxford (1994) · Zbl 0841.43002
[16] Freitag, E., Busam, R.: Complex Analysis, 2nd edn. Springer, Berlin (2009) · Zbl 1167.30001
[17] Gander, W; Golub, GH; Strebel, R, Least-squares Fitting of circles and ellipses, BIT, 34, 558-578, (1994) · Zbl 0817.65008
[18] Helton, JW; Nie, J, A semidefinite approach for truncated K-moment problems, Fond. Comput. Math., 12, 851-881, (2012) · Zbl 1259.44005
[19] Henk, M.: Löwner-John ellipsoids. Documenta Math. 95-106 (2012) (extra volume: optimization stories)
[20] Henrion, D; Lasserre, JB; Lofberg, J, Gloptipoly 3: moments, optimization and semidefinite programming, Optim. Method. Softw., 24, 761-779, (2009) · Zbl 1178.90277
[21] Henrion, D; Lasserre, JB; Savorgnan, C, Approximate volume and integration of basic semi-algebraic sets, SIAM Rev., 51, 722-743, (2009) · Zbl 1179.14037
[22] 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
[23] 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
[24] 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
[25] Hiriart-Urruty, J.B., Lemarechal, C.: Convex Analysis and Minimization Algorithms I. Springer, Berlin (1993) · Zbl 0795.49001
[26] Hiriart-Urruty, J.B., Lemarechal, C.: Convex Analysis and Minimization Algorithms II. Springer, Berlin (1993) · Zbl 0795.49002
[27] Karimi, A; Khatibi, H; Longchamp, R, Robust control of polytopic systems by convex optimization, Automatica, 43, 1395-1402, (2007) · Zbl 1130.93339
[28] 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
[29] Kemperman, JHB, The general moment problem, a geometric approach, Annals Math. Stat., 39, 93-122, (1968) · Zbl 0162.49501
[30] Lasserre, JB, Global optimization with polynomials and the problem of moments, SIAM J. Optim., 11, 796-817, (2001) · Zbl 1010.90061
[31] Lasserre, J.B.: Moments, Positive Polynomials and Their Applications. Imperial College, London (2009)
[32] Lasserre, JB, Recovering an homogeneous polynomial from moments of its level set, Discrete Comput. Geom., 50, 673-678, (2013) · Zbl 1311.44009
[33] Morosov, A; Shakirov, S, New and old results in resultant theory, Theor. Math. Phys., 163, 587-617, (2010) · Zbl 1254.15011
[34] Morosov, A., Shakirov, S.: Introduction to integral discriminants, J. High Energy Phys. 12 (2009). arXiv:0911.5278v1
[35] Nurges, U, Robust pole assignment via reflection coefficientsof polynomials, Automatica, 42, 1223-1230, (2006) · Zbl 1122.93033
[36] O’Rourke, J; Badler, NI, Decomposition of three-dimensional objets into spheres, IEEE Trans. Pattern Anal. Machine Intell., 1, 295-305, (1979)
[37] Pratt, V.: Direct least squares fitting of algebraic surfaces. ACM J. Comp. Graph. 21, 145-152 (1987)
[38] Putinar, M, Positive polynomials on compact semi-algebraic sets, Indiana Univ. Math. J., 42, 969-984, (1993) · Zbl 0796.12002
[39] Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton, NJ (1970) · Zbl 0193.18401
[40] Rosen, JB, Pattern separation by convex programming techniques, J. Math. Anal. Appl., 10, 123-134, (1965) · Zbl 0134.37503
[41] Rosin, PL, A note on the least squares Fitting of ellipses, Pattern Recog. Lett., 14, 799-808, (1993) · Zbl 0802.68155
[42] Rosin, PL; West, GA, Nonparametric segmentation of curves into various representations, IEEE Trans. Pattern Anal. Machine Intell., 17, 1140-1153, (1995)
[43] Rousseeuw, P.J., Leroy, A.M.: Robust Regression and Outlier Detection. John Wiley, New York (1987) · Zbl 0711.62030
[44] Royden, H.L.: Real Analysis. Macmillan, New York (1968) · Zbl 0197.03501
[45] Sun, P; Freund, R, Computation of minimum-volume covering ellipsoids, Oper. Res., 52, 690-706, (2004) · Zbl 1165.90571
[46] 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)
[47] Vandenberghe, L; Boyd, S, Semidefinite programming, SIAM Rev., 38, 49-95, (1996) · Zbl 0845.65023
[48] 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.