有约束优化方法讲义

《有约束优化方法讲义》由会员分享，可在线阅读，更多相关《有约束优化方法讲义（103页珍藏版）》请在金锄头文库上搜索。

1、第五章 有约束优化方法,5-1 引言 5-2 随机方向法 5-3 复合形法 5-4 可行方向法 5-5 惩罚函数法,5-1 引言,机械优化设计中的问题，大多数属于约束优化设计问题，其数学模型为,上一章讨论的都是无约束条件下非线性函数的寻优方法，但在实际工程中大部分问题的变量取值都有一定的限制，也就是属于有约束条件的寻优问题。与无约束问题不同，约束问题目标函数的最小值是满足约束条件下的最小值，即是由约束条件所限定的可行域内的最小值。只要由约束条件所决定的可行域是一个凸集，目标函数是凸函数，其约束最优解就是全域最优解。否则，将由于所选择的初始点的不同，而探索到不同的局部最优解上。在这种情况下，探索

2、结果经常与初始点的选择有关。为了能得到全局最优解，在探索过程中最好能改变初始点，有时甚至要改换几次。,可行域D为凸集,可行域D为非凸集,根据求解方式的不同，约束优化设计问题可分为:直接解法、间接解法。,（1）直接法 这种方法主要用于求解仅含不等式约束条件的最优化问题。其基本思想是在可行域内按照一定的原则直接探索出它的最优解，而不需要将约束最优化问题转换成无约束问题去求优。设计一个直接解法的迭代程序，除应具有下降性、收敛性外，还必须具有可行性，即每次迭代后得到的新点都应在可行域内。 直接法包括：随机试验法、随机方向探索法、复合形法、可行方向法、可变容差法和简约梯度法等。,直接解法思路是在m个不等

3、式约束条件所确定的可行域内，选择一个初始点，然后决定可行搜索方向 d 且以适当的步长 ，进行搜索，得到一个使目标函数值下降的可行的新点，即完成一次迭代。再以新点为起点，重复上述搜索过程，直至满足收敛条件。,步长,可行搜索方向,可行搜索方向:当设计点沿该方向作微量移动时，目标函数值将下降，且不会越出可行域。,（2）间接法 这种方法对于不等式约束问题和等式约束问题均有效。其基本思想是按照一定的原则构造一个包含原目标函数和约束条件的新目标函数，再对新的目标函数进行无约束优化计算，从而间接地搜索到原约束问题的最优解。即约束最优化问题的求解转换为无约束最优化问题求解。间接法包括：罚函数法、内点罚函数法、

4、外点罚函数法、混合罚函数法、增广乘子法等。,间接解法的基本迭代过程是：,间接解法框图,该问题的约束最优解为,可以用解析法求 最小值，即令,间接解法存在的主要问题是，选取加权因子较为困难。,5-2 随机方向法,基本思想：在可行域内选择一个初始点，利用计算机产生的随机数的概率特性，产生若干个随机方向，并从中选择一个能使目标函数值下降最快的随机方向作为寻优方向，以该方向上的最优点（该最优点必须在可行域内）作为初始点进行下一步探测。重复进行以上步骤，直到满足收敛条件为止。 随机方向法，对目标函数的性态无特殊要求，程序简单，使用方便，是约束最优化问题的一种常用的直接求解方法。它对求解小型的机械优化设计问

5、题十分有效。,约束随机方向探索法的基本原理,其基本原理如图所示，在约束可行域D内选取一个初始点X（0），在不破坏约束的条件下以合适的步长a0沿 X（0）点周围几个不同的方向（以某种形式产生的随机方向）进行若干次探索，并计算各方向上等距离（步长a0）点的函数值，找出其中的最小值f（X（L）及点X（L）。若f（X（L）f（X（0），则继续沿方向（X(L)-X(0) 以适当的步长a向前跨步，得到新点X(1)，若f（X(1)）f（X(L)），则将新的起点移至X(1)，重复前面过程。否则应缩短步长a，直至取得约束好点。如此循环下去。当迭代的步长已经很小时，则表明已经逼近约束最优点。达到计算精度要求时，即

6、可结束迭代计算。,一、随机数的产生,1、伪随机数,在计算机内，随机数通常是按一定的数学模型进行计算后得到的。这样的随机数称伪随机数。,2、随机数的特性有较好的概率统计特性 抽样的随机性； 分布的均匀性； 前后数之间的独立性； 周期性长。,下面介绍一种常用的产生伪随机数的数学模型：,则,q 为（0，1）区间内的伪随机数。利用q，容易求得任意区间（a，b）内的伪随机数，其计算公式为：,二、 随机产生初始点：, 输入设计变量的上、下限值：ai x i bi ，（i=1,2,n）； 在区间0,1中产生n个伪随机数 qi ，计算x的各分量 判断随机点是否可行，若随机点x为可行点，则取初始点 ；若随机点x

7、为非可行点，则转步骤重新计算，直到产生的随机点是可行点为止。,三、 随机产生搜索方向：,2、取一 试验步长 ，按下式计算k个随机点,3、检验k个随机点 是否为可行点，除去非可行点， 计算余下的点的目标函数值，比较其大小，选出目标 函数值最小的点 。,4、比较 和 两点的函数值的大小，若 则取 和 两点的连线方向；若 ，则将步长 缩小，转步骤1重新计算，直至 为止。如果 缩小到很小，仍然找不到一个 ，使则说明 是一个局部极小点，此时可更换初始点，转步骤1。,四、搜索步长的确定,可行搜索方向d确定后，初始点移至 点，即 从 点出发沿d方向进行搜索，所用步长 一般按加速步长法来确定。所谓加速步长法是

8、指依次迭代的步长按一定的比例递增的方法。各次迭代的步长按下式计算,随机方向法评价,5-3 复合形法,复合形法是求解约束非线性最优化问题的一种重要的直接方法。它来源于用于求解无约束非线性最优化问题的单纯形法，实际上是单纯形法在约束问题中的发展。如前所述，在求解无约束问题的单纯形法中，不需计算目标函数的梯度，而是靠选取单纯形的顶点并比较各顶点处目标函数值的大小，来寻找下一步的探索方向的。在用于求解约束问题的复合形法中，复合形各顶点的选择和替换，不仅要满足目标函数值的下降，还应当满足所有的约束条件。,例 设有一个约束优化问题的数学模型,在可行域内任选三个初始点X(1)、X(2)、X(3)，连接这三点

9、形成一个三角形，此三角形称为初始复合形。计算各个顶点函数值F(X(1)、 F(X(2)、F(X(3)，找出最大值，记为坏点X(H)。最小值，记为最好点X(L)。由此可以推出，在次好点和好点连线与坏点反向一侧的各点应具有较小的目标值。,取次好点和好点连线的中点为X（0）。,令：X(4)= X(0)+(X(0)-X(H),称X(4)为映射点，记为X(R)，为映射系数，通常取=1.3，可根据实际情况进行缩减。,一般情况下，映射点的函数值比坏点的函数值要小，即F(X(R) F(X(H)。若满足可行域，则用X(R)代替X(H)构成新的复合形。如此反复迭代直到找到最优解。,在迭代过程中，按映射系数=1.3

10、得到的映射点，不一定满足适用性和可行性，如出现此情况，将映射系数减半，重新取得X(R)， 使它满足适用性和可行性。,基本思想：在可行域中选取K个设计点 （n+1K2n）作为初始复合形的顶点。比较各顶点目标函数值的大小，去掉目标函数值最大的顶点(称最坏点)，以坏点以外其余各点的中心为映射中心，用坏点的映射点替换该点，构成新的复合形顶点。 反复迭代计算，使复合形不断向最优点移动和收缩，直至收缩到复合形的顶点与形心非常接近，且满足迭代精度要求为止。,一、初始复合形的构成复合形的顶点K通常取n+1K2n个。 1、对于维数较低的优化问题，由于顶点数目较少，可以由设计者决定k个可行点，构成初始复合形。 2

11、、对于维数较高的问题，由设计者选定一个可行点，其余的（K-1）个可行点用随机法产生。（1）产生K-1个随机点xi= ai +i (bi - ai) i=1,2,.,n i为（0，1）区间内产生的均匀分布的随机数，需要n个随机数产生一个点X (1)。同样，产生其它的随机点X (2)、X (3)、X (K-1)。,（2）将非可行点调入可行域将产生的K-1个随机点进行判断是否在可行域内，重新排列，将可行点依次排在前面，如有q个顶点X (1)、X (2)、X (q)是可行点，其它K-q个为非可行点。对X (q+1)，将其调入可行域的步骤是：（a）计算q个点集的几何中心X (s), ；（b）将第q+1点

12、朝着点X （s）的方向移动，按下式产生新的X (q+1)，即X(q+1)= X(s)+0.5 (X(q+1)-X(s),这个新点X(q+1)实际就是X(s)与原X(q+1)两点连线的中点，如图。若新的X(q+1)点仍为非可行点，按上式再产生X(q+1)，使它更向X(s)靠拢，最终使其成为可行点。,按照这个方法，同样使X (q+2)、X (q+3)、X (K)都变为可行点，这K个点就构成了初始复合形。,如果可行域为非凸集，则改变设计变量的上下限值，重新产生各顶点。,中心点为非可行点的情况,3、由计算机自动生成初始复合形的全部顶点。,二、复合形法的搜索方法,1、反射,反射成功条件,2、扩张,3、收

13、缩,4、压缩,二、复合形法的迭代步骤 （1）构造初始复合形； （2）计算各顶点的函数值F(X(j)，j=1,2,.,K。选出好点X(L)、坏点X(H)次坏点X(G)。,（3）计算除坏点外的其余各顶点的中心点X(c)。,（4）可行域为非凸集，重新确定设计变量的下限和上限值，即令a=X(L) ,b=X（c），然后转步骤（1），重新构造初始复合形。,（5）计算映射点X(R),（6）构造新的复合形计算映射点的函数值F(X(R)，并与坏点的函数值F(X(H)比较，可能存在两种情况：1）映射点优于坏点F(X(R) F(X(H)这种情况由于映射点过远引起的，减半映射系数，若有F(X(R) F(X(H)，这又

14、转化为第一种情况。,再转回本步骤的开始处，直到构成新的复合形。,（7）判断终止条件 1)各顶点与好点函数值之差的均方根值小于误差限，即,如果不满足终止迭代条件，则返回步骤（2）继续进行下一次迭代；否则，可将最后复合形的好点X(L)及其函数值F(X(L)作为最优解输出。,方法特点 （1）复合形法是求解约束非线性最优化问题的一种直接方法，仅通过选取各顶点并比较各点处函数值的大小，就可寻找下一步的探索方向。但复合形各顶点的选择和替换，不仅要满足目标函数值下降的要求，还应当满足所有的约束条件。 （2）复合形法适用于仅含不等式约束的问题。,5-4 可行方向法,可行方向法是求解大型不等式约束优化问题的主要

15、方法之一。基本思想：这种方法的基本原理是在可行域内选择一个初始点 ，当确定了一个可行方向d和适当的步长后，按式:,进行迭代计算,迭代点既不超出可行域,又使目标函数的值有所下降。在不断调整可行方向的过程中，使迭代点逐步逼近约束最优点。,综合上述可知，可行方向法的求优过程可归纳为：,从可行点 出发，找到一个可行下降方向 和 一个适当的 ，使,满足,极值点所处位置不同的情况,1.可行方向法的搜索策略,* 其特点是注意到约束最优点通常在约束边界上： 为此，可先找出一个边界点，然后沿边界搜索;,第一步迭代都是从可行的初始点 出发，沿点的负梯度 方向，将初始点移动到某一个约束面（只有一个起作用的约束时）上, 或约束面的交集（有几个起作用的约束时）上。,根据约束函数和目标函数的不同性状，分别采用以下三种策略继续搜索。,（2） 沿非线性约束面的搜索,