第五章约束优化方法课件

1

第五章约束优化方法

5.1约束优化问题的最优解5.2约束优化问题极小点的条件

5.3常用的约束优化方法

5.3.1约束坐标轮换法5.3.2约束随机方向法5.3.3复合形法5.3.5惩罚函数法1

第五章约束优化方法5.1约束优化问题的最优解2概述约束优化问题最优解最优值最优点约束最优解和无约束最优解无论是在数学模型上还是几何意义上均是不同的概念2概述约束优化问题最优解最优值最优点约束最优解和无约束最优解3等值线等值线族的中心无约束最优解解：等值线的共同中心.数学模型:3等值线等值线族的中心无约束最优解解：等值线的共同中心.数学4数学模型:可行域约束最优解

4数学模型:可行域约束最优解

5无约束最优点约束最优点5无约束最优点约束最优点6约束优化问题的类型

1.不等式约束优化问题(IP型)2.等式约束优化问题(EP型)3.一般约束优化问题(GP型)6约束优化问题的类型1.不等式约束优化问题(IP型)2.7约束优化方法分类约束优化方法

约束坐标轮换法直接法：约束随机方向法

复合形法间接法：惩罚函数法

直接法：设法使每一次迭代产生的新迭代点限制在可行域内，且一步一步的降低目标函数值，直至最后获得一个可行域内的约束最优解。间接法：将约束优化问题通过一定形式的变换，转化为无约束优化问题，然后采用约束优化方法进行求解。7约束优化方法分类约束优化方法85.3.1约束坐标轮换法基本思想:与无约束坐标轮换法类似,依此沿坐标轴方向寻优,逐步逼近最优点。85.3.1约束坐标轮换法基本思想:与无约束坐标轮换法9任取一个初始点取初始步长α0沿e1方向检查可行性:适用性:检查......加速步长检查可行性:适用性:9任取一个初始点取初始步长α0沿e1方向检查可行性:适用性10沿e2方向检查可行性:适用性:检查可行性:适用性:检查可行性:适用性:检查可行性:适用性:10沿e2方向检查可行性:适用性:检查可行性:适用性:检查可11沿e1方向检查可行性:适用性:检查可行性:适用性:沿e2方向检查可行性:适用性:检查......11沿e1方向检查可行性:适用性:检查可行性:适用性:沿e212沿坐标轴方向找不到合适的点:缩减初始步长

α0←0.5α0

继续迭代终止准则:

α0≤ε约束坐标轮换法与无约束坐标轮换法的区别：①步长

无约束:最优步长

约束:加速步长②对每一个迭代点的检查

无约束:检查适用性

约束:检查适用性和可行性③终止准则

无约束:点距准则

约束:步长准则12沿坐标轴方向找不到合适的点:约束坐标轮换法与无约束坐标轮13特点:约束坐标轮换法具有算法明了、迭代简单、便于设计者掌握运用等优点。但是，它的收敛速度较慢，对于维数较高的优化问题(例如10维以上)很费机时。另外，这种方法在某些情况下还会出现“死点”的病态，导致输出伪最优点。

避免输出伪最优点的办法:1、输入不同的初始点2、用不同的不长多次计算13特点:约束坐标轮换法具有算法明了、迭代简单、便于设计者掌14基本原理：典型的“瞎子爬山”式的数值选代解法。在可行域内，任选初始点x(0)，以给定的步长a=a0

，沿按某方法产生的随机方向S(1)取探索点x=x(0)+aS(1），若该点同时符合下降性（F(x)<F(x(0)))和可行性（x∈D)则表示x点探索成功。并以它为新的起始点，继续按上面的迭代公式在S(1）方向上获取新的成功探索点……..

5.3.2约束随机方向法14基本原理：典型的“瞎子爬山”式的数值选代解法。在可行域内155.3.2约束随机方向法任取一个初始点取初始步长α0利用随机函数构成随机方向S(1)

检查可行性:适用性:检查若m个方向都不行,则减小步长:α0←0.5α0终止准则:

α0≤ε155.3.2约束随机方向法任取一个初始点取初始步长α016说明当在某个转折点处沿m个(预先限定的次数)随机方向试探均失败，则说明以此点为中心，α0为半径的圆周上各点都不是适用、可行点。此时，可将初始步长α0缩半后继续试探。直到α0≤ε，且沿m个随机方向都试探失败时，则最后一个成功点(如图中的x(3))就是达到预定精度ε要求的约束最优点，迭代即可结束。m是预先规定在某转折点处产生随机方向所允许的最大数目。一般可在50~500范围内选取。约束随机方向法的搜索方向比坐标轮换法要灵活得多。当预定的随机方向限定数m足够大时，它不会像约束坐标轮换法那样出现“病态”而导致输出伪最优点。

16说明17随机搜索方向的产生在（a,b）之间的随机数：yi=ai+

(bi–ai)

（-1,1）之间的随机数：yi=2-1设是在区间(一l，1)上的两个随机数。将它们分别作为坐标轴上的分量所构成的向量即为相应的二维随机向量，其单位向量：同理，n维问题,随机方向的单位向量：在算法语言所使用的函数库中，有一种随机函数RND(X)。利用这一随机函数可在程序运行过程中产生一个0到1之间的随机数。

(i＝l，2，…，n)17随机搜索方向的产生在（a,b）之间的随机数：yi=a18约束随机方向搜索法的特点：对目标函数的性态无特殊要求，程序设计简单，使用方便。在维数较少的情况下是一种十分有效的方法，适用于小型问题。18约束随机方向搜索法的特点：195.3.3复合形法基本思想：在可行域中选取K个点作为一复合形（多面体）的K个顶点。比较各点函数值的大小，去掉函数值最大所对应的最坏点，而代之最坏点的映射点构成新的复合形。不断重复上述过程，使复合形不断向最优点移动和收缩，直至满足选代精度为止。

132X0X(R)n+l≤k≤2n195.3.3复合形法基本思想：在可行域中选取K个点作为20[引例]

设有一约束优化问题的数学模型20[引例]设有一约束优化问题的数学模型21一、复合形法的基本思想步骤：第一步：初始复合形的构成

顶点X(1)、X(2)、X(3)第二步：对复合形进行

调优迭代计算顶点X(1)、X(2)、X(3)

F1>F2>F3

↓↓

X(H)

X(L)

坏点好点先求出除坏点外，其余各点构成的图形的形心点X0再求坏点X(H)相对于形心点X0的映射点

X(R)132X0X(R)21一、复合形法的基本思想步骤：132X0X(R)22步骤：第一步：初始复合形的构成

第二步：对复合形进行调优迭代计算

形心点X0

映射点

X(R)

α:反射系数，一般开始是取α=1.3132检查可行性:适用性:新复合形4点的映射复合形的收缩22步骤：132检查可行性:适用性:新复合形4点的映射23二、初始复合形的构成

方法一:试凑法方法二:随机产生(1)产生K个随机点随机数

(i＝l，2，…，n)(2)将非可行点调入可行域123423二、初始复合形的构成方法一:试凑法随机数24终止条件:24终止条件:25例:用复合形法求解下例约束最优化问题，迭代精度取

解：取复合形的顶点数:(1)获得初始复合形:本例采用人为给定四个点检验各点是否可行：将各点的坐标值代入以上三个约束方程，均满足约束要求，这四个点为可行点，用作初始复合形的四个顶点25例:用复合形法求解下例约束最优化问题，迭代精度取26(2)迭代计算获得新复合形计算复合形各顶点目标函数值，

定出最坏点最好点计算除坏点外其余各顶点的中心

将代入诸约束条件均满足，可知在可行城内。

取，求坏点的映射点

在可行域内

26(2)迭代计算获得新复合形计算复合形各顶点目标函数值27计算并与比较：

用替换，亦即替换构成新的复合形：

比较各点目标函数值，定出最坏点:最好点:

（3）检验迭代终止条件

27计算并与比较：用替换282829复合形法的特点:

对目标函数及约束函数无特殊要求，适应性强，计算量一般，收敛较快，适用中小型问题。是现有解不等式约束优化问题的一种重要的直接法。29复合形法的特点:305.3.5惩罚函数法将约束优化问题通过一定形式的变换，转化为无约束优化问题，然后采用约束优化方法进行求解转化必须满足条件：1、不破坏原约束问题的约束条件，

2、最优解必须归结到原约束问题的最优解上去。约束优化问题的间接法有:消元法、拉格朗日乘子法、

惩罚函数法等.305.3.5惩罚函数法将约束优化问题通过一定形式的变换31minφ(x，r(k)，m(k)) (5.56)x∈Rn式中，φ(x，r(k)，m(k))为增广函数，称为惩罚函数，简称罚函数

将一般约束优化问题数学模型minF(x)x∈Rn：gu(x)≥0，u＝l，2，…，phv(x)=0，v=1，2，…，q转化成为一个如下的无约束优化问题构造的新目标函数一般形式为惩罚函数法惩罚项31minφ(x，r(k)，m(k)) (5.56)式中，φ32按照惩罚函数构成的形式不同，惩罚函数法又分为三种：1、内点惩罚函数法2、外点惩罚函数法3、混合惩罚函数法32按照惩罚函数构成的形式不同，惩罚函数法又分为三种：33一、内点惩罚函数法基本思想：将新目标函数定义于可行域内，序列迭代点在可行域内逐步逼近原目标函数约束边界上的最优点。将约束优化问题：

minF(x)x∈:gu(x)≥0(u=12……m)转化为无约束优化问题

其中：r(1)>r(2)>r(3)…>r(k)…>0是一个递减的正值数列：

r(k)＝Cr(k-1)，

0＜C＜1

(k)=0

33一、内点惩罚函数法基本思想：将新目标函数定义于可行域内，34内点惩罚函数法的思路:当X由可行域内靠近任一约束边界时,惩罚项值趋于无穷大,所以它就像围墙一样阻止迭代点越出约束边界.条件1：不破坏原约束问题的约束条件34内点惩罚函数法的思路:条件1：不破坏原约束问题的约束条件35minф(x,r(k))=min{F(x)+r(k)∑（1/gu(x)）}条件2：最优解必须归结到原约束问题的最优解上去35minф(x,r(k))=min{F(x)+r(k)36解：若用内点法求解此约束最优化问题，由式知惩罚函数为将函数对求导，得:令:解得无约束极小值的点列为

:例:用内点法求解

的约束最优化问题。

无约束极小值点列相应的惩罚函数值为

36解：若用内点法求解此约束最优化问题，由式知惩罚函数为将函373738序列极小点都在可行域内38序列极小点都在可行域内39初始点x(0)的确定

自定法:搜索法

先任取一个设计点x(k)；计算x(k)点的诸约束函数值gu(x(k))，u＝1，2，…，p若：构造：按照该数学模型解出的最优点x*，至少比原设计点x(k)多满足一个约束条件

重复数次，直到所有的约束条件都得到满足，最终可取得在可行域内部的初始点x(0)。39初始点x(0)的确定若：构造：按照该数学模型解出的最优40

关于几个参数的选择(1)初始罚因子r(0)的选取一般可取初始罚因子r(0)＝1~50也有建议取：(2)递减系数C的选择

通常建议取C＝0.1~0.540关于几个参数的选择一般可取初始罚因子r(0)＝1~5041内点惩罚函数法的特点:在给定一个可行初始方案后，能求出一系列逐步得到改进的可行的设计方案。但只适用于解不等式约束优化问题，且初始点须在可行域内。41内点惩罚函数法的特点:42=

已知约束优化问题:试写出内点罚函数,并选出初始迭代点.内点罚函数:例：42=已知约束优化问题:试写出内点罚函数,并选出初始迭代点43例：桁架设计问题：minF(x)=1.57x1

x=[x1x2]T∈

43例：桁架设计问题：minF(x)=1.57x144设有不等式约束优化问题：构造外点法惩罚函数的常见形式如下：惩罚因子r(k)规定取正。且在优化过程中r(k)取为递增数列

r(k)=Cr(k-1)，C＞1则将保证(k)=∞二、外点惩罚函数法基本思想：将新目标函数定义于可行域外，序列迭代点在可行域外逐步逼近原目标函数约束边界上的最优点。44设有不等式约束优化问题：构造外点法惩罚函数的常见形式如下45式中:外点惩罚函数法的思路：可行域内时,新目标函数就是原目标函数,当X位于可行域外时,惩罚项为正值,新目标函数值增大,就构成了对不满足约束条件时的一种”惩罚”.且离可行域越远,惩罚就越严厉.当r(k）不够大时，罚函数（新目标函数）的极小值在可行域外，即惩罚不够，可加大r(k），随着r(k）的增大，使新目标函数）的极小点越来越逼近原目标函数极小点。可行域外可行域内45式中:外点惩罚函数法的思路：可行域外46对于解不等式约束优化问题minF(x)＝xx∈R1

：g1(x)=x－1≥0用外点法构造惩罚函数，具体构造形式如下：写成另一种形式例46对于解不等式约束优化问题写成另一种形式例47令:解得无约束极小值的点列为

:无约束极小值点列相应的惩罚函数值为

求惩罚函数极小点:

47令:解得无约束极48由此可见，当惩罚因子为一递增正值数列时，其极值点离约束最优点愈来愈近，的差值与愈来愈小。当时，，亦即逼近于真正的约束最优解。无约束极值点列随值递增从可行域外向最优点收敛。

48由此可见，当惩罚因子为一递增正值数列时，其极值点49对几个问题的讨论初始点x(0)的选取:外点法的初始点x(0)可以任选，即在可行域与非可行域选取均可。(2)初始罚因子r(0)和递增系数C的选取初始罚因子r(0)选得是否恰当，对算法的成败和计算速度仍有着显著的影响。因此，选取时要谨慎。递增系数C的取值，一般影响不太显著，但也不宜取得过大。通常取C＝5~10。(3)约束容差带用外点法求解时，由于罚函数的无约束最优点列是从可行域外部向约束最优点逼近的，所以最终取得的最优点一定是在边界的非可行域一侧。严格地说，它是一个非可行点。这对某些工程问题可能是不允许的。为了解决这一问题。可在约束边界的可行域一侧加一条容差带，如图5.21。这就相当于将约束条件改为gu(x)－δu≥0，u=1，2，…，p式中的δu是容差量，一般可取δu=10－3~10－4。

49对几个问题的讨论50约束容差带。50约束容差带。51外点法不但可以解不等式约束优化问题，而且还可以解等式约束优化问题

用外点法求解二维等式约束优化问题：按外点法的基本思想，构造惩罚函数51外点法不但可以解不等式约束优化问题，而且还可以解等式约束52

外点法的特点外点法既可解不等式约束优化问题，也能解等式约束优化问题，且其初始点x(0)可任选，即在可行域中或非可行域中均可。其缺点是序列无约束最优点是一系列的非可行点，对于工程设计一般是不可取的。为使最终的迭代点能落入可行域，必须设置约束容差带。52外点法的特点53例：已知约束优化问题:试写出外点罚函数,并选出初始迭代点.外点罚函数:53例：已知约束优化问题:试写出外点罚函数,并选出初始迭代点54三、混合法

用罚函数法解决有等式约束和不等式约束的一般约束（GP型）优化问题的方法，把它称为混合惩罚函数法，简称混合法。

一般约束优化问题的数学模型

minf(x)x∈ÐÐ:gu(x)≥0(u=12……p)hv(x)=0(v=12……q,q<n)54三、混合法

用罚函数法解决有等式约束和不等式约束的一般约55内点形式的混合型惩罚函数法r(k)---递减m(k)---递增初始点必须是严格的内点为了统一用一个内点法惩罚因子,上式也可写成:不等式约束部分按内点法形式处理r(k)---递减55内点形式的混合型惩罚函数法r(k)---递减不等式约束56r(k)---递增外点形式的混合型惩罚函数法不等式约束部分按外点法形式处理56外点形式的混合型惩罚函数法不等式约束部分按外点法形式处理57如何判断优化结果的正确性:1、约束优化问题，最优点大多位于边界上。2、输入不同的初始点多次计算。3、用不同的方法解。作业：1、了解各种方法的基本思想和特点2、P130题23757如何判断优化结果的正确性:58机械优化举例：已知给定轨迹曲线，其上１２个主要点的坐标见下表，并给定

（该机构主要传递运动，对动力特性要求不高）。试设计一曲柄摇杆机构，使其连杆上点Ｍ的连杆曲线最佳逼近已知