2
(2 x 3 y 5) 2
ADMM算法应用实例
• • • • • • 求解步骤如下 1） xk yk k 0 2） x arg min L ( x, y , ), 3） y arg min L ( x , y, ), k 1 k k 1 k 1 (2 x 3 y 5) 4） k 1 pri k 1 dual if s and , stop. Else, goto 2) 5） 2 2
ADMM算法原理
2015-12-3
提纲
• ADMM算法原理介绍 • ADMM算法应用实例
ADMM算法原理介绍
• Alternating Direction Method of Multipliers (ADMM) 交替方向乘子法 • 设计于1970年代，在求解大规模分布式凸 优化问题中具有广泛应用。 • 凸优化：目标函数和约束均为凸；
k 1 k k 0 x 3
k 1 k 1 k 1 y 4
ADMM算法应用实例
• MATLAB仿真结果如下：
0.8
x opt=0.53846, y opt=1.3077 1.8 1.6 1.4 x y
0.7
Optimal decision variables
0.6
Objective function
-8
0
5
10
15 20 Iteration number
25
30
35
0
5
10
15 20 Iteration number
25
30
35
– 其中：
ADMM算法应用实例
• 求解下列最优化问题
min ( x 1) 2 ( y 2) 2
x, y
s.t. 0 x 3, 1 y 4, 2x 3y 5
• 增广拉格朗日函数为：
L ( x, y, ) ( x 1) 2 ( y 2) 2 (2 x 3 y 5)
凸函数的特征
• 凸集合与凸函数
ADMM算法原理
• ADMM求解最优化问题
ADMM算法原理
• 增量拉格朗日函数
ADMM算法原理
• 分解原问题，并各自求解
ADMM算法原理
• 分解原问题，并各自求解
ADMM算法原理
• 收敛性
ADMM算法原理
• 停止条件
– 对偶残差： – 主残差： – 同时满足下面的不等式：
1.2 1 0.8 0.6 0.4
0.5
0.4
0.3
0.2
0.2 0
0.1
0
5
10
15 20 Iteration number
25
30
35
0
5
10
15 20 Iteration number
25
30
35
ADMM算法应用实例
• MATLAB仿真结果如下：
10 10 10 10 10 10 10 10 10
1 0
Primal residual Primal feasibility
10 10 10 10 10 10 10 10 10
0
-1
Dual residual Dual feasibility
-1
-2
-2
-3
Primal residual
-3
Dual residual
-4
-4
-5
-5
-6
-6
-7
-7