FoCM 2014 conference
Workshop B3 - Continuous Optimization
December 15, 17:30 ~ 18:00 - Room A21
Geodesic distance maximization via convex optimization
Maryam Fazel
University of Washington, USA - mfazel@uw.edu
Given a graph with fixed edge weights, finding the shortest path, also known as the geodesic, between two nodes is a well-studied network flow problem. We introduce the Geodesic Distance Maximization Problem (GDMP), i.e., the problem of finding the edge weights that maximize the length of the geodesic, subject to convex constraints on the weights.
We show that GDMP is a convex optimization problem for a wide class of flow costs, and provide a physical interpretation using the dual. We present applications in various fields, including network interdiction, optical lens design, and control of forest fires. GDMP can be generalized from graphs to continuous fields, where the Eikonal equation (a fundamental partial differential equation governing flow propagation) naturally arises in the dual problem. For the case of propagation on a regular grid, the problem can be cast as a second-order cone program; however standard solvers fail to scale to the large grid sizes of interest. We develop an Alternating Direction Method of Multipliers (ADMM) algorithm by exploiting specific problem structure to solve large-scale GDMP, and demonstrate its effectiveness in numerical examples.
Joint work with De Meng (University of Washington, USA), Pablo A. Parrilo (MIT, USA) and Stephen P. Boyd (Stanford University, USA).