Frameworks for High Dimensional Optimization

I present frameworks for solving extremely large, prohibitively massive optimization problems. Today, practical applications require optimization solvers to work at extreme scales, but existing solvers do not often scale as desired. I present black-box acceleration algorithms for speeding up optimization solvers, in both distributed and parallel settings. Given a huge problem, I develop dimension reduction techniques that allow the problem to be solved in a fraction of the original time, and simultaneously make the computation amenable to distributed computation. Efficient, dependable and secure distributed computing is increasingly fundamental to a wide range of core applications including distributed data centers, decentralized power grid, coordination of autonomous devices, and scheduling and routing problems.

In particular, I consider two optimization settings of interest. First, I consider packing linear programming (LP). LP solvers are fundamental to many problems in supply chain management, routing, learning and inference problems. I present a framework that speeds up linear programming solvers such as Cplex and Gurobi by an order of magnitude, while maintaining provably nearly optimal solutions. Secondly, I present a distributed algorithm that achieves an exponential reduction in message complexity compared to existing distributed methods. I present both empirical demonstrations and theoretical guarantees on the quality of the solution and the speedup provided by my methods