问题形式
- 原问题：
)
，
，其中)
是个凸函数
- 原问题的Lagrangian：
:=f(x)+\left<\lambda,Ax-b\right>)
，后面的尖括号是内积的操作符
- 显然：
+\left<\lambda,Ax-b\right>=\left\{\begin{matrix}f(x),&Ax-b\\\infty,&otherwise\\\end{matrix}\right.)
- 因此，原问题等于：
,s.t.Ax=b\Leftrightarrow&space;min_{x}max_{\lambda}\L(x,\lambda))
- 几何解释
- 最优解即Lagrangian函数的鞍点
- 从上图可以看到，
时，
取无穷大，即可让Lagrangian函数趋于无穷大；
时，取负无穷大，即可让Lagrangian函数趋于无穷大；只有当
时，无论取什么值，Lagrangian函数的值都保持在一个上界之下
Uzawa’s Method
- 推导过程
:=f(x)+\left<\lambda,Ax-b\right>)
的后半部分:=f(x)+\left<\lambda,Ax-b\right>)
的取值是或
，即对于前面的
来说，Lagrangian函数是不连续的，导致这个min问题很难求- 现在假设我们把min和max交换一下顺序，
:=f(x)+\left<\lambda,Ax-b\right>)
，并且，如果后半部分:=f(x)+\left<\lambda,Ax-b\right>)
是严格凸的话，给定一个就可以很轻易的求解
- 注意！von Neumann提到：
\leq&space;min_{x}max_{\lambda}\L(x,\lambda))
，当且仅当连续且凸时取等号
- 因此我们直接通过梯度上升法求解对做maximize的对偶问题：
:=min_{x}f(x)+\left<\lambda,Ax-b\right>)
- 由于每确定一个，都可以求得一个确定的，所以的值本质上是关于的函数，因此上面的对偶问题又可以写成
=\L(x^{*}(\lambda),\lambda))
- 我们将它对求导，
，注意
就是0，对于凸函数来说，导数为0的点就是最优解所在的点，所以})
，也就说，我们给定一个，可以确定一个最优的，然后用求得
后，通过梯度上升求得新的.
- 总结一下，迭代步骤如下：
\\\lambda^{k+1}=\lambda^{k}+\alpha(Ax^{k+1}-b)\end{matrix}\right.)
是沿梯度方向前进的步长
- 缺陷
- (致命)该方法要求是凸的
- (致命)该方法要求关于原问题的优化变量是严格凸的
- 梯度上升的步长需要调参
- 收敛速度不一定快，因为严格凸不保证函数的光滑性，如果函数不光滑，在某些点就只存在次梯度，根据前面的介绍，沿着次梯度的反（正）方向走不保证函数值下降（上升）。
