Alternating Direction Method of Multipliers

author: Stephen P. Boyd, Department of Electrical Engineering, Stanford University
published: Jan. 25, 2012,   recorded: December 2011,   views: 2684
Categories
You might be experiencing some problems with Your Video player.

Slides

Slides
0:00 Alternating Direction Method of Multipliers
1:20 Goals
4:07 Outline - 01
4:28 Dual problem
5:55 Dual ascent
7:29 Dual decomposition - 01
8:04 Dual ascent
8:17 Dual decomposition - 02
9:07 Outline - 02
9:17 Method of multipliers - 01
10:46 Method of multipliers dual update step
11:58 Method of multipliers - 02
13:33 Outline - 03
13:35 Alternating direction method of multipliers - 01
14:17 Alternating direction method of multipliers - 02
15:46 Alternating direction method of multipliers - 03
16:07 ADMM and optimality conditions
17:17 ADMM with scaled dual variables
18:17 Convergence
21:45 Related algorithms
23:22 ADMM with scaled dual variables
23:58 Common patterns
27:05 Decomposition
27:24 Common patterns
27:41 Proximal operator
29:40 Quadratic objective
32:17 Smooth objective
32:21 Quadratic objective
32:42 Smooth objective
33:39 Outline - 04
33:41 Constrained convex optimization
35:55 Lasso
37:17 Lasso example
38:43 Sparse inverse covariance selection
39:50 Sparse inverse covariance selection via ADMM
40:54 Analytical solution for X-update
41:09 Sparse inverse covariance selection example
41:39 Outline - 05
41:52 Consensus optimization
43:24 Consensus optimization via ADMM - 01
44:03 Consensus optimization via ADMM - 02
45:33 Statistical interpretation
46:01 Consensus optimization via ADMM - 02
46:16 Statistical interpretation
46:57 Consensus classification
47:40 Consensus SVM example
48:29 Iteration 1
49:01 Iteration 5
49:07 Iteration 40
50:04 Distributed lasso example
53:21 Exchange problem
54:48 Exchange ADMM
55:45 Interpretation as tatonnement process
55:49 Distributed dynamic energy management
56:22 Summary and conclusions

Related content

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
Lecture popularity: You need to login to cast your vote.
 
    Delicious Bibliography

Description

Problems in areas such as machine learning and dynamic optimization on a large network lead to extremely large convex optimization problems, with problem data stored in a decentralized way, and processing elements distributed across a network. We argue that the alternating direction method of multipliers is well suited to such problems. The method was developed in the 1970s, with roots in the 1950s, and is equivalent or closely related to many other algorithms, such as dual decomposition, the method of multipliers, Douglas-Rachford splitting, Spingarn's method of partial inverses, Dykstra's alternating projections, Bregman iterative algorithms for $\ell_1$ problems, proximal methods, and others. After briefly surveying the theory and history of the algorithm, we discuss applications to statistical and machine learning problems such as the lasso and support vector machines.

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Write your own review or comment:

make sure you have javascript enabled or clear this field: