第三章 等式约束的优化
§1 最优性条件
考虑具有等式约束的最优化问题：
（1）
其中,.这类问题的求解方法在数学分析中已解决，即Lagranger乘数法，先作简要复述。
定理1（一阶必要条件） 设、在可行点x*的某个邻域可微，向量组线性无关，若x*是（1）的局部最优解，则存在实数使得
（2）
定义（n+)元函数
称为Lagrange函数，其中称为Lagrange乘子，。可以证明（2）成立。这只需考虑函数在无约束条件下取极值的必要条件。
由，立得（2）式且有
（3）
它表明x*必须满足（1）之约束条件。
联立（2）、（3）所得的解称为Lagrange函数的稳定点。
定理2（二阶充分条件） 设x*是（1）的可行解，、二次可微，若存在向量，使，且的Hesse矩阵正定，则x*是（1）的严格局部最优解。
定理的证明只要注意到对任意可行解x，有，故由上一章定理7
故当x为可行解时上式亦成立。
定理2中关于Hesse矩阵H(x*,)正定的要求太强，很难满足，其实只需要求H(x*,)在集合
D={y︱
上正定即可。即若对于有H(x*,)，则是（1）的严格局部最优解（证明略，可参见文献[34]）。
例1 研究问题 min f=-x1x2-x2x3-x1x3
s.t,x1+x2+x3=3
容易求得稳定点为x*=（1，1，1）T，=2。在这种情况下，的H(x*,)阵变为（视为常数，只考虑对x的导数）：
H=
它既不是正定，也不是负定，但在子空间︱ 上，注意
于是H在D上是正定的，所以x*至少是问题的局部极小点。
下面讨论把Botsko一阶充分条件用于等式约束(1)的情形.以下总假定f(x)及hk(x)(k=1,2…)于点x*的某邻域O(x*,内可微，且可从（1）的约束条件中解出（这只需满足隐函数存在定理的条件）：
（4）
这里（。
将（4）代入目标函数f(x)中，可得
F(x1,..x, x1,..x)…( x1,..x)]=
于是Botsko一阶充分条件(上一章(9)式)变成
(5)
其中=(, O(,。
这时，利用复合函数求导，则上一章（13）式变成
(6)
其中由方程组
(7)
给出(这要求其导数矩阵 非奇异).而解的矩阵形式为
(8)
其中（,数值计算时,代入点的值.
充分性的另一条件(上一章(14)式)变成
(9)
其极限形式为
(10)
其中
与仅第i个分量不同.
例2
求在条件
(11)
下的极值.
解 用Lagrange乘数法可求得问题的稳定点为
及
把看作是x1的函数,然后于(11)式对x1求偏导数,可得
2
1+
解得
将上式代入(6)式,并代入之值,得
()
()
再检验条件(10):
=1>0
=1>0
自然成立.故知是极小值点,是极大值点(对于判断极大值点来讲,(5),(6)式中的不等号应反号,而(9),(10) 式中的不等号不变号)
对此例,由于消元后变成一元函数,(10)的极限必为1,故只需检验(6)式是否成立,即可作出判断,而不必再检验(9)或(10)式成立.
§2、乘子法
定理1.2给出了Lagrange乘子的存在性，但如何寻找并未真正解决，这里介绍的乘子法恰好给出一个如何寻找的方法。为此引入增广Lagrange函数：
（12）
其中为Lagrange乘子，M为较大正数。由定理（1）对于局部最优解x*存在，使（x*,为的稳定点。即，而附加项在x*点的梯度为0，因此，亦有，这样x*将是的极小点，而求解问题（1），便可转化为对，求的无约束极小了。如何求？设对，求解得xk,则
即
与（2）相比，自然令
,j=1,…, (13)
来调整。那么迭代到什么时候才可以结束呢？下面的定理为我们提供了依据。
定理3 设由（12）式定义，xk是无约束优化问题：
（14）
的最优解，则是（1）的最优解，为其相应的Lagrange乘子的充要条件是
证,若是（1）的最优解，则显然有。反之若是（14）的最优解，且，则都有
特别当x是（1）的可行解时，有
故是（1）的最优解，即=x*，同时应有
这证明是与=x*对应的Lagrange乘子。
迭代应以结束。若收敛慢，可适当增大M，即将（13）中的M换成Mk=Mk-1,1。这样，用上述乘子法去求解（1）的迭代步骤为：
1° 给定初始点，初始乘子向量计算精度，取，，令k=1。
2° 以为初始点，求解得解，其中由（12）确定。
3° 若，计算结束，取为（1）的最优解，否则，令Mk=Mk-1,转到第4。步。
4° 计算
令k=k+1，返回第一步。
上述方法是Hestenes于1969年提出来的，故称为Hestenes乘子法。几乎同时，Powell也提出一种乘子法，它定义的增广目标函数为：
如果在上式中取和，则多出与x无关的一个项，故两者本质一致。
在一定条件下，可证迭代程序至少是线性收敛的。实际计算表明，随着罚参数Mk的增大乘子法产生的点列比罚函数法产生的点列更快地接近x*，因而乘子法一般可避免因罚参数过于增大带来的数值困难。
例3 考察。依次用罚函数和乘子法建立的迭代点列和。
采用罚函数法，由
用解析法可求得无约束最优解为
采用Hestenes乘子法，则由
可得
其中 k
选取，所得结果见下表：
从表中可见接近x*比接近x*的速度快得多，用乘子法迭代6次就达到了罚函数法迭代15次的结果。这里罚参数在罚函数中要增大到，而在乘子法中只要增大到，相比之下乘子法不需要过份地增大罚参数，从而改进了罚函数法。
1973年，Rockfellar将乘子法推广到解不等式约束的优化问题：
（15）
其中
求解它的办法是引入松弛变量将不等式约束化为等式约束,
(16)
然后再利用前面讲述的等式约束最优化问题的结果。这时（14）式具形式
（17）
而（13）式变成
（18）
其中(k.
设法消去松弛变量y.不难证明（只须令）（17）右端的和式中的各项，当满足下式时取最小值：
（19）
代入（17）得
（20）
代入（18）得：
（21）
而结束准则可采用
（22）
对于一般非线性优化问题，可类似地推出相应结果。
有人采用异于（13）的乘子迭代公式：
（23）
在加速迭代收敛方面取得了很好的计算结果。
还有把乘子表示成x的函数的，如Polak乘子法这里就不介绍了。
§1 最优性条件
考虑具有等式约束的最优化问题：
（1）
其中,.这类问题的求解方法在数学分析中已解决，即Lagranger乘数法，先作简要复述。
定理1（一阶必要条件） 设、在可行点x*的某个邻域可微，向量组线性无关，若x*是（1）的局部最优解，则存在实数使得
（2）
定义（n+)元函数
称为Lagrange函数，其中称为Lagrange乘子，。可以证明（2）成立。这只需考虑函数在无约束条件下取极值的必要条件。
由，立得（2）式且有
（3）
它表明x*必须满足（1）之约束条件。
联立（2）、（3）所得的解称为Lagrange函数的稳定点。
定理2（二阶充分条件） 设x*是（1）的可行解，、二次可微，若存在向量，使，且的Hesse矩阵正定，则x*是（1）的严格局部最优解。
定理的证明只要注意到对任意可行解x，有，故由上一章定理7
故当x为可行解时上式亦成立。
定理2中关于Hesse矩阵H(x*,)正定的要求太强，很难满足，其实只需要求H(x*,)在集合
D={y︱
上正定即可。即若对于有H(x*,)，则是（1）的严格局部最优解（证明略，可参见文献[34]）。
例1 研究问题 min f=-x1x2-x2x3-x1x3
s.t,x1+x2+x3=3
容易求得稳定点为x*=（1，1，1）T，=2。在这种情况下，的H(x*,)阵变为（视为常数，只考虑对x的导数）：
H=
它既不是正定，也不是负定，但在子空间︱ 上，注意
于是H在D上是正定的，所以x*至少是问题的局部极小点。
下面讨论把Botsko一阶充分条件用于等式约束(1)的情形.以下总假定f(x)及hk(x)(k=1,2…)于点x*的某邻域O(x*,内可微，且可从（1）的约束条件中解出（这只需满足隐函数存在定理的条件）：
（4）
这里（。
将（4）代入目标函数f(x)中，可得
F(x1,..x, x1,..x)…( x1,..x)]=
于是Botsko一阶充分条件(上一章(9)式)变成
(5)
其中=(, O(,。
这时，利用复合函数求导，则上一章（13）式变成
(6)
其中由方程组
(7)
给出(这要求其导数矩阵 非奇异).而解的矩阵形式为
(8)
其中（,数值计算时,代入点的值.
充分性的另一条件(上一章(14)式)变成
(9)
其极限形式为
(10)
其中
与仅第i个分量不同.
例2
求在条件
(11)
下的极值.
解 用Lagrange乘数法可求得问题的稳定点为
及
把看作是x1的函数,然后于(11)式对x1求偏导数,可得
2
1+
解得
将上式代入(6)式,并代入之值,得
()
()
再检验条件(10):
=1>0
=1>0
自然成立.故知是极小值点,是极大值点(对于判断极大值点来讲,(5),(6)式中的不等号应反号,而(9),(10) 式中的不等号不变号)
对此例,由于消元后变成一元函数,(10)的极限必为1,故只需检验(6)式是否成立,即可作出判断,而不必再检验(9)或(10)式成立.
§2、乘子法
定理1.2给出了Lagrange乘子的存在性，但如何寻找并未真正解决，这里介绍的乘子法恰好给出一个如何寻找的方法。为此引入增广Lagrange函数：
（12）
其中为Lagrange乘子，M为较大正数。由定理（1）对于局部最优解x*存在，使（x*,为的稳定点。即，而附加项在x*点的梯度为0，因此，亦有，这样x*将是的极小点，而求解问题（1），便可转化为对，求的无约束极小了。如何求？设对，求解得xk,则
即
与（2）相比，自然令
,j=1,…, (13)
来调整。那么迭代到什么时候才可以结束呢？下面的定理为我们提供了依据。
定理3 设由（12）式定义，xk是无约束优化问题：
（14）
的最优解，则是（1）的最优解，为其相应的Lagrange乘子的充要条件是
证,若是（1）的最优解，则显然有。反之若是（14）的最优解，且，则都有
特别当x是（1）的可行解时，有
故是（1）的最优解，即=x*，同时应有
这证明是与=x*对应的Lagrange乘子。
迭代应以结束。若收敛慢，可适当增大M，即将（13）中的M换成Mk=Mk-1,1。这样，用上述乘子法去求解（1）的迭代步骤为：
1° 给定初始点，初始乘子向量计算精度，取，，令k=1。
2° 以为初始点，求解得解，其中由（12）确定。
3° 若，计算结束，取为（1）的最优解，否则，令Mk=Mk-1,转到第4。步。
4° 计算
令k=k+1，返回第一步。
上述方法是Hestenes于1969年提出来的，故称为Hestenes乘子法。几乎同时，Powell也提出一种乘子法，它定义的增广目标函数为：
如果在上式中取和，则多出与x无关的一个项，故两者本质一致。
在一定条件下，可证迭代程序至少是线性收敛的。实际计算表明，随着罚参数Mk的增大乘子法产生的点列比罚函数法产生的点列更快地接近x*，因而乘子法一般可避免因罚参数过于增大带来的数值困难。
例3 考察。依次用罚函数和乘子法建立的迭代点列和。
采用罚函数法，由
用解析法可求得无约束最优解为
采用Hestenes乘子法，则由
可得
其中 k
选取，所得结果见下表：
从表中可见接近x*比接近x*的速度快得多，用乘子法迭代6次就达到了罚函数法迭代15次的结果。这里罚参数在罚函数中要增大到，而在乘子法中只要增大到，相比之下乘子法不需要过份地增大罚参数，从而改进了罚函数法。
1973年，Rockfellar将乘子法推广到解不等式约束的优化问题：
（15）
其中
求解它的办法是引入松弛变量将不等式约束化为等式约束,
(16)
然后再利用前面讲述的等式约束最优化问题的结果。这时（14）式具形式
（17）
而（13）式变成
（18）
其中(k.
设法消去松弛变量y.不难证明（只须令）（17）右端的和式中的各项，当满足下式时取最小值：
（19）
代入（17）得
（20）
代入（18）得：
（21）
而结束准则可采用
（22）
对于一般非线性优化问题，可类似地推出相应结果。
有人采用异于（13）的乘子迭代公式：
（23）
在加速迭代收敛方面取得了很好的计算结果。
还有把乘子表示成x的函数的，如Polak乘子法这里就不介绍了。
