Geometric optimization problems with applications to ellipsoidal approximations and quasi-Newton methods

Abstract

Our goal in this dissertation is to study some optimization problems with special structure and exploit this structure to obtain additional information that will be useful in the development of numerical methods. In particular, we are interested in geometric optimization problems including ellipsoidal approximations of convex bodies and the ones related to the DFP and BFGS updates in the context of quasi-Newton methods.In the context of ellipsoidal approximations of convex bodies, we treat two problems, namely, finding an ellipsoid of minimum volume containing a convex body (in $\R^n$) and finding an ellipsoid of maximum volume contained in a convex body. We make contributions to this area in various directions. We, first, present a unified and modern presentation of the basic results about these extremal volume ellipsoids. Then, we study the symmetry properties of convex bodies and the associated symmetry properties of their extremal volume ellipsoids. Additionally, we provide exact determination of the extremal volume ellipsoids of some special convex bodies employing our results on their symmetry properties. Finally, we study the duality of the extremal volume ellipsoids and, for this purpose, we also develop the duality of semi--infinite programming.For the geometric optimization problems appearing in the context of quasi-Newton methods, our contributions are twofold, namely, providing simple proofs of some of the existing results and studying, for the first time, the duals of the variational problems for the DFP and BFGS updates.