6第六章-约束优化方法new

第六章约束优化方法约束优化方法概述随机方向法复合形法可行方向法惩罚函数法教学要求：1、掌握随机方向法。2、掌握复合形法的原理。3、掌握内点法和外点法的惩罚函数的构造原理及程序设计。6.1约束优化方法概述无约束优化方法是优化方法中最基本最核心的部分。在工程实际中，优化问题大都属于有约束的优化问题，即其设计变量的取值要受到一定的限制，用于求解约束优化问题最优解的方法称为约束优化方法。约束优化设计的数序模型为：根据求解方式的不同，约束优化方法可以分为：直接解法和间接解法lkxxxhxhmjxxxgxgtsxxxfxfnkknjjn,,2,10,,,,,2,10,,,..,,,min2121211、直接法只能求解不等式约束优化问题的最优解。其根本做法是在约束条件所限制的可行域内直接求解目标函数的最优解。如：约束坐标轮换法、复合形法等。其基本要点：选取初始点x0、确定可行搜索方向d及适当步长。每次迭代计算均按以下基本迭代格式进行xk+1=xk+kdk(k=1,2,)可行搜索方向：当设计点沿该方向作微量移动时，目标函数值下降，且不越出可行域。特点：1）求解在可行域内进行，当前设计点总比初始设计点好；2）若目标函数为凸函数，可行域为凸集，可保证获得全域最优解；3）要求可行域为有界的非空集，即在有界可行域内存在满足全部约束条件的点，且目标函数有定义。2、间接法该方法可以求解等式约束优化问题和一般约束优化问题。其基本思想是将约束优化问题通过一定的方法进行改变，将约束优化问题转化为无约束优化问题，再采用无约束优化方法进行求解。如：惩罚函数法基本迭代过程，将约束优化问题转化成新的无约束目标函数式中为转化后的目标函数分别为约束函数gj(x),hk(x)经过加权处理后构成的某种形式的复合函数或泛函数‘1，2为加权因子。xhHxgGxfxklijmj121121,,21,,xxhHxgGklijmj1211，例6.1求约束优化问题minf(x)=(x12)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)=(x12)2+(x2–1)2+0.8(x1+2x22)可以用解析法求min(x,2),令=0，得到/x1=2(x12)+0.8=0/x2=2(x12)+1.6=0求得的无约束最优解为x*=[1.60.2]T,(x*，2)=0.8。其结果与原约束最优解相同。特点：1）由于无约束优化方法的日趋成熟，使得间接解法有了可靠的基础；2）可以有效地处理具有等式约束的约束优化问题；3）存在的主要问题，选取加权因子较为困难。加权因子选取不当，会影响收敛速度和计算精度，甚至会导致计算失败。6.2随机方向法本方法是在可行域内利用随机产生的可行方向进行搜索的一种直接解法，用于求解这类约束优化设计问题。在可行域内选择一个初始点x0，利用随机数的概率特性，产生若干个随机方向，并从中找出一个能使目标函数值下降最快的随机方向作为可行搜索方向，记作d1。从初始点x0出发，沿方向d1按给定的初始步长取试探点x=x0+d1检查x点的适用性和可行性，即检查f(x)f(x0),xD?若满足，则以x为新的起点，即x0x。继续按上面的迭代式在d1方向上获取新点。重复上述步骤，迭代点可沿d1方向前进，直至到达某迭代点不能同时满足适用性和可行性条件时为止，退到前一点作为改方向搜索中的最终成功点，记作x1.将x1作为新的始点x0x1，再产生另一随机方向d2,以步长0重复以上过程，直到沿d2方向得到最终成功点x3。如此循环，点列x1、x2、必将逼近约束极值点x*。mjxxxgxgtsxxxfxfnjjn,,2,10,,,..,,,min2121一、随机数的产生首先令r1=235,r2=236,r3=237,取r=2657863(r为小于r1的正奇数），然后按一下步骤计算令r5r若rr3,则rrr3若rr2,则rrr2若rr1,则rrr1则q=r/r1q即为(0,1)区间内的伪随机数。利用q,容易求得任意区间(a,b)内的伪随机数，其计算公式为x=a+q(ba)（6-5）（6-4）这部分内容为产生伪随机数的数学模型，可写成子程序。或者大家可以直接利用算法语言中自带的产生随机数的子程序。二、初始点的选择随机方向法的初始点x0必须是一个可行点，满足全部不等式约束条件。当约束条件较为复杂，用人工不易选择可行初始点时，可用计算机随机选择的方法来产生。其计算步骤如下：1）输入设计变量的下限值和上限值，即aixibi(i=1,2,,n)2）在区间（0，1）内产生n个伪随机数qi(i=1,2,,n)3）计算随机点x的分量xi=ai+qi(biai)(i=1,2,,n)4)判别随机点x是否可行，若可行取x0x;否则转步骤2）重新计算。直到产生的随即点是可行点为止。（6-6）三、可行搜索方向的产生从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缩小到很小（例如106），仍然找不到一个xL,使f(xL)f(x0),则说明x0是一个局部极小点，此时可更换初始点，转步骤1.njrrrrejnjjnijij,,2,1121211kjexxjj,,2,100（6-8）（6-7）产生可行搜索方向的条件可以概括为，当xL点满足则可行搜索方向为四、搜索方向的确定可行搜索方向d确定后，初始点移至xL点，从xL点出发沿d方向进行搜索，所用的步长一般按加速步长法来确定。所谓加速步长法是指依次迭代的步长按一定的比例递增的方法。各次迭代的步长按下式计算=式中为步长加速系数，可取为1.3；为步长，初始步长取=0。0,,2,1min,,2,10xfxfxfxfmjxgLkjjLLj0xxdL（6-9）（6-10）五、计算步骤1）选择一个可行的初始点x0;2)按式（6-7）产生k个n维随即单位向量ej(j=1,2,…,k);3)取试验步长0，按式（6-8）计算出k个随机点xj(j=1,2,…,k);4)在k个随机点中，找出满足式（6-9）的随机点xL,产生可行搜索方向d=xLx0.5)从初始点x0出发，沿可行搜索方向d以步长进行迭代计算，直到搜索到一个满足全部约束条件，且目标函数值不再下降的新点x.6)若收敛条件得到满足，停止迭代。约束最优解为。否则，令x0x转步骤2）。2010xxxfxf（6-12）,xxfxfx随机方向法的程序框图见图6-5。例6-2求约束优化问题的最优解。解：用随机方向法程序，在计算机上运行，迭代13次，求得约束最优解：x*=[0.00273.0]T,f(x*)=3。计算机计算的结果摘录于表6-1，该问题的图解示于图6-6.0109..min21222211221xxxgxxxgtsxxxf（课外）例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,其传动角允许在45o135o范围内变化。20032E(1)解：(1)数学模型的建立已经给定了两根杆长:l1=1,l4=5,且0和0不是独立的参数，因为所以只剩下两个独立参数l2,l3。因此设计变量取复演预期函数的机构设计问题，可以按期望机构的输出函数与给定函数的均方根误差达到最小来建立目标函数，即或者由于和E均为输入角的连续函数，为了进行数值计算，可将[0,m]区间划分为30等分，将上式改写为梯形近似积分计算公式4323242210421232422102arccos2arccoslllllllllllll3221llxxxminmin00202mmdEdEmE(2)(3)(4)式中j为当=j时机构的实际输出角；Ej为复演预期函数当=j时的函数值，也是欲求机构的理论输出角。下标j为j=0,1,2,,30。Ej值按式（1）计算，j值可按下式计算：目标函数是一个凸函数，等值线如右图所示。293023030012112921221EEjjjEjjxf2214124212421242221222322232cos1026cos21024arccos2arccos2arccos2arccosjjjjjjjjjjjjjjjjllllllllllllxlxxllllll(5)(6)(7)(8)(9)由于要求四杆机构的杆1能做整周转动，且机构的最小传动角min45o、最大传动角min135o，所以根据四杆机构的曲柄存在条件，得不等式约束条件为根据传动角的条件有cosmincos45o,cosmax135o，因所以得到不等式约束条件为在上面7个约束条件中，式(10)-(14)的约束边界为直线，式(17)和(18)的约束边界为椭圆。在设计空间内组成一个可行设计区域，即阴影线所包围的部分。040406002151242132211xxxgxxxgxxxgxxgxxg322142322max322142322min2cos2cosllllllllllll0364142.10164142.121222172122216xxxxxgxxxxxg(10)(11)(12)(13)(14)(15)(16)(17)(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。最终设计方案的参数为l1=1,l2=4.1286,l3=2.3325,l4=5,0=26o28,0=108o0