第六章约束优化方法课件

第六章约束优化方法约束优化方法概述随机方向法复合形法可行方向法惩罚函数法

教学要求：

1、掌握随机方向法。

2、掌握复合形法的原理。

3、掌握内点法和外点法的惩罚函数的构造原理及程序设计。第六章约束优化方法约束优化方法概述16.1约束优化方法概述

无约束优化方法是优化方法中最基本最核心的部分。在工程实际中，优化问题大都属于有约束的优化问题，即其设计变量的取值要受到一定的限制，用于求解约束优化问题最优解的方法称为约束优化方法。约束优化设计的数序模型为：

根据求解方式的不同，约束优化方法可以分为：直接解法和间接解法

6.1约束优化方法概述无约束优化方2

1、直接法

只能求解不等式约束优化问题的最优解。其根本做法是在约束条件所限制的可行域内直接求解目标函数的最优解。如：约束坐标轮换法、复合形法等。

其基本要点：选取初始点x0、确定可行搜索方向d及适当步长。

每次迭代计算均按以下基本迭代格式进行xk+1=xk+kdk(k=1,2,)可行搜索方向：当设计点沿该方向作微量移动时，目标函数值下降，且不越出可行域。

特点：1）求解在可行域内进行，当前设计点总比初始设计点好；2）若目标函数为凸函数，可行域为凸集，可保证获得全域最优解；3）要求可行域为有界的非空集，即在有界可行域内存在满足全部约束条件的点，且目标函数有定义。1、直接法

只能求解不等式约束优3

2、间接法

该方法可以求解等式约束优化问题和一般约束优化问题。其基本思想是将约束优化问题通过一定的方法进行改变，将约束优化问题转化为无约束优化问题，再采用无约束优化方法进行求解。如：惩罚函数法基本迭代过程，将约束优化问题转化成新的无约束目标函数式中为转化后的目标函数分别为约束函数gj(x),hk(x)经过加权处理后构成的某种形式的复合函数或泛函数‘

1，2为加权因子。

2、间接法

该方法可以求解等式约束优化问题和4例6.1求约束优化问题minf(x)=(x12)2+(x2–1)2s.t.h(x)=x1+2x2

2=0的最优解。解：该问题的最优解为x*=[1.60.2]T,f(x*)=0.8。由图6-3a可知，约束最优点x*为目标函数等值线与等式约束函数（直线）的交点。用间接法求解时，可取1=0.8，转换后的新目标函数为(x,2)=(x12)2+(x2–1)2+0.8(x1+2x2

2

)可以用解析法求min(x,2),令=0，得到/x1=2

(x12)+0.8=0/x2=2

(x12)+1.6=0求得的无约束最优解为x*=[1.60.2]T,(x*，2)=0.8。其结果与原约束最优解相同。例6.1求约束优化问题minf(x)=(x12)25特点：1）由于无约束优化方法的日趋成熟，使得间接解法有了可靠的基础；2）可以有效地处理具有等式约束的约束优化问题；3）存在的主要问题，选取加权因子较为困难。加权因子选取不当，会影响收敛速度和计算精度，甚至会导致计算失败。特点：66.2随机方向法

本方法是在可行域内利用随机产生的可行方向进行搜索的一种直接解法，用于求解这类约束优化设计问题。在可行域内选择一个初始点x0，利用随机数的概率特性，产生若干个随机方向，并从中找出一个能使目标函数值下降最快的随机方向作为可行搜索方向，记作d1。从初始点x0出发，沿方向d1按给定的初始步长取试探点x=x0+d1检查x点的适用性和可行性，即检查f(x)<f(x0),xD?若满足，则以x为新的起点，即x0x。继续按上面的迭代式在d1方向上获取新点。重复上述步骤，迭代点可沿d1方向前进，直至到达某迭代点不能同时满足适用性和可行性条件时为止，退到前一点作为改方向搜索中的最终成功点，记作x1.将x1作为新的始点x0x1，再产生另一随机方向d2,以步长0重复以上过程，直到沿d2方向得到最终成功点x3。如此循环，点列x1、x2、必将逼近约束极值点x*。6.2随机方向法本方法是在可行域内利用随机产生的7一、随机数的产生

首先令r1=235,r2=236,r3=237,取r=2657863(r为小于r1的正奇数），然后按一下步骤计算令r5r若r

r3,则rrr3若r

r2,则rrr2

若r

r1,则rrr1则q=r/r1q即为(0,1)区间内的伪随机数。利用q,容易求得任意区间(a,b)内的伪随机数，其计算公式为x=a+q(ba)（6-5）（6-4）

这部分内容为产生伪随机数的数学模型，可写成子程序。或者大家可以直接利用算法语言中自带的产生随机数的子程序。一、随机数的产生（6-5）（6-4）这部分内容为产生8二、初始点的选择

随机方向法的初始点x0必须是一个可行点，满足全部不等式约束条件。当约束条件较为复杂，用人工不易选择可行初始点时，可用计算机随机选择的方法来产生。其计算步骤如下：1）输入设计变量的下限值和上限值，即ai

xi

bi

(i=1,2,,n)2）在区间（0，1）内产生n个伪随机数qi(i=1,2,,n)3）计算随机点x的分量xi=ai+qi(biai)(i=1,2,,n)4)判别随机点x是否可行，若可行取x0x;否则转步骤2）重新计算。直到产生的随即点是可行点为止。（6-6）二、初始点的选择（6-6）9三、可行搜索方向的产生从k(k

n)个随机方向中，选取一个较好的方向。计算步骤为：1）在（-1，1）区间内产生伪随机数rij(i=1,2,,n;j=1,2,,k),rij=2qi

-1计算随机单位向量ej2)取一试验步长0，按下式计算k个随机点3）检验k个随机点xj(j=1,2,,k)是否为可行点，除去非可行点，计算余下的可行随机点的目标函数值，比较其大小，选出目标函数值最小的点xL.4)比较xL和x0两点的目标函数值，若f(xL)<f(x0),取xL和x0的连线方向作为可行搜索方向；若f(xL)f(x0),则将步长0缩小，转步骤1重新计算，直至f(xL)<f(x0)为止。如果0缩小到很小（例如106），仍然找不到一个xL,使f(xL)<f(x0),则说明x0是一个局部极小点，此时可更换初始点，转步骤1.（6-8）（6-7）三、可行搜索方向的产生（6-8）（6-7）10

产生可行搜索方向的条件可以概括为，当xL点满足则可行搜索方向为四、搜索方向的确定可行搜索方向d确定后，初始点移至xL点，从xL点出发沿d方向进行搜索，所用的步长一般按加速步长法来确定。所谓加速步长法是指依次迭代的步长按一定的比例递增的方法。各次迭代的步长按下式计算=式中为步长加速系数，可取为1.3；

为步长，初始步长取=0。

（6-9）（6-10）产生可行搜索方向的条件可以概括为，当xL点满足（611五、计算步骤1）选择一个可行的初始点x0;按式（6-7）产生k个n维随即单位向量ej(j=1,2,…,k);取试验步长0，按式（6-8）计算出k个随机点xj(j=1,2,…,k);在k个随机点中，找出满足式（6-9）的随机点xL,产生可行搜索方向d=xLx0.从初始点x0出发，沿可行搜索方向d以步长进行迭代计算，直到搜索到一个满足全部约束条件，且目标函数值不再下降的新点x.若收敛条件得到满足，停止迭代。约束最优解为。否则，令x0x转步骤2）。（6-12）五、计算步骤（6-12）12随机方向法的程序框图见图6-5。随机方向法的程序框图见图6-5。13例6-2求约束优化问题的最优解。解：用随机方向法程序，在计算机上运行，迭代13次，求得约束最优解：x*=[0.00273.0]T,f(x*)=3。计算机计算的结果摘录于表6-1，该问题的图解示于图6-6.例6-2求约束优化问题14（课外）例6-3如图所示为平面铰接四杆机构。各杆的长度分别为l1,l2,l3,l4;主动杆1的输入角为,相应于摇杆3在右极位（杆1与杆2伸直位置）时，主动杆1的初始位置角为0;从动杆的输出角为，初始位置角为0。试确定四杆机构的运动参数，使输出角=f(,l1,l2,l3,l4,,0)的函数关系，当曲柄从0位置转到m=0+90o时，最佳再现下面给定的函数关系已知l1=1,l4=5,其传动角允许在45o135o范围内变化。(1)（课外）例6-3如图所示为平面铰接四杆机构。各杆的长度分别15解：(1)数学模型的建立已经给定了两根杆长:l1=1,l4=5,且0和0不是独立的参数，因为

所以只剩下两个独立参数l2,l3。因此设计变量取复演预期函数的机构设计问题，可以按期望机构的输出函数与给定函数的均方根误差达到最小来建立目标函数，即或者由于和E均为输入角的连续函数，为了进行数值计算，可将[0,m]区间划分为30等分，将上式改写为梯形近似积分计算公式(2)(3)(4)解：(1)数学模型的建立(2)(3)(4)16式中j为当=j时机构的实际输出角；

Ej为复演预期函数当=j时的函数值，也是欲求机构的理论输出角。下标j为j=0,1,2,,30。Ej值按式（1）计算，j值可按下式计算：目标函数是一个凸函数，等值线如右图所示。(5)(6)(7)(8)(9)(5)(6)(7)(8)(9)17

由于要求四杆机构的杆1能做整周转动，且机构的最小传动角min45o、最大传动角min135o，所以根据四杆机构的曲柄存在条件，得不等式约束条件为根据传动角的条件有cosmincos45o,cosmax135o，因所以得到不等式约束条件为在上面7个约束条件中，式(10)-(14)的约束边界为直线，式(17)和(18)的约束边界为椭圆。在设计空间内组成一个可行设计区域，即阴影线所包围的部分。(10)(11)(12)(13)(14)(15)(16)(17)(18)由于要求四杆机构的杆1能做整周转动，且机构的最小传18(2)优化设计结果

上述设计问题是属于二维的非线性规划问题，有7个不等式约束条件，其中主要的是g6(x)0和g7(x)0。现在采用随机方向法求解。取初始点x10=4.5,x20=4,搜索步长0=0.1,目标函数值的收敛精度1=0.0001，步长的收敛精度2=0.0001，经过9次迭代，其最优解为x1*=l2=4.1286,x2*=l3=2.3325,f(x*)=0.0156。

(2)优化设计结果19

最终设计方案的参数为l1=1,l2=4.1286,l3=2.3325,l4=5,0=26o28,0=108o08,机构图如下图左所示，机构实际输出角和复演预期函数E的关系和误差见下图右。最终设计方案的参数为l1=1,l2=4.1206.3复合形法复合形法是求解约束优化问题的一种重要的直接解法。一、复合形法的基本思想

其基本思路(见图6-7)是在可行域内构造一个具有k个顶点的初始复合形。对该复合形各顶点的目标函数值进行比较，去掉目标函数值最大的顶点（称最坏点），然后按一定法则求出目标函数值下降的可行的新点,并用此点代替最坏点，构成新的复合形，复合形就向最优点移动一步，直至逼近最优点。6.3复合形法复合形法是求解约束优21二、初始复合形的构成

要构成初始复合形，实际上就是确定k个可行点作为复合形的顶点，顶点数目一般在n+1k2n范围内。对于维数较低的优化问题，因顶点数目较少，可以由设计者自行凑出可行点作为复合形顶点。但对于维数较高的优化问题，这种方法常常很困难。

为此，提出构成复合形的随机方法。该方法是先产生k个随机点，然后再把那些非可行随机点调入可行域内，最终使k个随机点都称为可行点而构成初始复合形。

生成初始复合形的方法有以下几种：

1)由设计者决定k个可行点，构成初始复合形。当设计变量较多或约束函数复杂时，由设计者决定k个可行点常常很困难。只有在设计变量少，约束函数简单的情况下，这种方法才被采用。二、初始复合形的构成

222）构成复合形的随机方法：

1、产生k个随机点

由设计者选定一个可行点，其余的(k1)个可行点用随机法产生。利用标准随机函数产生在（0，1）区间内均匀分布的随机数rj，然后产生区间[a，b]内的随机变量xj，xj=a+rj（ba），j=1，2，…，k(6-13)xj-----复合形中的第j个顶点；a,b-----设计变量的下限和上限；rj-----在（0，1）区间内的伪随机数。

(6-14)2）构成复合形的随机方法：

1、产生k个随机232、将非可行点移入可行域

用上述方法的随机点不一定是可行点。但是只要它们中至少有一个点在可行域内，就可以用一定的方法将非可行点移入可行域。如果k个随机点没有一个是可行点，则应重新产生随机点，直至其中有至少一个是可行点为止。将非可行点移入可行域的方法：求出已经在可行域内的L个顶点的中心xC

然后将非可行点向中心点移动，得

若xL+1仍为不可行点，则利用上式，使其继续向中心点移动。只要中心点可行，xL+1点一定可以移到可行域内。随机产生的（k1)个点经过这样的处理后，全部变为可行点，并构成初始复合形。（6-14）（6-15）2、将非可行点移入可行域

用上述方法的随机点243、由计算机自动生成初始复合形的全部顶点。其方法是首先随机产生一个可行点，然后按第二种方法产生其余的（k-1)个可行点。事实上，只要可行域为凸集，其中心点必为可行点，用上述方法可以成功地在可行域内构成初始复合形。如果可行域为非凸集，如图6-8所示，中心点不一定在可行域之内，则上述方法可能失败。此时可以通过改变设计变量的下限和上限值，重新产生各顶点。经过多次试算，有可能在可行域内生成初始复合形。3、由计算机自动生成初始复合形的全部顶点。其方法是首先随机25三、复合形法的搜索算法一）反射

1、构成初始复合形；计算个顶点函数值f(xj),j=1,2,…,k，并选出好点xL与坏点xH及次坏点xG：

xL:f(xL)=min{f(xL),j=1,2,…,k}

xH:f(xH)=max{f(xj),j=1,2,…,k}xG:f(xG)=max{f(xj),j=1,2,…,k,GH}；

2、

计算除去最坏点xH外其余各顶点的中心点xC,3、反射就是沿最坏点xH和中心点xC的连线方向上去映射点xR,即

xR=xC+(xC

xH)式中，称为反射系数，一般=1.3。反射点xR与最坏点xH、中心点xc的相对位置如图6-9所示。

三、复合形法的搜索算法264、如果xR满足所有约束条件，且f(xR)<f(xH),可用xR代替xH组成新复合形，完成一次迭代。如果xR不满足约束条件，或不满足f(xR)<f(xH),将减半重新计算xR，若仍不满足，可以继续将减为0.7倍重新计算xR，直到减得很小（例如小于105）还不满足要求时，就放弃这一方向，改用次坏点的映射方向。4、如果xR满足所有约束条件，且f(xR)<f(x27第六章约束优化方法ppt课件28第六章约束优化方法ppt课件29第六章约束优化方法ppt课件30第六章约束优化方法ppt课件31复合形法的程序框图见图6-13。复合形法的程序框图见图6-13。32第六章约束优化方法ppt课件33第六章约束优化方法ppt课件34（课外）例用复合形法求解解;1)产生初始复合形的顶点。取复合形顶点的数目为k=2n=4,并采用认为选点的方法确定初始复合形的四个顶点为以上四点均满足约束条件2）四点的函数值分别为由此可知最坏点为x10,好点为x40.3)计算除去坏点后，各点的中心点4）检查xC0点的可行性，由于所以xc0是可行点。（课外）例用复合形法求解355)求反射点xr0并检查其可行性取反射系数=1.3，可得反射点也是可行的。6）比较反射点与最坏点的目标函数值用xr0代替xH0，与其余3点构成新的复合形。第二轮迭代，k=1新复合形的四个顶点为其对应的函数值为5)求反射点xr0并检查其可行性36

由此可见，xH1=x21=[1,4]T，除去坏点后其余各点的中心为xC1=[2.77,4.46]T,满足所有约束条件，是可行点。进行反射计算，得xr1=[5.071,5.058]T,经检验xr1也是可行点，其f(xr1)=14.71<47=f(xh1),故可重新组成复合形，再计算，直至达到精度要求停机，最后所求得的x1k和f(x1k)接近理论最优解x*=[6,5]T,f(x*)=11.由此可见，xH1=x21=[1,4]T，376.4可行方向法基本原理

在可行域内选择一个初始点x0,当确定了一个可行方向d和适当的步长之后，按下式xk+1=xk+dk(k=1,2,)进行迭代进算。在不断调整可行方向的过程中，使迭代点逐步逼近约束最优点。一、搜索策略

第一步从可行的初始点x0,沿x0的负梯度方向d0=f(x0),将初始点x0移动到某一约束面（当只有一个起作用的约束时）上或约束面的交集（有几个起作用的约束时）上。根据约束函数和目标函数的不同性状，可以采用如下几种策略。6.4可行方向法基本原理一、搜索策略381）如图6-15，在约束面上的迭代点xk处，产生一个可行方向dk,沿此方向作一维最优化搜索，得到的新点x在可行域内，即令xk+1=x,再沿xk+1的负梯度方向dk+1=f(xk+1)继续搜索2）如图6-16，沿可行方向dk作一维最优化搜索，所得到的新点x在可行域外，则设法将x点移动到约束面上，即取dk和约束面的交点作为新的迭代点xk+1。1）如图6-15，在约束面上的迭代点xk处，产生一个393）沿约束面搜索。如图6-17，对于只具有线性约束条件的非线性规划问题，从xk点出发，沿约束面移动，在有限的几步内即可搜索到约束最优点；对于非线性约束函数如图6-18，沿约束面移动将会进入非可行域，使问题变得复杂得多。此时，需将进入非可行域的新点x设法调整到约束面上，然后才能进入下一次迭代。调整的方法是先规定约束面容差，建立新的约束边界（如6-18中虚线所示），然后将已离开约束面的x点，沿起作用约束函数的负梯度方向g(x)返回到约束面上。其计算公式为xk+1=x+tg(x)式中的t为调整步长，可用试探法决定，或者用下式计算3）沿约束面搜索。如图6-17，对于只具有线性约束条件的非40二、产生可行方向的条件可行方向是指沿该方向做微小移动后，得到的新点是可行点，且目标函数值下降。包括可行和下降两个条件。1）可行条件如图6-19a，若xk点在一个约束面上，对xk点作约束面g(x)=0的切线，显然满足可行条件的方向dk应与起作用的约束函数在该点的梯度的夹角大于或等于90o。即[g(xk)]Tdk0若xk点在J个约束面的交集上，如图6-19b，为保证dk可行，要求dk与J个约束函数在xk点的梯度gj(xk)(j=1,2,,J)的夹角均大于等于直角。即[gj(xk)]Tdk0(j=1,2,,J)dk二、产生可行方向的条件dk412）下降条件如图6-20，满足下降条件的方向dk应与目标函数在xk点的梯度的f(xk)的夹角大于90o。即[f(xk)]Tdk<0同时满足可行和下降条件的方向称为可行方向。如图6-21所示，它位于约束曲面在xk点的切线和目标函数等值线在xk点的切线所围成的扇形区内，该扇形区称为可行下降方向区。

即当xk点位于J个起作用的约束面上时，满足的方向dk称可行方向。2）下降条件如图6-20，满足下降条件的方向dk应42三、可行方向的产生方法1.优选方法在可行下降扇形区内选择任一方向d进行搜索，可得到一个目标函数值下降的可行点。如何在可行下降扇形区内选择一个能使目标函数下降最快的方向作为本次迭代的方向，是一个以搜索方向d为设计变量的约束优化问题，这个新的约束优化问题的数学模型可写成（6-31）

由于f(xk)和gj(xk)(j=1,2,,J)为定值，上述各函数均为设计变量d的线性函数。求解式(6-31)得到的最优解d*即为本次迭代的可行方向，即dk=d*.三、可行方向的产生方法432梯度投影法当xk点目标函数的负梯度方向f(xk)不满足可行条件时，可将其方向投影到约束面（或约束面的交集）上，得到投影向量d，从图6-22可以看出，改投影向量显然满足方向的可行和下降条件。梯度投影法就是取该方向作为本次迭代的可行方向。可行方向的计算公式为式中，P为投影算子，为nn阶方阵，计算公式为式中，I为单位矩阵，nn阶矩阵；

G为起作用约束函数的梯度矩阵，是nJ阶矩阵(J为起作用的约束函数个数)：

2梯度投影法444、步长的确定确定可行方向dk后，计算新的迭代点:xk+1=xk+kdkk的确定有两种方法（1）取最优步长如图6-23所示，从xk出发，沿dk方向进行一维最优搜索，取得最优步长*，计算新点的值x=xk+*dk。若新点x可行，则取k=*。4、步长的确定45（2）k取到约束边界的最大步长如图6-24所示，从xk出发，沿dk方向进行一维最优搜索，得到的新点x不可行，根据可行方向法的搜索策略，应改变步长，使新点x返回到约束面上来。使新点恰好位于约束面上的步长称为最大步长，记作M。则取k=M。M的确定步骤：1）取一试验步长t，计算试验点xt。试验步长t的值不能太大，以免因一步走得太远导致计算困难；t也不能太小，降低计算效率。依据经验，其值应能使试验点x的目标函数值下降5-10%将目标函数f(x)在xt点展开成泰勒级数的线性式则于是得则试验点xt的计算公式为（2）k取到约束边界的最大步长462）判别试验点xt的位置。由试验步长t确定的试验点xt可能在约束面上，可行域或非可行域。若不在约束面上，须设法将其调整到约束面上来。使xt到达约束面gj(x)=0(j=1,2,,J)常很困难。为此，确定一个约束允差。若试验点xt满足gj(x)0(j=1,2,,J)时，可认为试验点xt已经位于约束面上。若试验点位于非可行域，转步骤3）；若试验点位于可行域，应沿dk方向以步长t2t继续向前搜索，直至新的试验点xt到达约束面或越出可行域，再转步骤3)。为约束面的容差值，一般视计算精度而定，开始可以取大一点，0.01~0.001，然后在迭代中当满足一定的收敛条件时，在将容差值逐渐缩小，直至当=105时，则认为该点已经位于约束面上。2）判别试验点xt的位置。由试验步长t确定的试验点xt473）将位于非可行域的试验点xt调整到约束面上。如图6-25所示，在xt点处，g1(xt)>0,g2(xt)>0。应将xt点调整到g1(xt)=0的约束面上，因为对于xt点来说，g1(xt)的约束违反量比g2(xt)大。若设gk(xt)为约束违反量最大的约束条件，则应满足

将试验点xt调整到gk(xt)=0的约束面上的方法有试探法和插值法两种。试探法：当试验点位于非可行域时，将试验步长t缩短；当位于可行域时，将试验步长t加倍，直至满足gj(x)0(j=1,2,,J)，即认为试验点已经被调整到约束面上了。3）将位于非可行域的试验点xt调整到约束面上。48图6-26所示框图表示了用试探法调整试验步长t的过程。图6-26所示框图表示了用试探法调整试验步长t的过程。49(b)插值法：利用线性插值将位于非可行域的试验点xt调整到约束面上。设试验步长t，求得可性试验点当试验步长为t+0时，求得非可行试验点并设在该两点的约束函数分别为gk(xt1)<0和gk(xt2)<0,如图6-27所示。若考虑约束允差，并按允差中心/2做线性内插，可以得到将xt1调整到约束面上的步长s。本次迭代步长取为(b)插值法：利用线性插值将位于非可行域的试验点xt调整到50五、收敛条件将设计点调整到约束面上后，需判断迭代是否收敛，即判断该迭代点是否为约束最优点。1）满足2)满足库恩-塔克条件六、可行方向法的计算步骤1）在可行域内选一个初始点x0，给出约束允差及收敛精度值。2）令迭代次数k=0,第一次迭代的搜索方向取d0=f(x0)估算试验步长t，按式(6一38)计算试验点xt若试验点xt满足gj(xt)0，xt点必位于第j个约束面上，则转步骤6）；若试验点xt位于可行域内，则加大试验步长t，重新计算新的试验点，直至xt越出可行域，再转步骤5）；若试验点位于非可行域，则直接转步骤5）五、收敛条件六、可行方向法的计算步骤515）确定约束违反量最大的约束函数gk(xt)。用插值法计算调整步长t，使试验点xt返回到约束面上，则完成一次迭代。再令kk+1,xk=xt,转步骤6）6）在新的设计点xk处产生新的可行方向dk7)在xk点满足收敛条件，停机。约束最优解为x*=xk,f(x*)=f(xk)。否则，改变允差的值，令可行方向法的程序框图示于图6-28。第六章约束优化方法ppt课件52可行方向法的程序框图示于图6-28。可行方向法的程序框图示于图6-28。53例用可行方向法求约束优化问题minf(x1,x2)=x12+x22-10x1-x1x2-4x2+60s.t.g1(x)=x10

g2(x)=x20g3(x)=x160g4(x)=x280g5(x)=x1+x2110的约束最优解。解：取初始点x0=[01]T，为约束边界g1(x)=0上的一点。第一次迭代用优选方向法确定可行方向。为此，首先计算x0点的目标函数f(x0)和约束函数g1(x0)的梯度为在可行下降扇形区内寻找最优方向，需求解一个以可行方向d=[d1d2]T为设计变量的线性规划问题，其数学模型为：例用可行方向法求约束优化问题54

现用图解法求解，如图6-30所示。最优方向是d*=[0.9840.179]T，它是目标函数等值线（直线束）和约束函数d12+d22=1（半径为1的圆）的切点。第一次迭代的可行方向为d0=d*。若步长取0=6.098，则可见第一次迭代点x1在约束边界g3(x1)=0上。第六章约束优化方法ppt课件55第二次迭代用梯度投影法来确定可行方向。迭代点x1的目标函数负梯度-f(x1)=[0.0925.818]T，不满足方向的可行条件。现将f(x1)投影到约束边界g3(x)=0上，按式（6-33）计算投影算子P本次迭代的可行方向为显然，d1为沿约束边界g3(x)=0的方向。若取1=2.909，则本次迭代点即为该问题的约束最优点x*，则得约束最优解

第二次迭代用梯度投影法来确定可行方向。迭代点x1的目标函数负566.5惩罚函数法

惩罚函数法的基本原理是将约束优化问题

中的不等式约束和等式约束经过加权转化后，与原目标函数一起构成新的目标函数––惩罚函数

求解该新目标函数的无约束极小值，以期得到原问题的约束最优解。为此，按一定法则改变加权因子r1、r2的值，求得惩罚函数的一系列无约束最优解，并使其不断逼近原约束优化问题得最优解。因此，惩罚函数法又称序列无约束极小化方法---SUMT法。式(6-47)中的称为加权转化项，并根据它们在惩罚函数中的作用，又分别称为障碍项和惩罚项。6.5惩罚函数法57障碍项的作用是当迭代点在可行域内时，在迭代过程中阻止迭代点越出可行域。惩罚项的作用是当迭代点在非可行域或不满足等式约束条件时，在迭代过程之中迫使迭代点逼近约束边界或等式约束曲面。根据迭代过程是否在可行域内进行，惩罚函数法又可分为内点惩罚函数法、外点惩罚函数法、混合惩罚函数法三种。一、内点惩罚函数法

简称内点法。将新目标函数定义在可行域内，序列迭代点在可行域内逐步逼近约束边界的最优点。内点法只能求解具有不等式约束的优化问题。对于只具有不等式约束的优化问题障碍项的作用是当迭代点在可行域内时，在迭代过程中阻止58转化后的惩罚函数形式为或式中r为惩罚因子，它是由大到小且趋近于0的数列，即r0>r1>r2>……→0。由于内点法的迭代过程在可行域内进行，障碍项的作用是阻止迭代点越出可行域。由障碍项的函数形式可知，当迭代点靠近某一约束边界时，其值趋于0，而障碍项的值陡然增加，并趋近于无穷大，好像在可行域的边界上筑起了一道“围墙”，使迭代点始终不能越出可行域。显然，只有当惩罚因子r→0时，才能求得在约束边界上的最优解。

转化后的惩罚函数形式为59例6-5

用内点法求问题的约束最优解。

解：如图6-31所示，该问题的约束最优点为x*=[10]T，它是目标函数等值线，即x12+x22=1的圆和约束函数，即1-x1=0的直线的切点，最优值为f(x*)=1。用内点法求解该问题时，首先按式（6-50）构造内点惩罚函数对于任意给定的惩罚因子r(r>0)，函数Φ(x,r)为凸函数。用解析法求函数Φ(x,r)的极小值，即令(x,r)

=0，得方程组例6-5用内点法求问题60当时不满足约束条件g(x)=1–x1

0,应舍去。无约束极值点为可知，当逐步减小r值，直至趋近于0时，x*(r)逼近原问题的约束最优解。当r=4,1.26,0.36时，惩罚函数(x,r)的等值线分别如图6-32a、b、c所示。当时不满足约束条61重要参数的选取1、初始点x0的选取应选择一个离约束边界较远的可行点。若其太靠近某一个约束边界，构造的惩罚函数可能由于障碍项的值很大而变得畸形，使无约束优化问题的求解发生困难。2、惩罚因子初值r0的选取应适当选取，否则会影响迭代计算的正常进行。r0太大，将增加迭代次数；太小会使惩罚函数的性态变坏，甚至难以收敛到极值点。由于问题的多样化，是的r0的取值相当困难，目前尚无一定的有效的方法。一般需由此试算，来决定一个适当的初值。可参考以下方法：1）取r0=1,根据试算的结果，再决定增加或减小r0的值。2）按经验公式计算。这样选取的r0可使惩罚函数中的障碍项和原目标函数的值大致相等，不会因障碍项的值太大起支配作用，也不会因障碍项的值太小而被忽略。重要参数的选取623、惩罚因子的缩减系数c的选取rk=crk+1(k=1,2,)c称为惩罚因子的缩减系数，一般认为其值大小在迭代过程中不起决定性作用，通常在0.1~0.7范围内选取。4、收敛条件原约束问题的最优解为3、惩罚因子的缩减系数c的选取63内点法的计算步骤：1）选取可行的初始点x0，惩罚因子的初值r0，缩减系数c和收敛精度1、2.迭代次数k0。2）构造惩罚函数(x,r)，选择适当的无约束优化方法，求函数的无约束极值，得x*(rk)点3）判断是否收敛，收敛则停止计算；约束最优解为否则令转步骤2）内点法的计算步骤：64二、外点惩罚函数法

简称外点法。其基本思想是将新目标函数定义在可行域之外，序列迭代点从可行域之外逐步逼近约束边界的最优点。外点法可以求解具有不等式约束和等式约束问题的优化问题。1、惩罚函数的形式

对于约束优化问题

转化后的外点惩罚函数形式为式中r为惩罚因子，它由小到大，且趋近于的数列，即r0<r1<r2<…→分别为对应于不等式约束和等式约束函数的惩罚项。二、外点惩罚函数法

简称外点法。其基本思想是将新目标65

外点法的迭代过程在可行域之外进行，惩罚项的作用是迫使迭代点逼近约束边界或等式约束曲面。有惩罚项的形式可知，当迭代点x不可行时，惩罚项的值大于0.使得惩罚函数(x,r)大于原目标函数，这可看成是对迭代点不满足约束条件的一种惩罚。当迭代点离约束边界愈远，惩罚项的值愈大，这种惩罚愈重。但当迭代点不断接近约束边界和等式约束曲面时，惩罚项的值减小，且趋近于0，惩罚项的作用逐渐消失，迭代点也就趋近于约束边界上的最优点了。外点法的迭代过程在可行域之外进行，惩罚项的66例6-5用外点法求问题的约束最优解。

解：该问题的约束最优点为x*=[10]T，它是目标函数等值线，即x12+x22=1的圆和约束函数，即1-x1=0的直线的切点，最优值为f(x*)=1。构造外点惩罚函数对于任意给定的惩罚因子r>0，函数(x,r)为凸函数。求其无约束极小值，令(x,r)=0，得求得由计算可知，当逐渐增大r值直至无穷时，x*(r)逼近原目标函数的极值点。例6-5用外点法求问题67第六章约束优化方法ppt课件68

初始点x0的选取,在可行域及非可行域内均可。惩罚因子的递增系数c的选取rk=crk-1(k=1,2,)c称为惩罚因子的递增系数，通常在5~10范围内选取。在外点法中，r0的合理取值也是很重要的。选取过小，则序贯无约束求解的次数就增多，收敛速度慢；反之，则在非可行域中，发函数比原目标函数要大得多，特别在起作用约束边界处产生尖点，函数性态变坏，从而限制了某些无约束优化方法的使用，致使计算失败。取r0=1,c=10常可取得满意的结果。也可按下面的经验公式来计算r0.r0=max{rj0}(j=1,2,,m)式中

69混合法

用罚函数法解决有等式约束和不等式约束的一般约束优化问题的方法，把它称为混合惩罚函数法，简称混合法。1混合法惩罚函数的形式及特点一般约束问题的优化模型转化后的混合惩罚函数的形式为为障碍项，r为惩罚因子，按内点法取r0>r1>r2>……→0。为惩罚项，

为惩罚因子，当r→0时，满足外点法对惩罚因子的要求。混合法用罚函数法解决有等式约束和不等式约束的一般约束70例6-7试求点集A(x1,x2,x3)和点集B(x4,x5,x6)之间的最短距离。限制条件为由右下图可知，表示以原点为球心，半径为的球体，点集A在球面上取点。其余两个限制条件表示一圆柱体，点集B在圆柱面上取点。因此该问题就是求这两个几何体间的最短距离的约束优化问题，其数学模型为解:用混合法编程计算，取x0=[111315]T,r0=1,c=0.2.在计算机上迭代13可求得最优解为x*=[1.0015-0.00351.992.0-0.00774.07]Tf(x*)=5.0008例6-7试求点集A(x1,x2,x3)和点集B(x471第六章约束优化方法ppt课件72（课外）例：如图所示为一对称的两杆支架，在支架的顶点承受一个荷载2F=300000N，支座之间的水平距离为2B=1520mm，若选定壁厚T=2.5mm的钢管，弹性模量E=2.16105MPa,密度=8300kg/mm3,屈服点σs=700MPa,要求在满足强度与稳定性条件下设计最轻的支架尺寸。

（课外）例：如图所示为一对称的两杆支架，在支架的顶点承受一个73解：数学模型的建立设计变量取

目标函数为约束条件为1）圆管杆件中的压应力σ应小于或等于材料的屈服极限σs,即于是得到2）圆管杆件中的压应力应小于或等于压杆稳定的临界压力，由欧拉公式得钢管的压杆稳定应力于是得解：74（2）求解结果和分析此问题的外点法惩罚函数为取初始点x0=15.2，f(x0)=21.24,r0=10-10,无约束极小化，用变尺度法求解。

（2）求解结果和分析75(课外)例：如6-47图所示，设有一箱形盖板，已知长度L=6000mm，宽度b=600mm，厚度ts=5mm。翼板厚度为tf（cm），它承受最大的单位载荷q=0.01MPa。弹性模量E=7104MPa，泊松比μ=0.3，允许弯曲应为[σu]=70MPa，允许剪切应力[]=45MPa。要求在满足强度、刚度和稳定性等条件下，设计一个重量最轻的方案。解：（1）设计分析截面的惯性矩近似取(课外)例：如6-47图所示，设有一箱形盖板，已知长度L=76最大剪应力为最大弯曲应力（翼板中间）为式中Q----最大剪应力，Q=18000N。翼板中的屈曲临界稳定应力为最大挠度为盖板单位长度的质量（kg/cm）为最大剪应力为77式中----材料的密度，t/m3。数学模型根据设计要求，建立如下数学模型：设计变量：目标函数：式中已略去密度，因为它对目标函数极小化没有影响。设计约束：按照强度、刚度和稳定性要求建立如下约束条件。式中----材料的密度，t/m3。78单位长度允许挠度取[f]/L=1/400。在下图中给出了问题在设计平面上的几何关系：f(x)的等值线和约束边界曲线g1(x)~g6(x)。阴影线的右边为可行设计区域，其最优解在P点。单位长度允许挠度取[f]/L=1/400。79（3）求解方法和结果用内点惩罚