Thesis (Ph. D.)--University of Wisconsin--Madison, 1969. / Typescript. Vita. eContent provider-neutral record in process. Description based on print version record. Includes bibliographical references.

本论文着重研究了带有Lp模球约束以及二次约束的多项式优化问题的计算复杂度以及关于此类问题的近似算法。在本论文中，利用张量对称化的技巧，我们首次证明了当P∈ [2 ，∞] ，任意高阶的带有Lp模球约束的多项式优化问题均为NP 困难。借助模的对偶性质，我们将这类优化问题转化为求解凸体半径的问题，从而使得我们获得了之前研究所无法使用的算法工具。具体来说，利用计算凸几何的算法工具，对于Lp模球约束的多项式优化问题，我们得到了近似比为[附圖]的确定性多项式时间近似算法，其中d为目标多项式的阶次， n 为问题的维度。使用随机算法，我们将近似比进一步提高为此类问题的己知最优值。[附圖]。此外，我们发展了计算凸几何当中对于凸体半径的计算方法，从而设计出了一种对二次约束多项式优化问题近似比为[附圖]的近似算法，其中m为问题的约束个数。我们的结果涵盖并提高了之前关于此类问题的研究结果。我们相信在本论文中使用的新的算法工具，将在今后的多项式优化问题研究中得到更广泛的应用。 / In this thesis, we present polynomial time approximation algorithms for solving various homogeneous polynomial optimization problems and their multilinear relaxations. Specifically, for the problems with Lp ball constraint, where P∈ [2 ，∞], by reducing them to that of determining the Lq-diameter of certain convex body, we show that they can be approximated to within a factor of [with formula] in deterministic polynomial time, where q = p=(p - 1) is the conjugate of p, n is the number of variables, and d is the degree of the polynomial. We further show that with the help of randomization, the approximation guarantee can be improved to [with formula], which is independent of p and is currently the best for the aforementioned problems. Moreover, we extend the argument of deterministic algorithm mentioned above to solve the quadratically constrained polynomial optimization problems. In particular, for any intersection of ellipsoids K, we can, in polynomial time, construct a random polytope P, which satisfies [with formula]. Then, by reducing the problem to that of evaluating the maximum polytopal norm [with formula] induced by P, over certain convex body, we can approximate the quadratically constrained problem within a factor of [with formula] in polynomial time. Our results unify and generalize those in the literature, which focus either on the quadratic case or the case where [with formula]. We believe that the wide array of tools used in this thesis will have further applications in the study of polynomial optimization problems. / Detailed summary in vernacular field only. / Hou, Ke. / On title page "p" is subscript. / Thesis (Ph.D.) Chinese University of Hong Kong, 2013. / Includes bibliographical references (leaves 106-111). / Abstracts also in Chinese.

No description available.

This thesis is based on three papers on selected topics in Asymptotic Geometric Analysis. The first paper is about the volume of high-dimensional random polytopes; in particular, on polytopes generated by Gaussian random vectors. We consider the question of how many random vertices (or facets) should be sampled in order for such a polytope to capture significant volume. Various criteria for what exactly it means to capture significant volume are discussed. We also study similar problems for random polytopes generated by points on the Euclidean sphere. The second paper is about volume distribution in convex bodies. The first main result is about convex bodies that are (i) symmetric with respect to each of the coordinate hyperplanes and (ii) in isotropic position. We prove that most linear functionals acting on such bodies exhibit super-Gaussian tail-decay. Using known facts about the mean-width of such bodies, we then deduce strong lower bounds for the volume of certain caps. We also prove a converse statement. Namely, if an arbitrary isotropic convex body (not necessarily satisfying the symmetry assumption (i)) exhibits similar cap-behavior, then one can bound its mean-width. The third paper is about random polytopes generated by sampling points according to multiple log-concave probability measures. We prove related estimates for random determinants and give applications to several geometric inequalities; these include estimates on the volume-radius of random zonotopes and Hadamard's inequality for random matrices. / Mathematics

No description available.

Dans ce travail, nous nous intéressons à l'estimation d'ensembles convexes dans l'espace Euclidien R^d, en nous penchant sur deux modèles. Dans le premier modèle, nous avons à notre disposition un échantillon de n points aléatoires, indépendants et de même loi, uniforme sur un ensemble convexe inconnu. Le second modèle est un modèle additif de régression, avec bruit sous-gaussien, et dont la fonction de régression est l'indicatrice d'Euler d'un ensemble convexe ici aussi inconnu. Dans le premier modèle, notre objectif est de construire un estimateur du support de la densité des observations, qui soit optimal au sens minimax. Dans le second modèle, l'objectif est double. Il s'agit de construire un estimateur du support de la fonction de régression, ainsi que de décider si le support en question est non vide, c'est-'a-dire si la fonction de régression est effectivement non nulle, ou si le signal observé n'est que du bruit. Dans ces deux modèles, nous nous intéressons plus particulièrement au cas où l'ensemble inconnu est un polytope convexe, dont le nombre de sommets est connu. Si ce nombre est inconnu, nous montrons qu'une procédure adaptative permet de construire un estimateur atteignant la même vitesse asymptotique que dans le cas précédent. Enfin, nous démontrons que ce m$eme estimateur pallie à l'erreur de spécification du modèle, consistant à penser à tort que l'ensemble convexe inconnu est un polytope. Nous démontrons une inégalité de déviation pour le volume de l'enveloppe convexe des observations dans le premier modèle. Nous montrons aussi que cette inégalité implique des bornes optimales sur les moments du volume manquant de cette enveloppe convexe, ainsi que sur les moments du nombre de ses sommets. Enfin, dans le cas unidimensionnel, pour le second modèle, nous donnons la taille asymptotique minimale que doit faire l'ensemble inconnu afin de pouvoir être détecté, et nous proposons une règle de décision, permettant un test consistant du caractère non vide de cet ensemble.

This work refers to ball-intersections bodies as well as covering, packing, and kissing problems related to balls and spheres in normed spaces. A quick introduction to these topics and an overview of our results is given in Section 1.1 of Chapter 1. The needed background knowledge is collected in Section 1.2, also in Chapter 1. In Chapter 2 we define ball-intersection bodies and investigate special classes of them: ball-hulls, ball-intersections, equilateral ball-polyhedra, complete bodies and bodies of constant width. Thus, relations between the ball-hull and the ball-intersection of a set are given. We extend a minimal property of a special class of equilateral ball-polyhedra, known as Theorem of Chakerian, to all normed planes. In order to investigate bodies of constant width, we develop a concept of affine orthogonality, which is new even for the Euclidean subcase. In Chapter 2 we solve kissing, covering, and packing problems. For a given family of circles and lines we find at least one, but for some families even all circles kissing all the members of this family. For that reason we prove that a strictly convex, smooth normed plane is a topological Möbius plane. We give an exact geometric description of the maximal radius of all homothets of the unit disc that can be covered by 3 or 4 translates of it. Also we investigate configurations related to such coverings, namely a regular 4-covering and a Miquelian configuration of circles. We find the concealment number for a packing of translates of the unit ball.

This work refers to ball-intersections bodies as well as covering, packing, and kissing problems related to balls and spheres in normed spaces. A quick introduction to these topics and an overview of our results is given in Section 1.1 of Chapter 1. The needed background knowledge is collected in Section 1.2, also in Chapter 1. In Chapter 2 we define ball-intersection bodies and investigate special classes of them: ball-hulls, ball-intersections, equilateral ball-polyhedra, complete bodies and bodies of constant width. Thus, relations between the ball-hull and the ball-intersection of a set are given. We extend a minimal property of a special class of equilateral ball-polyhedra, known as Theorem of Chakerian, to all normed planes. In order to investigate bodies of constant width, we develop a concept of affine orthogonality, which is new even for the Euclidean subcase. In Chapter 2 we solve kissing, covering, and packing problems. For a given family of circles and lines we find at least one, but for some families even all circles kissing all the members of this family. For that reason we prove that a strictly convex, smooth normed plane is a topological Möbius plane. We give an exact geometric description of the maximal radius of all homothets of the unit disc that can be covered by 3 or 4 translates of it. Also we investigate configurations related to such coverings, namely a regular 4-covering and a Miquelian configuration of circles. We find the concealment number for a packing of translates of the unit ball.

We consider the distribution of the zero and typical cells of a (homogeneous) Poisson hyperplane tessellation. We give a direct proof adapted to our setting of the well known Complementary Theorem. We provide sharp bounds for the tail distribution of the number of facets. We also improve existing bounds for the tail distribution of size measurements of the cells, such as the volume or the mean width. We improve known results about the generalised D.G. Kendall's problem, which asks about the shape of large cells. We also show that cells with many facets cannot be close to a lower dimensional convex body. We tacle the much less study problem of the number of facets and the shape of small cells. In order to obtain the results above we also develop some purely geometric tools, in particular we give new results concerning the polytopal approximation of an elongated convex body.