A modified Frank-Wolfe algorithm for computing minimum-area enclosing ellipsoidal cylinders: Theory and algorithms

作者：Ahipasaoglu S Damla^*; Todd Michael J

来源：Computational Geometry-Theory and Applications, 2013, 46(5): 494-519.

DOI：10.1016/j.comgeo.2011.11.004

• Linear convergence
• Frank-Wolfe algorithm
• Minimum-volume ellipsoids
• Minimum-area cylinders
• D-optimality
• D-k-optimality

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.

• 出版日期2013-7