Optimization Online


A Modified Frank-Wolfe Algorithm for Computing Minimum-Area Enclosing Ellipsoidal Cylinders: Theory and Algorithms

S. Damla Ahipasaoglu (dse8***at***cornell.edu)
Michael J. Todd (mjt7***at***cornell.edu)

Abstract: We study a first-order method to find the minimum cross-sectional area ellipsoidal cylinder containing a finite set of points. This problem arises in optimal design in statistics when one is interested in a subset of the parameters. We provide convex formulations of this problem and its dual, and analyze a method based on the Frank-Wolfe algorithm for their solution. Under suitable conditions on the behavior of the method, we establish global and local convergence properties. However, difficulties may arise when a certain submatrix loses rank, and we describe a technique for dealing with this situation.

Keywords: Linear convergence, Frank-Wolfe algorithm, minimum-volume ellipsoids, minimum-area cylinders, D-optimality, and D$_k$-optimality.

Category 1: Convex and Nonsmooth Optimization

Citation: Technical Report No. 1472, School of Operations Research and Information Engineering, Cornell University, Ithaca, NY 14853-3801. Submitted to Mathematical Programming.

Download: [PDF]

Entry Submitted: 04/16/2009
Entry Accepted: 04/16/2009
Entry Last Modified: 09/14/2009

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society