《第7章约束问题的优化方法》由会员分享，可在线阅读，更多相关《第7章约束问题的优化方法（26页珍藏版）》请在金锄头文库上搜索。
1、第7章 约束问题的优化方法7.1 可行方向法7.1.1 可行方向法的基本思想可行方向法是一类算法,可看作无约束下降算法的自然推广。典型策略是从可行点出发，沿着下降可行方向进行搜索，求出使目标函数值下降的新的可行点考虑只含线性约束的非线性规划问题： （1）为非线性函数，.注1：线性约束规格保证了优化问题（1）的可行方向集、线性化可行方向集以及序列化可行方向集是等同的。当某个可行方向同时也是目标函数的下降方向时，沿此方向移动一定会在满足可行性的情况下改进迭代点的目标函数值。目前已经提出许多可行方向法，用来处理具有线性约束的非线性规划问题。搜索方向选择方式不同形成不同的可行方向法：（1）Zouten
2、dijk可行方向法（2）Rosen梯度投影法（3）Wolfe既约梯度法可行方向的判定：定理1：设是问题（1）的可行解，在点处有，其中，则非零向量为处的可行方向的充要条件是，证明：必要性：设非零向量是处的可行方向根据可行方向的定义，使得对每个有为可行点，即，.由于，由上式得到又由得到. 充分性：设，.由于，则，使得对于所有的,成立.根据假设及，得到.上述两式组合起来就是.又由及可知表明是可行点，因此是处的可行方向7.1.2 Zoutendijk可行方向法Zoutendijk子问题：根据定理1，如果非零向量同时满足, ，,则是处的下降可行方向Zoutendijk可行方向法把确定搜索方向归结为求解线
3、性规划问题 （2）在（2）式中，显然是可行解，可推知目标函数最优值必定小于或等于零如果目标函数最优值小于零，则得到下降可行方向；否则，如果目标函数最优值为零，则x是K-T点定理2：考虑问题（1），设是可行解，在点处有，其中，则为K-T点的充要条件是问题（2）的目标函数最优值为零一维搜索步长的确定：设为处一个下降可行方向后继点迭代公式：的取值原则：(l)保持迭代点的可行性；(2)使目标函数值尽可能减小根据上述原则，可以通过求解一维搜索问题来确定步长： （3）由于是可行方向，因此，(3)式中第2个约束是多余的在点处，把不等式约束区分为起作用约束和不起作用约束：，(3)式中第1个约束可以写成 （4）
4、由于为可行方向，以及，因此自然成立约束条件（4）简化为问题（3）简化为 （5）根据（5）式的约束条件，容易求出的上限，令 由知. (5)式的约束条件写成：由此得到的上限：问题（3）最终简化成： （6）给定问题（1）和一个可行点以后，可以通过求解问题（2）得到下降可行方向，通过求解问题（6）确定沿此方向进行一维搜索的步长初始可行点的确定：为求（1）式的一个可行点，引入人工变量（向量）和，解辅助线性规划 （7）如果（7）式的最优解，那么就是（1）式的一个可行解可行方向法的计算步骤：(l)给定初始可行点，置.(2)在点处把A和b分解成和，使得，计算 (3)求解线性规划问题得到最优解. (4)如果，则
5、停止计算，为K-T点，否则，进行步骤（5）. (5)计算的上限，在上作一维搜索：得到最优解，令 (6)置，返回步骤（2）.例：用Zoutendijk可行方向法解下列问题：取初始可行点.第1次迭代：，在处，起作用约束和不起作用约束的系数矩阵及右端分别为，；，先求在处的下降可行方向： 即 由单纯形方法求得最优解：再求步长: 解一维搜索问题得到：令 第2次迭代：，在处，起作用约束和不起作用约束的系数矩阵及右端分别为，；，求在处的下降可行方向：由单纯形方法求得最优解：沿搜索，求步长: 解一维搜索问题得到：.令 第3次迭代：，；，求在处的下降可行方向：由单纯形方法求得最优解：根据定理1，是K-T点。该例
6、是凸规划，是最优解，目标函数最优值.将可行方向法推广到非线性约束情形：考虑不等式约束问题 （8）定理3：设x是问题（8）的可行解，是在处起作用约束下标集，又设函数,在处可微，函数在处连续，如果，则d是下降可行方向根据定理3，求下降可行方向归结为求解LP问题 （9）设（9）式的最优解为如果，则是在x处的下降可行方向；如果，相应的x必为Fritz John点定理4：设x是问题（9）的可行解，则x是Fritz John点的充要条件是问题（9）的目标函数最优值等于零步长的确定，仍然需要求解一维搜索问题其中 （10）计算步骤：(l)给定初始可行点，置. (2)令，解线性规划问题得最优解，若，则停止计算，
7、为Fritz John 点；否则，进行步骤（3）. (3)求解一维搜索问题其中由（10）式确定，得到最优解（4）令，置，返回步骤（2）.Zoutendijk算法的收敛问题：不能保证Zoutendijk方法迭代产生的序列收敛于K-T点Topkis-Veinott修正Topkis和Veinott把求方向的线性规划改成紧约束和非紧约束在确定下降可行方向中均起作用，并且在接近非紧约束边界时，不至发生方向突然改变修正方法计算步骤：(l)给定初始可行点，置. (2)解线性规划问题得最优解.(3)若，则停止计算，为Fritz John 点；否则，进行步骤（4）.(4)求解一维搜索问题其中由（10）式确定，得
8、到最优解（5）令，置，返回步骤（2）.Topkis-Veinott修正方法的收敛性:定理5: 考虑问题（8），设函数连续可微，又设是Topkis-Veinott算法产生的序列，则的任一聚点是Fritz John点7.2 惩罚函数法7.2.1 惩罚函数法的基本思想惩罚函数法的基本思想：借助罚函数把约束问题转化为无约束问题，进而用无约束最优化方法来求解考虑约束问题 （1）求解的一种途径是由目标函数和约束函数组成辅助函数，把原来的约束问题转化为极小化辅助函数的无约束问题对于等式约束问题： （2）可定义辅助函数参数是很大的正数（2）式转化为无约束问题 （3）求解问题（3）能够得到问题(2)的近似解对于
9、不等式约束问题： （4）定义辅助函数（4）式转化为无约束问题 （5）通过（5）式求得（4）式的近似解一般情形（1）式）：可定义辅助函数其中连续函数和满足条件：函数和的典型取法：为给定常数通常取作 . 约束问题（1）转化为无约束问题 （6）称为罚项，称为罚因子，而称为罚函数。 当x为可行点时，有；当x不是可行点时，是很大的正数，它的存在是对点脱离可行域的一种惩罚，作用是在极小化过程中迫使迭代点靠近可行域求解问题（6）能够得到约束问题（1）的近似解。越大，近似效果越好。7.2.2 乘子法1 乘子法的基本思想考虑只有等式约束问题（2）.运用乘子法事先需要定义增广Lagrange函数（乘子罚函数）:
10、(7)与Lagrange函数的区别在于增加罚项;与罚函数的区别在于增加了乘子项注1：增广Lagrange函数与Lagrange函数及罚函数具有不同的性态，即对于，只要取足够大的罚因子，不必趋向无穷大，就可通过极小化，求得问题（2）的局部最优解为证明上述结论，先给出如下假设：设是等式约束问题（2）的一个局部最优解，且满足二阶充分条件，即存在乘子，使得且对每一个满足的非零向量d ，有其中，定理1：设和满足问题（2）的局部最优解的二阶充分条件，则存在，使得对所有的，是的严格局部极小点反之，若存在点，使得且对于某个，是的无约束极小点，又满足极小点的二阶充分条件，则是问题（2）的严格局部最优解证明：需要
11、用到矩阵理论的相关知识和二阶充分条件的定义。注2：根据定理1，如果知道最优乘子 ，那么只要取充分大的罚因子，不需趋向无穷大，就能通过极小化求出问题（2）的解注3：确定最优乘子一般方法：先给定充分大的和Lagrange乘子的初始估计v，然后在迭代过程中修正v，力图使v趋向.修正v的公式：设在第k次迭代中，Lagrange乘子向量的估计为，罚因子取，得到的极小点这时有对问题（2）最优解，当线性无关，应有假如，则必有一般来说，并非是，因此该等式并不成立但由此可以给出修正乘子v的公式，令 （7）然后再进行第k+1次迭代，求的极小点这样做下去，可望, 从而如果不收敛，或者收敛太慢，则增大参数，再进行迭代
12、收敛快慢一般用来衡量2 等式约束问题乘子法计算步骤（1）给定初始点，乘子向量初始估计，参数，允许误差，常数, ，置. （2）以为初点，解无约束问题得解. （3）若 ,则停止计算，得到点；否则，进行步骤（4）. （4）若，则置，转步骤（5）；否则，进行步骤（5）.（5）用（7）式计算，置，转步骤（2）. 例1：用乘子法求解下列问题：增广Lagrange函数取罚因子，令Lagrange乘子的初始估计，由此出发求最优乘子及问题的最优解.以下用解析方法求函数的极小点第1次迭代：容易求得的极小点为第k次迭代：取乘子，增广Lagrange函数的极小点为现在通过修正求，由（7）式，有易证当时，序列收敛，且同
13、时，得到最优乘子.问题的最优解注4：在实际计算中，应注意的取值如果太大，则会给计算带来困难；如果太小，则收敛减慢，甚至出现不收敛情形.3 不等式约束问题的乘子法考虑只有不等式约束的问题(4).为利用关于等式约束问题得到的结果，引入变量，把问题（4）化为等式约束问题这样可定义增广Lagrange函数问题（4）转化为求解 (8)将关于y求极小，由此解出y，并代入（8）式，将其化为只关于x求极小的问题为此求解用配方法将化为（9）为使关于取极小，取值如下：当时，当时，综合以上两种情形，即 将上式代入（9）式，由此定义增广Lagrange函数将问题（4）转化为求解无约束问题： 4 一般约束问题的乘子法对于既含有不等式约束又含有等式约束的问题（1），定义增广Lagrange函数 在迭代中，与只有等式约束问题类似，取定充分大的参数，通过修正第k次迭代中的乘子和，得到第次迭代中的乘子和乘子和修正公式： (10)计
