Optimization-Constrained
标签： Optimization Math
概述
约束优化问题(Constrained-Optimization)在实际应用中很常用，之前在参加数学建模竞赛的时候也处理过一些约束优化问题，但是一直没有一个比较系统的整理，所以这几天稍微整理了下约束优化问题的一些知识点。
分类
问题分类
单目标的约束优化问题可以分为三类：
1.仅有等式约束的优化问题(IP)
2.仅有不等式约束的优化问题(EP)
3.一般约束优化问题(GP)
其中一般优化问题的约束条件包含了等式和不等式。
方法分类
约束优化问题的优化方法可以分为两大类，分别是直接优化方法，和间接优化方法。
直接优化方法的思路是先确定可行初始点，然后确定搜索方向，之后在可行域中进行迭代搜索，直到收敛。其迭代点应该满足的两个条件是在可行域之内，并且目标函数值下降。常见的直接优化方法有复合形法和可行方向法。
间接优化方法的思路是将约束优化问题转变为无约束优化问题进行优化，转变的前提是不能破坏原始的约束条件。常见的简介简介优化方法是罚函数法。
算法
下面我们来熟悉下几个比较常见的约束优化方法的具体思路。
可行方向法
其基本思路是在可行域内选择一个初始点，然后开始迭代；每次迭代的过程中选择合适的搜索方向和步长，知道目标函数收敛。需要满足的条件是每次的迭代点都应该在可行域之内，并且无特殊情况下应该使目标函数得到优化。
可行方向法只是一个类似于下降方法的一般框架，其具体的实现应该选择合适的寻找搜索方向和步长的方法。举一个例子来说，就是等式约束的Newton方法，其初始点给定一个可行域内的点，之后的迭代过程与无约束问题下的Newton方法的迭代过程完全一样，原因是Newton在初始点可行的条件下，每次的迭代点都是可行的，这个性质可以进行证明。
有些资料上说可行方方向方法仅适用于不等式约束的优化问题，但是并没有给出详细的原因，个人认为这种说法是错误的，因为等式约束下的Newton方法是可行的。
复合形法
复合行的定义是在$n$维空间中，由$k\geqslant n+1$个点组成的多面体。
其实现的思路是在可行域内构造一个$k$个顶点的初始复合形，比较复合形的各顶点值，并去掉坏点，然后根据一定法则求出目标函数值优化的新点，用新点代替坏点，构成新的复合形，优化一步；之后重复此步骤直到逼近最优点。
复合形法是单纯形法的一种发展，具体实现中，新点的选择方法包括映射法，收缩法，扩张法等。
罚函数法
罚函数法考虑一般形式的约束优化问题：
其思路是将约束优化问题近似处理为如下的无约束优化：
其中$\gamma$称为惩罚因子，$P(x)$称为罚函数，罚函数的定义为：
对于上述有约束优化问题，如果满足下列3个条件，则称函数$P$为罚函数：
1.$P$是连续的
2.对所有的$x\in R^n$，$P(x) \geqslant 0$成立
3.$P(x)=0$当且仅当$x$是可行点
在这样的定义下，我们可以发现当$x$在可行域内时，罚函数为0，当$x$在可行域外时，因为$\gamma$的作用，$\gamma P(x)$会为一个较大的值，因此近似处理后目标方程不会选择可行域外的点。为了使得无约束化问题能够更好地近似约束优化，需要选择合适的罚函数。
常用的发函数法包括外点法和内点法，外点法的迭代初期是在可行域之外进行的，内点法的迭代则是严格在可行域内进行。
拉格朗日法
这里的拉格朗日法是基于拉格朗日函数的求解方法，其基本思路是利用梯度法更新参数并同时更新拉格朗日乘子。
拉格朗日乘子一般表示如下，其中$h(x)$为等式约束,$g(x)$为不等式约束：
对于仅包含等式约束的拉格朗日法迭代如下：
对于仅包含不等式约束的拉格朗日法迭代如下：
其中$[\cdot]_+ = max\{\cdot , 0\}$。该方法的详细介绍可以参考《最优化导论》一书。
小结
本次只是熟悉了下约束优化的整体思路。