等式约束问题求解方法研究

1.基木原理

对于含等式约束的优化问题

构造拉格朗日函数

当令▽L（X，λ）=0可得原问题的极值点X^*以及相应的拉格朗日乘子向量λ^*，若构造外点惩罚函数

当r→∞时，对函数φ（X，r）迸行序列极小化，可求得原问题的极值点X*巨h_P（X^*）=0（p=1，2，…，l）。

前已述及，用拉格朗日乘子法求解约束优化问题往往失败，而用惩罚函数法求解，又因要求r→∞而使计算效率低。为此，将这两种方法结合起来，即构造惩罚函数的拉格朗日函数

若令

求得约束极值点X^*巨使h_P（X^*）=0（p=1，2，…，l），所以，不论r取何值，式（5-57）与原问题有相同的极值点X^*，与式（5-55）有相同的拉格朗日乘子向量λ^*。

式（5-57）称增广乘子函数，或称增广惩罚函数，式中的r仍称惩罚因子。

既然式（5-55）和式（5-57）有相同的X^*和λ^*。仍然要考虑由式（5-57）表示的增广乘子函数的主要原因是，这两类函数的二阶导数矩阵，即黑塞矩阵的性质不同。一般来说，式（5-55）所表示的拉格朗日函数L（X，λ）的黑塞矩阵

并不是正定的。而式（5-57）所表示的增广乘子函数M（X，λ，r）的黑塞矩阵

必定存在一个r′，对于一切满足r≥r′的值总是正定的。下面举一个简单例子来说明上述结论的正确性。

例5-4 求优化问题

minf（X）=x²₁-3x₂-x²₂

s.t.h（X）=x₂=0

的约束最优解。

解：该问题的约束最优解为X^*=（0，0）^T，f（X^*）=0，相应的拉格朗日乘子为λ^*=3。

构造拉格朗日函数

L（X，λ）=x²₁-3x₂-x²₂+λx2

其黑塞矩阵为，巨其在全平面上任一点，包括X^*处，都不是正定的。

构造增广乘子函数

其黑塞矩阵为，当取r＞2时，它在全平面上处处正定。

由这一性质可知，当惩罚因子r取足够大的定值，即r＞r′，不必趋于无穷大，巨恰好取λ=λ^*时，X^*就是函数M（X，λ，r）的极小点。也就是说，为了求得原问题的约束最优点，只需对增广乘子函数M（X，λ，r）求一次无约束极值。当然，问题并不是如此简单，因为λ^*是未知的，为了求得λ*采取如下方法。

假定惩罚因子r取为大于r′的定值，则增广乘子函数只是X、λ的函数。若不断地改变λ，并对每一个λ求minM（X，λ），将得到极小点的点列：X^*（λ^（k））（k=1，2，…）。

显然，当λ^（k）→λ^*时，X^*=X^*（λ^*）将是原问题的约束最优解。为使λ^（k）→λ^*，采用如下公式来校正λ（k）：

λ^（k+1）=λ^（k）+▽λ^（k） （5-60）

这一步骤在增广乘子法中称为乘子迭代，是惩罚函数法中所没有的。为了确定式（5-60）中的校正量▽λ^（k），再定义

M（λ）=M（X（λ），λ） （5-61）

为了直观地说明函数M（λ）的属性，仍然从分析例5-4入手。将例5-4的原问题构造成增广乘子函数(www.xing528.com)

若取r=6，则上式可简化为

M（X，λ）=x²₁+（λ-3）x₂+2x²₂

对X求函数M（X，λ）的极值，即令▽M（X，λ）=0得方程组

联立方程并求解得

代入上式，得

令

解得

λ^*=3

函数M（λ）的二阶导数为，可见λ^*=3是函数M（λ）的极大值。

从对这个例子的分析可知，为了求得λ^*，只需求函数M（λ）的极大值。求函数M（λ）极大值的方法不同，将会得到不同的乘子迭代公式。目前常采用近似的牛顿法求解，得到的乘子迭代公式为

λ_P^（k+1）=λ_P^（k）+rh_P（X^（k）（p=1，2，…，l） （5-62）

2.参数选择

增广乘子法中的乘子向量λ、惩罚因子r、设计变量的初值都是重要参数。下面分别介绍选择这些参数的一般方法。

1）在没有其他信息的情况下，初始乘子向量取零向量，即λ^（0）=0，显然，这时增广乘子函数和外点惩罚函数的形式相同。也就是说，第一次迭代计算是用外点法迸行的。从第二次迭代开始，乘子向量按式（5-62）校正。

2）惩罚因子的初值r^（0），可按外点法选取。以后的迭代计算，惩罚因子按下式递增

式中，β为惩罚因子递增系数，取β=10；δ为判别数，取δ=0.25。

惩罚因子的递增公式可以这样来理解：开始迭代时，因r不可能取很大的值，只能在迭代过程中根据每次求得的无约束极值点X^（k）趋近于约束面的情况来决定。当X^（k）离约束面很远，即h（X^（k））的值很大时，则增大r值，以加大惩罚项的作用，迫使迭代点更快地逼近约束面。当X^（k）已接近约束面，即h（X^（k））明显减小时，则不再增加r值了。

惩罚因子也可以用简单的递增公式计算：

r^（k+1）=βr^（k） （5-64）

这一公式形式上和外点法所用的公式相同，但实质上不同。因为增广乘子法并不要求r→∞。事实上，当r增加到一定值时，λ已趋近于λ^*。从而增广乘子函数的极值点也逼近原问题的约束最优点了。用式（5-64）计算r^k+1时，一般取β=2～4，以免因r增加太快，使乘子迭代不能充分发挥作用。

3）设计变量的初值X^（0）也按外点法选取，以后的迭代初始点都取上次迭代的无约束极值点，以提高计算效率。

3.计算步骤

1）选取设计变量的初值X^（0）、惩罚因子初值r^（0）、增长系数β、判别数▽、收敛精度ε，并令λ_P^（0）=0（p=1，2，…，l），迭代次数k=0。

2）按式（5-57）构造增广乘子函数M（X，λ，r），并求minM（X，λ，r），得无约束最优解X^（k）=X^*（λ^（k），r^（k））。

3）计算

4）按式（5-62）校正乘子向量，求λ^（k+1）。

5）如果h（X^（k））≤ε，则迭代终止。约束最优解为X^*=X^（k），λ^*=λ^（k+1），否则转下一步。

6）按式（5-63）或式（5-64）计算惩罚因子r^（k+1），再令k=k+1转步骤2。