所有分类约束优化方法.pptx
5-15-1约束最优解及其一阶必要条件约束最优解及其一阶必要条件机械优化设计中的问题，大多数属于约束优化设计问题，其数学模型为第1页/共113页实际工程中大部分问题的变量取值都有一定的限制，也就是属于有约束条件的寻优问题。与无约束问题不同，约束问题目标函数的最小值必须是满足约束条件，即是由约束条件所限定的可行域内的最小值。只要由约束条件所决定的可行域是一个凸集，目标函数是凸函数，其约束最优解就是全域最优解。否则，将由于所选择的初始点的不同，而探索到不同的局部最优解上。在这种情况下，探索结果经常与初始点的选择有关。(为了能得到全局最优解，在探索过程中最好能改变初始点，有时甚至要改换几次。)第2页/共113页（1）直接法直接解法通常适用于仅含不等式约束的问题。思路:是在m个不等式约束条件所确定的可行域内，选择一个初始点，然后决定可行搜索方向sk且以适当的步长k，进行搜索，得到一个使目标函数值下降的可行的新点，即完成一次迭代。再以新点为起点，重复上述搜索过程，直至满足收敛条件。根据求解方式的不同，约束优化设计问题可分为根据求解方式的不同，约束优化设计问题可分为:直接解法、间接解法。直接解法、间接解法。第3页/共113页直接法主要包括：随机方向法、复合形法和可行直接法主要包括：随机方向法、复合形法和可行方向法。方向法。其迭代过程中，每一次的新迭代点X(K+1)都要经过可行性和适用性条件的检验。可行性条件是指新迭代点X(K+1)必须在可行域内，即满足适用性条件是指新迭代点X(K+1)的目标函数值较前一点是下降的，即满足第4页/共113页特点：在可行域内进行；若可行域是凸集，目标函数是定义在凸集上的凸函数，则收敛到全局最优点；否则，结果与初始点有关。凸集凸集非凸集非凸集第5页/共113页(2）间接法）间接法目的：目的：将有约束优化问题转化为无约束优化问题将有约束优化问题转化为无约束优化问题方方法法：以以原原目目标标函函数数和和加加权权的的约约束束函函数数共共同同构构成成一一个个新新的的目目标标函函数数(x,r1,r2)，成成为为无无约约束束优优化化问问题题。通通过过不不断断调调整整加加权权因因子子，产产生生一一系系列列函函数数的的极极小小点点序序列列xk*(r1k,r2k)k=0,1,2，逐逐渐渐收收敛敛到到原原目目标标函数的约束最优解。函数的约束最优解。间间接接法法主主要要包包括括：内内点点罚罚函函数数法法、外外点点罚罚函函数数法法和和混合罚函数法、扩展内惩罚函数法。混合罚函数法、扩展内惩罚函数法。第6页/共113页 新目标函数：新目标函数：其中：其中：惩罚项：惩罚项：加权因子加权因子(惩罚因子惩罚因子)：r1(k),r2(k)无约束优化问题：无约束优化问题：函数的极小点序列函数的极小点序列x(k)*(r1(k),r2(k)k=0,1,2其其收敛必须满足：收敛必须满足：第7页/共113页5-2 5-2 随机方向法随机方向法基本思想：基本思想：随机产生初始点随机产生初始点X(0)，随机产生搜索方向，随机产生搜索方向S(k)，进行搜索。但要确保：进行搜索。但要确保：新迭代点在可行域中；新迭代点在可行域中；目标函数值的下降性。目标函数值的下降性。随机方向法，是约束最优化问题的一种常用的随机方向法，是约束最优化问题的一种常用的直接求解方法。直接求解方法。第8页/共113页一、随机方向的构成在计算机语言所适用的函数库中，都有一种随机函数，可以产生01之间的均匀分布的随机数，利用产生的随机数构成随机方向。若利用在（0，1）之间产生的随机数，i=1，2，n，构成单位矢量S，方法如下。把随机数，转化为另一区间（-1，1）之间的随机数然后由随机数yi构成以下随机方向由于随机数由于随机数yi在区间（在区间（-1，1）内产生，所构成的随机方向）内产生，所构成的随机方向矢量矢量S一定是在超球面空间里均匀分布且模等于一定是在超球面空间里均匀分布且模等于1的单位矢量。的单位矢量。第9页/共113页如图5-1所示的二维问题。首先选定可行初始点X(0)，利用随机函数构成随机方向S（1），按给定的初始步长h=h0沿S（1）方向取得试探点检查点X(1)的适用性和可行性，即检查二、随机方向法随机方向法图图5-1随机方向法随机方向法第10页/共113页直至达到某迭代点不能同时满足适用性和可行性条件时停止，退回到前一点作为该方向搜索中的最终成功点，记作X(1)。进而，将X(1)作为新的始点X(0)X(1)，再产生另一随机方向S(2)，重复以上过程，得到沿S(2)方向的最终成功点X(2)。如此循环，点列X(1)、X(2)、必将逼近于约束最优点X*。若两者均满足，X作为新的起点，继续按上述迭代式在S(1)方向上取得新点。重复上述步骤，迭代点可沿S(1)方向前进。第11页/共113页(1)若在某个换向转折点处（如图中的X(1)点），沿某搜索方向的试探点目标函数值增大或越出可行域，则弃去该方向，再产生另一随机方向作试探。试探成功就前进，试探失败再重新产生新的随机方向。(2)当在某个转折点处沿当在某个转折点处沿m个（预先限定的次数）个（预先限定的次数）随机方向试探均失败，如图中点随机方向试探均失败，如图中点X(2)，则说明以此，则说明以此点为中心，点为中心，h0为半径的圆周上各点都不是适用、为半径的圆周上各点都不是适用、可行的。此时可将初始步长可行的。此时可将初始步长h0缩半后继续试探缩半后继续试探,直直到到f(k+1)f(k)，且沿，且沿m个随机方向都试探失败时，则个随机方向都试探失败时，则最后一个成功点（如图中的最后一个成功点（如图中的X(3)点）就是到达预定点）就是到达预定精度要求的约束最优点，迭代即可结束。精度要求的约束最优点，迭代即可结束。第12页/共113页(3)m是预先规定在某转折点处产生随机方向所允许的最大数目。对于性态不好的目标函数或可行域有狭长弯道的问题，m应取较大的值，以提高解题的成功率。约束随机方向法的搜索方向比较灵活，当预定的随机方向限定数m足够大时，无“病态”问题出现，一般都能求出最优点。第13页/共113页入口XX(0)，aa0F0F(X)K=1 j0在（-1，1）区间产生随机数yiXX(0)+aSYgu(X)0FF(X)Fm?ae?KK+1X*X F*F出口a0.5aYYYYNNNNN图5-2随机方向法程序框图第14页/共113页三举例例：用约束随机方向法求解 解：人工选取一初始点X0=5，5T，初始点在可行域内。相应的目标函数值为F(X0)=50。第一次迭代1)产生两个伪随机数，求出第一个随机方向。生成两个伪随机数第15页/共113页由此得第一个随机方向为：2)求第一个迭代点第一个迭代点表达式为：式中a为步长。第16页/共113页 将X1的表达式代入目标函数中，进行一维搜索，令目标函数对步长a的一阶导数为0，即可求出沿e1方向的最优步长。第一个迭代点为：第17页/共113页3）检验X1点是否满足约束条件 g(X1)=2*4.2+5.6=1 4 1 2，X1满足约束条件，是可行点。相应的目标函数值为:第二次迭代以X1为初始点，继续使用e1方向直到不满足可行性和适用性条件，再重新生成随机搜索方向e2。（以下过程略）目标函数值下降目标函数值下降第18页/共113页 随机方向法方法评价：优点：1对目标函数无性态要求；2收敛快（当随机方向限定数m 足够大时）；3不受维数影响，维数愈高，愈体现优点。缺点：1对于严重非线性函数，只能得近似解；2当m不够大时，解的近似程度大；3对于非凸函数，有可能收敛于局部解。第19页/共113页 复复合合形形法法是是求求解解约约束束非非线线性性最最优优化化问问题题的的一一种种重重要要的的直直接接方方法法。不不需需计计算算目目标标函函数数的的梯梯度度，而而是是靠靠选选取取复复合合形形的的顶顶点点井井比比较较各各顶顶点点处处目目标标函函数数值值的的大大小小，来来寻寻找找下下一一步步的的探探索索方方向向的的。在在用用于于求求解解约约束束问问题题的的复复合合形形法法中中，复复合合形形各各顶顶点点的的选选择择和和替替换换，不不仅仅要要满满足足目目标标函函数值的下降，还应当满足所有的约束条件。数值的下降，还应当满足所有的约束条件。5-3 5-3 5-3 5-3 复合形法复合形法第20页/共113页 比较复合形各顶点目标函数值的大小，去掉目标函数值最大的顶点(称最坏点)，以坏点以外其余各点的形心为映射中心，用坏点的映射点替换该点，构成新的复合形顶点。一、复合形法基本思想:在n维空间中，由n+1k2n个点组成的多（边）面体称为复合形。以新的复合形顶点,代替原复合形中的最坏点，组成新的复合形，以不断的迭代，使新复合形逐渐逼近最优点。第21页/共113页例如：设有一约束优化问题的数学模型是该目标函数的等值线和可行域的几何图形如图5-3所示。用复合形法求该问题的约束最优解的过程如下:第22页/共113页第23页/共113页令：X(R)=X(S)+(X(S)-X(H)称X(R)为映射点，为映射系数，通常取=1.3，可根据实际情况进行缩减。取次好点和好点连线的中点为X(S)。一般情况下，映射点的函数值比坏点的函数值要小，即F(X(R)F(X(H)。若满足可行域，则用X(R)代替X(H)构成新的复合形。如此反复迭代直到找到最优解。在可行域内任选三个初始点X(1)、X(2)、X(3)，连接这三点形成一个三角形，此三角形称为初始复合形。计算各个顶点函数值F(X(1)、F(X(2)、F(X(3)，找出最大值，记为坏点X(H)。最小值，记为最好点X(L)。在次好点和好点连线与坏点反向一侧的各点应具有较小的目标值。第24页/共113页二、初始复合形的构成复合形的顶点Kn+1个。对于维数较低的优化问题，由于顶点数目较少，可试凑几个可行点作为复合形的顶点。对于维数较高的问题，采用随机方法，先产生K个随机点，然后再把非可行点逐一调入可行域内。最终使K个随机点都成为可行点而构成初始复合形。复合形的产生可以：（1）人工选择初始复合形（2）随机产生初始复合形第25页/共113页xi=ai+i(bi-ai)i=1,2,.,n用这n个随机数xi作为坐标的点X就是一个随机点。这第一个点记作X(1)。同样，产生其它的随机点X(2)、X(3)、X(K)。1.产生K个随机点 根据随机数产生的标准函数，可以在（0，1）开区间内产生均匀分布的随机数i。利用该随机数可产生变量xi在给定界限aixibi内的随机数因每产生一个随机点，需要n个随机数，因此，产生k个随机点总共需要连续发生Kn个随机数。第26页/共113页2、将非可行点调入可行域用上述方法产生的K个随机点，并不一定都是可行的。但是，只要它们中间有一个点在可行域内，就可以用一定的方法将非可行点逐一调入可行域。将产生的K个随机点进行判断是否在可行域内，重新排列，将可行点依次排在前面，如有q个顶点X(1)、X(2)、X(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)第27页/共113页这个新点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个点就构成了初始复合形。第28页/共113页三、复合形法的迭代步骤（1）构造初始复合形；（2）计算各顶点的函数值F(X(j)，j=1,2,.,K。选出好点X(L)和坏点X(H)。（3）计算坏点外的其余各顶点的中心点X(s)。（4）计算映射点X(R):检查X(R)是否在可行域内。若X(R)为非可行点，将映射系数减半后再按上式改变映射点，直到X(R)进入可行域内为止。第29页/共113页（5）构造新的复合形计算映射点的函数值F(X(R)，并与坏点的函数值F(X(H)比较，可能存在两种情况：1）映射点优于坏点:F(X(R)F(X(H)在此情况，用X(R)代替X(H)，构成新的复合形。2）映射点次于坏点:F(X(R)F(X(H)这种情况由于映射点过远引起的，减半映射系数，若有F(X(R)F(X(H)，这又转化为第一种情况。若经过多次的映射系数减半，仍不能使映射点优于坏点，则说明该映射方向不利，此时，应改变映射方向，取对次坏点的映射。再转回本步骤的开始处，直到构成新的复合形。第30页/共113页(6)判断终止条件1)各顶点与好点函数值之差的均方根值小于误差限，即2）各顶点与好点的函数值之差的平方和小于误差限，即3）各顶点与好点函数值差的绝对值之和小于误差限，即如果不满足终止迭代条件，则返回步骤2继续进行下一次迭代；否则，可将最后复合形的好点X(L)及其函数值F(X(L)作为最优解输出第31页/共113页例：用复合形法求解约束优化问题，迭代精度为0.01。(课堂练习)解：n=2,取复合形顶点数k=2n=4。1.人为给出4个复合形顶点。经检验4个顶点均在可行域内。第32页/共113页2进行迭代，获得新的复合形。求4个点的目标函数值：知.计算除坏点外所有顶点的中心XC：经检验XC在可行域内。第33页/共113页求XH的映射点XR，取映射系数为1.3：经检验，映射点XR在可行域内。因F(XR)=5.10920，用解析法求的无约束极小点，即：由上面可知，当逐渐增大由上面可知，当逐渐增大r(k)值，直至趋近于无穷大时，值，直至趋近于无穷大时，X*(r(k)逼近原约束问题的最优解。逼近原约束问题的最优解。第85页/共113页x2x1第86页/共113页例5-4：用外点法求解 st.的最优解解构成惩罚函数 第87页/共113页得到约束极值点，即：得：无约束极值点沿直线从约束区域外向最优点收敛。第88页/共113页第89页/共113页用外惩罚函数法解等式约束优化问题设有二维等式约束优化问题函数图形见图。函数图形见图。x1+x2-10=0直线是该约束优化问题的可行直线是该约束优化问题的可行域，这条直线以外的整个平面为非可行域。目标函数的等值域，这条直线以外的整个平面为非可行域。目标函数的等值线与直线线与直线x1+x2-10=0的切点是该问题的最优点。的切点是该问题的最优点。按外点法构造惩罚函数按外点法构造惩罚函数第90页/共113页第91页/共113页该惩罚函数是由原目标函数及惩罚项组成。在可行域上，惩罚项的值为零，惩罚函数的值与原目标函数的值相同；而在非可行域上惩罚项的值恒为正，惩罚函数大于原目标函数，即在可行域外惩罚项起到了惩罚作用。惩罚因子r(K)越大，则惩罚的作用越大。随着惩罚因子随着惩罚因子r(K)的增大过程，求出惩罚函数的无约的增大过程，求出惩罚函数的无约束最优点列束最优点列，在，在的过程中，则点的过程中，则点列将趋于原约束优化的最优解列将趋于原约束优化的最优解X*。第92页/共113页此例可以推广到一般具有等式约束优化的问题构成外惩罚函数如下式中，惩罚因子式中，惩罚因子r(K)，规定为正，且是递增数列，即，规定为正，且是递增数列，即r(0)r(1)r(2)1。罚函数解等式约束优化问题的求解过程及基本参数的罚函数解等式约束优化问题的求解过程及基本参数的选择与前述用外点法解不等式约束优化问题相同。选择与前述用外点法解不等式约束优化问题相同。第94页/共113页外点法特点外点法特点:外惩罚函数法既可解不等式约束优化问题，外惩罚函数法既可解不等式约束优化问题，也可解等式约束优化问题，这是其重要优点；另也可解等式约束优化问题，这是其重要优点；另外一个优点是其初始点外一个优点是其初始点X(0)可以任选，即在可行可以任选，即在可行域中或非可行域均可。其确定是系列无约束最优域中或非可行域均可。其确定是系列无约束最优点是非可行点，对于工程设计一般是不可取的。点是非可行点，对于工程设计一般是不可取的。为使最终的迭代点落入可行域，必须设置约束容为使最终的迭代点落入可行域，必须设置约束容差带。差带。第95页/共113页课堂练习例5-5用外点法求解下列有约束优化问题第96页/共113页解：惩罚函数为：解：惩罚函数为：对上式求偏导，得对上式求偏导，得可行域内可行域外第97页/共113页无约束目标函数极小化问题的最优解系列为：无约束目标函数极小化问题的最优解系列为：当惩罚因子渐增时，由下表可看出收敛情况。当惩罚因子渐增时，由下表可看出收敛情况。第98页/共113页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.6582108/38/3第99页/共113页第100页/共113页第101页/共113页内点法和外点法的简单比较内点法的特点：（1）始点必须为严格内点（2）不适于具有等式约束的数学模型（3）迭代过程中各个点均为可行设计方案（4）一般收敛较慢（5）初始罚因子要选择得当（6）罚因子为递减，递减率c有0c1第102页/共113页5-7 5-7 混合惩罚函数法混合惩罚函数法用惩罚函数法解含有不等式约束和等式约束的一般约用惩罚函数法解含有不等式约束和等式约束的一般约束优化问题的方法称为混合惩罚函数法，简称混合法。束优化问题的方法称为混合惩罚函数法，简称混合法。一、混合惩罚函数法的形式及其特点一、混合惩罚函数法的形式及其特点一般约束优化问题的数学模型一般约束优化问题的数学模型由前述可知，惩罚函数是由原目标函数和惩罚项组成的。由前述可知，惩罚函数是由原目标函数和惩罚项组成的。由于该问题的约束条件包含不等式约束与等式约束两部分，由于该问题的约束条件包含不等式约束与等式约束两部分，因此，惩罚项也由对应的两部分组成。对于等式约束的部分因此，惩罚项也由对应的两部分组成。对于等式约束的部分只有外惩罚函数一种形式，而对于不等式约束部分可以用内只有外惩罚函数一种形式，而对于不等式约束部分可以用内惩罚函数或外惩罚函数的形式。按照对不等式约束处理的方惩罚函数或外惩罚函数的形式。按照对不等式约束处理的方法不同，混合惩罚函数法具有两种不同的形式。法不同，混合惩罚函数法具有两种不同的形式。第103页/共113页1、内点形式的混合法不等式约束部分按照内点法形式处理的混合法，其惩罚函数的形式为初始点必须是满足诸不等式约束条件的可行点初始点必须是满足诸不等式约束条件的可行点x(o),初始初始罚因子罚因子r(0)、降低系数、降低系数c的选取均应参照内点法。的选取均应参照内点法。2、外点形式的混合法不等式约束部分按外点法处理的混合法，其惩罚函数的形式为初始点可以在空间内任选，初始罚因子r(0)、递增系数c可以参照外点法选取。第104页/共113页3、对于设计点x,不满足的等式约束和不等式约束部分按照外点法处理，而对于x满足不等式约束用内点法形式处理，其惩罚函数的形式为初始点必须是满足诸不等式约束条件的可行点初始点必须是满足诸不等式约束条件的可行点x(o),初始罚初始罚因子因子r(0)、降低系数、降低系数c的选取均应参照内点法。的选取均应参照内点法。第105页/共113页二、算法步骤及流程图例5-4：设有二维一般约束优化问题，数学模型为解：目标函数的等值线和约束曲线见图所示，最优点解：目标函数的等值线和约束曲线见图所示，最优点X*既既要落在要落在gu(X)，u=14所包围的区域内，同时必须在等式所包围的区域内，同时必须在等式约束约束h(X)=0的直线上。的直线上。第106页/共113页第107页/共113页首先写出罚函数。用内点形式的混合法的罚函数为用外点形式的混合法的罚函数为将已知条件代入上式中，选取初始点X(0)，初始罚因子r(0)，递减系数c（对于内点形式的混合法）或递增系数c（对于外点形式的混合法）。选择无约束优化方法进行求解，即可获得其结果。第108页/共113页惩罚函数法原理简单，算法易行，且分内点法、外点法和混合法三种，各有特点，适用范围广。需要和有效的无约束优化方法结合使用。因此该方法也是应用较多的有约束优化方法。第109页/共113页5-8扩展内惩罚函数法（新）这种方法的实质是将惩罚函数在可行域内和可行域外，分别给出定义，这样一旦遇上非可行初始点，也能立即为极小化的程序所接受，自动为下一次求惩罚函数的极小化提供一个可行的初始点，这是一种比较成功的替换方法。二次扩展内惩罚函数 可行域内，内点法。可行域内，内点法。第110页/共113页G0转换点，一般取0.002或0.001约束裕量，将约束面放宽采用一维搜索H-1惩罚函数在Xk点的二阶导数逆矩阵。g0F(X)Xg(X)=X-1第111页/共113页g0F(X)Xg(X)=X-1第112页/共113页感谢您的观看！第113页/共113页
