求解约束最优化问题，一种途径是在可行域内寻找目标函数值下降得迭代点列（可行方向法），这种方法对于带非线性约束的最优化问题求解效果一般都不太理想。（这也就是为什么可行方向法中约束条件一般是线性约束的原因）。

本文学习求解有约束最优化的另一种方法，称为罚函数法。它的基本思想是用原问题的目标函数和约束函数构造新的目标函数——罚函数，从而将约束最优化问题转化为无约束最优化问题来求解。

外罚函数法：

本文我们先介绍外罚函数法。

考虑约束非线性最优化问题

其中  ，， 都是定义在  上的实值连续函数，可行域为 S 。

罚函数是指利用目标函数  和约束函数 ， 构造的，具有”惩罚性质“的辅助函数：

当  时，当且仅当 ,

当  时，，并且  随着 x 到 S 的距离增大而增大。

1，等式约束优化问题：

定义罚函数为：，其中参数  为罚因子（通常为一个大的正数）。

2，不等式约束优化问题：

定义罚函数为：，其中参数  为罚因子（通常为一个大的正数）。

3，一般约束优化问题：

定义罚函数为：，其中参数  为罚因子（通常为一个大的正数）。

其中：

典型取法：，其中  通常取 1 或 2 。

定理1：设对于某个给定的  ，无约束优化问题  的最优解为 ，S 是原问题的可行域，那么：

（1）若 ，则  必为原问题的最优解；

（2），无约束问题，存在最优解  ，并且若 ，则 ，即  也是原问题的最优解。

引理：设 ， 和  分别是取罚因子  和  时无约束优化问题  的最优解，则下列各式成立：

（1） ———— F 是单调增数列；

（2） ————P 是单调减数列；

（3） ————f 是单调增数列。

证明：

（1）  是  取罚因子  时的最优解

 

取  为 ，有：

  是单调增数列。

（2）  和  分别是  取罚因子  和  时的最优解

 

将上面两式分别相加，消去相同的项，得：

 

 

  是单调减数列

（3） 

 

 

  是单调增数列

算法步骤：

步骤1：选取初始点  ，初始罚因子  ，放大系数 ，允许误差 ，令 k =1;

步骤2：以  为初始点，求解 ，求得最优解  ；

步骤3：若 ，停止，输出  ；否则，令 ，返回步骤2。 

例题解析：

例题：用外罚函数法求解约束优化问题：

解：定义罚函数：

对应的无约束优化问题是：

 得最优解

依次对 k=1,2,...，计算得到要使 

总结：

优点：（1）对初始点无要求；(2）既可用于求解等式约束，也可用于求解不等式约束。

缺点：（1）求出的最优解不一定是可行解；（2）罚函数在可行域边界上往往不可导。

（行文中若有纰漏，希望大家指正）