Separable Augmented Lagrangians for the decomposition of large convex programs

Augmented Lagrangians are very attractive to regularize the classical dual methods for complex constrained optimization problems. They are particularly useful to decentralize the local subproblems in the decomposition of block-structured programs, but, to achieve that goal, they must present a separable structure themselves. This paper shows how to build separable Augmented Lagrangians by applying the Proximal Decomposition method to some monotropic formulations of the global problem where the coupling between the subsystems is merged in a very simple subspace. The approach is very sensitive to the model structure and the paper presents two applications in network optimization: first, the method is applied to the decomposition of a multicommodity flow problem issued from a nonlinear routing problem for packet-switched networks. Significant improvements over classical algorithms like the Flow Deviation method were obtained on large networks with up to 10⁴ commodities. The parallel features of the proximal approach are exploited in a second application on large nonlinear transportation problems. A dense implementation of the code on a 32K processors Connection Machine CM-2 has shown to be competitive with the best known massively parallel algorithms like the row-action method.