1. Introduction

1.1 Goal

Background: BigData -> extremely large amount of data. Very high-dimensional data, distributed stored data.

• Decentralized collection or storage.
• Distributed solution methods (e.g. ADMM).

Robust methods for :

• Arbitraty-scale optimization * Machine learning/statistics with huge data-size * Dynamic optimziation on large-scale network
• Decentralized optimization * Devices/processors/agents coordinate to solve large problem, by passing relatively small messages.

1.2 Closely Related Algorithms

• Dual Decomposition. (explained in Chapter 2)
• The method of multipliers. (explained in Chapter 2)
• Douglas-Rachford splitting. (lots of them 1950s, 1979)
• Proximal point algorithm. (Rockafellar 1976)
• Dykstra’s alternating projections. (1983)
• Spingarn’s method of partial inverses. (1985)
• Rockafellar-Wets progressive hedging. (1991)
• Proximal methods. (Rockafellar, many others, 1976-present)
• Bregman iterative algorithms for l1 problems. (2008-present)
• Most of these are special cases of the proximal point algorithm.

ADMM: The blender of the decomposability of dual ascent with the superior convergence properties of the method of multipliers.

1.3 BluePrint

• Dual problem \(\to\) Dual ascent method \(\to\) Decomposition.
• Method of Multipliers \(\to\) Augmented Lagrangian \(\to\) Cannot decompose (as the variables are entangled)
• ADMM \(\to\) Decomposed variation of augmented lagrangian method.

1.4 Interpretation as tatonnement process

• Tatonnement process: iteratively update prices to clear market.
• Work towards equilibrium by increasing/decreasing prices of goods based on excess demand/supply.
• Dual decomposition is the simplest tatonnement algorithm.
• ADMM adds proximal regulization: * incorporate agents’ prior commitment to help clear market. * convergence far more robust convergence that dual decompostion.