总目录
一、 凸优化基础（Convex Optimization basics）
凸优化基础（Convex Optimization basics）
二、 一阶梯度方法（First-order methods）
梯度下降（Gradient Descent）
次梯度（Subgradients）
近端梯度法（Proximal Gradient Descent）
随机梯度下降（Stochastic gradient descent）
三、对偶
线性规划中的对偶（Duality in linear programs）
凸优化中的对偶（Duality in General Programs）
KKT条件（Karush-Kuhn-Tucker Conditions）
对偶的应用及拓展（Duality Uses and Correspondences）
对偶方法（Dual Methods）
交替方向乘子法（Alternating Direction Method of Multipliers）
近端梯度法（Proximal Gradient Descent）
在凸优化问题中，对于可微分的目标函数，我们可以通过梯度下降法（gradient descent）迭代求解最优解，而对于不可微分的目标函数，通过引入次梯度（subgradient）也可以迭代求解最优解，然而比起梯度下降法，次梯度法的速度比较缓慢。为此，针对于一些整体不可微分但却可以分解的目标函数来说，我们可以使用一种更快的算法——近端梯度法。
1. 可分解的目标函数
考虑一个目标函数可以分解为如下形式的两个函数：
f ( x ) = g ( x ) + h ( x ) (1) f(x)=g(x)+h(x) \tag{1}
f(x)=g(x)+h(x)(1)
其中，g ( x ) g(x)g(x)是凸函数且是可微分的，h ( x ) h(x)h(x)也是凸函数但可能不可微分。使用近端梯度下降，可以实现O ( 1 / ϵ ) O(1/\epsilon)O(1/ϵ)的收敛率（ϵ = f ( x ( k ) ) − f ( x ∗ ) \epsilon=f(x^{(k)})-f(x^*)ϵ=f(x
(k)
)−f(x
∗
)，即当前迭代结果与最优解之间的偏差）。通过对近端梯度法加速，可以达到O ( 1 / ϵ ) O(1/\sqrt\epsilon)O(1/
ϵ
)收敛速率。
2. 梯度下降法回顾
对于一个可微分的凸函数f ( z ) f(z)f(z)，假设起始点在x xx，则可以做二阶泰勒展开：
f ( z ) ≈ f ( x ) + ∇ f ( x ) T ( z − x ) + 1 2 ∇ 2 f ( x ) ∥ z − x ∥ 2 2 (2) f(z)\approx f(x)+\nabla f(x)^T(z-x)+\frac{1}{2}\nabla^2f(x)\|z-x\|^2_2 \tag{2}
f(z)≈f(x)+∇f(x)
T
(z−x)+
2
1
∇
2
f(x)∥z−x∥
2
2
(2)
通过替换∇ 2 f ( x ) = 1 t I \nabla^2f(x)=\frac{1}{t}I∇
2
f(x)=
t
1
I，可以得到
f ( z ) ≈ f ( x ) + ∇ f ( x ) T ( z − x ) + 1 2 t ∥ z − x ∥ 2 2 (3) f(z)\approx f(x)+\nabla f(x)^T(z-x)+\frac{1}{2t}\|z-x\|^2_2 \tag{3}
f(z)≈f(x)+∇f(x)
T
(z−x)+
2t
1
∥z−x∥
2
2
(3)
最小化上述二次近似
x + = arg min z f ( x ) + ∇ f ( x ) T ( z − x ) + 1 2 t ∥ z − x ∥ 2 2 (4) x^+=\arg\min_zf(x)+\nabla f(x)^T(z-x)+\frac{1}{2t}\|z-x\|^2_2 \tag{4}
x
+
=arg
z
min
f(x)+∇f(x)
T
(z−x)+
2t
1
∥z−x∥
2
2
(4)
可以得到下一个点的位置
z = x + = x − t ∇ f ( x ) (5) z=x^+=x-t\nabla f(x) \tag{5}
z=x
+
=x−t∇f(x)(5)
这就是我们常见的梯度下降的迭代更新策略。
3. 近端投影
如果f ff不可微，但可以分解为上述的两个函数g gg和h hh，则我们仍然可以使用平滑部分g gg的二次近似来定义向最小值走的一步：
x + = arg min a g ( z ) + h ( z ) ≈ arg min z g ( x ) + ∇ g ( x ) T ( z − x ) + 1 2 t ∥ z − x ∥ 2 2 + h ( z ) (6)
\begin{aligned} x^+&=\arg\min_a g(z)+h(z) \\ &\approx \arg\min_z g(x)+\nabla g(x)^T(z-x)+\frac{1}{2t}\|z-x\|^2_2+h(z) \tag{6} \end{aligned}
\begin{aligned} x^+&=\arg\min_a g(z)+h(z) \\ &\approx \arg\min_z g(x)+\nabla g(x)^T(z-x)+\frac{1}{2t}\|z-x\|^2_2+h(z) \tag{6} \end{aligned}
x
+
=arg
a
min
g(z)+h(z)
≈arg
z
min
g(x)+∇g(x)
T
(z−x)+
2t
1
∥z−x∥
2
2
+h(z)
(6)
式（6）可以写成：
x + = arg min z 1 2 t ∥ z − ( x − t ∇ g ( x ) ) ∥ 2 2 + h ( z ) : = p r o x h , t ( x − t ∇ g ( x ) ) (7) x^+=\arg\min_z\frac{1}{2t}\|z-(x-t\nabla g(x))\|^2_2+h(z):=prox_{h,t}(x-t\nabla g(x)) \tag{7}
x
+
=arg
z
min
2t
1
∥z−(x−t∇g(x))∥
2
2
+h(z):=prox
h,t
(x−t∇g(x))(7)
其中，近端函数p r o x proxprox定义为
p r o x h , t ( x ) = arg min z 1 2 t ∥ z − x ∥ 2 2 + h ( z ) (8) prox_{h,t}(x)=\arg\min_z\frac{1}{2t}\|z-x\|^2_2+h(z) \tag{8}
prox
h,t
(x)=arg
z
min
2t
1
∥z−x∥
2
2
+h(z)(8)
4. 近端梯度下降
使用近端函数，我们可以定义一个迭代过程，叫做迭代梯度下降。其过程如下：
首先，选择一个初始点x ( 0 ) x^{(0)}x
(0)
，然后重复：
x ( i ) = p r o x h , t i ( x ( i − 1 ) − t i ∇ g ( x ( i − 1 ) ) ) , i = 1 , 2 , 3 , . . . (9) x^{(i)}=prox_{h,t_i}(x^{(i-1)}-t_i\nabla g(x^{(i-1)})), i=1,2,3,... \tag{9}
x
(i)
=prox
h,t
i
(x
(i−1)
−t
i
∇g(x
(i−1)
)),i=1,2,3,...(9)
使用该方法有几个优点：
对于许多h hh函数，其近端投影p r o x h , t prox_{h,t}prox
h,t
有解析解；
p r o x t prox_{t}prox
t
仅仅依赖于h hh，因此可以被用于不同的g gg函数；
g gg可以是任意复杂的函数，只要我们能计算其梯度；
4.1 例子：迭代软阈值算法（ISTA）
考虑下面lasso问题：
min β ∈ R p 1 2 ∥ y − X β ∥ 2 2 + λ ∥ β ∥ 1 (10) \min_{\beta \in \mathcal{R}^p}\frac{1}{2}\|y-X\beta\|^2_2+\lambda\|\beta\|_1 \tag{10}
β∈R
p
min
2
1
∥y−Xβ∥
2
2
+λ∥β∥
1
(10)
令g ( β ) = 1 2 ∥ y − X β ∥ 2 2 g(\beta)=\frac{1}{2}\|y-X\beta\|^2_2g(β)=
2
1
∥y−Xβ∥
2
2
，h ( β ) = ∥ β ∥ 1 h(\beta)=\|\beta\|_1h(β)=∥β∥
1
。对于目标函数的近端映射可以用软阈值法来计算：
p r o x h , t ( β ) = arg min z 1 2 t ∥ β − z ∥ 2 2 + λ ∥ z ∥ 1 = S λ t ( β ) (11) prox_{h,t}(\beta)=\arg\min_z \frac{1}{2t}\|\beta-z\|^2_2+\lambda\|z\|_1=S_{\lambda t}(\beta) \tag{11}
prox
h,t
(β)=arg
z
min
2t
1
∥β−z∥
2
2
+λ∥z∥
1
=S
λt
(β)(11)
其中，S λ t ( β ) S_{\lambda t}(\beta)S
λt
(β)有解析解，相当于软阈值算子：
[ S λ t ] i = { β i − λ t , β i > λ t 0 , − λ t ≤ β i ≤ λ t β i + λ t , β i < − λ t (12) [S_{\lambda t}]_i=\left\{
βi−λt,0,βi+λt,βi>λt−λt≤βi≤λtβi<−λt
βi−λt,βi>λt0,−λt≤βi≤λtβi+λt,βi<−λt
\right. \tag{12}
[S
λt
]
i
=
⎩
⎪
⎨
⎪
⎧
β
i
−λt,
0,
β
i
+λt,
β
i
>λt
−λt≤β
i
≤λt
β
i
<−λt
(12)
而g ( β ) g(\beta)g(β)的梯度为X T ( X β − y ) X^T(X\beta-y)X
T
(Xβ−y)，因此，我们可以得到近端梯度下降更新策略：
β + = S λ t ( β − t X T ( X β − y ) ) (13) \beta^+=S_{\lambda t}(\beta-tX^T(X\beta-y)) \tag{13}
β
+
=S
λt
(β−tX
T
(Xβ−y))(13)
5. 特殊情况
近端梯度下降相当于梯度下降法的一种推广，因此也被称为复合梯度下降（composite gradient descent）或者广义梯度下降（generalized gradient descent）。下面几个特殊的情况可以看出为什么称之为广义梯度下降。
5.1 梯度下降
当h ( x ) = 0 h(x)=0h(x)=0时，近端映射函数变为：
p r o x t ( x ) = arg min z 1 2 t ∥ x − z ∥ 2 2 = x (14) prox_t(x)=\arg\min_z\frac{1}{2t}\|x-z\|^2_2=x \tag{14}
prox
t
(x)=arg
z
min
2t
1
∥x−z∥
2
2
=x(14)
因此，更新策略变为
x ( k ) = x ( k − 1 ) − t k ∇ g ( x ( k − 1 ) ) , k = 1 , 2 , 3 , . . . (15) x^{(k)}=x^{(k-1)}-t_k\nabla g(x^{(k-1)}), k=1,2,3,... \tag{15}
x
(k)
=x
(k−1)
−t
k
∇g(x
(k−1)
),k=1,2,3,...(15)
即正常的梯度下降法。
5.2 投影梯度下降
当h ( x ) = I c h(x)=I_ch(x)=I
c
，I c I_cI
c
为集合C CC的指示函数时，近端映射函数变为：
p r o x t ( x ) = arg min z 1 2 t ∥ x − z ∥ 2 2 + I c = arg min z ∈ C 1 2 t ∥ x − z ∥ 2 2 = P C ( x ) (16)
proxt(x)=argminz12t∥x−z∥22+Ic=argminz∈C12t∥x−z∥22=PC(x)
proxt(x)=argminz12t‖x−z‖22+Ic=argminz∈C12t‖x−z‖22=PC(x)
\tag{16}
prox
t
(x)
=arg
z
min
2t
1
∥x−z∥
2
2
+I
c
=arg
z∈C
min
2t
1
∥x−z∥
2
2
=P
C
(x)
(16)
其中，P C ( x ) P_C(x)P
C
(x)表示集合C CC上的投影算子。
因此，更新策略变为
x ( k ) = P c ( x ( k − 1 ) − t k ∇ g ( x ( k − 1 ) ) ) , k = 1 , 2 , 3 , . . . (17) x^{(k)}=P_c(x^{(k-1)}-t_k\nabla g(x^{(k-1)})), k=1,2,3,... \tag{17}
x
(k)
=P
c
(x
(k−1)
−t
k
∇g(x
(k−1)
)),k=1,2,3,...(17)
即为投影梯度下降法。其先使用正常的梯度更新策略，然后将得到的x xx投影回集合C CC中。
5.3 近端最小化算法
当g ( x ) = 0 g(x)=0g(x)=0时，更新策略变为：
x ( k ) = arg min z 1 2 t ∥ x ( k − 1 ) − z ∥ 2 2 + h ( z ) , k = 1 , 2 , 3 , . . . (18) x^{(k)} = \arg\min_z\frac{1}{2t}\|x^{(k-1)}-z\|^2_2+h(z), k=1,2,3,... \tag{18}
x
(k)
=arg
z
min
2t
1
∥x
(k−1)
−z∥
2
2
+h(z),k=1,2,3,...(18)
其叫做近端最小化算法（proximal minimization algorithm）。其比次梯度方法快，但仅仅适用于近端算子是闭合形式的情况。
————————————————
版权声明：本文为CSDN博主「JimmyCM」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/zbwgycm/article/details/83060251
