优化设计约束优化方法1.ppt

1、第六章 约束优化方法,第一节 概述,第二节 随机方向法,第三节 复合形法,第四节 可行方向法,第五节 惩罚函数法,根据约束条件的不同，优化问题可以分为三种类型，其数学模型分别为： 1、不等式约束优化问题（IP型）,第一节 约束优化方法概述,2、等式约束优化问题（EP型）,3、一般约束优化问题（GP型）,求解上述模型的方法即约束优化方法。 包括直接解法、间接解法,1、适用条件 仅含不等式约束的问题，即IP问题。 2、直接解法的基本思路 在约束条件所限制的可行域内直接求解目标函数的最优解。即选取初始点、确定搜索方向及适当步长进行搜索，得到一个使目标函数下降的新点；反复进行，直到满足收敛条件。 即：

2、,一、约束优化问题的直接解法,每次产生的迭代点必须满足可行性与适用性两个条件。 可行性：迭代点必须在约束条件所限制的可行域内，即满足 gu(x) 0, u=1,2,p 适用性：当前迭代点的目标函数值较前一点是下降的，即满足 F(xk+1)F(xk),步长,可行搜索方向,前述可行搜索方向的产生办法取决于各种算法，约束坐标轮换法、复合形法、可行方向法、广义简约梯度法等。,3、采用直接解法的有关算法,4、直接解法的特点 （1）每次迭代均能获得一个更好的点； （2）若为凸规划（凸目标函数、凸可行域），则可保证获得全域最优，否则为局部最优解； 取不同的初始点分别计算以便获得多个局部最优解，再从中选优；

3、（3）可行域有界、非空集，且目标函数有定义。,二、约束优化问题的间接解法,1、适用条件 该方法可以求解等式约束优化问题（EP）和一般约束优化问题（GP）。 2、基本思路 将约束优化问题通过一定的方法进行改变，将约束优化问题转化为无约束优化问题，再采用无约束优化方法进行求解。 如将最具一般形式的GP问题转化为：,转换后的新目标函数,加权因子,约束函数经加权处理后构成的复合函数或泛函,3、求解过程,对构成的新目标函数进行无约束优化求解；然后改变加权因子，可以不断调整设计点，使其逐步逼近约束边界，从而间接地获得原约束问题的最优解。,4、相关算法 如惩罚函数法、增广乘子法等。,5、间接法的特点 （1）

4、算法日益成熟、可靠； （2）可以有效处理等式约束问题； （3）加权因子的选取困难； 其选择影响收敛速度、计算精度及计算的成败。,第二节 随机方向法,基本思路 利用计算机产生的随机数所构成的随机方向进行搜索，产生的新点必须在可行域内，即满足直接法的特性。 优点 对目标函数的性态无特殊要求； 收敛速度较快，是求解小型机械优化问题的一种十分有效的方法。 随机方向法，是约束最优化问题的一种常用的直接求解方法。它和随机梯度法等都属于约束随机法。,在约束可行域S内选取一个初始点X(0)，在不破坏约束的条件下以合适的步长，沿X(0)点周围几个不同的方向（以某种形式产生的随机方向）进行若干次探索，并计算各方向

5、上等距离（步长 ）点的函数值，找出其中的最小值f(X(l)及点X(l)。 若f（X(l)）f（X(0)），则继续沿方向（X(l)-X(0)）以适当的步长向前跨步，得到新点X(1)，若f（X(1)）老f（X(l)），则将新的起点移至X(1) ，重复前面过程。 否则应缩短步长，直至取得约束好点。如此循环下去。当迭代的步长已经很小时，则表明已经逼近约束最优点。达到计算精度要求时，即可结束迭代计算。 随机方向探索法的一般迭代计算公式为： X(k+1)=X(k)+d(k) (k=0,1,2,) 式中为步长，d(k) 为第k次迭代的可行搜索方向。 可行搜索方向产生的条件. .,一、基本原理,d,二、算法技

6、术,1、随机数的产生 可以利用各种计算机语言的随机函数，也可利用随机数的数学模型自行产生。 2、初始点的选择 无法人工给出初始点时，可以用随机选择的方法得到。 （1）产生一个随机点,3、随机搜索方向的产生 即从k（ kn）个随机方向中选择一个较好的方向。 ,（2）判断点x可行否，不可行则重新产生。,01之间的随机数,维数,（3）去除k个点中的非可行点，选出目标函数值最小的点xL。 （4）比较xL和x0，若f(xL)f(x0)，则二者连线为搜索方向；否则，缩小0 ，至（1）重新开始，反复进行直到成功。若0太小（10-6），则x0为局部低点，更换初始点再从头开始。,随机搜索方向的产生,（1）产生伪

7、随机数rij（i=1，2，n；j=1，2，k），并构成单位随机矢量ej，即：,（2）取试验步长0，计算k个随机点,. .,4、搜索步长的确定 d确定后，x0 xL，采加速步长（如每次增30%）搜索，即 =,5、收敛条件 若获得新点x，与前一点x0的关系满足,则迭代终止。,三、计算步骤及框图,计算实例,四、随机方向法 计算实例,求约束优化问题,s.t.,解： 可获得最优解 x*=(-0.0027, -3.0)T f(x*)=-3,复合形法是求解约束非线性最优化问题的一种重要的直接方法。来源于用于求解无约束非线性最优化问题的单形替换法，是单形替换法在约束优化问题中的发展。 在求解无约束问题的单形替

8、换法中，不需计算目标函数的梯度，而是靠选取单纯形的顶点并比较各顶点处目标函数值的大小，来寻找下一步的探索方向的。 复合形法中，上述原理与单形替换法相同。只是，复合形各顶点的选择和替换，不仅要满足目标函数值的下降，还应当满足所有的约束条件。,第三节 复合形法,一、复合形法的基本思想,在可行域内构造一个具有k个顶点的初始复合形。,对该复合形各顶点的目标函数值进行比较，去掉目标函数值最大的顶点（称最坏点），然后按一定法则求出目标函数值下降的可行的新点，并用此点代替最坏点，构成新的复合形，复合形就向最优点移动一步，直至逼近最优点。,1、复合形的顶点数目 k通常取 n+1k2n 2、初始复合形的产生办法

9、 可以有多种方法完成初始复合形的产生。 （1）由设计者确定k个可行点构成初始复合形 用于维数较低的小型优化问题。 （2）由设计者指定一个可行点，其余用随机法产生 即随机产生剩余的k-1顶点，对于在非可行域外的点则可将其往可行点靠拢，即调入可行域内。 （3）由计算机自动生成初始复合形的全部顶点 先随机产生一个可行点，再象（2）那样产生剩余的k-1个随机点，然后再把其中的非可行点逐一调入可行域内。,二、初始复合形的形成,（1）产生一个随机点 xi= ai +i (bi - ai) i=1, 2, ., n i为（0，1）区间内产生的均匀分布的随机数，依据上式产生点X (1) =x1, x2, ,x

10、nT 。,3、生成可行点,（2）产生其余k-1个顶点 （3）位置重新排列 将产生的k个随机点进行判断是否在可行域内，重新排列，将可行点依次排在前面。 （3）将非可行点调入可行域 如有q个顶点X (1)、X (2)、X (q)是可行点，其它k-q个为非可行点。 对X (q+1)，将其调入可行域的步骤 ,这个新点X(q+1)实际就是Xc与原X(q+1)两点连线的中点，如图。若新的X(q+1)点仍为非可行点，按上式再产生X(q+1)，使它更向Xc靠拢，最终使其成为可行点。,按照这个方法，同样使X (q+2)、X (q+3)、X (K)都变为可行点，这k个点就构成了初始复合形。,a）计算q个点集的中心

11、X c； b）将第q+1点朝着点Xc的方向移动，按下式产生新的X (q+1)，即： X(q+1)= Xc + 0.5 (X(q+1) - Xc),将非可行点调入可行域,主要搜索方法有三个： 反射； 收缩； 压缩。,在可行域内生成了初始复合形后，可采用不同的搜索方法来改变其形状，使复合形逐步向约束最有点趋近。,三、复合形法的搜索方法,（2）计算除xH外其余各顶点的中心xc，即,分以下几个步骤： （1）确定最好点xL、最坏点xH和次坏点xG，即,1、反射,（3）计算反射点xR，即,其中，是反射系数，一般， .,不可行，则将缩至0.7倍，重新反射，直到f(xR)f(xH)为止。,可行，则进一步比较：

12、若f(xR)f(xH)，则用xR取代xH，完成一次迭代。若f(xR) f(xH)，则将缩至0.7倍，重新反射，直到f(xR)f(xH)为止。,（4）判别反射点的位置,即，反射成功的条件为,若xR下降较多，如f(xR)f(xC)，则可采用扩张的方法继续向前移动，可能找到更好的点xE。,若xE可行且f(xE)f(xR)，则扩张成功，用xE取代xR，可构成新的复合形；否则放弃。,扩张系数=1,其中，收缩系数=0.7 若f(xK)f(xH)，则收缩成功，可用xK取代xH，构成新的复合形。,当在中心点xC外找不到好的反射点，可以在xC以内找，即,2、收缩,若某顶点压缩后在可行域外，可将其继续向xL靠拢，

13、直到其回到可行域。,若上述方法均无效，可让复合形各顶点向xL靠拢，即压缩复合形。,3、压缩,1、确定k值，产生初始复合形； 2、比较各顶点，排序； 3、计算除xH外的中心点xC。若可行，则继续，否则则重新确定设计变量的下限和上限，即a=xL，b=xC，转而重新构造初始复合形；,4、反射，反复反射，直至成功。 5、收敛条件,四、复合形法的迭代步骤,只含反射功能的复合形法迭代步骤为：,若满足，则输出xL。否则，至步骤2继续。,复合形法程序框图,1、复合形法是求解约束非线性最优化问题的一种直接方法，仅通过选取各顶点并比较各点处函数值的大小，就可寻找下一步的探索方向。 但复合形各顶点的选择和替换，不仅

14、要满足目标函数值下降的要求，还应当满足所有的约束条件。 2、复合形法适用于仅含不等式约束的问题。,五、复合形法的方法特点,复合形法例题,经检验，这四点均满足约束条件。,复合形法例题,解： (1)复合形顶点数为k=2n=4，给定初始反射系数 =1.3和允许误差。 (2)用任选点法确定复合形的4个顶点：,（4）除最坏点以外，其余各顶点的中心为： X(c)= (X(2)+X(3)+X(4)/3 = 2 4.63T 经检验， X(c) 满足约束条件，为可行点。,（5）求反射点，即： X(r) = X(c) + (X(c) - X(b) = 3.3 3.499T 经检验， X(r) 满足约束条件，为可行点。,（6）反射点的函数值f(X(r) = 24.59。经比较可见，反射点好于最坏点。于是以X(r) 代替X(b)，并和原复合形中的顶点X(2)， X(3)， X(4)构成新的复合形。 新复合形顶点为：,X(1) = 3 3.499T X(2) = 1 4T X(3) = 2 6.4T X(4) = 3 3.5T,第一次迭代结束。经判别，不符合收敛条件，则进入第二次迭代。,第二次迭代开始时，各顶点的函数值为： f(X(1) = 24.59f(X(2) =47 f(X(3) =46.56