第5章 约束优化方法2(白版).ppt

《第5章 约束优化方法2(白版).ppt》由会员分享，可在线阅读，更多相关《第5章 约束优化方法2(白版).ppt（79页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第五章 有约束优化方法 5-1 5-1 引言引言5-25-2 随机方向法随机方向法5-35-3 复合形法复合形法5-45-4 可行方向法可行方向法 5-5 5-5 惩罚函数法惩罚函数法5-65-6 序列二次规划法序列二次规划法5-1 5-1 引言引言机械优化设计中的问题，大多数属于约束优化设计机械优化设计中的问题，大多数属于约束优化设计问题，其数学模型为问题，其数学模型为上一章讨论的都是无约束条件下非线性函数的寻上一章讨论的都是无约束条件下非线性函数的寻优方法，但在实际工程中大部分问题的变量取值都有优方法，但在实际工程中大部分问题的变量取值都有一定的限制，也就是属于有约束条件的寻优问题。一定的

2、限制，也就是属于有约束条件的寻优问题。与无约束问题不同，约束问题目标函数的最小值与无约束问题不同，约束问题目标函数的最小值是满足约束条件下的最小值，即是由约束条件所限定是满足约束条件下的最小值，即是由约束条件所限定的可行域内的最小值。只要由约束条件所决定的可行的可行域内的最小值。只要由约束条件所决定的可行域必是一个凸集，目标函数是凸函数，其约束最优解域必是一个凸集，目标函数是凸函数，其约束最优解就是全域最优解。否则，将由于所选择的初始点的不就是全域最优解。否则，将由于所选择的初始点的不同，而探索到不同的局部最优解上。在这种情况下，同，而探索到不同的局部最优解上。在这种情况下，探索结果经常与初始

3、点的选择有关。为了能得到全局探索结果经常与初始点的选择有关。为了能得到全局最优解，在探索过程中最好能改变初始点，有时甚至最优解，在探索过程中最好能改变初始点，有时甚至要改换几次。要改换几次。（1）直接法）直接法直接法包括：网格法、复合形法、随机试验法、直接法包括：网格法、复合形法、随机试验法、随机方向法、可变容差法和可行方向法。随机方向法、可变容差法和可行方向法。（2）间接法）间接法间接法包括：罚函数法、内点罚函数法、外点罚间接法包括：罚函数法、内点罚函数法、外点罚函数法、混合罚函数法、广义乘子法、广义简约梯度函数法、混合罚函数法、广义乘子法、广义简约梯度法和约束变尺度法等。法和约束变尺度法等

4、。根据求解方式的不同，约束优化设计问题可分为根据求解方式的不同，约束优化设计问题可分为:直直接解法、间接解法。接解法、间接解法。直接解法通常适用于仅含不等式约束的问题，思路是直接解法通常适用于仅含不等式约束的问题，思路是在在m个不等式约束条件所确定的可行域内，选择一个初始个不等式约束条件所确定的可行域内，选择一个初始点，然后决定可行搜索方向点，然后决定可行搜索方向d 且以适当的步长且以适当的步长，进行，进行搜索，得到一个使目标函数值下降的可行的新点，即完成搜索，得到一个使目标函数值下降的可行的新点，即完成一次迭代。再以新点为起点，重复上述搜索过程，直至满一次迭代。再以新点为起点，重复上述搜索过

5、程，直至满足收敛条件。足收敛条件。步长步长可行搜索方向可行搜索方向可行搜索方向可行搜索方向:当设计点沿该方向作微量移动时，当设计点沿该方向作微量移动时，目标函数值将下降，且不会越出可行域目标函数值将下降，且不会越出可行域。间接解法的基本思路是按照一定的原则构造一个间接解法的基本思路是按照一定的原则构造一个包含原目标函数和约束条件的新目标函数，即将原约包含原目标函数和约束条件的新目标函数，即将原约束优化问题转化成为一个或一系列的无约束优化问题。束优化问题转化成为一个或一系列的无约束优化问题。再对新的目标函数进行无约束优化计算，从而间接地再对新的目标函数进行无约束优化计算，从而间接地搜索到原约束问

6、题的最优解。搜索到原约束问题的最优解。5-25-2 随机方向法随机方向法基基基基本本本本思思思思想想想想：利利利利用用用用计计计计算算算算机机机机产产产产生生生生的的的的随随随随机机机机数数数数所所所所构构构构成成成成的的的的随随随随机机机机方方方方向向向向进进进进行行行行搜搜搜搜索索索索，产产产产生生生生的的的的新新新新点点点点必必必必须须须须在在在在可可可可行行行行域域域域内内内内，即即即即满满满满足直接法的特性。足直接法的特性。足直接法的特性。足直接法的特性。随随随随机机机机方方方方向向向向法法法法，是是是是约约约约束束束束最最最最优优优优化化化化问问问问题题题题的的的的一一一一种种种种

7、常常常常用用用用的的的的直直直直接接接接求求求求解解解解方方方方法法法法。它它它它和和和和随随随随机机机机梯梯梯梯度度度度法法法法、GaussGaussSeidelSeidel法法法法等等等等都都都都属于约束随机法。属于约束随机法。属于约束随机法。属于约束随机法。其其其其基基基基本本本本原原原原理理理理如如如如图图图图所所所所示示示示，在在在在约约约约束束束束可可可可行行行行域域域域S S内内内内选选选选取取取取一一一一个个个个初初初初始始始始点点点点X(0)X(0)，在在在在不不不不破破破破坏坏坏坏约约约约束束束束的的的的条条条条件件件件下下下下以以以以合合合合适适适适的的的的步步步步长长长

8、长a a。沿沿沿沿X(0)X(0)点点点点周周周周围围围围几几几几个个个个不不不不同同同同的的的的方方方方向向向向（以以以以某某某某种种种种形形形形式式式式产产产产生生生生的的的的随随随随机机机机方方方方向向向向）进进进进行行行行若若若若干干干干次次次次探探探探索索索索，并并并并计计计计算算算算各各各各方方方方向向向向上上上上等等等等距距距距离离离离（步步步步长长长长a a。）点点点点的的的的函函函函 数数数数 值值值值，找找找找 出出出出 其其其其 中中中中 的的的的 最最最最 小小小小 值值值值 f f（X(lX(l)）及及及及 点点点点 X(lX(l)。若若若若f f（X(lX(l)）f

9、 f（X(0)X(0)），则则则则继继继继续续续续沿沿沿沿方方方方向向向向（X(l)-X(0)X(l)-X(0)）以以以以适适适适当当当当的的的的步步步步长长长长a a向向向向前前前前跨跨跨跨步步步步，得得得得到到到到新新新新点点点点X(1)X(1)，若若若若f f（X(1)X(1)）老老老老f f（X(lX(l)），则则则则将将将将新新新新的的的的起起起起点点点点移移移移至至至至X(1)X(1)，重重重重复复复复前前前前面面面面过过过过程程程程。否否否否则则则则应应应应缩缩缩缩短短短短步步步步长长长长a a，直直直直至至至至取取取取得得得得约约约约束束束束好好好好点点点点。如如如如此此此此循

10、循循循环环环环下下下下去去去去。当当当当迭迭迭迭代代代代的的的的步步步步长长长长已已已已经经经经很很很很小小小小时时时时，则则则则表表表表明明明明已已已已经经经经逼逼逼逼近近近近约约约约束束束束最最最最优优优优点点点点。达到计算精度要求时，即可结束迭代计算。达到计算精度要求时，即可结束迭代计算。达到计算精度要求时，即可结束迭代计算。达到计算精度要求时，即可结束迭代计算。图图约束随机方向探索法的基本原理约束随机方向探索法的基本原理随机方向探索法的一般迭代随机方向探索法的一般迭代随机方向探索法的一般迭代随机方向探索法的一般迭代计计计计算公式算公式算公式算公式为为为为：X X(k+1)(k+1)=X

11、 X(k)(k)+aS+aS(k(k)(k=0,1,2,)(k=0,1,2,)式中式中式中式中a a为为为为步步步步长长长长，S S(k(k)为为为为第第第第k k次迭代的随机探索方向。次迭代的随机探索方向。次迭代的随机探索方向。次迭代的随机探索方向。因此，随机方向探索法的因此，随机方向探索法的因此，随机方向探索法的因此，随机方向探索法的计计计计算算算算过过过过程可程可程可程可归结为归结为归结为归结为：复复复复合合合合形形形形法法法法是是是是求求求求解解解解约约约约束束束束非非非非线线线线性性性性最最最最优优优优化化化化问问问问题题题题的的的的一一一一种种种种重重重重要要要要的的的的直直直直接

12、接接接方方方方法法法法。它它它它来来来来源源源源于于于于用用用用于于于于求求求求解解解解无无无无约约约约束束束束非非非非线线线线性性性性最最最最优优优优化化化化问问问问题题题题的的的的单单单单纯纯纯纯形形形形法法法法，实实实实际际际际上上上上是是是是单单单单纯纯纯纯形形形形法法法法在在在在约约约约束束束束问问问问题题题题中中中中的发展。的发展。的发展。的发展。如如如如前前前前所所所所述述述述，在在在在求求求求解解解解无无无无约约约约束束束束问问问问题题题题的的的的单单单单纯纯纯纯形形形形法法法法中中中中，不不不不需需需需计计计计算算算算目目目目标标标标函函函函数数数数的的的的梯梯梯梯度度度度，

13、而而而而是是是是靠靠靠靠选选选选取取取取单单单单纯纯纯纯形形形形的的的的顶顶顶顶点点点点井井井井比比比比较较较较各各各各顶顶顶顶点点点点处处处处目目目目标标标标函函函函数数数数值值值值的的的的大大大大小小小小，来来来来寻寻寻寻找找找找下下下下一一一一步步步步的的的的探探探探索索索索方方方方向向向向的的的的。在在在在用用用用于于于于求求求求解解解解约约约约束束束束问问问问题题题题的的的的复复复复合合合合形形形形法法法法中中中中，复复复复合合合合形形形形各各各各顶顶顶顶点点点点的的的的选选选选择择择择和和和和替替替替换换换换，不不不不仅仅仅仅要要要要满满满满足足足足目目目目标标标标函函函函数数数数

14、值值值值的的的的下下下下降，还应当满足所有的约束条件。降，还应当满足所有的约束条件。降，还应当满足所有的约束条件。降，还应当满足所有的约束条件。5-35-3 复合形法复合形法基基基基 本本本本 思思思思 想想想想：在在在在 可可可可 行行行行 域域域域 中中中中 选选选选 取取取取 KK个个个个 设设设设 计计计计 点点点点 （n+1K2nn+1K2n）作作作作为为为为初初初初始始始始复复复复合合合合形形形形的的的的顶顶顶顶点点点点。比比比比较较较较各各各各顶顶顶顶点点点点目目目目标标标标函函函函数数数数值值值值的的的的大大大大小小小小，去去去去掉掉掉掉目目目目标标标标函函函函数数数数值值值值

15、最最最最大大大大的的的的顶顶顶顶点点点点(称称称称最最最最坏坏坏坏点点点点)，以以以以坏坏坏坏点点点点以以以以外外外外其其其其余余余余各各各各点点点点的的的的中中中中心心心心为为为为映映映映射射射射中中中中心心心心，用用用用坏坏坏坏点点点点的映射点替换该点，构成新的复合形顶点。的映射点替换该点，构成新的复合形顶点。的映射点替换该点，构成新的复合形顶点。的映射点替换该点，构成新的复合形顶点。反反反反复复复复迭迭迭迭代代代代计计计计算算算算，使使使使复复复复合合合合形形形形不不不不断断断断向向向向最最最最优优优优点点点点移移移移动动动动和和和和收收收收缩缩缩缩，直直直直至至至至收收收收缩缩缩缩到到

16、到到复复复复合合合合形形形形的的的的顶顶顶顶点点点点与与与与形形形形心心心心非非非非常常常常接接接接近近近近，且且且且满满满满足迭代精度要求为止。足迭代精度要求为止。足迭代精度要求为止。足迭代精度要求为止。令：令：X(4)=X(0)+(X(0)-X(H)称称X(4)为映射点，记为为映射点，记为X(R)，为映射系数，通常取为映射系数，通常取=1.3，可根据实际情况进行缩减。，可根据实际情况进行缩减。取次好点和好点连线的中点为取次好点和好点连线的中点为X(0)。一般情况下，映射点的函数值比坏点的函数值要一般情况下，映射点的函数值比坏点的函数值要小，即小，即F(X(R)F(X(H)。若满足可行域，则

17、用。若满足可行域，则用X(R)代替代替X(H)构成新的复合形。如此反复迭代直到找到最优解。构成新的复合形。如此反复迭代直到找到最优解。在在可可行行域域内内任任选选三三个个初初始始点点X(1)、X(2)、X(3)，连连接接这这三三点点形形成成一一个个三三角角形形，此此三三角角形形称称为为初初始始复复合合形形。计计算算各各个个顶顶点点函函数数值值F(X(1)、F(X(2)、F(X(3)，找找出出最最大大值值，记记为为坏坏点点X(H)。最最小小值值，记记为为最最好好点点X(L)。在在次次好好点点和和好好点连线与坏点反向一侧的各点应具有较小的目标值。点连线与坏点反向一侧的各点应具有较小的目标值。在在迭

18、迭代代过过程程中中，按按映映射射系系数数=1.3得得到到的的映映射射点点，不不一一定定满满足足适适用用性性和和可可行行性性，如如出出现现此此情情况况，将将映映射射系系数数减减半半，重重新新取取得得X(R)，使使它它满满足足适适用用性性和和可可行性。行性。一、初始复合形的构成一、初始复合形的构成复合形的顶点复合形的顶点K通常取通常取n+1K2n个。对于维数较低个。对于维数较低的优化问题，由于顶点数目较少，可试凑几个可行点作的优化问题，由于顶点数目较少，可试凑几个可行点作为复合形的顶点。对于维数较高的问题，采用随机方法，为复合形的顶点。对于维数较高的问题，采用随机方法，先产生先产生K个随机点，然后

19、再把非可行点逐一调入可行域内。个随机点，然后再把非可行点逐一调入可行域内。1、产生、产生K个随机点个随机点xi=ai+i(bi-ai)i=1,2,.,ni为（为（0，1）区间内产生的均匀分布的随机数，需要）区间内产生的均匀分布的随机数，需要n个个随机数产生一个点随机数产生一个点X(1)。同样，产生其它的随机点。同样，产生其它的随机点X(2)、X(3)、X(K)。2、将非可行点调入可行域、将非可行点调入可行域将产生的将产生的K个随机点进行判断是否在可行域内，个随机点进行判断是否在可行域内，重新排列，将可行点依次排在前面，如有重新排列，将可行点依次排在前面，如有q个顶点个顶点X(1)、X(2)、X

20、(q)是可行点，其它是可行点，其它K-q个为非可行点。个为非可行点。对对X(q+1)，将其调入可行域的步骤是：，将其调入可行域的步骤是：（1）计算）计算q个点集的中心个点集的中心X(s)；（2）将第）将第q+1点朝着点点朝着点X(s)的方向移动，按下式产的方向移动，按下式产生新的生新的X(q+1)，即，即X(q+1)=X(s)+0.5(X(q+1)X(s)这这个个新新点点X(q+1)实实际际就就是是X(s)与与原原X(q+1)两两点点连连线线的的中中点点，如如图图。若若新新的的X(q+1)点点仍仍为为非非可可行行点点，按按上上式式再再产产生生X(q+1)，使它更向，使它更向X(s)靠拢，最终使

21、其成为可行点。靠拢，最终使其成为可行点。按按照照这这个个方方法法，同同样样使使X(q+2)、X(q+3)、X(K)都变为可行点，这都变为可行点，这K个点就构成了初始复合形。个点就构成了初始复合形。二、复合形法的迭代步骤二、复合形法的迭代步骤（1）构造初始复合形；）构造初始复合形；（2）计算各顶点的函数值）计算各顶点的函数值F(X(j)，j=1,2,.,K。选出好。选出好点点X(L)和坏点和坏点X(H)。（3）计算坏点外的其余各顶点的中心点）计算坏点外的其余各顶点的中心点X(0)。（4）计算映射点）计算映射点X(R)检查检查X(R)是否在可行域内。若是否在可行域内。若X(R)为非可行点，将映为非

22、可行点，将映射系数减半后再按上式改变映射点，直到射系数减半后再按上式改变映射点，直到X(R)进入可行域进入可行域内为止。内为止。（5）构造新的复合形）构造新的复合形计算映射点的函数值计算映射点的函数值F(X(R)，并与坏点的函数值，并与坏点的函数值F(X(H)比较，可能存在两种情况：比较，可能存在两种情况：1）映射点优于坏点）映射点优于坏点F(X(R)F(X(H)在此情况，用在此情况，用X(R)代替代替X(H)，构成新的复合形。，构成新的复合形。若经过多次的映射系数减半，仍不能使映射点由于坏若经过多次的映射系数减半，仍不能使映射点由于坏点，则说明该映射方向不利，此时，应改变映射方向，点，则说明

23、该映射方向不利，此时，应改变映射方向，取对次坏点取对次坏点的映射。的映射。再转回本步骤的开始处，直到构成新的复合形。再转回本步骤的开始处，直到构成新的复合形。2）映射点次于坏点）映射点次于坏点F(X(R)F(X(H)这这种种情情况况由由于于映映射射点点过过远远引引起起的的，减减半半映映射射系系数数，若有若有F(X(R)F(X(H)，这又转化为第一种情况。，这又转化为第一种情况。(6)判断终止条件判断终止条件1)各顶点与好点函数值之差的均方根值小于误差限，即各顶点与好点函数值之差的均方根值小于误差限，即2）各顶点与好点的函数值之差的平方和小于误差限，即）各顶点与好点的函数值之差的平方和小于误差限

24、，即3）各顶点与好点函数值差的绝对值之和小于误差限，即）各顶点与好点函数值差的绝对值之和小于误差限，即如果不满足终止迭代条件，则返回步骤如果不满足终止迭代条件，则返回步骤2继续进行下继续进行下一次迭代；否则，可将最后复合形的好点一次迭代；否则，可将最后复合形的好点X(L)及其函数值及其函数值F(X(L)作为最优解输出。作为最优解输出。方法特点方法特点（1 1）复复复复合合合合形形形形法法法法是是是是求求求求解解解解约约约约束束束束非非非非线线线线性性性性最最最最优优优优化化化化问问问问题题题题的的的的一一一一种种种种直直直直接接接接方方方方法法法法，仅仅仅仅通通通通过过过过选选选选取取取取各各

25、各各顶顶顶顶点点点点并并并并比比比比较较较较各各各各点点点点处处处处函函函函数数数数值值值值的的的的大大大大小小小小，就就就就可可可可寻寻寻寻找找找找下下下下一一一一步步步步的的的的探探探探索索索索方方方方向向向向。但但但但复复复复合合合合形形形形各各各各顶顶顶顶点点点点的的的的选选选选择择择择和和和和替替替替换换换换，不不不不仅仅仅仅要要要要满满满满足足足足目目目目标标标标函函函函数数数数值值值值下下下下降降降降的的的的要求，还应当满足所有的约束条件。要求，还应当满足所有的约束条件。要求，还应当满足所有的约束条件。要求，还应当满足所有的约束条件。（2 2）复合形法适用于仅含不等式约束的问题。

26、）复合形法适用于仅含不等式约束的问题。）复合形法适用于仅含不等式约束的问题。）复合形法适用于仅含不等式约束的问题。可可行行方方向向是是求求解解大大型型不不等等式式约约束束优优化化问问题题的的主主要要方方法之一。法之一。基基本本思思想想：这这种种方方法法的的基基本本原原理理是是在在可可行行域域内内选选择择一一个个初初始始点点，当当确确定定了了一一个个可可行行方方向向d和和适适当当的的步步长长后，按式后，按式:5-45-4 可行方向法可行方向法进行迭代计算进行迭代计算,迭代点既不超出可行域迭代点既不超出可行域,又使目标函又使目标函数的值有所下降。在不断调整可行方向的过程中，数的值有所下降。在不断调

27、整可行方向的过程中，使迭代点逐步逼近约束最优点。使迭代点逐步逼近约束最优点。可行方向法的搜索策略？可行方向法的搜索策略？即：即：Ox1x2Ox1x2a)极值点处于多角形的某一顶点上b)极值点处于等值线的中心c)极值点处于约束曲线与等值线的切点上d)极值点处于两个约束曲线的交点上xg1(x)0g2(x)0g3(x)0 xg2(x)0g3(x)0g4(x)0g1(x)0g2(x)0Ox1x2Ox1x2xg2(x)0 xg1(x)0g1(x)0图图图图1-101-101.可行方向法的搜索策略可行方向法的搜索策略第一步迭代都是从可行的初始点第一步迭代都是从可行的初始点出发，沿点的出发，沿点的负梯度负梯

28、度方向，将初始点移动到某一个约束方向，将初始点移动到某一个约束面（只有一个起作用的约束时）上面（只有一个起作用的约束时）上,或约束面的交集或约束面的交集（有几个起作用的约束时）上。（有几个起作用的约束时）上。根据约束函数和目标函数的不同性状，分别采用根据约束函数和目标函数的不同性状，分别采用以下几种策略继续搜索。以下几种策略继续搜索。1新点在可行域内的情况新点在可行域内的情况2新点在可行域外的情况新点在可行域外的情况3沿线性约束面的搜索沿线性约束面的搜索4沿非线性约束面的搜索沿非线性约束面的搜索l2.产生可行方向的条件产生可行方向的条件可行方向是指沿该方向作微小移动后，所得到的可行方向是指沿该

29、方向作微小移动后，所得到的新点是可行点，且目标函数值有所下降。新点是可行点，且目标函数值有所下降。可行方向应满足两个条件可行方向应满足两个条件:(1)可行可行;(2)下降下降。1）可行条件）可行条件方向的可行条件是指沿该方向作微小移动后，所得到方向的可行条件是指沿该方向作微小移动后，所得到的新点为可行点。的新点为可行点。l2）下降条件）下降条件方向的下降条件是指沿该方向作微小移动后，所得方向的下降条件是指沿该方向作微小移动后，所得新点的目标函数值是下降的。新点的目标函数值是下降的。l满足可行和下降条件，即式满足可行和下降条件，即式:位于约束位于约束曲面在点曲面在点xk的切线和目的切线和目标函数

30、等值标函数等值线在点线在点xk的的切线所围成切线所围成的扇形区内，的扇形区内，该扇形区称该扇形区称为可行下降为可行下降方向区方向区。同时成立的方向称可行方向。同时成立的方向称可行方向。l3.可行方向的产生方法可行方向的产生方法满足可行、下降条件的方向位于可行下降扇满足可行、下降条件的方向位于可行下降扇形区内，在扇形区内寻找一个最有利的方向作为形区内，在扇形区内寻找一个最有利的方向作为本次迭代的搜索方向。本次迭代的搜索方向。（1 1）优选方向法）优选方向法由条件：由条件：求一个以搜索方向求一个以搜索方向d为设计变量的约束优化问题为设计变量的约束优化问题s.t.各函数均为设计变量各函数均为设计变量

31、dk的线性函的线性函数，因此该式为一个（线性）数，因此该式为一个（线性）规划问题。规划问题。当当xk点点目目标标函函数数的的负负梯梯度度方方向向不不满满足足可可行行条条件件时时，可可将将方方向向投投影影到到约约束束面面（或或约约束束面面的的交交集集）上上，得到投影向量得到投影向量dk。xkdkg g1 1(x)=0)=0g g2 2(x)=0)=0g g3 3(x)=0)=0g g4 4(x)=0)=0P P投影算子，投影算子，为为nX Xn阶矩阵阶矩阵G 起作用约起作用约束函数的梯度矩束函数的梯度矩阵，阵，nX XJ阶矩阵；阶矩阵；（2）梯度投影法）梯度投影法l4.4.步长的确定步长的确定

32、确定的确定的步步长长应使新的迭代点为可行点，且目标函数应使新的迭代点为可行点，且目标函数具有最大的下降量具有最大的下降量约束一维搜索。约束一维搜索。1 1）取最优步长）取最优步长 从从xk点点出发，沿出发，沿dk方向进行一维最优方向进行一维最优化搜索，取得最优步长，计算新点化搜索，取得最优步长，计算新点x的值的值。l取到约束边界的最大步长取到约束边界的最大步长l从从xk点出发，沿点出发，沿dk方向进行一维最优化搜索，方向进行一维最优化搜索，得到的新点得到的新点x为为不可行点不可行点。改变步长，改变步长，使新点使新点x返回到返回到约束面上来。约束面上来。使新点使新点x恰好位恰好位于约束面上的于约

33、束面上的步长称为最大步长称为最大步长步长。l约束一维搜索：约束一维搜索：与与以以前前所所讲讲过过的的一一维维搜搜索索相相比比，约约束束一一维维搜搜索索的的特特点点在在于于：确确定定初初始始区区间间时时，对对产产生生的的每每一一个个探探测测点点都都进进行行可可行行性性判判断断，如如违违反反了了某某个个或或某某些些约约束束条条件件，就就必必须须减减少少步步长长因因子子，以以使使新新的的探探测测点点落落在在最最近近的的一一个个约约束曲面上或约束曲面的一个容许的区间束曲面上或约束曲面的一个容许的区间内。内。0 x1x2xkdkxk+1g2(x)=0g1(x)=0a*dkaMdkxl如得到的相邻三个探测

34、点都是可行点，而且函数如得到的相邻三个探测点都是可行点，而且函数值呈值呈“大小大大小大”变化，则与前面一维搜索相同，变化，则与前面一维搜索相同，两端点所决定的区间就是初始区间，接着缩小区间直两端点所决定的区间就是初始区间，接着缩小区间直到一维最小点。到一维最小点。f(a1)f(a2)f(a1)f(a2)a1 a1 a2a0a0 a2f(a3)f(a3)a3a3f(a3)f(a3)a3a3l如如最最后后得得到到的的探探测测点点落落在在约约束束曲曲面面的的一一个个容容限限之之内，而且函数值比前一点的小，则该点就是一维极小点。内，而且函数值比前一点的小，则该点就是一维极小点。收敛条件收敛条件2 2）

35、设计点）设计点xk满足库恩满足库恩-塔克条件塔克条件l1）设计点）设计点xk及约束允差及约束允差满足满足l例题例题5-1：用可行方向法求约束优化问题：用可行方向法求约束优化问题解解:(1)取取初初始始点点，则则取取作作用用约约束束集集:Jk=1(2)寻找最优方向，即解一个以可行方向为设计变量寻找最优方向，即解一个以可行方向为设计变量的规划问题：的规划问题：1d1d2用图解法：用图解法：最优方向：最优方向：l(3)沿沿d0方向进行一维搜索方向进行一维搜索x1在约束边界在约束边界g3(x)=0上上:g3(x1)=0(4)第二次迭代，用梯度投影法确定可行方向第二次迭代，用梯度投影法确定可行方向,迭代

36、点迭代点x的目标函数负梯度的目标函数负梯度不不满满足足方方向向的的可可行行条条件件，将将投投影影到到约约束束边边界界g3(x)=0上。上。投影算子：投影算子：由上式可由上式可求得：求得：本次本次迭代方向迭代方向D为沿为沿约束边界约束边界g3(x)=0的的方向，求最佳步长方向，求最佳步长求得：求得：g5(x)=068x1x2g4(x)=0g3(x)=0g2(x)=0g1(x)=0 x0d0l（4）收敛判断：）收敛判断：由于由于Jk=3，5代入代入KT条件：条件：基本思想：通过构造罚函数把约束问题基本思想：通过构造罚函数把约束问题转化为一系列无约束最优化问题，进而用无转化为一系列无约束最优化问题，

37、进而用无约束最优化方法去求解，这类方法称为序列约束最优化方法去求解，这类方法称为序列无约束最小化方法。简称为无约束最小化方法。简称为SUMTSUMT法。法。5-5 5-5 惩罚函数法惩罚函数法 将将有有约约束束的的优优化化问问题题转转化化为为无无约约束束优优化化问问题题来来求求解解。前前提提：一一是是不不能能破破坏坏约约束束问问题题的的约约束束条条件件，二二是是使使它它归归结结到原约束问题的同一最优解上去。到原约束问题的同一最优解上去。构成一个新的目标函数，称为惩罚函数构成一个新的目标函数，称为惩罚函数l从而有从而有惩罚项必须具有以下极限性质：惩罚项必须具有以下极限性质：求求解解该该新新目目标

38、标函函数数的的无无约约束束极极小小值值，以以期期得得到到原原问问题题的的约约束束最最优优解解。按按一一定定的的法法则则改改变变罚罚因因子子r1和和r2的的值值，求求得得一一序序列列的的无无约约束束最最优优解解，不不断断地地逼逼近近原原约约束束优优化化问问题题的最优解。的最优解。根根据据约约束束形形式式和和定定义义的的泛泛函函及及罚罚因因子子的的递递推推方方法法等等不不同同，罚罚函函数数法法可可分分为为内内点点法法、外外点点法法和和混混合合罚罚函函数数法法三三种种。这这种种方方法法是是1968年年由由美美国国学学者者AVFiacco和和GPMcormick提提出出的的，把把不不等等式式约约束束引

39、引入入数数学学模模型型中中，为为求求多多维维有有约约束束非非线线性性规规划划问问题题开开创创了一个新局面。了一个新局面。1.内点法内点法内点法内点法这这种种方方法法将将新新目目标标函函数数定定义义于于可可行行域域内内，序序列列迭迭代代点点在在可可行行域域内内逐逐步步逼逼近近约约束束边边界界上上的的最最优优点点。内内点点法只能用来求解具有不等式约束的优化问题。法只能用来求解具有不等式约束的优化问题。对于只具有不等式约束的优化问题：对于只具有不等式约束的优化问题：转化后的惩罚函数形式为：转化后的惩罚函数形式为：或：或：rk是是惩惩罚罚因因子子，它它是是一一个个由由大大到到小小且且趋趋近近于于0的的

40、正正数数列列，即即:由由于于内内点点法法的的迭迭代代过过程程在在可可行行域域内内进进行行，“障障碍碍项项”的的作作用用是是阻阻止止迭迭代代点点越越出出可可行行域域。由由“障障碍碍项项”的的函函数数形形式式可可知知，当当迭迭代代点点靠靠近近某某一一约约束束边边界界时时，其其值值趋趋近近于于0，而而“障障碍碍项项”的的值值陡陡然然增增加加，并并趋趋近近于于无无穷穷大大，好好像像在在可可行行域域的的边边界界上上筑筑起起了了一一道道“高高墙墙”，使使迭代点始终不能越出可行域。显然，只有当惩罚因子迭代点始终不能越出可行域。显然，只有当惩罚因子 时，才能求得在约束边界上的最优解。时，才能求得在约束边界上的

41、最优解。罚罚因因子子的的作作用用是是：由由于于内内点点法法只只能能在在可可行行域域内内迭迭代代，而而最最优优解解很很可可能能在在可可行行域域内内靠靠近近边边界界处处或或就就在在边边界界上上，此此时时尽尽管管泛泛函函的的值值很很大大，但但罚罚因因子子是是不不断断递递减减的的正正值值，经经多多次次迭迭代代，接接近近最最优优解解时时，惩惩罚项已是很小的正值。罚项已是很小的正值。例例5-2用内点法求用内点法求的约束最优解。的约束最优解。解解:用内点法求解该问题时，首先构造内点惩罚函用内点法求解该问题时，首先构造内点惩罚函数数:用解析法求函数的极小值，运用极值条件：用解析法求函数的极小值，运用极值条件：

42、联立求解得：联立求解得：时不满足约束条件时不满足约束条件应舍去应舍去。无约束极值点为无约束极值点为当当l1）初始点初始点x0的选取的选取 使使用用内内点点法法时时，初初始始点点应应选选择择一一个个离离约约束束边边界界较较远远的的可可行行点点。如如太太靠靠近近某某一一约约束束边边界界，构构造造的的惩惩罚罚函函数数可可能能由由于于障障碍碍项项的的值值很很大大而而变变得得畸畸形形，使使求求解解无约束优化问题发生困难无约束优化问题发生困难.2）惩罚因子初值惩罚因子初值r0的选取的选取 惩惩罚罚因因子子的的初初值值应应适适当当，否否则则会会影影响响迭迭代代计计算算的的正正常常进进行行。一一般般而而言言，

43、太太大大，将将增增加加迭迭代代次次数数；太太小小，会会使使惩惩罚罚函函数数的的性性态态变变坏坏，甚甚至至难难以以收收敛敛到到极极值值点点。无无一一般般性性的的有有效效方方法法。对对于于不不同同的的问问题题，都都要经过多次试算，才能决定一个适当要经过多次试算，才能决定一个适当r03)惩罚因子的缩减系数惩罚因子的缩减系数c的选取的选取 在在构构造造序序列列惩惩罚罚函函数数时时，惩惩罚罚因因子子r是是一一个个逐逐次次递递减到减到0的数列，相邻两次迭代的惩罚因子的关系为的数列，相邻两次迭代的惩罚因子的关系为:式式中中的的c称称为为惩惩罚罚因因子子的的缩缩减减系系数数，c为为小小于于1的的正正数数。一一

44、般般的的看看法法是是，c值值的的大大小小在在迭迭代代过过程程中中不不起起决决定定性性作作用用，通常的取值范围在通常的取值范围在0.10.7之间。之间。4)收敛条件收敛条件算法步骤：算法步骤：算法步骤：算法步骤：1）选择可行域内初始点）选择可行域内初始点X(0);2）选取初始罚因子）选取初始罚因子r(0)与罚因子降低系数与罚因子降低系数c，并置，并置K0；3）求）求min(x(K),r(K)解出最优点解出最优点xK*；4）当）当K=0转步骤转步骤5），否则转步骤），否则转步骤6）；）；5）KK+1，r(K+1)r(K)，xK+10 xK*，并转步骤，并转步骤3）；）；6）按终止准则判别，若满足转

45、步骤）按终止准则判别，若满足转步骤7），否则转步骤），否则转步骤5）；）；7）输出最优解（）输出最优解（X*，F*），停止计算），停止计算。2.外点法外点法l 外点法是从可行域的外部构造一个点序列去逼近外点法是从可行域的外部构造一个点序列去逼近原约束问题的最优解。外点法可以用来求解含不等式和原约束问题的最优解。外点法可以用来求解含不等式和等式约束的优化问题。等式约束的优化问题。外点惩罚函数的形式为：外点惩罚函数的形式为：r是惩罚因子是惩罚因子,外外点点法法的的迭迭代代过过程程在在可可行行域域之之外外进进行行，惩惩罚罚项项的的作作用用是是迫迫使使迭迭代代点点逼逼近近约约束束边边界界或或等等式式约

46、约束束曲曲面面。由由惩惩罚罚项项的形式可知，当迭代点的形式可知，当迭代点x不可行时，惩罚项的值大于不可行时，惩罚项的值大于0。l例例5-3用外点法求解下列有约束优化问题用外点法求解下列有约束优化问题解：惩罚函数为：解：惩罚函数为：对上式求偏导，得对上式求偏导，得无约束目标函数极小化问题的最优解系列为：无约束目标函数极小化问题的最优解系列为：当惩罚因子渐增时，由下表可看出收敛情况。当惩罚因子渐增时，由下表可看出收敛情况。r0.01-0.80975-50.00000-24.9650-49.99770.1-0.45969-5.00000-2.2344-4.947410.23607-0.500000.

47、96310.1295100.83216-0.050002.30682.000110000.99800-0.000502.66242.6582108/38/3内点法和外点法的简单比较内点法和外点法的简单比较内点法的特点：内点法的特点：（1）始点必须为严格内点）始点必须为严格内点（2）不适于具有等式约束的数学模型）不适于具有等式约束的数学模型（3）迭代过程中各个点均为可行设计方案）迭代过程中各个点均为可行设计方案（4）一般收敛较慢）一般收敛较慢（5）初始罚因子要选择得当）初始罚因子要选择得当（6）罚因子为递减，递减率）罚因子为递减，递减率c有有0c13.混合法混合法l 混合法是用内点法处理不等式约

48、束，用外点法处混合法是用内点法处理不等式约束，用外点法处理等式约束。可以用来求解含不等式和等式约束的优化理等式约束。可以用来求解含不等式和等式约束的优化问题。问题。混合惩罚函数的形式为：混合惩罚函数的形式为：r是惩罚因子是惩罚因子,混混合合法法具具有有内内点点法法的的特特点点，迭迭代代过过程程在在可可行行域域之之内内进行，参数的选择同内点法。进行，参数的选择同内点法。惩罚函数法原理简单，算法易行，且分惩罚函数法原理简单，算法易行，且分内点法、外点法和混合法三种，各有特点，内点法、外点法和混合法三种，各有特点，适用范围广。需要和有效的无约束优化方法适用范围广。需要和有效的无约束优化方法结合使用。

49、因此该方法也是应用较多的有约结合使用。因此该方法也是应用较多的有约束优化方法。束优化方法。5-6 5-6 序列二次规划法序列二次规划法l 序列二次规划法的基本原理是将原问题转化为一序列二次规划法的基本原理是将原问题转化为一系列二次规划子问题。系列二次规划子问题。对于对于 相对应的拉格朗日函数为：相对应的拉格朗日函数为：在在xk点作泰勒展开，取二次近似表达式点作泰勒展开，取二次近似表达式令令,拉格朗日函数的一阶导数为拉格朗日函数的一阶导数为Hk用用变尺度矩阵变尺度矩阵Bk来代替来代替 将将等等式式约约束束 函函数数在在xk作作泰泰勒勒展展开开，取取线线性近似式性近似式:构成二次规划子问题构成二次

50、规划子问题 求求解解上上述述二二次次规规划划子子问问题题，得得到到的的d就就是是搜搜索索方方向向。沿沿搜搜索索方方向向进进行行一一维维搜搜索索确确定定步步长长，最最终终得得到到原原问问题题的的最最优解。优解。对具有不等式约束的非线性规划问题：对具有不等式约束的非线性规划问题：构成二次规划子问题为构成二次规划子问题为:求求解解时时，在在每每次次迭迭代代中中应应对对不不等等式式约约束束进进行行判判断断，保保留留其其中中的的起起作作用用约约束束，除除掉掉不不起起作作用用的的约约束束，将将起起作作用用的的约约束束纳纳入入等等式式约约束束中中。这这样样，其其中中不不等等式式约约束束的的子子问题和只具有等