最优化方法：六、约束最优化方法

主要参考书目：

• 最优化方法及其应用/郭科，陈聆，魏友华.-北京：高等教育出版社,2007.7(2013.7重印)

前面我们已经讨论无约束问题的最优化方法，但实际碰到的问题常常是存在约束的。一般的约束最优化问题的数学模型为：

解决约束问题一般有两种思路，一是通过“罚函数”把约束问题转化为无约束问题解决；二则是构造某种迭代过程使之不能越出可行域。

1、外点罚函数法

• 基本思路
  构造一函数为
  
  F(X,Mk)=f(X)+Mkα(X),$$F(X,M_k)=f(X)+M_k\alpha (X),$$
  
  
  该方法之所以叫做外点法，是因为在很多情况下（不是所有情况），当惩罚因子比较小的时候，最优解会落在可行域之外，随着惩罚因子的增加，向可行域内部移动，也就是说迭代过程中最优解一直在可行域之外。
• 特点
  该方法实现了有约束问题向无约束问题的转化，但存在着一些问题：
  (1)惩罚因子选的小会使最优解更容易落在可行域外，而惩罚因子选的大又会使函数的Hesse矩阵性质变坏。
  (2)迭代过程中得到的解常常在可行域之外，难以观察到内点的变化情况也无法求得近似最优解。

2、内点罚函数法

• 基本思路
  对于纯不等式约束问题，为使得迭代过程中解一直在可行域内。我们通过罚函数在可行域边界处构造一个“壁垒”使得迭代过程中解不能离开可行域。
  
• 特点
  该方法保证了迭代过程中得到的解一直处于可行域内，但仍然面临过三个问题：
  (1)需要找到一个可行的初始点。
  (2)如果搜索步长过大，有可能一步跨过壁垒，所以在搜索过程中应适当控制步长，防止该情况发生。
  (3)无法解决等式约束的问题。

3、混合罚函数法

• 基本思路
  为解决内点法不能应对等式约束的问题，采用以下混合罚函数：
  
  F(X,rk)=f(X)+rk∑i=1l1gi(X)+1rk−−√∑j=1m[hj(X)]2$$F(X,r_k)=f(X)+r_k\sum _{i=1}^l{\displaystyle \frac{1}{g_i(X)}}+{\displaystyle \frac{1}{\sqrt{r_k}}}\sum _{j=1}^m[h_j(X){]}^2$$
• 外插技术
  F(X,r)$F(X,r)$的最优解X∗$X^{\ast }$可以看做r$r$的函数，当我们得到了前几点的X∗(r)$X^{\ast }(r)$后，可以通过外插法估计下一个最优值，并把该点当做下一次迭代的初始点，以加快收敛速度。
  通常使用两点外插或者三点外插。

4、约束坐标轮换法

• 基本思路
  与无约束优化问题的坐标轮换法类似，但是搜索时不再使用一般的以为搜索方法，而采用以下规则：
  
  该方法可以引入一个步长缩放因子，当在t步长下的搜索已满足该步长下的终止限，而步长并不足够下，则缩短步长进行下一轮搜索。
• 特点
  该方法算法简单明了，但存在以下问题：
  (1)收敛较慢；
  (2)可能出现“死点”，导致输出伪最优点；
  (3)可能出现在某几个点之间循环的现象。

5、复合型法

• 基本思路
  与单纯形法类似，但该方法使用的是顶点更多的复合型。（顶点可以使降维的可能性减小，而且由于约束边界的限制，使用单纯形容易“卡死”在某个地方，而复合型则提供了更多可能的搜索方向）
• 具体细节
  (1)生成初始复合型
  
  (2)跑出可行域的点一律认为是最坏的点。
  (3)如果无法利用最坏点搜索（即步长t降的很小仍不符合要求）则改用次坏点替代最坏点，并以此类推。
  (4)关于复合型的顶点数，当n≤5$n\le 5$时，一般取k=2n$k=2n$，n>5$n>5$时一般取k=(1.25∼1.5)n$k=(1.25\sim 1.5)n$。
• 特点
  属于直接法，对目标函数要求少。
  但其收敛速度较慢，而且不能应对等式约束。