约束优化算法

下面内容是根据自己看书，对拉格朗日乘子法、罚函数法、增广拉格朗日乘子法做一个小结：

一、“拉格朗日乘子法和罚函数法都用于将有约束的优化问题转化为无约束的优化问题”

---

• 比如最小化目标函数 ，约束等式为    ，这里的是维向量，是矩阵，,那么使用拉格朗日乘子将约束条件合并到目标函数中，得到拉格朗日函数：。
• 对变量和拉格朗日乘子的更新遵循这两个式子：$x_{k+1}=arg min_{x} L(x,\lambda_{k})$;    ，这里的是步长
• 这里涉及到对偶方面的相关知识，我在这里的知识比较欠缺，所以就只是说明一下拉格朗日乘子法是这么个东西，后面再加一篇博客讲清楚点。

---

• 罚函数添加的项跟拉格朗日乘子法不同。但顾名思义，就是对约束条件之外的点进行惩罚，或者说进行最小化处理
• 罚函数可以有两种添加方式：加法罚函数，即直接把惩罚项与目标函数相加；另一种是乘法罚函数，将惩罚项和目标函数相乘，通常加法罚函数的使用更多，个人感觉应该是为了后面的求解更加方便，而且加法罚函数在目标函数中会先乘以惩罚系数再加上目标函数，也就是$f(x)+\rho*p(x)$，用来选择一个适当的权重，也可以认为是标志惩罚的分量，所以一般取值是大于0的
• 内部是怎么设置的，下面分成等式和不等式约束两种进行说明

在等式约束中，对于约束条件为$f(x)=0$，罚函数取$p(x)=f^{2}(x)$。即满足等式时该项为0，不满足该项时取平方加到目标函数中对它做最小化处理；

在不等式约束$f(x)\geq 0$中有两种形式，内罚$p(x)=\frac{1}{f(x)}$或者$p(x)=\frac{log(f(x))}{f(x)}$，而外罚是$p(x)=(max\{0,-f(x)\})^{r}$;

有三个点要注意：1、内罚法由于位于分母，所以得到的解并不满足等于0的情况，阻挡了可行集边界的点，而外罚法没有这一缺点；2、外罚法可以用可行集外的点做为初始点，所以要经过比较大量的迭代才能收敛到可行集中，所以收敛慢，而内罚法要求初始点是可行集中的点，所以收敛相对较快；3、通常适用外罚法，因为内罚法的初始点搜索是件很难的事情。

---

缺点（书里说的，我自己也不是特别理解）

拉格朗日乘子法的两个缺点：1、当约束优化问题有局部凸结构时，对偶的无约束优化问题才是良好定义，拉格朗日乘子的更新才是合理的；2、拉格朗日目标函数收敛比较耗时，因为乘子的迭代式上升迭代。

罚函数法的两个缺点：1、收敛慢，这个应该是跟内罚法的初始点可以选择为可行集外的点有关系，一般都会做随机初始，所以选到可行集外的点就会收敛慢；2、惩罚系数太大会使得无约束优化问题产生病态，造成算法不稳定。

 

二、“增广拉格朗日乘子法”

增广拉格朗日乘子法把上面两种方法结合到一起。下面介绍下等式和不等式约束的增广拉格朗日乘子法

---

等式约束：比如等式约束为，罚函数取，那么增广拉格朗日函数为

，而更新的式子如下：

$x_{k+1}=arg min_{x} L_{\rho}(x,\lambda_{k})$；  ，注意这里更新乘子跟前面标准的拉格朗日乘子法不同，步长变成惩罚系数。

---

不等式约束：在上面等式约束基础上，添加一不等式约束（我不太理解这里为啥用的是这个符号，跟小于等于有什么区别吗，如果你知道麻烦给我留言哦，万分感谢），这时采取的做法是将不等式变成等式，添加松弛变量，使得，并构造出如下的拉格朗日目标函数：

，而且，

更新式子如下所示：

$x_{k+1}=arg min_{x} L_{\rho}(x,s_k,\lambda_{k},v_k)$;  $s_{k+1}=arg min_{s\succeq 0} L_{\rho}(x_{k+1},s,\lambda_{k},v_k)$;

;  

---

这里有几个问题要注意：

1、增广拉格朗日乘子法不再需要惩罚因子$\rho_k$增加至无穷大， 只要更新拉格朗日乘子就可以收敛了。所以前面说的罚函数法的病态条件应该指的是要把惩罚因子增加至无穷大才会收敛。

2、增广拉格朗日乘子法的乘子比普通的拉格朗日乘子法要收敛得更快，而且不再像标准拉格朗日乘子法要求有局部凸结构，也就是说应用范围更广。另外，标准的拉格朗日乘子法的是更新的结果，而增广的是更新的结果，差别在于有没有惩罚项。

三、“交替方向乘子法和增广拉格朗日乘子法的关系”

交替方向乘子法是为了适应大尺度的等式约束问题，即$x\in R^n$的维数很高。但是变量可以分成很多个子变量$x=(x_1,x_2,...,x_r)$，同时目标函数可以根据这些子变量做一个分解：$f(x)=\sum_{i=1}^{r}f_i(x_i)$，这时候就变成一个分布式优化的问题。而且既然变量可以分解，那么等式约束就变成$Ax=\sum_{i=1}^{r}A_ix_i$，所以可以得到如下的增广拉格朗日目标函数：

，然后利用下面的式子做更新：

$x^{k+1}_i=arg min _{x_i}L_i(x_i,\lambda_k),i=1,...,r$

 

以上是我看完这部分的一个小结，但理解上差了很多，只能有大概一个轮廓，如果读者有更好更容易理解的中文或者英文文献资料，麻烦给我留言，或者一起讨论学习，谢谢！！！