机械优化设计总概和Zoutendijk可行方向法举例.docx

北京理工大学机械优化设计课程论文机械优化设计总概和Zoutendijk可行方向法举例专业班级：学生姓名：学号：指导教师： 学院： 2013年1月机械优化设计总概和Zoutendijk可行方向法举例1机械优化设计的一般步骤机械优化设计是将机械工程设计问题转化为最优化问题，然后选择恰当的最优化方法，利用电子计算机从满足要求的可行设计方案中自动寻找实现预期目标的最优设计方案。从中可以看到，机械优化设计包含两个部分，首先是把实际的机械设计问题用数学表达式加以描述，即转化为数学模型，然后是根据数学模型的特性，选择某种适当的优化设计方法及其程序，通过电子计算机求得最优解。2数学模型的建立首先是几个概念的建立。设计变量：可做变量处理的独立参数。目标函数：在设计中能最好地反映该项设计所追求的某些特定目标的评价标准。约束条件：对设计变量的取值加以某些限制的条件。根据实际问题的各种条件，将最优化问题抽象成数学模型，标准化为：maxxEnfxs.t. gux0 (u=1,2,m)hvx=0 (v=1,2,pn)3求解最优化问题将最优化问题抽象为数学上的求最优解问题之后，求最优解就成了我们所需要解决的问题，而很多或简单或复杂的最优解问题，是很难求出准确解的，即便能够求出，也需要大量繁杂的计算，所以我们必须开发出一些方法，让计算机帮助我们解决这个问题，限于计算机的构成及设计原理，我们开发了各种是数值方法。根据数学模型的不同，主要是问题维数的不同、目标函数的不同、约束条件的不同，最优化问题主要有以下几类算法1：机械优化算法1，一维搜索方法1.1黄金分割法1.2二次插值法2，多维无约束优化方法2.1导数解法2.1.1最速下降法2.1.2共轭梯度法2.1.3牛顿法2.1.4坐标轮换法2.2直接解法2.2.1变尺度法2.2.2鲍威尔法3，多维有约束优化方法3.1约束优化问题的直接解法3.1.1随机方向法3.1.2复合形法3.1.3可行方向法3.1.4约束坐标轮换法3.2约束优化问题的直接解法3.2.1罚函数法3.2.2增广乘子法 3.1 一维搜索方法3.1.1 黄金分割法特点：简单，有效，成熟的一维直接搜索方法，应用广泛。可以把区间缩小的任意长度。使用条件：适用于a,b区间上使用原则：黄金分割点的内分点选取必须遵循每次区间缩短都取相等区间缩短率的原则。3.1.2二次插值法特点：收敛速度较黄金分割法快，可靠性不如黄金分割法，初始点的选择影响收敛效果。不可能一次就达到函数的最优解，必须重复多次，向最优值逐渐逼近。原则：首先要选择一个初始步长，用外推法确定极值点存在的区间，然后用二次差值法求极值点的近似值。3.2无约束多维优化方法3.2.1 最速下降法特点：1）最速下降法是求解无约束多元函数极值问题的古老算法之一；2）最速下降法理论明确，方法简单，概念清楚，每迭代一次除需进行一维搜索外，只需计算函数的一阶偏导数，计算量小；3）对初始点的要求较低，初始迭代效果较好，前后两步迭代的搜索方向相互正交，在极值点附近收敛很慢。选用原则及条件：一般与其他算法配合，在迭代开始时使用。3.2.2共轭梯度法特点：1）仅需计算函数的一阶偏导数，编程容易，准备工作量比牛顿法小，收敛速度远超过梯度法，但有效性比DFP(变尺度)法差；2）使用一阶倒数的算法，所用公式结构简单，并且所需的储存量少。3）收敛速度很快，有超线性的手链速度。使用条件：适用于维数较高(50维以上)、一阶偏导数易求的优化问题。使用原则：共轭梯度法在第一个搜索方向取负梯度方向，而其余各步的搜索方向将负梯度偏转一个角度，即对负梯度进行修正，实质上是对最速下降法的改进。在n次迭代后如果没有达到收敛精度，则通常以重置负梯度方向开始，直到满足精度为止。3.2.3 牛顿法特点：牛顿法对初始点要求不严格，具有二次收敛性，最优点附近的收敛速度极快，对于正定二次函数的寻优，迭代一次即可达到极小点；当初始点选的合适的时候，是目前算法中收敛的最快的一种（尤其对二次函数）。使用条件：缺点是要求目标函数必须有一阶、二阶偏导数及海森矩阵非奇异且正定或负定，需要计算一阶、二阶偏导数及海森矩阵的逆阵，程序复杂、计算量大。使用条件：该方法适用于目标函数具有一阶、二阶偏导数，海森矩阵非奇异，维数不太高的场合。3.2.4 坐标轮换法特点：坐标轮换法是最简单的直接优化方法之一，方法易懂，程序简单，无需求导，计算费用低。但可靠性差、效率低，当目标函数等值线具有脊线形态时可能失败。该方法适用于目标函数导数不存在或不易求得、维数较低(一般，l5)的情况。从坐标轮换法的迭代过程可以看出其探索路线较长，而且显然是问题的维数愈多求最优解得效率愈低。使用条件：对设计变量少的最优化问题有效，对设计变量较多的问题则不太适用。3.2.5 变尺度法特点：DFP综合了梯度法和牛顿法的优点，对初始点要求不高，不必计算二阶偏导数矩阵及其逆阵，收敛速度快、效果好；缺点是需计算一阶偏导数，且由于舍入误差和一维搜索的不精确等原因，数值稳定性仍不够理想，有时因计算误差引起变尺度矩阵奇异而导致计算失败。使用条件：Broyden、Fletcher、Goldtein、Shanno等于1970年提出了更具数值稳定性的BFGS变尺度法，适用于求解维数较高(10具有一阶偏导数的无约束优化问题，被认为是目前最成功的变尺度法。3.2.6鲍威尔法特点：该方法直接利用函数值逐次构造共轭方向，并在改进的算法中增加了判断原方向组是否需要替换和哪个方向需要替换，保证了共轭方向的生成，具有二次收敛性，收敛速度快，可靠性好，但编程较复杂。是直接搜索法中最为有效的算法之一。使用条件：适用于维数较高的优化问题。3.3 多维有约束优化方法3.3.1随机方向搜索法特点：简单、方便，对目标函数性态无特殊要求，收敛较快，但计算精度不高，对严重非线性问题一般只能提供较近似的最优解。使用原则：适用于中小型无约束或有约束优化问题。3.3.2 复合型法特点：具有单纯型法的特点，适合于求解n15)和有等式约束的优化，是求解非线性优化的有效方法之一，在优化设计中得到广泛应用。3.3.3 可行方向法特点：1）可行方向法是用梯度去求解约束优化设计问题的一种有代表性的直接搜索方法。2）收敛速度快，效果较好，但程序比较复杂。使用条件：适用于大中型约束优化设计问题的求解。3.3.4 惩罚函数法特点：1）将有约束问题转化为无约束问题，对大中型问题的求解均较适合，计算效果较好；2）基本构思简单，课求解等式约束，不等式约束以及两种约束兼有的优化问题。3）罚函数法又可分为内点法、外点法和混合法。内点法能给出一系列逐步改进的可行设计方案，但其初始点为严格的可行内点，初始惩罚因子、递减系数往往需试算才能确定，对收敛速度和迭代成败影响较大。外点法克服了内点法的一些缺点，且其初始点可任选。混合法在一定程度上综合了内点法和外点法的优点，其初始点可任选，可处理多个变量和多个函数，能解决具有等式和不等式约束的优化问题。使用条件：适用于中、小型非线性的约束优化。使用原则：应用罚函数法时，首先应取适当小的初始惩罚因子，再根据运算结果进行调整，此外，其递增系数也不宜选得过大。4 可行方向法应用分析2可行方向法属于多维有约束优化方法直接解法的一种，可行方向法是最大的一类，它也是求解大型约束优化问题的主要方法之一。其基本思想是给定一个可行点之后，用某种方法确定一个改进的可行方向，然后沿方向，求解一个有约束的线搜索问题，得极小点，令，如果不是最优解，则重复上述步骤。可行方向法就是利用线性规划方法来确定的。可行方向法常用方法有Zoutendijk可行方向法，既约梯度法，Rosen梯度投影法，Frank-Wolfe方法。Zoutendijk可行方向法对线性和非线性的不等式约束问题均适用，但约束条件不含等式约束，是可行方向法中选择可行下降方向的主要方法之一。4.1 线性不等式约束的Zoutendijk可行方向法34.1.1 利用起作用约束构造可行下降方向考虑NLP问题minfx s.t.Axbx+c (4.1.1)Ex=eTh1设x是问题(4.1.1)的可行解，在点x处有A1x=b1,A2=b2,其中A=A1A2,b=b1b2则非零向量d为x处的可行方向的充要条件是A1d0,Ed=0.Zoutendijk法把确定搜索方向归结为求解LP:minfxTds.t. A1d0, Ed=0, (4.1.2)dj1, j=1,n显然d=0是可行解。由此可知，目标函数的最优值必小于等于0.瑞最优值小于0，则可得下降可行方向d，否则我们可证x是KKT点。Th2 考虑问题(4.1.2)，设x是可行解，在点x处有A1x=b1,A2x=b2，其中 A=A1A2,b=b1b2则x为KKT点的充要条件是问题（4.1.2）的目标函数最优值0。4.1.2确定一维搜索步长设xk是（1）的可行解，不妨看做第k次迭代的出发点，dk为xk处一个下降可行方向。后继点xk+1由下列迭代公式给出：xk+1=xk+kdkk的取值原则有两点：第一， 保持迭代点xk+kdk的可行性；第二， 使目标函数值尽可能减小。根据上述原则，可以通过求解下列一维搜索问题来确定步长：min fxk+dks.t. A(xk+dk）b Exk+dk=e (4.1.3)0问题(4.1.3)可作进一步简化。由于dk是可行方向，必有Edk=0Exk=e因此，(4.1.3)中第2个约束是多余的在点xk处，根据约束是否起作用，记A=A1,A2T，b=b1,b2T A1xk=b1 （4.1.4） A2xkb2 （4.1.5）于是，(4.1.3)中第1个约束可写成： A1xk+A1dkA2xk+A2dkb1b2 （4.1.6）由于dk为可行方向，A1dk0，A1xk=b1，0，A1xk+A1dkb1自然成立。约束（4.1.6）化为A2xk+A2dkb2 （4.1.7）这样，问题(4.1.3)化简为min fxk+dk A2xk+A2dkb2 （4.1.8）0根据（4.1.8）的约束条件，易求出的上限，令b=b2-A2xk (4.1.8)d=A2dk (4.1.9)由（4.1.5）知b0，（4.1.8）的约束可写成db0由此得到的上限max=minbididi0,当dib2，3）求解问题minfxTds.t. A1d0, Ed=0, (4.1.2)dj1, j=1,n，得最优解dk。4）如果fxTdk=0，计算结束，xk是KKT点；否则转5。5）利用（4.1.8）-（4.1.10）计算，然后再0, 上作一维搜索min fxk+dk s.t. 0max设k为最优解，令xk+1=xk+kdk6）置k=k+1，转24.3非线性约束问题可行方向法设是问题的一个可行解，令，即是点紧约束的指标集，设和在点可微，在点连续，如果，则是一改进的可行方向。4.4非线性不等式约束的Zoutendijk方法的计算步骤：1) 选取允许误差，求一初始可行点，令，转2)。2）确定指标集。3) 若，且，计算结束，取；若，且，令，转6)；若，转4)。4) 令，求解线性规划问题(4-2)的最优解；5) 若，计算结束，取；否则令，转6)。6) 求出线搜索问题的最优解，其中；令，返回2)。4.3 Zoutendijk法使用举例3求minfx=x1-12+x2-22+1=x12+x22-2x1-4x2+6, xR2s.t. g1x=2x1-x21g2x=x1+x22g3x=-x10g4x=-x204.4 matlab主程序function kexingfangxiangfaclc;x0=0;0;A=2.0 -1.0;1.0 1.0;-1.0 0.0;0.0 -1.0;b=1.0;2.0;0.0;0.0;c=0;kk=0;while c=b(i)-1e-3 %不起作用约束 k=k+1; A1(k,:)=A(i,:); b1(k,1)=b(i); end if Cb(i)-1e-3 %起作用约束 j=j+1; A2(j,:)=A(i,:); b2(j,1)=b(i); end end A1,b1 A2,b2 if isempty(A1(:,:) %A1为0向量矩阵 break end %pause f=dfxfun(x0); lb=-1 -1; ub=1 1; b0=zeros(size(b1); d=linprog(f,A1,b0,lb,ub); %求解最小化问题 if (abs(d)=1e-5) break end dd=A2*d; bb=b2-A2*x0; lamdmax=max(bb./dd); options=optimset(Display,off); lamda=fminbnd( (lamda)fun(lamda,d,x0),0,lamdmax,options); %求函数的局部极小值 if (isempty(lamda(:) break end x0=x0+lamda*d;endx0fvall=fun1(x0);x0=0,1;x,fval=fmincon( fun1,x0,A,b,options);x,fval;%目标函数求导后的函数functio