背景
- PHR是Powell、Hestenes和Rockafellar三个人名的缩写，前两个人在等式约束的优化问题中提出了增广拉格朗日乘子法，第三个作者将其推广到不等式约束上，并给出了新的解释
等式约束
- 问题形式
- 推导
- Uzawa’s method
- 通过冯诺依曼定理将minmax问题转化为maxmin（对偶）问题，只需要满足原问题是严格凸的，原问题和对偶问题的最优解就是一致的
:=min_{x}f(x)+\lambda^{T}h(x))
- 如果原问题不是严格凸，上面的式子求得的
就不是唯一的，导致)
不是光滑的，梯度)
有可能不存在
- PHR Augmented Lagrangian Method
- 核心思路
- 不直接依赖冯诺依曼定理将minmax问题转化为maxmin问题。
- 再来观察一下原问题
- 现在的主要难点在于，函数的max部分，取值要么是无穷大要么是一个定值，他是一个non smooth的函数，一个很直观的想法是，把这部分近似一下，变成一个smooth的函数：
- 我们在右边加一个proximal point项。其思路是，我们并不知道
最优应该取什么值，但可以先假设的最优解是
，那么我们在优化的时候尽可能让靠近
+\lambda^{T}h(x)-\frac{1}{2\rho}\left\|\lambda-\bar{\lambda}\right\|)
，)
- 加上这个proximal point项（正则项）之后，原问题的max部分就是对的线性项加上对的二次项，这对来说是一个连续且严格凸的函数，且二次函数的最优值是有解析解的
- 但目前我们只是得到了对原问题的minmax解的一个粗略估计，仍需要持续迭代提高精度，从两个角度进行提升
- 让正则项趋近于0，即
- 不断更新更准确的，
)
。因为第一次优化时，是我们猜的，优化结束后，我们得到的
比之前猜的更接近最优解，所以第二次就把作为下一轮的来不断提高精度
- 注意，由于我们不断地在更新更精确的，这意味着
本身不断在接近0，所以
的取值不需要真的趋向无穷大， 慢慢增长到一定程度大即可,取到1000就可以了
- 现在我们不需要借助冯诺依曼定理最minmax问题进行对换了，也就不需要保证
)
严格凸
- 原问题的拉格朗日函数 + 增广项 = 增广拉格朗日法
- 一般来说，我们常把上面的式子整理为如下形式（灰色部分可以省略），进行迭代
不等式约束
- 问题形式
- 原问题变形（不等式变等式）
)
+\left[s\right]^{2}\leq0)
，其中
表示element-wise squaring
等式约束+不等式约束
- 问题形式
- PHR_Augmented Lagrangian
:=f(x)+\frac{\rho}{2}\left\{\left\|h(x)+\frac{\lambda}{\rho}\right\|^{2}+\left\|max\left[g(x)+\frac{\mu}{\rho},0\right%20])\right\|\right\}-\frac{1}{2\rho}\left\{\left\|\lambda\right\|^{2}%20+%20\left\|\mu\right\|^{2}\right\})
- 丄式的最后一项一般都省略掉
- 迭代步骤
- 参数初始化
- 内层循环退出条件（求
）
\right\|_{\infty}%3C\xi^{k}min\left[1,max\left[\left\|h(x)\right\|_{\infty},\left\|max\left[g(x),-\frac{\mu}{\rho}\right]\right\|_{\infty}\right]\right])
从一个正数逐渐收敛到0
- 外层迭代退出条件
无约束优化问题
