第7章约束问题的优化方法.doc

第7章 约束问题的优化方法
§7.1 可行方向法
7.1.1 可行方向法的基本思想
可行方向法是一类算法,可看作无约束下降算法的自然推广。典型策略是从可行点出发，沿着下降可行方向进行搜索，求出使目标函数值下降的新的可行点．
考虑只含线性约束的非线性规划问题：
（1）
为非线性函数，，，，.
注1：线性约束规格保证了优化问题（1）的可行方向集、线性化可行方向集以及序列化可行方向集是等同的。
当某个可行方向同时也是目标函数的下降方向时，沿此方向移动一定会在满足可行性的情况下改进迭代点的目标函数值。
目前已经提出许多可行方向法，用来处理具有线性约束的非线性规划问题。
搜索方向选择方式不同形成不同的可行方向法：
（1）Zoutendijk可行方向法
（2）Rosen梯度投影法
（3）Wolfe既约梯度法
可行方向的判定：
定理1：设是问题（1）的可行解，在点处有，，其中
，
则非零向量为处的可行方向的充要条件是
，
证明：
必要性：设非零向量是处的可行方向．根据可行方向的定义，，使得对每个．有为可行点，即，.

由于，由上式得到．
又由得到.

充分性：设，.
由于，则，使得对于所有的,成立.
根据假设及，得到.
上述两式组合起来就是.
又由及可知

表明是可行点，因此是处的可行方向．
7.1.2 Zoutendijk可行方向法
Zoutendijk子问题：
根据定理1，如果非零向量同时满足, ，,则是处的下降可行方向．
Zoutendijk可行方向法把确定搜索方向归结为求解线性规划问题
（2）
在（2）式中，显然是可行解，可推知目标函数最优值必定小于或等于零．如果目标函数最优值小于零，则得到下降可行方向；否则，如果目标函数最优值为零，则x是K-T点．
定理2：考虑问题（1），设是可行解，在点处有，，其中
，
则为K-T点的充要条件是问题（2）的目标函数最优值为零．
一维搜索步长的确定：
设为处一个下降可行方向．后继点迭代公式：

的取值原则：
(l)保持迭代点的可行性；
(2)使目标函数值尽可能减小．
根据上述原则，可以通过求解一维搜索问题来确定步长：
（3）
由于是可行方向，因此，(3)式中第2个约束是多余的．
在点处，把不等式约束区分为起作用约束和不起作用约束：，
(3)式中第1个约束可以写成
（4）
由于为可行方向，，，以及，因此自然成立．约束条件（4）简化为

问题（3）简化为
（5）
根据（5）式的约束条件，容易求出的上限，令

由知.
(5)式的约束条件写成：
由此得到的上限：

问题（3）最终简化成：
（6）
给定问题（1）和一个可行点以后，可以通过求解问题（2）得到下降可行方向，通过求解问题（6）确定沿此方向进行一维搜索的步长．
初始可行点的确定：
为求（1）式的一个可行点，引入人工变量（向量）和，解辅助线性规划
（7）
如果（7）式的最优解，那么就是（1）式的一个可行解．
可行方向法的计算步骤：
(l)给定初始可行点，置.
(2)在点处把A和b分解成和，使得
，
计算．
(3)求解线性规划问题

得到最优解.
(4)如果，则停止计算，为K-T点，否则，进行步骤（5）.
(5)计算的上限，在上作一维搜索：

得到最优解，令

(6)置，返回步骤（2）.
例：用Zoutendijk可行方向法解下列问题：

取初始可行点.
第1次迭代：，在处，起作用约束和不起作用约束的系数矩阵及右端分别为
，；，
先求在处的下降可行方向：
即
由单纯形方法求得最优解：
再求步长:

解一维搜索问题

得到：
令
第2次迭代：，在处，起作用约束和不起作用约束的系数矩阵及右端分别为
，；，
求在处的下降可行方向：

由单纯形方法求得最优解：
沿搜索，求步长:

解一维搜索问题

得到：.
令
第3次迭代：
，；，
求在处的下降可行方向：

由单纯形方法求得最优解：
根据定理1，是K-T点。
该例是凸规划，是最优解，目标函数最优值.
将可行方向法推广到非线性约束情形：
考虑不等式约束问题
（8）
定理3：设x是问题（8）的可行解，是在处起作用约束下标集，又设函数,在处可微，函数在处连续，如果
，
则d是下降可行方向．
根据定理3，求下降可行方向归结为求解LP问题
（9）
设（9）式的最优解为．如果，则是在x处的下降可行方向；如果，相应的x必为Fritz John点．
定理4：设x是问题（9）的可行解，，则x是Fritz John点的充要条件是问题（9）的目标函数最优值等于零．
步长的确定，仍然需要求解一维搜索问题

其中
（10）
计算步骤：
(l)给定初始可行点，置.
(2)令，解线性规划问题

得最优解，若，则停止计算，为Fritz John 点；否则，进行步骤（3）.
(3)求解一维搜索问题

其中由（10）式确定，得到最优解．
（4）令，置，返回步骤（2）.
Zoutendijk算法的收敛问题：
不能保证Zoutendijk方法迭代产生的序列收敛于K-T点．
Topkis-Veinott修正
Topkis和Veinott把求方向的线性规划改成

紧约束和非紧约束在确定下降可行方向中均起作用，并且在接近非紧约束边界时，不至发生方向突然改变．
修正方法计算步骤：
(l)给定初始可行点，置.
(2)解线性规划问题

得最优解.
(3)若，则停止计算，为Fritz John 点；否则，进行步骤（4）.
(4)求解一维搜索问题

其中由（10）式确定，得到最优解．
（5）令，置，返回步骤（2）.
Topkis-Veinott修正方法的收敛性:
定理5: 考虑问题（8），设函数连续可微，又设是Topkis-Veinott算法产生的序列，则的任一聚点是Fritz John点．
§7.2 惩罚函数法
7.2.1 惩罚函数法的基本思想
惩罚函数法的基本思想：借助罚函数把约束问题转化为无约束问题，进而用无约束最优化方法来求解．
考虑约束问题
（1）
求解的一种途径是由目标函数和约束函数组成辅助函数，把原来的约束问题转化为极小化辅助函数的无约束问题．

对于等式约束问题：
（2）
可定义辅助函数

参数是很大的正数．

（2）式转化为无约束问题
（3）
求解问题（3）能够得到问题(2)的近似解．
对于不等式约束问题：
（4）
定义辅助函数

（4）式转化为无约束问题
（5）
通过（5）式求得（4）式的近似解．
一般情形（（1）式）：
可定义辅助函数

其中

连续函数和满足条件：
函数和的典型取法：

为给定常数．通常取作 .
约束问题（1）转化为无约束问题
（6）
称为罚项，称为罚因子，而称为罚函数。

当x为可行点时，，有
当x不是可行点时，是很大的正数，它的存在是对点脱离可行域的一种惩罚，作用是在极小化过程中迫使迭代点靠近可行域．
求解问题（6）能够得到约束问题（1）的近似解。
越大，近似效果越好。
7.2.2 乘子法
1 乘子法的基本思想
考虑只有等式约束问题（2）.
运用乘子法事先需要定义增广Lagrange函数（乘子罚函数）:
(7)
与Lagrange函数的区别在于增加罚项;与罚函数的区别在于增加了乘子项．
注1：增广Lagrange函数与Lagrange函数及罚函数具有不同的性态，即
对于，只要取足够大的罚因子，不必趋向无穷大，就可通过极小化，求得问题（2）的局部最优解．
为证明上述结论，先给出如下假设：
设是等式约束问题（2）的一个局部最优解，且满足二阶充分条件，即存在乘子，使得

且对每一个满足的非零向量d ，有

其中
，
定理1：设和满足问题（2）的局部最优解的二阶充分条件，则存在，使得对所有的，是的严格局部极小点．反之，若存在点，使得

且对于某个，是的无约束极小点，又满足极小点的二阶充分条件，则是问题（2）的严格局部最优解．
证明：需要用到矩阵理论的相关知识和二阶充分条件的定义。
注2：根据定理1，如果知道最优乘子 ，那么只要取充分大的罚因子，不需趋向无穷大，就能通过极小化求出问题（2）的解．
注3：确定最优乘子一般方法：
先给定充分大的和Lagrange乘子的初始估计v，然后在迭代过程中修正v，力图使v趋向.
修正v的公式：
设在第k次迭代中，Lagrange乘子向量的估计为，罚因子取，得到的极小点．这时有

对问题（2）最优解，当线性无关，应有

假如，则必有

一般来说，并非是，因此该等式并不成立．但由此可以给出修正乘子v的公式，令
（7）
然后再进行第k+1次迭代，求的极小点．
这样做下去，可望, 从而．
如果不收敛，或者收敛太慢，则增大参数，再进行迭代．
收敛快慢一般用来衡量．
2 等式约束问题乘子法计算步骤
（1）给定初始点，乘子向量初始估计，参数，允许误差，常数, ，置.
（2）以为初点，解无约束问题

得解.
（3）若 ,则停止计算，得到点；否则，进行步骤（4）.
（4）若，则置，转步骤（5）；否则，进行步骤（5）.
（5）用（7）式计算，置，转步骤（2）.

例1：用乘子法求解下列问题：

增广Lagrange函数

取罚因子，令Lagrange乘子的初始估计，由此出发求最优乘子及问题的最优解.
以下用解析方法求函数的极小点．
第1次迭代：容易求得的极小点为

第k次迭代：取乘子，增广Lagrange函数的极小点为

现在通过修正求，由（7）式，有

易证当时，序列收敛，且

同时，，得到最优乘子.
问题的最优解

注4：在实际计算中，应注意的取值．
如果太大，则会给计算带来困难；
如果太小，则收敛减慢，甚至出现不收敛情形.
3 不等式约束问题的乘子法
考虑只有不等式约束的问题(4).为利用关于等式约束问题得到的结果，引入变量，把问题（4）化为等式约束问题

这样可定义增广Lagrange函数

问题（4）转化为求解
(8)
将关于y求极小，由此解出y，并代入（8）式，将其化为只关于x求极小的问题．为此求解

用配方法将化为
（9）
为使关于取极小，取值如下：
当时，
当时，
综合以上两种情形，即
将上式代入（9）式，由此定义增广Lagrange函数

将问题（4）转化为求解无约束问题：
4 一般约束问题的乘子法
对于既含有不等式约束又含有等式约束的问题（1），定义增广Lagrange函数

在迭代中，与只有等式约束问题类似，取定充分大的参数，通过修正第k次迭代中的乘子和，得到第次迭代中的乘子和．
乘子和修正公式：
(10)
计算步骤与等式约束情形相同．
例2：用乘子法求解下列问题：

增广Lagrange函数为

令
得到的无约束极小点

取，，得到的极小点：

修正，令

求得的极小点

以此类推，设在第k次迭代取乘子，求得的极小点

修正，得到

显然，按上式迭代得到的序列是收敛的.
令，则 及
注5：在乘子法中，由于参数不必趋向无穷大就能求得约束问题的最优解，因此不出现罚函数法中的病态．
计算经验表明，乘子法优于罚函数法，受到广大使用者的欢迎．
§7.3 序列二次规划法
7.3.1 序列二次规划法的基本思想
序列二次规划法（SQP）的基本思想：
在迭代点处构造一个二次规划（QP）子问题，近似原来的约束优化问题；通过求解该QP子问题，获得约束优化问题的一个改进迭代点；不断重复这个过程，直到求出满足一定要求的迭代点。
考虑一般的约束优化问题
（1）
直觉：利用泰勒展开在迭代点构造QP子问题：
（2）
令，则（2）等价于二次规划：

求出最优解为，则新的迭代点为：
7.3.2 Lagrange-Newton法
等式约束的Lagrange-Newton法
求解非线性方程组的Newton迭代公式为

可以证明：解方程组的Newton法具有局部二次收敛性。
考虑等式约束最优化问题：
（3）
问题（3）的Lagrange函数为

令表示在处的Jacobi矩阵，即

设为（3）的解且行满秩，则存在使得是（3）的K-T点，即
（4）

令，则函数的Jacobi矩阵为

求解非线性方程组（4）的Newton迭代公式为：
（5）
是如下线性方程组的解：
（6）
称由（5）-（6）式建立的求解约束最优化问题（3）的算法为Lagrange-Newton法.
Lagrange-Newton法不易于直接用于不等式约束最优化问题，需要导出Lagrange-Newton法的另一种形式.(与QP挂钩)
由约束最优化问题的K-T条件不难看出：
Lagrange-Newton法迭代公式（5）-（6）计算的是如下QP问题的解：
（7）
且是相应于等式约束的Lagrange乘子.
求解等式约束问题（3）的Newton法可等价地叙述为：先求二次规划（7）的K-T点，然后由（5）式确定.
对问题（7）的任何可行点，有

问题（7）等价于二次规划
（8）
二次规划问题（8）的K-T条件为：
（9）
比较（5）、（7）、（9）式，可看出：
求解非线性方程组（4）的Lagrange-Newton法可等价地叙述为：求QP问题（8）的K-T点，令，由此产生迭代序列，称此Lagrange-Newton法为求解等式约束问题（3）的SQP算法.
一般约束优化问题的Lagrange-Newton法
对一般约束优化问题，在当前点构造如下QP子问题：
（10）
解上述QP子问题，得到解及对应的乘子和，产生新的迭代点，其中.
该算法称为求解约束问题（1）的局部Newton-SQP算法.
注1：子问题（10）的目标函数是问题（1）的Lagrange函数的二次近似，而不是我们通常认为的仅是问题（1）的目标函数的二次近似.
基于Lagrange-Newton法的局部SQP算法步骤：
（1）取初始点，置.
（2）若满足约束问题（1）的K-T条件（从计算角度应考察），则停止计算，得到；否则，转步骤（3）.
（3）解QP子问题（10），得到解.
（4）令，，转步骤（2）.
注2：遗留问题：
（i）如何求解QP子问题（后面再讨论）？
（ii）如果初始点取得不恰当，即使原问题可行，也可导致QP子问题不相容。QP子问题不相容（可行域为空）如何处理？
例1：对于约束，在点处，线性化近似约束为，不相容！
7.3.3 Wilson-Han-Powell法
在构造QP子问题（10）时，需要计算Lagrange函数在迭代点的Hesse矩阵，这种计算工作量比较大。
借鉴无约束优化的拟牛顿法在迭代过程中利用对称正定矩阵替代Hesse矩阵的思想，韩世平（S.P. Han）1976年基于Lagrange-Newton法提出了一种利用对称正定矩阵替代矩阵的序列二次规划法（也称为约束拟牛顿法，约束变尺度法
Wilson在1963年较早地考虑了Lagrange-Newton法. 后来Powell在1977年修正了Han的方法，故将这种序列二次规划法称为Wilson-Han-Powell(WHP)方法．
对于一般的约束问题（1），WHP方法需要构造如下的QP子问题：
（11）
利用子问题（11）的解作为搜索方向。
WHP方法除了用矩阵替代矩阵外，新的迭代点不直接按计算，而是由一维搜索确定步长，新的迭代点为.
由于这些改进，WHP方法在一定条件下具有全局收敛性. 相对于Lagrange-Newton法（局部SQP算法），WHP方法称为全局SQP算法.
（11）式确定的具有一个比较好的性质：它是许多罚函数（价值函数，Merit Function）的下降方向.
WHP方法中一种罚函数形式如下(范数-1罚函数)：
（12）
为罚因子.利用该罚函数作一维搜索确定步长.
WHP方法的计算步骤：
（1）初始化：给定初始点，对称正定矩阵，容许误差和满足的非负序列；取参数，，置.
(2)收敛性检验：求解二次规划子问题（11），得到最优解.若，则得到原来约束优化问题的一个近似K-T点，算法停止；否则，转步骤（3）.
（3）改进迭代点：利用（12）式的罚函数,按照某种线性搜索规则确定步长，使得

置.
(4)修正矩阵：利用矩阵，在和点的其它信息，计算对称正定矩阵；令，转步骤（2）.
注3：遗留问题：
（1） 如何求解QP子问题（11）？（后面讨论）
（2） 如何修正获得？
（3） 如何处理QP子问题不相容？
（1）的修正方法：
的修正有多种方法：
（i）基于拟牛顿校正公式的方法
（ii）基于增广Lagrange函数的方法
（iii）基于既约Hesse矩阵的方法
只介绍基于拟牛顿校正公式的方法.
对于的修正，一方面，应为Lagrange函数的Hesse矩阵的近似；另一方面，要保持的对称正定性，使得相应的QP子问题是一个严格的凸二次规划问题.
类似于无约束问题的拟牛顿法，令

然后可利用BFGS等公式计算.

(BFGS公式)
注4：与无约束问题不同的是：这种修正不能保证条件（曲率条件）成立，因此，即使对称正定，也不能保证正定.
为了克服此困难，1978年Powell利用和的一个凸组合代替，记为
（13）

修正后的BFGS公式（称为截断BFGS修正）
(14)
（2）QP子问题不相容的处理：
Powell提出了一种处理方法：引进辅助变量，解LP：
（15）
为该问题的可行解，故（15）式的最优解总是存在的，记为，显然有.
显然原子问题（11）（或（10））相容当且仅当.
（i）若或很小，则改变初始点重新开始，此情况的发生常常因原问题是不相容的；
（ii）若，则将子问题（11）中的约束条件用（15）中的约束条件代替，即子问题取为
（16）
其中取为中的一个定值.
例2：对于约束，在点处，求如下线性规划

最优解为.
若取，则对应的QP子问题（16）是相容的.
7.3.4 二次规划的求解方法
二次规划（QP）是非线性规划中一种特殊情形，目标函数是二次函数，约束是线性函数。
许多现实问题本身可建模为二次规划。
QP是前面讨论的SQP的基础，在每一迭代步，均要求解一个QP子问题。
QP的算法较多，如：
（1）Lagrange方法
（2）起作用集方法
（3）Lemke方法
（4）路径跟踪法
1．Lagrange方法（求解等式约束QP问题）
考虑QP问题
（17）
为n阶对称矩阵，为矩阵，秩为.
该问题的Lagrange函数为

令，，得到方程组

将此方程组写成
（18）
系数矩阵称为Lagrange矩阵.
设Lagrange矩阵可逆，可表示为

由式，推得

假设逆矩阵存在，由上述关系可得的表达式
（19）
（20）
（21）
（18）式两端乘以Lagrange矩阵的逆，得到问题的解
（22）
（23）
的另一种表达式：
设是问题（17）的任一可行解，即满足，在此点目标函数的梯度

利用和，可将（22）、（23）改写为
（24）
（25）
例3：用Lagrange法求解

，，，
可计算出
由（19）-（21）式算得
，

再根据（22）式，计算问题的最优解

2．起作用集方法（具有不等式约束的QP问题）
考虑具有不等式约束的QP问题：
（26）
为n阶对称正定矩阵，为矩阵，秩为.
该问题不能直接用Lagrange方法求解，求解的策略之一，是用起作用集方法将它转化为求解等式约束问题.
起作用集方法的基本思想：在每次迭代中，以已知的可行点为起点，把在该点起作用约束作为等式约束，在此约束下极小化目标函数，而其余的约束暂且不管，求得新的比较好的可行点后，再重复以上做法。
设在第次迭代中，已知可行点，在该点起作用约束指标集用表示.这时需求解等式约束问题
（27）
表示矩阵A的第i行，也是在处起作用约束函数的梯度.
将坐标原点移至，令，则
（28）
问题（27）等价于求校正量的问题：
（29）
解此二次规划问题，求出最优解，然后区别不同的情形，决定下面应采取的步骤.
（1）如果是可行点，且，则在第次迭代中，已知点取作

（2）如果不是可行点，则令方向，沿搜索. 令

沿方向搜索步长确定方法：
基本要求：保持点的可行性.
的取值应使得对于每个，有
（30）
已知是可行点，故.
（1）当时，对于任意非负数，（30）式总成立；
（2）当时，只要取正数

对于每个，（30）式成立.
记

是问题（29）的最优解，为在第次迭代中得到较好的可行点，应取
（31）
并令
如果
（32）
则在点，有

故在处，为起作用约束.
把指标p加入，得到在处的起作用约束指标集.
如果，则是问题（27）的最优解，这时应判断是否为问题（26）的最优解. 为此，需要用（25）式计算起作用的约束乘子.
(i) 如果这些，则点是问题（26）的K-T点.（26）是凸规划，因此是最优解.
(ii) 如果存在，使得，则不可能是最优解. 把下标q剔出.
如果有几个乘子同时为负数，令，将对应的约束从起作用约束集中去掉，再解问题（29）.
注5：可以验证：当时，在处存在可行下降方向. 如设是起作用约束系数矩阵，且满秩，令方向

是单位向量，对应下标的分量为1，则有

因此d是处的下降方向.
容易验证d也是可行方向.

起作用集方法计算步骤：
（1）给定初始可行点，相应的起作用约束指标集为，置.
（2）求解问题

设其最优解为.若，则进行步骤（5）；否则，进行步骤（3）.

（3）令,由确定，令

计算.
（4）若，则置，，返回步骤（2）；若，记点处起作用约束指标集为，置，进行步骤（5）.
（5）用计算对应起作用约束的Lagrange乘子，设. 若，则停止计算，得到最优解；否则，从中删除，返回步骤（2）.
例4：用起作用集方法求解问题

目标函数

取初始可行点，在该点起作用约束指标集，求解问题（29）:

得到.因此是相应问题（27）的最优解.
为判断是否为本例最优解，需计算Lagrange乘子.
由知:
利用（25）式算得乘子，，可知不是问题的最优解.
将对应的约束从起作用约束集中去掉，置，再解问题（29）:

得解.由于，需要由（31）式计算:

令
算出.
由于，置.在点处计算相应的Lagrange乘子，此时

由（25）式算得，不是问题的最优解.
将指标2从中删除，有，再解问题（29）：

得解.由于，需要计算：

令
算出.
在点，第1个约束是起作用约束，这时有，解问题（29）：

得解. 需要计算.
令
算出.
在点，，计算相应的Lagrange乘子.因此是所求的最优解.

习题
1用Zoutendijk方法求解下列问题

取初始可行点.
2 用乘子法求解下列问题

3 用Lagrange方法求解二次规划问题

115