1、第六章第六章 约束优化方法约束优化方法第一节第一节 概概 述述 机械优化设计中的问题，大多数属于约束机械优化设计中的问题，大多数属于约束优化设计问题，其数学模型为：优化设计问题，其数学模型为：l,2,1k0 x,x,xhhm,2,1j0 x,x,xgg.t.sx,x,xffminn21kkn21jjn21xxx求解上式的方法称为约束优化方法。求解上式的方法称为约束优化方法。根据求解方式的不同，可分为直接解法根据求解方式的不同，可分为直接解法和间接解法。和间接解法。直接解法通常适用于仅含不等式约束的问直接解法通常适用于仅含不等式约束的问题。题。,2,1kkkk1kdxx步长步长可行搜索方向可行搜
2、索方向满足两个条件：满足两个条件：1 1、设计点沿该方向作微、设计点沿该方向作微量移动时，目标函数值下量移动时，目标函数值下降；降；2 2、不会越出可行域。、不会越出可行域。直接解法的特点：直接解法的特点：1 1）由于整个求解过程在可行域内进行，因此）由于整个求解过程在可行域内进行，因此迭代计算不论何时终止，都可以获得一个比初迭代计算不论何时终止，都可以获得一个比初始点好的设计点。始点好的设计点。2 2）若目标函数为凸函数，可行域为凸集，则）若目标函数为凸函数，可行域为凸集，则可保证获得全域最优解，否则，因存在多个局可保证获得全域最优解，否则，因存在多个局部最优解，当选择的初始点不同时，可能搜
3、索部最优解，当选择的初始点不同时，可能搜索到不同的局部最优解。到不同的局部最优解。为此常在可行域内选择几个差别较大的初为此常在可行域内选择几个差别较大的初始点分别进行计算，以便从求得的多个局部最始点分别进行计算，以便从求得的多个局部最优解中选择更好的最优解。优解中选择更好的最优解。3 3）要求可行域为有界的非空集，即在有界可）要求可行域为有界的非空集，即在有界可行域内存在满足全部约束条件的点，且目标函行域内存在满足全部约束条件的点，且目标函数有定义。数有定义。间接解法有不同的求解策略。间接解法有不同的求解策略。其中一种解法的基本思路是将约束优化问其中一种解法的基本思路是将约束优化问题中的约束函
4、数进行特殊的加权处理后，和目题中的约束函数进行特殊的加权处理后，和目标函数结合起来，构成一个新的目标函数，即标函数结合起来，构成一个新的目标函数，即将原约束优化问题转化成一个或一系列的无约将原约束优化问题转化成一个或一系列的无约束优化问题，再对新的目标函数进行无约束优束优化问题，再对新的目标函数进行无约束优化计算，从而间接的搜索到原约束问题的最优化计算，从而间接的搜索到原约束问题的最优解。解。间接解法的基本迭代过程是，首先将约束间接解法的基本迭代过程是，首先将约束优化问题转化成新的无约束目标函数优化问题转化成新的无约束目标函数 l1kk2m1jj121hHgGf,xxxx 然后对然后对 进行无
5、约束极小化计进行无约束极小化计算。由于在新目标函数中包含了各种约束条算。由于在新目标函数中包含了各种约束条件，在求极值的过程中还将改变加权因子的件，在求极值的过程中还将改变加权因子的大小，因此可以不断地调整设计点，使其逐大小，因此可以不断地调整设计点，使其逐步逼近约束边界，从而间接的求得原约束问步逼近约束边界，从而间接的求得原约束问题的最优解。题的最优解。21,x例例6-1 6-1 求解约束优化问题的最优解求解约束优化问题的最优解 022xxh.t.s1x2xfmin212221xx解：解：8.0f2.06.1*T*xx用间接解法时，用间接解法时，可取可取8.0222xx8.01x2x,212
6、2212x令令006.11x2x08.02x2x2211解得：解得：8.0,2.06.12*T*xx 22xx8.01x2x,2122212x间接解法的特点：间接解法的特点：1 1）由于无约束优化方法的研究日趋成熟，使）由于无约束优化方法的研究日趋成熟，使得间接解法有了可靠的基础。得间接解法有了可靠的基础。这类算法的计算效率和数值计算的稳定性这类算法的计算效率和数值计算的稳定性也都有较大的提高。也都有较大的提高。2 2）可以有效的处理具有等式约束的约束优化）可以有效的处理具有等式约束的约束优化问题。问题。3 3）主要问题：选取加权因子较为困难。）主要问题：选取加权因子较为困难。加权因子选取不当
7、，不但影响收敛速度和加权因子选取不当，不但影响收敛速度和计算精度，甚至会导致计算失败。计算精度，甚至会导致计算失败。第二节第二节 随随 机机 方方 向向 法法 随机方向法是一种原理简单的直接解法，随机方向法是一种原理简单的直接解法，基本思路是在可行域内选择一个初始点，利用基本思路是在可行域内选择一个初始点，利用随机数的概率特性，产生若干个随机方向，并随机数的概率特性，产生若干个随机方向，并从中选择一个能使目标函数值下降最快的随机从中选择一个能使目标函数值下降最快的随机方向，作为可行搜索方向，然后从初始点出发，方向，作为可行搜索方向，然后从初始点出发，沿该方向以一定的步长进行搜索，得到新点，沿该
8、方向以一定的步长进行搜索，得到新点，新点应满足约束条件。至此完成一次迭代，然新点应满足约束条件。至此完成一次迭代，然后将起始点移至新点，重复上述过程，最终取后将起始点移至新点，重复上述过程，最终取得约束最优解。得约束最优解。优点：优点：对目标函数的性态无特殊要求，程序设计对目标函数的性态无特殊要求，程序设计简单，使用方便。简单，使用方便。由于可行搜索方向是从许多随机方向中选由于可行搜索方向是从许多随机方向中选择的使目标函数下降最快的方向，加之步长还择的使目标函数下降最快的方向，加之步长还可以灵活变动，所以此算法的收敛速度比较快，可以灵活变动，所以此算法的收敛速度比较快，若能取得一个较好的初始点
9、，迭代次数可以大若能取得一个较好的初始点，迭代次数可以大大减少，它是求解小型的机械优化设计问题的大减少，它是求解小型的机械优化设计问题的一种十分有效的算法。一种十分有效的算法。一、随机数的产生一、随机数的产生 在随机方向法中，为产生可行的初始点及在随机方向法中，为产生可行的初始点及随机方向，需要用到大量的（随机方向，需要用到大量的（0 0，1 1）和（）和（-1-1，1 1）区间内均匀分布的随机数，在计算机内，随机区间内均匀分布的随机数，在计算机内，随机数通常是按一定的数学模型进行计算后得到的，数通常是按一定的数学模型进行计算后得到的，这样得到的随机数称为伪随机数，它的特点是这样得到的随机数称
10、为伪随机数，它的特点是产生速度快，计算机内存占用少，并且有较好产生速度快，计算机内存占用少，并且有较好的概率统计特性。的概率统计特性。首先令首先令 取取r=2657863=2657863（为小于（为小于r1 1的正奇数），然后按以的正奇数），然后按以下步骤计算：下步骤计算：3733623512r,2r,2r1112233rrqrrrrrrrrrrrrrrr5rr则则若则若则若令即即q为（为（0 0，1 1）区）区间内的伪随机数，间内的伪随机数，利用利用q容易求得任容易求得任意区间意区间(a,b)内的内的伪随机数，即：伪随机数，即：abqax二、初始点的选择二、初始点的选择 随机方向法的初始点必
11、须是一个可行点，随机方向法的初始点必须是一个可行点，即满足全部不等式约束条件，当约束条件较为即满足全部不等式约束条件，当约束条件较为复杂时，用人工不易选择可行初始点，可用随复杂时，用人工不易选择可行初始点，可用随机选择的方法来产生。其计算步骤如下：机选择的方法来产生。其计算步骤如下：1 1）输入设计变量的下限值和上限值，即）输入设计变量的下限值和上限值，即n,2,1ibxaiii2 2）在区间（）在区间（0 0，1 1）内产生）内产生n个伪随机数个伪随机数n,2,1iqi3 3）计算随机点的各分量）计算随机点的各分量 n,2,1iabqaxiiiii4 4）判别随机点是否可行，若随机点为可行点
12、，）判别随机点是否可行，若随机点为可行点，则取为初始点，否则转步骤则取为初始点，否则转步骤2 2）重新计算，直到）重新计算，直到产生的随机点是可行点为止。产生的随机点是可行点为止。三、可行搜索方向的产生三、可行搜索方向的产生 在随机方向法中，产生可行搜索方向的在随机方向法中，产生可行搜索方向的方法是从方法是从 个随机方向中，选取一个随机方向中，选取一个较好的方向，其计算步骤为：个较好的方向，其计算步骤为：nkk1 1）在（）在（-1-1，1 1）区间内产生伪随机）区间内产生伪随机数数 ，其方法为：，其方法为：k,2,1j;n,2,1irji12qriji按下式计算随机单位向量按下式计算随机单位
13、向量,k1,2,jrrrr1jnj2j1n1i2jij21eje2 2）取一试验步长）取一试验步长 ，按下式计算，按下式计算k个随机点：个随机点：0k,2,1jj00jexx3 3）检验）检验k个随机点个随机点 是否为可行是否为可行点，除去非可行点，计算余下的可行随机点的点，除去非可行点，计算余下的可行随机点的目标函数值，比较其大小，选出目标函数值最目标函数值，比较其大小，选出目标函数值最小的点小的点 。k,2,1jjxLx4 4）比较）比较 和和 两点的目标函数值，若两点的目标函数值，若 则取则取 和和 的连线方向作为可行搜索方向，的连线方向作为可行搜索方向，若若 ，则将步长，则将步长 缩小
14、，转缩小，转1 1）重新）重新计算。直至计算。直至 为止。为止。Lx0 x0LffxxLx0 x00Lffxx0Lffxx如果如果 缩小到很小，仍然找不到一个缩小到很小，仍然找不到一个 ，使使 ，这说明，这说明 是一个局部极小点，是一个局部极小点，此时更换初始点，转此时更换初始点，转1 1）。）。0Lx0Lffxx0 x综上所述，产生可行搜索方向的条件可概括综上所述，产生可行搜索方向的条件可概括为，当为，当 点满足：点满足：Lx0Lk,2,1jjLLjfffminfm,2,1j0gxxxxx则可行搜索方向为：则可行搜索方向为：0Lxxd四、搜索步长的确定四、搜索步长的确定 可行搜索方向可行搜索
15、方向 确定后，初始点移至确定后，初始点移至 即即 ，从，从 点出发，沿点出发，沿 方向进行搜方向进行搜索，所用的步长索，所用的步长 一般按加速步长法来确定。一般按加速步长法来确定。dLxL0 xx 0 xd 所谓加速步长法是指一次迭代的步长按所谓加速步长法是指一次迭代的步长按一定的比例递增的方法，各次迭代的步长按一定的比例递增的方法，各次迭代的步长按下式计算：下式计算：步长加速系数，可取步长加速系数，可取1.31.3五、随机方向的计算步骤五、随机方向的计算步骤1 1）选择一个可行的初始点；）选择一个可行的初始点；2 2）产生）产生k个个n维随机单位向量维随机单位向量 ；je3 3）取试验步长）
16、取试验步长 ，计算，计算k个随机点个随机点 ；0jx4 4）在）在k个随机点中，找出满足要求的随机个随机点中，找出满足要求的随机点点 ，产生可行搜索方向，产生可行搜索方向 ；Lx0Lxxd5 5），从初始点，从初始点 出发，沿可行方出发，沿可行方向向 以步长以步长 进行迭代计算，直到搜索到进行迭代计算，直到搜索到一个满足全部约束条件，且目标函数值不再一个满足全部约束条件，且目标函数值不再下降的新点下降的新点 。L0 xx 0 xdx6 6）若收敛条件）若收敛条件 2010ffxxxx得到满足，迭代终止。约束最优解为得到满足，迭代终止。约束最优解为 xxxxff,*否则，令否则，令 转步骤转步骤
17、2 2）。）。xx 0例例6-2 6-2 求约束优化问题的最优解求约束优化问题的最优解 01xxg09xxg.t.sxxfmin21222211221xxx解：第三节第三节 复复 合合 形形 法法一、初始复合形的形成一、初始复合形的形成 复合形法是在可行域内直接搜索最优点，复合形法是在可行域内直接搜索最优点，因此要求初始复合型在可行域内生成，即复合因此要求初始复合型在可行域内生成，即复合形的形的k个顶点必须都是可行点。个顶点必须都是可行点。生成初始复合形的方法有以下几种：生成初始复合形的方法有以下几种：1 1、由设计者决定、由设计者决定k个可行点，构成初始复合形，个可行点，构成初始复合形，当设
18、计变量较多或约束函数复杂时，由设计者当设计变量较多或约束函数复杂时，由设计者决定决定k个可行点很困难，只有设计量少，约束函个可行点很困难，只有设计量少，约束函数简单的情况下，这种方法才被采用。数简单的情况下，这种方法才被采用。2 2、由设计者选定一个可行点，其余的（、由设计者选定一个可行点，其余的（k-1-1）个可行点用随机法产生，各顶点按下式计算：个可行点用随机法产生，各顶点按下式计算：1k,2,1jrjjabax 用上式计算得到的（用上式计算得到的（k-1-1）个随机点不一）个随机点不一定都在可行域内，因此要设法将非可行点移定都在可行域内，因此要设法将非可行点移到可行域内。到可行域内。通常
19、采用的方法是，求出已经在可行域通常采用的方法是，求出已经在可行域内的内的L个顶点的中心个顶点的中心cxL1jjcL1xx然后将非可行点向中心点移动，即：然后将非可行点向中心点移动，即：c1Lc1L5.0 xxxx若若 仍为不可行点，则利用上式使其继续仍为不可行点，则利用上式使其继续向中心移动，显然，只要中心点可行，向中心移动，显然，只要中心点可行，点一定可以移动到可行域内。随机产生的点一定可以移动到可行域内。随机产生的k-1-1个点经过这样处理后全部成为可行点，并构个点经过这样处理后全部成为可行点，并构成初始复合形。成初始复合形。1Lx1Lx 事实上，只要可行域为凸集，其中心点必事实上，只要可
20、行域为凸集，其中心点必为可行点，用上述方法可以成功的在可行域内为可行点，用上述方法可以成功的在可行域内构成初始复合形。构成初始复合形。如果可行域为非凸集，中心点不一定在可如果可行域为非凸集，中心点不一定在可行域内，则上述方法可能失败。行域内，则上述方法可能失败。此时可通过改变此时可通过改变设计变量的上限和下设计变量的上限和下限值，重新产生各顶限值，重新产生各顶点，经过多次试算，点，经过多次试算，有可能在可行域内生有可能在可行域内生成初始复合形。成初始复合形。3 3、由计算机自动生成初始复合形的全部顶点，、由计算机自动生成初始复合形的全部顶点，其方法是首先随机产生一个可行点，然后按第其方法是首先
21、随机产生一个可行点，然后按第二种方法产生其余的二种方法产生其余的k-1-1个可行点。个可行点。这种方法对设计者来说最简单，但因初始这种方法对设计者来说最简单，但因初始复合形在可行域内的位置不能控制，可能会给复合形在可行域内的位置不能控制，可能会给以后的计算带来困难。以后的计算带来困难。二、复合形法的搜索方法二、复合形法的搜索方法 在可行域内生成初始复合形后，将采用不在可行域内生成初始复合形后，将采用不同的搜索方法来改变其形状，使复合形逐步向同的搜索方法来改变其形状，使复合形逐步向约束最优点趋近，改变复合形形状的搜索方法约束最优点趋近，改变复合形形状的搜索方法主要有以下几种：主要有以下几种：1
22、1、反射、反射 反射是改变复合形形状的一种主要策略，反射是改变复合形形状的一种主要策略，其计算步骤为：其计算步骤为：1 1）计算复合形各顶点的目标函数值，并比较其）计算复合形各顶点的目标函数值，并比较其大小，求出最好点大小，求出最好点 ，最差点，最差点 及次差点及次差点 ；Lx HxG x2 2）计算除去最坏点）计算除去最坏点 外的（外的（k-1-1）个顶点的）个顶点的中心中心 Hxcxk1jjc1-k1xx3 3）从统计的观点来看，一般情况下最坏点）从统计的观点来看，一般情况下最坏点 和中心点和中心点 的连线方向为目标函数下降的方的连线方向为目标函数下降的方向。向。Hxcx 为此，以为此，以
23、 为中心，将为中心，将 按一定比例进按一定比例进行反射：行反射：cx HxHCCRxxxx反射系数，反射系数，1.31.34 4）判别反射点）判别反射点 的位置的位置Rx若若 为可行点，则比较为可行点，则比较 和和 目标函数目标函数值；若值；若 则用则用 取代取代 ，构成新，构成新的复合形，完成一次迭代；若的复合形，完成一次迭代；若 ，则将则将 缩小缩小0.70.7倍，重新计算反射点，若仍不倍，重新计算反射点，若仍不行，继续缩小行，继续缩小 ，直至，直至 为止。为止。若若 为非可行点，则将为非可行点，则将 缩小缩小0.70.7倍，重倍，重新计算新计算 ，直至可行为止，然后重复以上步，直至可行为
24、止，然后重复以上步骤。骤。RxRx HxHRffxxRx HxHRffxxHRffxxRxRx2 2、扩张、扩张 当求得的反射点当求得的反射点 为可行点，且目标函为可行点，且目标函数值下降较多（如数值下降较多（如 ），则沿反射方），则沿反射方向继续移动，即采用扩张的方法，可能找到更向继续移动，即采用扩张的方法，可能找到更好的新点好的新点 ，成为扩张点。成为扩张点。RxCRffxxExExCRRExxxx扩张系数，取扩张系数，取1 1 若扩张点若扩张点 为可行点，且为可行点，且 ，则，则称扩张成功，称扩张成功，代替代替 ，构成新的复合形，否，构成新的复合形，否则扩张失败，放弃扩张，仍用则扩张失败
25、，放弃扩张，仍用 取代取代 。ExREffxxExRxRxHx3 3、收缩、收缩 若在中心点若在中心点 以外找不到好的反射点，还以外找不到好的反射点，还可以在可以在 以内，即采用收缩的方法寻找较好的以内，即采用收缩的方法寻找较好的新点新点 ，称为收缩点。，称为收缩点。CxCxKxHCHKxxxx收缩系数，取收缩系数，取0.70.7若若 则称收缩成则称收缩成功，用功，用 代替代替 。HKffxxKxHx4 4、压缩、压缩 若采用上述各种方法均无效，还可以采用若采用上述各种方法均无效，还可以采用将复合形各顶点向最好点将复合形各顶点向最好点 靠拢，即采用压靠拢，即采用压缩的方法来改变复合形的形状，各
26、顶点的计算缩的方法来改变复合形的形状，各顶点的计算公式为：公式为：LxLj;k,2,1j5.0jLLjxxxx 除此之外，还可以除此之外，还可以采用旋转的方法来改变采用旋转的方法来改变复合形形状。复合形形状。注意：注意：采用改变复合形形状的方法越多，程序设采用改变复合形形状的方法越多，程序设计越复杂，有可能降低计算效率及可靠性，因计越复杂，有可能降低计算效率及可靠性，因此，程序设计时应针对具体情况采取有效方法。此，程序设计时应针对具体情况采取有效方法。三、复合形法的计算步骤三、复合形法的计算步骤 只含反射只含反射1 1、选择复合形的顶点数、选择复合形的顶点数k，一般取，一般取 ,在可行域内构成
27、具有在可行域内构成具有k个顶点的初始复合形；个顶点的初始复合形；2nk1n2 2、计算复合形各顶点的目标函数值，比较其、计算复合形各顶点的目标函数值，比较其大小，找出最好点大小，找出最好点 和最坏点和最坏点 ；LxHx3 3、计算除去最坏点、计算除去最坏点 以外的以外的 k-1-1个顶点的个顶点的中心中心 ，判别，判别 是否可行，若可行转是否可行，若可行转4 4，否，否则重新确定设计变量的下限和上限值，即令：则重新确定设计变量的下限和上限值，即令：然后转然后转1 1，重新构造初始复合形；，重新构造初始复合形；HxCxCxCL,xbxa4 4、计算、计算 ，必要时改变反射系数，必要时改变反射系数
28、 的值，直的值，直至反射成功，然后用至反射成功，然后用 代替代替 ；RxRxHx5 5、若满足、若满足 计算终止，计算终止，否则转否则转2 2。21k1j2Ljff1k1xx L*L*ffxxxx例例6-3 6-3 用复合形法求约束优化问题的最优用复合形法求约束优化问题的最优解解 22122211222131546640100=100min fxxs.t.gxxgxxgxxxxx第五节第五节 惩惩 罚罚 函函 数数 法法 惩罚函数法是一种使用广泛，很有效的间惩罚函数法是一种使用广泛，很有效的间接解法，它的基本原理是将约束优化问题：接解法，它的基本原理是将约束优化问题：l,2,1k0hm,2,1
29、j0g.t.sfminkjxxx中的不等式和等式约束函数经过加权转化后，中的不等式和等式约束函数经过加权转化后，和原目标函数结合成新的目标函数和原目标函数结合成新的目标函数惩罚函惩罚函数：数：l1kk2m1jj121hHrgGrfr,r,xxxx障碍项障碍项惩罚项惩罚项 惩罚函数法称为序列无约束极小化方法，惩罚函数法称为序列无约束极小化方法，常称常称SUMT法。法。根据迭代过程是否在可行域内进行，惩罚根据迭代过程是否在可行域内进行，惩罚函数法又可分为内点惩罚函数法、外点惩罚函函数法又可分为内点惩罚函数法、外点惩罚函数法和混合惩罚函数法三种。数法和混合惩罚函数法三种。一、内点惩罚函数法一、内点惩
30、罚函数法 内点惩罚函数法又称为内点法，这种方法内点惩罚函数法又称为内点法，这种方法将目标函数定义于可行域内，序列迭代在可行将目标函数定义于可行域内，序列迭代在可行域内逐步逼近约束边界上的最优点。域内逐步逼近约束边界上的最优点。内点法只能用来求解具有不等式约束的优内点法只能用来求解具有不等式约束的优化问题。化问题。对于只具有不等式约束的优化问题：对于只具有不等式约束的优化问题：m,2,1j0g.t.sfminjxx转化后的惩罚函数形式为：转化后的惩罚函数形式为：m1jjm1jjglnrfr,g1rfr,xxxxxx或0rrr210 由于内点法的迭代过程在可行域内进行，由于内点法的迭代过程在可行域
31、内进行，障碍项的作用是阻止迭代点越出可行域。障碍项的作用是阻止迭代点越出可行域。例例6-5 6-5 用内点法求约束最优解用内点法求约束最优解 0 x1g.t.sxxfmin12221xx解：首先构造内点惩罚函数解：首先构造内点惩罚函数1xrlnxxr,12221x令令0r,x0201222111xxxrxx联立求解联立求解 0rx22r11rx21 22r11rx1不满足约束条件，应舍去。不满足约束条件，应舍去。无约束极值点为：无约束极值点为：0rx22r11rx*21 1*f01r0r336.1*f0156.1r36.0r022.2*f0422.1r2.1r4*f02r4rT*T*T*T*x
32、xxx时时时时r=4r=1.2r=0.36内点法中初始点内点法中初始点 、惩罚因子的初始值、惩罚因子的初始值 及其及其缩减系数缩减系数c等主要参数的选取和收敛条件的确定等主要参数的选取和收敛条件的确定:0 x0r一、初始点一、初始点 的选取的选取0 x 使用内点法时，初始点使用内点法时，初始点 应选择一个离应选择一个离约束边界较远的可行点。若约束边界较远的可行点。若 太靠近某一约太靠近某一约束边界，构造的惩罚函数可能由于障碍项的值束边界，构造的惩罚函数可能由于障碍项的值很大而变得畸形，使求解无约束优化问题发生很大而变得畸形，使求解无约束优化问题发生困难。困难。0 x0 x 程序设计时，一般都考
33、虑使程序具有人工程序设计时，一般都考虑使程序具有人工输入和计算机自动生成可行初始点的两种功能，输入和计算机自动生成可行初始点的两种功能，由使用者选用。由使用者选用。计算机自动生成可行点的常用方法是利用计算机自动生成可行点的常用方法是利用随机数生成设计点。随机数生成设计点。2 2、惩罚因子初值、惩罚因子初值r0 0的选取的选取 r0 0应适当，否则会影响迭代计算的正常进应适当，否则会影响迭代计算的正常进行。行。r0 0太大将增加迭代次数；太小，会使惩罚太大将增加迭代次数；太小，会使惩罚函数的性态变坏，甚至难以收敛到极值点。函数的性态变坏，甚至难以收敛到极值点。由于问题函数的多样化，使得由于问题函
34、数的多样化，使得r0 0的取值相的取值相当困难，目前还无一定的有效方法。当困难，目前还无一定的有效方法。对于不同的问题，都要经过多次试算，才对于不同的问题，都要经过多次试算，才能决定一个适当的能决定一个适当的r0 0 。以下方法可作为试算。以下方法可作为试算取值的参考。取值的参考。1 1）取）取r0 0=1=1，根据试算结果，再决定增加或减，根据试算结果，再决定增加或减少；少；2 2）按经验公式）按经验公式m1j0j00g1frxx3 3、缩减系数、缩减系数c的选取的选取 在构造序列惩罚函数时，惩罚因子在构造序列惩罚函数时，惩罚因子r r是一个是一个逐次减到逐次减到0 0的数列，相邻两次迭代的
35、惩罚因子的的数列，相邻两次迭代的惩罚因子的关系为：关系为：1kkcrr惩罚因子的惩罚因子的缩减系数，缩减系数，为小于为小于1 1的的正数，正数，0.10.10.70.74 4、收敛条件、收敛条件 21-k*k*11-k1-k*1-k1-k*kk*rrr,rr,rr,rxxxxx内点法的计算步骤：内点法的计算步骤：1 1）选取可行的初始点）选取可行的初始点 ，惩罚因子的初始，惩罚因子的初始值值 ，缩减系数，缩减系数c c以及收敛精度以及收敛精度 、，令，令迭代次数迭代次数 ；0 x0r210k 2 2）构造惩罚函数）构造惩罚函数 ，选择适当的无约束优，选择适当的无约束优化方法，求函数化方法，求函
36、数 的无约束极值得的无约束极值得 点；点；r,xr,x k*rx3 3）判别是否收敛，若满足，终止；否则，）判别是否收敛，若满足，终止；否则，转转2 2）。）。k1kcrr k*0rxx 1kk二、外点惩罚函数法二、外点惩罚函数法 简称外点法，和内点法相反，新目标函数简称外点法，和内点法相反，新目标函数定义在可行域之外，序列迭代从可行域之外逐定义在可行域之外，序列迭代从可行域之外逐渐逼近约束边界上的最优点。渐逼近约束边界上的最优点。可用来求解含有不等式和等式约束优化问可用来求解含有不等式和等式约束优化问题。题。对于约束优化问题：对于约束优化问题：l,2,1k0hm,2,1j0g.t.sfmin
37、kjxxx转化后的外点惩罚函数的形式为：转化后的外点惩罚函数的形式为：2l1kk2m1jjhrg0,maxrfr,xxxx210rrr例例6-6 6-6 用外点法求约束最优解用外点法求约束最优解 0 x1g.t.sxxfmin12221xx解：首先构造外点惩罚函数解：首先构造外点惩罚函数212221xrxx,r1x令令0r,x02xx0 x12r2xx22111联立求解联立求解 0rxr1rrx*21 1*f01rr78.0*f0882.0r5.7r36.0*f06.0r5.1r053.0*f0231.0r3.0rT*T*T*T*xxxx时时时时r=0.3r=1.5r=7.5外点法惩罚因子按下
38、式递增：外点法惩罚因子按下式递增：1kkcrr递增系数，取递增系数，取5 51010 与内点法相反，惩罚因子的初值若取相当与内点法相反，惩罚因子的初值若取相当大，会使大，会使 的等值线变形或偏心，求的等值线变形或偏心，求 的极值将发生困难。但取得过小，势必增加迭的极值将发生困难。但取得过小，势必增加迭代次数。所以在外点法中，代次数。所以在外点法中，的合理取值很重的合理取值很重要。许多计算表明，取要。许多计算表明，取 常常可以常常可以取得满意的结果。有时也按下式来计算：取得满意的结果。有时也按下式来计算：r,xr,x0r10c,1r0 m,2,1jrmaxr0j0 m,2,1jfmg02.0r0
39、0j0jxx式中式中 外点法的收敛条件和内点法相同，计算步外点法的收敛条件和内点法相同，计算步骤程序框图与内点法相近。骤程序框图与内点法相近。三、混合惩罚函数法三、混合惩罚函数法 简称混合法，是把内点法和外点法结合起简称混合法，是把内点法和外点法结合起来，用来求解同时具有等式约束和不等式约束来，用来求解同时具有等式约束和不等式约束函数的优化问题。函数的优化问题。对于约束优化问题：对于约束优化问题：l,2,1k0hm,2,1j0g.t.sfminkjxxx转化后的混合惩罚函数的形式为：转化后的混合惩罚函数的形式为：2l1kkm1jjhr1g1rfr,xxxx 混合法具有内点法的求解特点，即迭代混
40、合法具有内点法的求解特点，即迭代过程在可行域内进行，因而初始点、惩罚因过程在可行域内进行，因而初始点、惩罚因子的初始值均可参考内点法选取，计算步骤子的初始值均可参考内点法选取，计算步骤也与内点法相近。也与内点法相近。例例6-7 6-7 试求点集试求点集 和点集和点集 之间的最短距离。限制条件为：之间的最短距离。限制条件为：321x,x,xA654x,x,xB8x41x3x5xxx62524232221 0 x4g08xg01x3xg05xxxg.t.sxxxxxxfmin26263252422322211263252241xxxxx第四节第四节 可可 行行 方方 向向 法法 约束优化问题的直接
41、解法中，可行方向法约束优化问题的直接解法中，可行方向法是最大的一类，它也是求解大型约束优化问题是最大的一类，它也是求解大型约束优化问题的主要方法之一。的主要方法之一。这种方法的基本原理是在可行域内选择一这种方法的基本原理是在可行域内选择一个初始点个初始点 ，当确定了一个可行方向，当确定了一个可行方向d d 和适和适当的步长后，按式：当的步长后，按式：0 x1 (1,2,)kkkkxxd进行迭代计算。进行迭代计算。在不断调整可行方向的过程中，使迭代点在不断调整可行方向的过程中，使迭代点逐步逼近约束最优点。逐步逼近约束最优点。一、可行方向法的搜索策略一、可行方向法的搜索策略 可行方向法的第一步迭代
42、都是从可行的初可行方向法的第一步迭代都是从可行的初始点始点 出发，沿出发，沿 点的负梯度方向点的负梯度方向 ，将初始点移动到某一个约束面（只有一个起作将初始点移动到某一个约束面（只有一个起作用的约束时）上或约束面的交集（有几个起作用的约束时）上或约束面的交集（有几个起作用的约束时）。用的约束时）。然后根据约束函数和目标函数的不同性状，然后根据约束函数和目标函数的不同性状，分别采用以下几种策略继续搜索：分别采用以下几种策略继续搜索：0 x0 x00f dx第一种情况 第二种情况 第三种情况 1ktgxxx Ttgggxxx调整步长估算公式：二、产生可行方向的条件二、产生可行方向的条件 可行方向是
43、指沿该方向作微小移动后，所可行方向是指沿该方向作微小移动后，所得到的新点是可行点，且目标函数值有所下降。得到的新点是可行点，且目标函数值有所下降。显然，可行方向应满足显然，可行方向应满足可行可行和和下降下降两个条两个条件。件。1 1、可行条件、可行条件 方向的可行条件是指沿该方向作微小移动方向的可行条件是指沿该方向作微小移动后，所得到的新点即为可行点。后，所得到的新点即为可行点。T0kkgxdT0 (1,2,)kkjgjJxd2 2、下降条件下降条件 方向方向的下降条件是指沿该方向作微小移动的下降条件是指沿该方向作微小移动后，所得新点的目标函数值是下降的。后，所得新点的目标函数值是下降的。T0
44、kkfxd 同时满足可行和同时满足可行和下降条件的方向称为下降条件的方向称为可行方向。可行方向。TT0 (1,2,)0kkjkkgjJfxdxd三、可行方向的产生方法 由于满足可行、下降条件的方向位于可行下降扇形区内，在扇形区内寻找一个最有利的方向作为本次迭代的搜索方向。其方法主要有优选方向法和梯度投影法。1、优选方向法 在可行下降扇形区内选择任一方向进行搜索，可得到一个目标函数值下降的可行点。现在的问题是如何在可行下降扇形区内选择一个能使目标函数值下降最快的方向作为本次迭代的方向。显然，这是一个以搜索方向 为设计变量的约束优化问题，这个新的约束优化问题的数学模型可写成dTminkfxdTTs
45、.t.0 (1,2,)0 1kjkgjJf xdxdd线性规划问题2、梯度投影法 当 点目标函数的负梯度方向 不满足可行条件时，可将 方向投影到约束面（或约束面的交集）上，得到投影向量 。kxkfxkfxkd可行方向的计算公式为：/kkkPfPf dxx投影算子，为n*n阶矩阵 1TTPIG G GG起作用约束函数的梯度矩阵 12 kkkJGggg xxx起作用的约束函数个数 四、步长的确定1kkkkxxd两种方法 1、取最优步长2、取到约束边界的最大步长 由于不能预测点 到另一个起约束作用面的距离，的确定比较困难，大致可按以下步骤计算：kxM 1）取一试验步长 ，计算试验点 。试验步长的值不
46、能太大，以免因一步走得太远导致计算困难；也不能太小，使得计算效率太低。根据经验，试验步长 的值能使试验点 的目标函数值下降5%10%为宜，即ttxttx0.05 0.1kktffff xxx将目标函数 在 点展开成泰勒级数的线性式tx fxTkkkkktttffff xxdxxdT0.05 0.1kkktfff xdxTT0.05 0.1ktkkkkffffxxdxdkkttxxd恒为正值 2）判别试验点的位置 01,2,jtgjJx 若试验点 位于非可行域，则转步骤3）；若位于可行域内，则应沿方向 以步长 继续向前搜索，直至新的试验点到达约束面或超出可行域，再转步骤3）。txkd2tt3）将
47、位于非可行域的试验点 调整到约束面上 tx1,2,max0ktjtjJggxx 将试验点 调整到 的约束面上的方法有试探法和插值法两种。tx0ktgx 试探法的基本内容是当试验点位于非可行域时，将试验步长缩短；当试验点位于可行域内时，将试验步长增加，即不断变化的大小，直至满足条件时，就认为试验点已被调整到约束面上了。插值法是利用线性插值将位于非可行域的试验点 调整到约束面上。设试验步长为 时，求得可行试验点txt1kkttxxd当试验步长为 时，求得非可行试验点0t20kkttxxd10210.5()()()ktsktktgggxxxkMts五、收敛条件 按可行方向法的原理，将设计点调整到约束
48、面上后，需要判断迭代是否收敛，即判断该迭代点是否为约束最优点。常用的收敛条件有以下两种：1、设计点 即约束允差满足kxT2kkfxd条件时，迭代收敛。2、设计点 满足库-塔条件kx时，迭代收敛。100 (1,2,)JkkjjjjfgjJxx六、可行方向法的计算步骤 1）在可行域内选择一个初始点 ，给出约束允差 及收敛精度值 。0 x2）令迭代次数k=0，第一次迭代的搜索方向取 。00f dx3）估算试验步长 ，计算试验点 。ttx4）若试验点 满足 ，点必位于第j个约束面上，则转步骤6）；若试验点 位于可行域内，则加大试验步长 ，重新计算新的试验点，直至 越出可行域，再转步骤5）；若试验点位于
49、非可行域，则直接转步骤5）。tx0jtgxtxtxttx5）确定约束违反量最大的约束函数 。用插值法计算调整步长 ，使试验点 返回到约束面上，则完成一次迭代。再令k=k+1，转下步。ktgxstxktxx6）在新的设计点 处产生新的可行方向 。kxkd7）在 点满足收敛条件，则计算终止。约束最优解为 ，。否则，改变允差 的值，即令kx*kxx*kffxxTT,0.5,kkkkkkkffxdxd再转步骤2）。例例 6.4 用可行方向法求解下列约束优化问题的约束最优解。2212121211223142512min()60 104s.t.0 0 60 80 110f xxxxxx xgxgxgxgx
50、gxx xxxxx解：解：先采用优选方向法，后采用梯度投影法来确定可行方向。取初始点 为约束 边界上的一点。第一次迭代用优选方向法。计算 点的目标函数 和约束函数 的梯度T00,1x 10gx0 x0fx01gx1202110211422xxfxx x0110gx为在可行下降扇形区内寻找最优方向，需要求解一个以可行方向 为设计变量的线性规划问题，其数学模型为T12,dddT012T011T0122212min()112s.t.0 1120 1fddgdfdddd xdxdxd用图解法求解 最优方向是 。第一次迭代的可行方向为 。若取步长 ，则T*0.984,0.179d0*dd06.098TT
