第五章-约束优化方法

第五章约束优化方法2020/5/2212)约束随机方向法;3)复合形法;5)罚函数法;约束优化直接解法约束优化间接解法（1）内点罚函数法;（2）外点罚函数法;1)约束坐标轮换法；4)可行方向法;（自学）第五章约束优化方法根据求解方式的不同，可分为直接解法和间接解法两类。1,2,...,1,2,...,umvpn()0()0uvgxhx()fxminnxR..st机械优化设计的问题，大多属于约束优化设计问题，其数学模型为：直接解法是将迭代点限制在可行域内(可行性)，步步降低目标函数值(下降性)，直至到达最优点，求出问题的约束最优解。间接解法是将约束优化问题转化为一系列无约束优化问题来解的一种方法。常用方法有:约束坐标轮换法,约束随机方向法,复合形法,可行方向法,线性逼近法等.常用方法有:罚函数法,拉格朗日乘子法等.第五章约束优化方法直接解法是在满足不等式约束的可行设计区域内直接求出问题的约束最优解。属于直接解法的有：随机实验法、随机方向搜索法、复合形法、可行方向法等。间接解法是将约束优化问题转化为一系列无约束优化问题来解的一种方法。由于间接解法可以选用已研究比较成熟的无约束优化方法，并且容易处理同时具有不等式约束和等式约束的问题。因而在机械优化设计得到广泛的应用。间接解法中具有代表性的是惩罚函数法。直接解法的基本思想：在由m个不等式约束条件gu(x)≤0所确定的可行域φ内，选择一个初始点x(0)，然后确定一个可行搜索方向S，且以适当的步长沿S方向进行搜索，取得一个目标函数有所改善的可行的新点x(1)，即完成了一次迭代。以新点为起始点重复上述搜索过程，每次均按如下的基本迭代格式进行计算：x(k+1)＝x(k)+α(k)S(k)(k=0,1,2,…)逐步趋向最优解，直到满足终止准则才停止迭代。直接解法的原理简单，方法实用，其特点是：1）由于整个过程在可行域内进行，因此，迭代计算不论何时终止，都可以获得比初始点好的设计点。2）若目标函数为凸函数，可行域为凸集，则可获得全域最优解，否则，可能存在多个局部最优解，当选择的初始点不同，而搜索到不同的局部最优解。3）要求可行域有界的非空集。直接解法的特点：a)可行域是凸集；b)可行域是非凸集间接解法的基本思路：将约束函数进行特殊的加权处理后，和目标函数结合起来，构成一个新的目标函数，即将原约束优化问题转化为一个或一系列的无约束优化问题。121211,,mljkjkxfxGgxHhx新目标函数加权因子然后对新目标函数进行无约束极小化计算。间接解法的基本思路2020/5/229第二节约束坐标轮换法一.基本思路•①可取定步长、加速步长和收缩步长,但不能取最优步长;1.依次沿各坐标轴方向---e1,e2,…,en方向搜索;2.将迭代点限制在可行域内.②对每一迭代点均需进行可行性和下降性检查.2020/5/2210二.迭代步骤)3(X)1(X)0(X)4(X)2(X2020/5/2211三.存在问题有时会出现死点,导致输出“伪最优点”.*为辨别真伪,要用K-T条件进行检查.3.1随机方向法的基本思路1、在可行域内选择一个初始点；2、利用随机数的概率特性，产生若干个随机方向；3、从中选一个能使目标函数值下降最快的方向作为搜索方向d；4、从初始点x0出发，沿d方向以一定步长进行搜索，得到新点X，新点X应满足约束条件且f(x)f(x0)，至此完成一次迭代。基本思路如图所示。随机方向法程序设计简单，搜索速度快，是解决小型机械优化问题的十分有效的算法。第三节约束随机方向法坐标轮换法有时会输出“伪最优点”,用随机方向法可克服这一缺点.随机方向法的基本思路3.2随机方向的构成1.用RND(X)产生n个随机数)10(,...,2,1,iini2.将(0,1)中的随机数变换到(-1,1)中去(归一化);i12iiyni,...,2,13.构成随机方向nniiyyyyS...12112变换得:6.0,2.0,6.0321yyy于是6882.02294.06882.06.02.06.06.02.0)6.0(1222S例:对于三维问题8.0,6.0,2.0321第二节约束随机方向法从k个随机方向中，选取一个较好的方向。3.3可行搜索方向的产生第二节约束随机方向法1.检验k个随机点是否为可行点，除去非可行点，计算余下的可行点的目标函数值，比较其大小，选出目标函数最小的点XL。2.比较XL和X0两点的目标函数值，•若f(XL)f(X0)，则取XL和X0连线方向为可行搜索方向；•若f(XL)f(X0)，则步长α0缩小，转步骤1）重新计算，直至f(XL)f(X0)为止。•如果α0缩小到很小，仍然找不到一个XL，使f(XL)f(X0)则说明X0是一个局部极小点，此时可更换初始点，转步骤1）。产生可行搜索方向的条件为：00min1,2,...,LjLjLgxfxfxjkfxfx则可行搜索方向为：0Ldxx3.3可行搜索方向的产生第二节约束随机方向法3.4初始点的选择随机方向法的初始点x0必须是一个可行点，既满足全部不等式约束条件。初始点可以通过随机选择的方法产生。1）输入设计变量的下限值和上限值，即iiiaxb2）在区间（0，1）内产生n个伪随机数iq3）计算随机点x的各分量()iiiiixaqba第二节约束随机方向法4）判别随机点x是否可行，若随机点可行，用x代替x0为初始点；若非可行点，转到步骤2）重新产生随机点，只到可行为止。3.5.迭代过程①在初始点处产生一随机方向，若该方向适用、可行，则以定步长前进；②若该方向不适用、可行，则产生另一方向；③若在某处产生的方向足够多(50-100)，仍无一适用、可行，则采用收缩步长；④若步长小于预先给定的误差限则终止迭代。(0)X(1)S(1)(0)XXS(1)X(2)X第二节约束随机方向法3.6.流程图X0=X,F0=F给定内点X0,α0,m,εα=α0,F0=F(X0)F=F（X）j=1K=K+1是K=0,j=00XXS产生随机方向α=0.5α否FF0j=0Kmα≤ε结束X*=X0,F*=F0是否是否是否X∈D是否)(0步长终止误差限的方向数在一迭代点处允许产生初始步长；m；)0,1()(否则为沿该方向前进过为计数器方向数计数器jKfunction[x1,fx1,gx]=opt_random2(f,g_cons,xl,xu,TolX,TolFun)N=length(xl);M=size(g_cons);M=length(M(:,1));gx=ones(M,1);whilemax(gx)=0dir0=rand(N,1);x0=xl+dir0.*xu;gx=feval(g_cons,x0);%feval()执行由串指定的函数end%========================================================fx0=feval(f,x0);xk=x0+1;fxk=feval(f,xk);xmin=x0;alpha=1.3;k1=0;flag1=1;whilenorm(xk-x0)TolX|abs(fxk-fx0)TolFunk1=k1+1;x0=xmin;fx0=feval(f,x0);3.7随机方向法的Matlab程序dir0=rand(N,1)*2-1;dir0=dir0/norm(dir0);xk=x0+alpha*dir0;gx=feval(g_cons,xk);ifmax(gx)0alpha=alpha*0.7;elsefxk=feval(f,xk);iffxkfx0ifnorm(xk-x0)TolX&abs(fxk-fx0)TolFunbreakelsexmin=xk;alpha=1.3;endx0,xk,fx0,fxkelsealpha=-alpha;endendendx1=x0;fx1=feval(f,x1);gx=feval(g_cons,x1);k1end例:求3.7随机方向法的Matlab程序functionopt_random1_test1%opt_random1_test1.mclc;clearall;f=inline('x(1)^2+x(2)','x');xl=[-3-3]';xu=[33]';TolX=1e-8;TolFun=1e-8;[x1,fx1,g]=opt_random1(f,@fun_cons,xl,xu,TolX,TolFun)functiong=fun_cons(x)g=[x(1)^2+x(2)^2-9x(1)+x(2)-1];计算结果：x1=[-0.0076-3.0000],f=-2.9999,g=[-0.0000-4.0076]第四节复合形法复合形法是求解约束优化问题的一种重要的直接解法。基本思路：1、在可行域内构造一个具有k个顶点的初始复合形；2、对该复合形各顶点的目标函数值进行比较，找到目标函数最大的顶点（最坏点）；3、然后按一定的法则求出目标函数值有所下降的可行的新点，并用此点代替最坏点，构成新的复合形，复合形的形状每改变一次，就向最优点移动一步，直至逼近最优点。由于复合形的形状不必保持规则的图形，对目标函数和约束函数无特殊要求，因此这种方法适应性强，在机械优化设计中应用广泛。4.1基本思路在可行域内选取若干初始点并以之为顶点构成一个多面体(复合形),然后比较各顶点的函数值,去掉最坏点,代之以好的新点,并构成新的复合形,以逼近最优点.4XCX3X1X2X第四节复合形法4.2初始复合形生成的方法：（1）由设计者决定k个可行点，构成初始复合形。设计变量少时适用。（2）由设计者选定一个可行点，其余的k-1个可形点用随机法产生。()iixarba11LcjjxxL110.5LcLcxxxx（3）由计算机自动生成初始复合形的所有顶点。第四节复合形法*初始复合形的构成*复合形的移动和收缩4.2.1初始复合形的构成(1)复合形顶点数K的选择建议:nKn21小取大值,大取小值nn(2)初始复合形顶点的确定★用试凑方法产生---适于低维情况;★用随机方法产生4.2初始复合形生成的方法：第四节复合形法1,2,...,(),iiiiiinxbaa②将非可行点调入可行域内★K个顶点中要求无一在可行域内。重新产生。★K个顶点中有可行点，重新排列，将可行点依次排在前面，如有q个顶点X(1)、X(2)、……X(q)是可行点，其它K-q个为非可行点。对X(q+1)，将其调入可行域的步骤是：先用随机函数产生个随机数,然后变换到预定的区间中去.n)10(iiiiibxa①用随机方法产生K个顶点(1)计算q个点集的中心X(s)；qjjsXqX1)()(1(1)()(1)()0.5()qsqsXXXX(2)将第q+1点朝着点X(s)的方向移动，按下式产生新的X(q+1)，即若仍不可行，则重复此步骤，直至进入可行域为止。按照这个方法，同样使X(q+2)、X(q+3)、……X(K)都变为可行点，这K个点就构成了初始复合形。)(sX)1(qX4XCX3X1X2X•有两种基本运算:1)映射---在坏点的对侧试探新点:先计算除最坏点外各顶点的几何中心,然后再作映射计算.2)收缩---保证映射点的“可行”与“下降”)()(5.01432XXXXXXXCCCX1为最坏点---映射系数常取3.1若发现映射点不适用、可行,则将减半后重新映射.4.3复合形法的搜索方法4.4复合形法的迭代步骤(1)构造初始复合形；(2)计算各顶点的函数值F(X(j))，j=1,2,….,K。选出好点X(L)和坏点X(H)；()()()()()():()min{(),1,2,,}:(