《机械优化设计约束优化方法.ppt》由会员分享，可在线阅读，更多相关《机械优化设计约束优化方法.ppt（120页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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)
9、）f 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、此循循循循环环环环下下下下去去去去。当当当当迭迭迭迭代代代代的的的的步步步步长长长长已已已已经经经经很很很很小小小小时时时时，则则则则表表表表明明明明已已已已经经经经逼逼逼逼近近近近约约约约束束束束最最最最优优优优点点点点。达到计算精度要求时，即可结束迭代计算。达到计算精度要求时，即可结束迭代计算。达到计算精度要求时，即可结束迭代计算。达到计算精度要求时，即可结束迭代计算。图图约束随机方向探索法的基本原理约束随机方向探索法的基本原理1产生随机方向的方法产生随机方向的方法在在n维设计空间中维设计空间中在在-1，1区间内，产生区间内，产生n N个均匀分布的伪随机数个均匀分布的伪随机数计算计算2、产
11、生随机初始点、产生随机初始点利利用用n个个在在0，1内内均均匀匀分分布布的的伪伪随随机机数数和和边边界约束界约束产生随机点产生随机点X(0)复复复复合合合合形形形形法法法法是是是是求求求求解解解解约约约约束束束束非非非非线线线线性性性性最最最最优优优优化化化化问问问问题题题题的的的的一一一一种种种种重重重重要要要要的的的的直直直直接接接接方方方方法法法法。它它它它来来来来源源源源于于于于用用用用于于于于求求求求解解解解无无无无约约约约束束束束非非非非线线线线性性性性最最最最优优优优化化化化问问问问题题题题的的的的单单单单纯纯纯纯形形形形法法法法，实实实实际际际际上上上上是是是是单单单单纯纯纯纯
12、形形形形法法法法在在在在约约约约束束束束问问问问题题题题中中中中的发展。的发展。的发展。的发展。如如如如前前前前所所所所述述述述，在在在在求求求求解解解解无无无无约约约约束束束束问问问问题题题题的的的的单单单单纯纯纯纯形形形形法法法法中中中中，不不不不需需需需计计计计算算算算目目目目标标标标函函函函数数数数的的的的梯梯梯梯度度度度，而而而而是是是是靠靠靠靠选选选选取取取取单单单单纯纯纯纯形形形形的的的的顶顶顶顶点点点点并并并并比比比比较较较较各各各各顶顶顶顶点点点点处处处处目目目目标标标标函函函函数数数数值值值值的的的的大大大大小小小小，来来来来寻寻寻寻找找找找下下下下一一一一步步步步的的的的
13、探探探探索索索索方方方方向向向向的的的的。在在在在用用用用于于于于求求求求解解解解约约约约束束束束问问问问题题题题的的的的复复复复合合合合形形形形法法法法中中中中，复复复复合合合合形形形形各各各各顶顶顶顶点点点点的的的的选选选选择择择择和和和和替替替替换换换换，不不不不仅仅仅仅要要要要满满满满足足足足目目目目标标标标函函函函数数数数值值值值的的的的下下下下降，还应当满足所有的约束条件。降，还应当满足所有的约束条件。降，还应当满足所有的约束条件。降，还应当满足所有的约束条件。5-35-3 复合形法复合形法基基基基 本本本本 思思思思 想想想想：在在在在 可可可可 行行行行 域域域域 中中中中 选
14、选选选 取取取取 KK个个个个 设设设设 计计计计 点点点点 （n+1K2nn+1K2n）作作作作为为为为初初初初始始始始复复复复合合合合形形形形的的的的顶顶顶顶点点点点。比比比比较较较较各各各各顶顶顶顶点点点点目目目目标标标标函函函函数数数数值值值值的的的的大大大大小小小小，去去去去掉掉掉掉目目目目标标标标函函函函数数数数值值值值最最最最大大大大的的的的顶顶顶顶点点点点(称称称称最最最最坏坏坏坏点点点点)，以以以以坏坏坏坏点点点点以以以以外外外外其其其其余余余余各各各各点点点点的的的的中中中中心心心心为为为为映映映映射射射射中中中中心心心心，用用用用坏坏坏坏点点点点的映射点替换该点，构成新的
15、复合形顶点。的映射点替换该点，构成新的复合形顶点。的映射点替换该点，构成新的复合形顶点。的映射点替换该点，构成新的复合形顶点。反反反反复复复复迭迭迭迭代代代代计计计计算算算算，使使使使复复复复合合合合形形形形不不不不断断断断向向向向最最最最优优优优点点点点移移移移动动动动和和和和收收收收缩缩缩缩，直直直直至至至至收收收收缩缩缩缩到到到到复复复复合合合合形形形形的的的的顶顶顶顶点点点点与与与与形形形形心心心心非非非非常常常常接接接接近近近近，且且且且满满满满足迭代精度要求为止。足迭代精度要求为止。足迭代精度要求为止。足迭代精度要求为止。令：令：X(4)=X(0)+(X(0)-X(H)称称X(4)
16、为映射点，记为为映射点，记为X(R)，为映射系数，通常取为映射系数，通常取=1.3，可根据实际情况进行缩减。，可根据实际情况进行缩减。取次好点和好点连线的中点为取次好点和好点连线的中点为X(0)。一般情况下，映射点的函数值比坏点的函数值要一般情况下，映射点的函数值比坏点的函数值要小，即小，即F(X(R)F(X(H)。若满足可行域，则用。若满足可行域，则用X(R)代替代替X(H)构成新的复合形。如此反复迭代直到找到最优解。构成新的复合形。如此反复迭代直到找到最优解。在在可可行行域域内内任任选选三三个个初初始始点点X(1)、X(2)、X(3)，连连接接这这三三点点形形成成一一个个三三角角形形，此此
17、三三角角形形称称为为初初始始复复合合形形。计计算算各各个个顶顶点点函函数数值值F(X(1)、F(X(2)、F(X(3)，找找出出最最大大值值，记记为为坏坏点点X(H)。最最小小值值，记记为为最最好好点点X(L)。在在次次好好点点和和好好点连线与坏点反向一侧的各点应具有较小的目标值。点连线与坏点反向一侧的各点应具有较小的目标值。在在迭迭代代过过程程中中，按按映映射射系系数数=1.3得得到到的的映映射射点点，不不一一定定满满足足适适用用性性和和可可行行性性，如如出出现现此此情情况况，将将映映射射系系数数减半，减半，重新取得重新取得X(R)，使它满足适用性和可行性。使它满足适用性和可行性。一、初始复
18、合形的构成一、初始复合形的构成复合形的顶点复合形的顶点K通常取通常取n+1K2n个。对于维数较低个。对于维数较低的优化问题，由于顶点数目较少，可试凑几个可行点作的优化问题，由于顶点数目较少，可试凑几个可行点作为复合形的顶点。对于维数较高的问题，采用随机方法，为复合形的顶点。对于维数较高的问题，采用随机方法，先产生先产生K个随机点，然后再把非可行点逐一调入可行域内。个随机点，然后再把非可行点逐一调入可行域内。1、产生、产生K个随机点个随机点xi=ai+i(bi-ai)i=1,2,.,ni为（为（0，1）区间内产生的均匀分布的随机数，需要）区间内产生的均匀分布的随机数，需要n个个随机数产生一个点随
19、机数产生一个点X(1)。同样，产生其它的随机点。同样，产生其它的随机点X(2)、X(3)、X(K)。2、将非可行点调入可行域、将非可行点调入可行域将产生的将产生的K个随机点进行判断是否在可行域内，个随机点进行判断是否在可行域内，重新排列，将可行点依次排在前面，如有重新排列，将可行点依次排在前面，如有q个顶点个顶点X(1)、X(2)、X(q)是可行点，其它是可行点，其它K-q个为非可行点。个为非可行点。对对X(q+1)，将其调入可行域的步骤是：，将其调入可行域的步骤是：（1）计算）计算q个点集的中心个点集的中心X(s)；（2）将第）将第q+1点朝着点点朝着点X(s)的方向移动，按下式产的方向移动
20、，按下式产生新的生新的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)靠拢，最终使其成为可行点。靠拢，最终使其成为可行点。按按照照这这个个方方法法，同同样样使使X(q+2)、X(q+3)、X(K)都变为可行点，这都变为可行点，这K个点就构成了初始复合形。个点就构成了初始复合形。二、复合形法的迭代步骤二、复合形法的迭代步骤（1）构造初始复合形；）
21、构造初始复合形；（2）计算各顶点的函数值）计算各顶点的函数值F(X(j)，j=1,2,.,K。选出好。选出好点点X(L)和坏点和坏点X(H)。（3）计算坏点外的其余各顶点的中心点）计算坏点外的其余各顶点的中心点X(0)。（4）计算映射点）计算映射点X(R)检查检查X(R)是否在可行域内。若是否在可行域内。若X(R)为非可行点，将映为非可行点，将映射系数减半后再按上式改变映射点，直到射系数减半后再按上式改变映射点，直到X(R)进入可行域进入可行域内为止。内为止。（5）构造新的复合形）构造新的复合形计算映射点的函数值计算映射点的函数值F(X(R)，并与坏点的函数值，并与坏点的函数值F(X(H)比较
22、，可能存在两种情况：比较，可能存在两种情况：1）映射点优于坏点）映射点优于坏点F(X(R)F(X(H)在此情况，用在此情况，用X(R)代替代替X(H)，构成新的复合形。，构成新的复合形。若经过多次的映射系数减半，仍不能使映射点优于坏若经过多次的映射系数减半，仍不能使映射点优于坏点，则说明该映射方向不利，此时，应改变映射方向，点，则说明该映射方向不利，此时，应改变映射方向，取对次坏点取对次坏点的映射。的映射。再转回本步骤的开始处，直到构成新的复合形。再转回本步骤的开始处，直到构成新的复合形。2）映射点次于坏点）映射点次于坏点F(X(R)F(X(H)这这种种情情况况由由于于映映射射点点过过远远引引
23、起起的的，减减半半映映射射系系数数，若有若有F(X(R)0，使得使得则称则称d为为X(k)点的一个可行方向。点的一个可行方向。i.（1）X(k)为可行域中的一个内点，为可行域中的一个内点，X(k)的任何方向均为可行方向。的任何方向均为可行方向。ii.（2）X(k)为可行域中的一个边界点，设为可行域中的一个边界点，设X(k)在约束面在约束面gi(X)=0上上。i.（3）X(k)为可行域中的一个外点，为可行域中的一个外点，X(k)的不存在可行方向。的不存在可行方向。2可行下降方向可行下降方向定义定义设设d是是的一个可行方向，即的一个可行方向，即若对于上式中的若对于上式中的X(k)、X(k+1)存在
24、存在则称则称d为为X(k)点的一个可行下降方向。点的一个可行下降方向。i.（1）X(k)为可行域中的一个内点为可行域中的一个内点（2）X(k)点是点是可行域中若干约束面的交点可行域中若干约束面的交点设设X(k)点在约束面点在约束面gj(X)=0，j=1,2,J若若dK是是X(k)点的一个可行下降方向，则应有点的一个可行下降方向，则应有可行：可行：下降：下降：i.（3）X(k)为可行域中的一个外点，为可行域中的一个外点，X(k)的不存在可行下降方向。的不存在可行下降方向。线性规划的图解法线性规划的图解法lMinz=3x1+x2ls.t.x1+x26l-x1+2x28l2x1-x20lx10,x2
25、0可行域可行域目标函数等值线目标函数等值线最优解最优解64-860 x1x21、最优解若存在，很可能就是可行域的顶点；、最优解若存在，很可能就是可行域的顶点；2、必须寻找一种代数方法，来解决高维的情况。、必须寻找一种代数方法，来解决高维的情况。可行方向法对线性规划问题的启示可行方向法对线性规划问题的启示单纯形法单纯形法 基本思想：通过构造罚函数把约束问题基本思想：通过构造罚函数把约束问题转化为一系列无约束最优化问题，进而用无转化为一系列无约束最优化问题，进而用无约束最优化方法去求解，这类方法称为序列约束最优化方法去求解，这类方法称为序列无约束最小化方法。简称为无约束最小化方法。简称为SUMTS
26、UMT法。法。5-5 5-5 惩罚函数法惩罚函数法 将将有有约约束束的的优优化化问问题题转转化化为为无无约约束束优优化化问问题题来来求求解解。前前提提：一一是是不不能能破破坏坏约约束束问问题题的的约约束束条条件件，二二是是使使它它归归结结到原约束问题的同一最优解上去。到原约束问题的同一最优解上去。构成一个新的目标函数，称为惩罚函数构成一个新的目标函数，称为惩罚函数l从而有从而有惩罚项必须具有以下极限性质：惩罚项必须具有以下极限性质：求求解解该该新新目目标标函函数数的的无无约约束束极极小小值值，以以期期得得到到原原问问题题的的约约束束最最优优解解。按按一一定定的的法法则则改改变变罚罚因因子子r1
27、和和r2的的值值，求求得得一一序序列列的的无无约约束束最最优优解解，不不断断地地逼逼近近原原约约束束优优化化问问题题的最优解。的最优解。根根据据约约束束形形式式和和定定义义的的泛泛函函及及罚罚因因子子的的递递推推方方法法等等不不同同，罚罚函函数数法法可可分分为为内内点点法法、外外点点法法和和混混合合罚罚函函数数法法三三种种。这这种种方方法法是是1968年年由由美美国国学学者者AVFiacco和和GPMcormick提提出出的的，把把不不等等式式约约束束引引入入数数学学模模型型中中，为为求求多多维维有有约约束束非非线线性性规规划划问问题题开开创创了一个新局面。了一个新局面。1.内点法内点法内点法
28、内点法这这种种方方法法将将新新目目标标函函数数定定义义于于可可行行域域内内，序序列列迭迭代代点点在在可可行行域域内内逐逐步步逼逼近近约约束束边边界界上上的的最最优优点点。内内点点法只能用来求解具有不等式约束的优化问题。法只能用来求解具有不等式约束的优化问题。对于只具有不等式约束的优化问题：对于只具有不等式约束的优化问题：转化后的惩罚函数形式为：转化后的惩罚函数形式为：或：或：rk是是惩惩罚罚因因子子，它它是是一一个个由由大大到到小小且且趋趋近近于于0的的正正数数列列，即即:由由于于内内点点法法的的迭迭代代过过程程在在可可行行域域内内进进行行，“障障碍碍项项”的的作作用用是是阻阻止止迭迭代代点点
29、越越出出可可行行域域。由由“障障碍碍项项”的的函函数数形形式式可可知知，当当迭迭代代点点靠靠近近某某一一约约束束边边界界时时，其其值值趋趋近近于于0，而而“障障碍碍项项”的的值值陡陡然然增增加加，并并趋趋近近于于无无穷穷大大，好好像像在在可可行行域域的的边边界界上上筑筑起起了了一一道道“高高墙墙”，使使迭代点始终不能越出可行域。显然，只有当惩罚因子迭代点始终不能越出可行域。显然，只有当惩罚因子 时，才能求得在约束边界上的最优解。时，才能求得在约束边界上的最优解。罚罚因因子子的的作作用用是是：由由于于内内点点法法只只能能在在可可行行域域内内迭迭代代，而而最最优优解解很很可可能能在在可可行行域域内
30、内靠靠近近边边界界处处或或就就在在边边界界上上，此此时时尽尽管管泛泛函函的的值值很很大大，但但罚罚因因子子是是不不断断递递减减的的正正值值，经经多多次次迭迭代代，接接近近最最优优解解时时，惩惩罚项已是很小的正值。罚项已是很小的正值。例例5-2用内点法求用内点法求的约束最优解。的约束最优解。解解:用内点法求解该问题时，首先构造内点惩罚函用内点法求解该问题时，首先构造内点惩罚函数数:用解析法求函数的极小值，运用极值条件：用解析法求函数的极小值，运用极值条件：联立求解得：联立求解得：时不满足约束条件时不满足约束条件应舍去应舍去。无约束极值点为无约束极值点为当当l1）初始点初始点x0的选取的选取 使使
31、用用内内点点法法时时，初初始始点点应应选选择择一一个个离离约约束束边边界界较较远远的的可可行行点点。如如太太靠靠近近某某一一约约束束边边界界，构构造造的的惩惩罚罚函函数数可可能能由由于于障障碍碍项项的的值值很很大大而而变变得得畸畸形形，使使求求解解无约束优化问题发生困难无约束优化问题发生困难.2）惩罚因子初值惩罚因子初值r0的选取的选取 惩惩罚罚因因子子的的初初值值应应适适当当，否否则则会会影影响响迭迭代代计计算算的的正正常常进进行行。一一般般而而言言，太太大大，将将增增加加迭迭代代次次数数；太太小小，会会使使惩惩罚罚函函数数的的性性态态变变坏坏，甚甚至至难难以以收收敛敛到到极极值值点点。无无
32、一一般般性性的的有有效效方方法法。对对于于不不同同的的问问题题，都都要经过多次试算，才能决定一个适当要经过多次试算，才能决定一个适当r03)惩罚因子的缩减系数惩罚因子的缩减系数c的选取的选取 在在构构造造序序列列惩惩罚罚函函数数时时，惩惩罚罚因因子子r是是一一个个逐逐次次递递减到减到0的数列，相邻两次迭代的惩罚因子的关系为的数列，相邻两次迭代的惩罚因子的关系为:式式中中的的c称称为为惩惩罚罚因因子子的的缩缩减减系系数数，c为为小小于于1的的正正数数。一一般般的的看看法法是是，c值值的的大大小小在在迭迭代代过过程程中中不不起起决决定定性性作作用用，通常的取值范围在通常的取值范围在0.10.7之间
33、。之间。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）按终止准则判别，若满足转步骤）按终止准则判别，若满足转步骤7），否则转步骤），否则转步骤5）；）；7）输出最优解（）输出最优解（X*，F*），停止计算），停止计算。2
34、.外点法外点法l 外点法是从可行域的外部构造一个点序列去逼近外点法是从可行域的外部构造一个点序列去逼近原约束问题的最优解。外点法可以用来求解含不等式和原约束问题的最优解。外点法可以用来求解含不等式和等式约束的优化问题。等式约束的优化问题。外点惩罚函数的形式为：外点惩罚函数的形式为：r是惩罚因子是惩罚因子,外外点点法法的的迭迭代代过过程程在在可可行行域域之之外外进进行行，惩惩罚罚项项的的作作用用是是迫迫使使迭迭代代点点逼逼近近约约束束边边界界或或等等式式约约束束曲曲面面。由由惩惩罚罚项项的形式可知，当迭代点的形式可知，当迭代点x不可行时，惩罚项的值大于不可行时，惩罚项的值大于0。l例例5-3用外
35、点法求解下列有约束优化问题用外点法求解下列有约束优化问题解：惩罚函数为：解：惩罚函数为：对上式求偏导，得对上式求偏导，得无约束目标函数极小化问题的最优解系列为：无约束目标函数极小化问题的最优解系列为：当惩罚因子渐增时，由下表可看出收敛情况。当惩罚因子渐增时，由下表可看出收敛情况。r0.01-0.80975-50.00000-24.9650-49.99770.1-0.45969-5.00000-2.2344-4.947410.23607-0.500000.96310.1295100.83216-0.050002.30682.000110000.99800-0.000502.66242.65821
36、08/38/3用内、外点法不同用内、外点法不同内点法和外点法的简单比较内点法和外点法的简单比较内点法的特点：内点法的特点：（1）始点必须为严格内点）始点必须为严格内点（2）不适于具有等式约束的数学模型）不适于具有等式约束的数学模型（3）迭代过程中各个点均为可行设计方案）迭代过程中各个点均为可行设计方案（4）一般收敛较慢）一般收敛较慢（5）初始罚因子要选择得当）初始罚因子要选择得当（6）罚因子为递减，递减率）罚因子为递减，递减率c有有0c13.混合法混合法l 混合法是用内点法处理不等式约束，用外点法处混合法是用内点法处理不等式约束，用外点法处理等式约束。可以用来求解含不等式和等式约束的优化理等式
37、约束。可以用来求解含不等式和等式约束的优化问题。问题。混合惩罚函数的形式为：混合惩罚函数的形式为：r是惩罚因子是惩罚因子,混混合合法法具具有有内内点点法法的的特特点点，迭迭代代过过程程在在可可行行域域之之内内进行，参数的选择同内点法。进行，参数的选择同内点法。惩罚函数法原理简单，算法易行，且分惩罚函数法原理简单，算法易行，且分内点法、外点法和混合法三种，各有特点，内点法、外点法和混合法三种，各有特点，适用范围广。需要和有效的无约束优化方法适用范围广。需要和有效的无约束优化方法结合使用。因此该方法也是应用较多的有约结合使用。因此该方法也是应用较多的有约束优化方法。束优化方法。内点法内点法内点法内
38、点法或或 外点法外点法外点法外点法 罚因子罚因子 混合法混合法混合法混合法 罚因子罚因子罚因子罚因子惩罚函数的不同构造形式惩罚函数的不同构造形式5-6 5-6 序列二次规划法序列二次规划法l序列二次规划法的基本原理是将原问题转化为一系列序列二次规划法的基本原理是将原问题转化为一系列二次规划子问题。二次规划子问题。对于对于 相对应的拉格朗日函数为：相对应的拉格朗日函数为：在在xk点作泰勒展开，取二次近似表达式点作泰勒展开，取二次近似表达式令令,拉格朗日函数的一阶导数为拉格朗日函数的一阶导数为Hk用用变尺度矩阵变尺度矩阵Bk来代替来代替 将将等等式式约约束束 函函数数在在xk作作泰泰勒勒展展开开，
39、取取线线性近似式性近似式:构成二次规划子问题构成二次规划子问题 求求解解上上述述二二次次规规划划子子问问题题，得得到到的的d就就是是搜搜索索方方向向。沿沿搜搜索索方方向向进进行行一一维维搜搜索索确确定定步步长长，最最终终得得到到原问题的最优解。原问题的最优解。对具有不等式约束的非线性规划问题：对具有不等式约束的非线性规划问题：构成二次规划子问题为构成二次规划子问题为:由由于于序序列列二二次次规规划划算算法法中中采采用用了了变变尺尺度度方方法法构构造造HESSENHESSEN矩矩阵阵H H(k(k),故故该该方方法法又又称称约约束束变变尺尺度度法法。该该法法不不仅仅利利用用了了目目标标函函数数和
40、和约约束束函函数数的的一一阶阶导导数数信信息息，而而且且利利用用了了目目标标函函数数的的二二阶阶导导数数信信息息，因因而而其其收收敛敛速速度度快快、效效率率高，被认为是比较好的非线性约束优化算法。高，被认为是比较好的非线性约束优化算法。5-7其它方法其它方法（一）蒙特卡洛优化方法（介绍）（一）蒙特卡洛优化方法（介绍）对于约束优化问题，最理想的当然是得到严格意义对于约束优化问题，最理想的当然是得到严格意义上的真正全局最优解。然而，要做到这一点往往是不现实上的真正全局最优解。然而，要做到这一点往往是不现实的，有的问题（例如非凸的非线性规划问题）至今在理论的，有的问题（例如非凸的非线性规划问题）至今
41、在理论上还没有一种算法能保证得到全局最优解；有些问题（如上还没有一种算法能保证得到全局最优解；有些问题（如凸规划）虽然从理论上讲可以得全局最优解，但是在实际凸规划）虽然从理论上讲可以得全局最优解，但是在实际计算中，也只能逼近最优解，且计算量往往很大，在实际计算中，也只能逼近最优解，且计算量往往很大，在实际工作中，人们往往希望只用较少的计算量就找到有较大概工作中，人们往往希望只用较少的计算量就找到有较大概率保证的近似最优解，蒙特卡洛（率保证的近似最优解，蒙特卡洛（MonteCarlo）优化方）优化方法就是达到这个目的的一种较为有效的方法。法就是达到这个目的的一种较为有效的方法。一、原理与基本方法
42、一、原理与基本方法在对大量的研究对象进行调查分析时，有两种基在对大量的研究对象进行调查分析时，有两种基本方法，普查与随机抽样。本方法，普查与随机抽样。穷举法就是对所有研究对象进行普查，其优点是穷举法就是对所有研究对象进行普查，其优点是结论完全可靠，但工作量大，适用于规模较小的问结论完全可靠，但工作量大，适用于规模较小的问题。而当问题的规模很大时，通常应采用随机抽样，题。而当问题的规模很大时，通常应采用随机抽样，对随机抽取的样本点进行研究，从样本点的性质来对随机抽取的样本点进行研究，从样本点的性质来推断原问题全面的性质，这样处理的工作量相对较推断原问题全面的性质，这样处理的工作量相对较少，可操作
43、性强，只要随机抽样得当，结论的可靠少，可操作性强，只要随机抽样得当，结论的可靠性可以得到保证。性可以得到保证。蒙蒙特特卡卡洛洛优优化化方方法法就就是是根根据据随随机机抽抽样样原原理理，利利用用计计算算机机语语言言所所提提供供的的随随机机数数函函数数对对约约束束优优化化问问题题的的可可行行点点进进行行随随机机抽抽样样，经经过过对对样样本本点点的的目目标标值值过过滤滤比比较较，找找出出全全体体样样本本点点中中目目标标值值最最优优的的点点，并并将将该该点点视视作作原原问问题题的的最最优解的一个近似点。优解的一个近似点。随随机机抽抽样样的的可可信信程程度度取取决决于于样样本本点点数数量量的的大大小小。
44、样样本本点点越越多多，可可信信程程度度就就越越高高。因因此此，能能否否迅迅速速地地取取得得大大量量样本点就成了决定蒙特卡洛优化方法是否有效的关键。样本点就成了决定蒙特卡洛优化方法是否有效的关键。二、蒙特卡洛优化方法的基本步骤二、蒙特卡洛优化方法的基本步骤（1）预置）预置L为充分大的正数，确定选点个数为充分大的正数，确定选点个数M；（2）用随机数函数（或子程序）产生可行点）用随机数函数（或子程序）产生可行点X；（3）计算目标函数值）计算目标函数值F；（4）比较函数值：若）比较函数值：若FL，转（，转（6）；否则，转（）；否则，转（5）；）；（5）记录当前最优点的信息：）记录当前最优点的信息：L=
45、F，X*=X；（6）若若已已选选完完M个个可可行行点点，输输出出X*和和L；否否则则，转转（2），寻找下一个可行点。寻找下一个可行点。蒙蒙特特卡卡洛洛优优化化方方法法具具有有许许多多显显著著的的优优点点，除除了了程程序简单，计算量小之外，还有可能获得全局最优点。序简单，计算量小之外，还有可能获得全局最优点。蒙蒙特特卡卡洛洛优优化化方方法法除除了了可可以以独独立立寻寻求求最最优优解解外外，往往往往还还与与其其它它算算法法相相配配合合。许许多多算算法法对对初初始始点点都都有有不不同同的的要要求求。一一般般而而言言，初初始始点点离离极极小小点点越越近近（即即初初始始点点的的函函数数值值越越好好），则
46、则算算法法越越有有效效。这这时时，可可以以先先使使用用蒙蒙特特卡卡洛洛优优化化方方法法找找到到较较好好的的初初始始点点，然然后后再再改改用用其其它它优优化化方方法法。另另外外，还还有有的的算算法法（如如可可行行方方向向法法、内内点点法法）对对初初始始点点的的可可行行性性有有较较高高的的要要求求，当当问问题题约约束束条条件件很很复复杂杂时时，很很难难凭凭人人的的直直觉觉找找到到符符合合要要求求的的点点，这这时时，也也可可利利用蒙特卡洛优化方法迅速找到需要的初始点。用蒙特卡洛优化方法迅速找到需要的初始点。5-7 其它方法其它方法 （二）网格法（二）网格法l l1 1基本思想基本思想基本思想基本思想
47、l网格法是直接在设计变量的可网格法是直接在设计变量的可行域内，有规律地取一系列点，如行域内，有规律地取一系列点，如分布网格，取网格上下的结点，求分布网格，取网格上下的结点，求这些点的目标函数值，找出其中较这些点的目标函数值，找出其中较小的点，作为第一次优化点；然后小的点，作为第一次优化点；然后在第一次迭代优化点附近，取一定在第一次迭代优化点附近，取一定的范围，再细分网格，计算网格结的范围，再细分网格，计算网格结点的目标函数值，进行比较，找出点的目标函数值，进行比较，找出第二次迭代的优化点，这样一直迭第二次迭代的优化点，这样一直迭代下去，直到满足精度要求为止。代下去，直到满足精度要求为止。2 迭
48、代步骤迭代步骤l（1）在变量的可行域内分布网格，网格的间隔均匀分布；）在变量的可行域内分布网格，网格的间隔均匀分布；l（2）计算网格的结点；）计算网格的结点；l（3）逐点检查网格结点是否符合约束条件，对符合约束条）逐点检查网格结点是否符合约束条件，对符合约束条件的点，计算其目标函数值，然后进行比较，找出函数值最件的点，计算其目标函数值，然后进行比较，找出函数值最小的点，为本次迭代的优化点；小的点，为本次迭代的优化点；l（4）满足迭代终止精度指标，结束；）满足迭代终止精度指标，结束；l（5）如不满足精度指标，则在本次迭代优化点附近，取下）如不满足精度指标，则在本次迭代优化点附近，取下次迭代的变量
49、的上、下限。然后转到第一步，分布网格，重次迭代的变量的上、下限。然后转到第一步，分布网格，重新计算。新计算。优优化方法化方法类类型型特点特点适用范适用范围围（正交）网格法（正交）网格法直接方法直接方法算法算法简单简单，对对函数性函数性态态要求不高，可求得全局最要求不高，可求得全局最优优解，特解，特别别适用于具有离散适用于具有离散变变量的量的问题问题，对对于于连续变连续变量量应给应给出出个个变变量的区量的区间间，计计算量大算量大适用于适用于维维数不大于数不大于8 8，约约束个数束个数不太多（一般小于不太多（一般小于10101515）的的问题问题约约束随机方向法束随机方向法直接方法直接方法方法方法
50、简单简单，使用方便，使用方便，对对目目标标函数性函数性态态无特殊要求，一般无特殊要求，一般收收敛较敛较快，但快，但计计算精度算精度较较低，低，对严对严重非重非线线性性问题问题一般一般只能提供只能提供较较近似的最近似的最优优解解适用于中小型适用于中小型优优化化问题问题，不，不仅仅可求解可求解约约束束优优化化问题问题，也，也能求解无能求解无约约束束优优化化问题问题复合形法复合形法直接方法直接方法方法方法简单简单，对对目目标标函数和函数和约约函数性函数性态态无特殊要求，无特殊要求，应应用用较较广，有一定收广，有一定收敛敛精度，但收精度，但收敛敛速度一般速度一般较较慢，若用随慢，若用随机机适用于适用于