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

北京理工大学机械优化设计课程论文机械优化设计总概和Zoutendijk可行方向法举例专业班级：学生姓名：学号：指导教师：学院：2013年1月机械优化设计总概和Zoutendijk可行方向法举例1机械优化设计的一般步骤机械优化设计是将机械工程设计问题转化为最优化问题，然后选择恰当的最优化方法，利用电子计算机从满足要求的可行设计方案中自动寻找实现预期目标的最优设计方案。从中可以看到，机械优化设计包含两个部分，首先是把实际的机械设计问题用数学表达式加以描述，即转化为数学模型，然后是根据数学模型的特性，选择某种适当的优化设计方法及其程序，通过电子计算机求得最优解。2数学模型的建立首先是几个概念的建立。设计变量：可做变量处理的独立参数。目标函数：在设计中能最好地反映该项设计所追求的某些特定目标的评价标准。约束条件：对设计变量的取值加以某些限制的条件。根据实际问题的各种条件，将最优化问题抽象成数学模型，标准化为：maxx∈Enf(x)s.t.gu(x)≥0(u=1,2,⋯,m)hv(x)=0(v=1,2,⋯⋯,p𝑛)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坐标轮换法特点：坐标轮换法是最简单的直接优化方法之一，方法易懂，程序简单，无需求导，计算费用低。但可靠性差、效率低，当目标函数等值线具有脊线形态时可能失败。该方法适用于目标函数导数不存在或不易求得、维数较低(一般，l≤5)的情况。从坐标轮换法的迭代过程可以看出其探索路线较长，而且显然是问题的维数愈多求最优解得效率愈低。使用条件：对设计变量少的最优化问题有效，对设计变量较多的问题则不太适用。3.2.5变尺度法特点：DFP综合了梯度法和牛顿法的优点，对初始点要求不高，不必计算二阶偏导数矩阵及其逆阵，收敛速度快、效果好；缺点是需计算一阶偏导数，且由于舍入误差和一维搜索的不精确等原因，数值稳定性仍不够理想，有时因计算误差引起变尺度矩阵奇异而导致计算失败。使用条件：Broyden、Fletcher、Gold—tein、Shanno等于1970年提出了更具数值稳定性的BFGS变尺度法，适用于求解维数较高(10具有一阶偏导数的无约束优化问题，被认为是目前最成功的变尺度法。3.2.6鲍威尔法特点：该方法直接利用函数值逐次构造共轭方向，并在改进的算法中增加了判断原方向组是否需要替换和哪个方向需要替换，保证了共轭方向的生成，具有二次收敛性，收敛速度快，可靠性好，但编程较复杂。是直接搜索法中最为有效的算法之一。使用条件：适用于维数较高的优化问题。3.3多维有约束优化方法3.3.1随机方向搜索法特点：简单、方便，对目标函数性态无特殊要求，收敛较快，但计算精度不高，对严重非线性问题一般只能提供较近似的最优解。使用原则：适用于中小型无约束或有约束优化问题。3.3.2复合型法特点：具有单纯型法的特点，适合于求解n20的规划问题，但不能求解有等式约束的问题。对目标函数和约束函数无特殊要求，不必计算目标函数的梯度和二阶导数矩阵，方法简单、实用可靠、应用较广，有一定的收敛精度，但收敛速度一般。使用条件：不适于变量较多(n15)和有等式约束的优化，是求解非线性优化的有效方法之一，在优化设计中得到广泛应用。3.3.3可行方向法特点：1）可行方向法是用梯度去求解约束优化设计问题的一种有代表性的直接搜索方法。2）收敛速度快，效果较好，但程序比较复杂。使用条件：适用于大中型约束优化设计问题的求解。3.3.4惩罚函数法特点：1）将有约束问题转化为无约束问题，对大中型问题的求解均较适合，计算效果较好；2）基本构思简单，课求解等式约束，不等式约束以及两种约束兼有的优化问题。3）罚函数法又可分为内点法、外点法和混合法。内点法能给出一系列逐步改进的可行设计方案，但其初始点为严格的可行内点，初始惩罚因子、递减系数往往需试算才能确定，对收敛速度和迭代成败影响较大。外点法克服了内点法的一些缺点，且其初始点可任选。混合法在一定程度上综合了内点法和外点法的优点，其初始点可任选，可处理多个变量和多个函数，能解决具有等式和不等式约束的优化问题。使用条件：适用于中、小型非线性的约束优化。使用原则：应用罚函数法时，首先应取适当小的初始惩罚因子，再根据运算结果进行调整，此外，其递增系数也不宜选得过大。4可行方向法应用分析[2]可行方向法属于多维有约束优化方法直接解法的一种，可行方向法是最大的一类，它也是求解大型约束优化问题的主要方法之一。。其基本思想是给定一个可行点)(kx之后，用某种方法确定一个改进的可行方向kd，然后沿方向kd，求解一个有约束的线搜索问题，得极小点k，令kkkkdxx)()1(，如果)1(kx不是最优解，则重复上述步骤。可行方向法就是利用线性规划方法来确定kd的。可行方向法常用方法有Zoutendijk可行方向法，既约梯度法，Rosen梯度投影法，Frank-Wolfe方法。Zoutendijk可行方向法对线性和非线性的不等式约束问题均适用，但约束条件不含等式约束，是可行方向法中选择可行下降方向的主要方法之一。4.1线性不等式约束的Zoutendijk可行方向法[3]4.1.1利用起作用约束构造可行下降方向考虑NLP问题minf(x)s.t.Ax≥bx+c(4.1.1)Ex=eTh1设x̂是问题(4.1.1)的可行解，在点x̂处有A1x̂=b1,A2=b2,其中A=[A1A2],b=(b1b2)则非零向量d为x̂处的可行方向的充要条件是A1d≥0,Ed=0.Zoutendijk法把确定搜索方向归结为求解LP:min∇f(x)Tds.t.𝐴1𝑑≥0,Ed=0,(4.1.2)|dj|≤1,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+λkdkλk的取值原则有两点：第一，保持迭代点xk+λkdk的可行性；第二，使目标函数值尽可能减小。根据上述原则，可以通过求解下列一维搜索问题来确定步长：minf(xk+λdk)s.t.A(xk+λdk）≥bE(xk+λdk)=e(4.1.3)λ≥0问题(4.1.3)可作进一步简化。由于dk是可行方向，必有Edk=0Exk=e因此，(4.1.3)中第2个约束是多余的在点xk处，根据约束是否起作用，记A=(A1,A2)T，b=(b1,b2)TA1xk=b1（4.1.4）A2xkb2（4.1.5）于是，(4.1.3)中第1个约束可写成：[A1xk+λA1dkA2xk+λA2dk]≥[b1b2]（4.1.6）由于dk为可行方向，A1dk≥0，A1xk=b1，λ≥0，A1xk+λA1dk≥b1自然成立。约束（4.1.6）化为A2xk+λA2dk≥b2（4.1.7）这样，问题(4.1.3)化简为minf(xk+λdk)A2xk+λA2dk≥b2（4.1.8）λ≥0根据（4.1.8）的约束条件，易求出λ的上限，令b̂=b2−A2xk(4.1.8)d̂=A2dk(4.1.9)由（4.1.5）知b̂0，（4.1.8）的约束可写成{λd̂≥b̂λ≥0由此得到λ的上限λmax={min{b̂id̂i|dî0,当dî0}∞，当dî≥0（4.1.10）问题（4.1.3）于是化为：min𝑓(𝑥𝑘+𝜆𝑑𝑘)s.t.0≤λ≤𝜆𝑚𝑎𝑥(4.1.11)于是，给定问题（4.1.1）和一个可行点，可以通过求解问题（4.1.2）得到下降可行方向，通过求解问题（4.1.11）确定沿此方向进行一维搜索的步长。4.2线性不等式约束的Zoutendijk可行方向法的计算步骤：1）求一初始可行解xk。，令k＝1，转2。2）对于可行点xk处对A和b进行分解，[A1A2]和(b1b2)，使得A1xk=b1,A2xkb2，3）求解问题min𝛻𝑓(𝑥)𝑇𝑑s.t.𝐴1𝑑≥0,Ed=0,(4.1.2)|dj|≤1,j=1,…,n，得最优解dk。4）如果𝛻𝑓(𝑥)𝑇𝑑𝑘=0，计算结束，xk是KKT点；否则转5。5）利用（4.1.8）-（4.1.10）计算max，然后再[0,max]上作一维搜索min𝑓(𝑥𝑘+𝜆𝑑𝑘)s.t.0≤λ≤𝜆𝑚𝑎𝑥设λk为最优解，令xk+1=xk+λkdk6）置k=k+1，转24.3非线性约束问题可行方向法设x是问题niRmifxxx,,2,10,)(gs.t.)(min的一个可行解，令0)(,|x