Geometry of Convex Optimization

Carnegie Mellon University, Pittsburgh PA

Investigators

Abstract

Certain geometric constructions play a central role in convex optimization - a vital computational technology for a variety of applied disciplines including data and imaging sciences. The very definition of convexity is purely geometric: a set is convex if it contains the segment joining any two points in it. Certain properties of convex objects provide the backbone for powerful optimization theory, and geometric constructions form the core of a variety of effective algorithmic techniques for solving optimization problems. The overarching goal of this research project is a deeper development and tighter integration of geometric properties for convex optimization problems. The main driving force for this project is the design of novel and more powerful algorithmic schemes. Given the role that convex optimization plays in a variety of timely applications, this research will provide opportunities for training doctoral students and for synergies with scholars in multiple disciplines including operations research, machine learning, and mathematics. A main long-term goal of this research plan is to design new algorithms for convex optimization problems via a careful blend of oracles, variable metrics, and adaptive problem preconditioning. To that end, this research project will pursue activities along four main threads. The first thread concerns the design of new algorithms by harnessing the power of separation oracles and space dilation. The second thread will focus on variants of the von Neumann and the Frank-Wolfe algorithms with away steps for faster convergence and sparsity. The third thread concerns refinements of conditioning for convex optimization problems. Special emphasis will be placed on extending the existing theory to problems with flat and nearly flat geometries. The fourth and most ambitious thread of this project will develop novel algorithms that adaptively precondition the problem at hand to rectify potential difficulties due to poor geometric structure such as those that emerge in degenerate or nearly degenerate problems. This last research thread may shed new light into one of the main open problems in computational mathematics, namely the existence of a strongly polynomial-time algorithm for linear programming.