约束问题的最优化方法.ppt

《约束问题的最优化方法.ppt》由会员分享，可在线阅读，更多相关《约束问题的最优化方法.ppt（45页珍藏版）》请在金锄头文库上搜索。

1、4.14.1 引言引言无约束优化方法是优化方法中最基本最核心的部分。但是，在工程实际中，优化问题大都是属于有约束的优化问题，即其设计变量的取值要受到一定的限制，用于求解约束优化问题最优解的方法称为约束优化方法。 根据约束条件类型的不同可以分为三种，其数学模型分别如下： 1、不等式约束优化问题（IP型） 2、等式约束优化问题（EP型） 3、一般约束优化问题（GP型）l 直接解法：直接解法：随机方向搜索法、复合形法、可行方向法l 间接解法：间接解法：内点惩罚函数法、外点惩罚函数法、混合惩罚函数法一.一.约束优化问题解法分类：约束优化问题解法分类：约束优化方法按求解原理求解原理的不同可以分为直接法和

2、间接法两类。二二. . 直接解法：直接解法：基本思想：基本思想：合理选择初始点，确定搜索方向，以迭代公式 x(k+1)= x(k)+(k)S(k)在可行域中寻优，经过若干次迭代，收敛至最优点。基本要点：基本要点：选取初始点、确定搜索方向及适当步长。搜索原则：搜索原则：每次产生的迭代点必须满足可行性与适用性两个条件。 可行性：可行性：迭代点必须在约束条件所限制的可行域内，即满足 gu(x)0, u=1,2,p 适用性：适用性：当前迭代点的目标函数值较前一点是下降的，即满足 F(xk+1)F(xk) 适用范围：适用范围：只能求解不等式约束优化问题的最优解。特点：特点：在可行域内进行； 若可行域是凸

3、集，目标函数是定义在凸集上的凸函数， 则收敛到全局最优点；否则，结果与初始点有关。收敛条件：收敛条件：边界点的收敛条件应该符合 K-T 条件； 内点的收敛条件为：目的：目的：将有约束优化问题转化为无约束优化问题来解决。前提：前提：一不能破坏约束问题的约束条件，二使它归结到原约束问题的同一最优解上去。惩罚函数法：惩罚函数法： 通过构造罚函数把约束问题转化为一系列无约束最优化问题，进而用无约束最优化方法去求解。惩罚函数法是一种使用很广泛、很有效的间接解法。 基本思想：基本思想：以原目标函数和加权的约束函数共同构成一个新的目标函数 ( x, r1 ,r2 )，将约束优化问题转化为无约束优化问题。通过

4、不断调整加权因子，产生一系列函数的极小点序列 x(k)* (r1(k),r2(k) k= 0,1,2 ，逐渐收敛到原目标函数的约束最优解原目标函数的约束最优解。三三. . 间接解法：间接解法：新目标函数：加权因子（即惩罚因子）： r1 , r2无约束优化问题无约束优化问题： 函数的极小点序列 x (k)* ( r1 (k) , r2 (k) ) k= 0,1,2 其收敛必须满足： 其中 和 称为加权转化项，并根据它们在惩罚函数中的作用，分别称为障碍项和惩罚项。 障碍项：当迭代点在可行域内时，在迭代过程中阻止迭代点越出边界。 惩罚项：当迭代点在非可行域或不满足不等式约束条件时，在迭代过程之中迫使

5、迭代点逼近约束边界或等式约束曲面。分类：分类：根据约束形式和定义的泛函及罚因子的递推方法等不同，罚函数法可分为内点法、外点法和混合罚函数法三种。 这种方法是1968年由美国学者AVFiacco和GPMcormick提出的，把不等式约束引入数学模型中，为求多维有约束非线性规划问题开创了一个新局面。适用范围：适用范围：求解等式约束优化问题和一般约束优化问题。4.24.2 内点惩罚函数法（障碍函数法）内点惩罚函数法（障碍函数法）一一. . 基本思想：基本思想： 内点法将新目标函数 ( x , r ) 构筑在可行域 D 内，随着惩罚因子 r(k) 的不断递减，生成一系列新目标函数 (xk ,r(k)，

6、在可行域内逐步迭代，产生的极值点 xk*(r(k) 序列从可行域内部趋向原目标函数的约束最优点 x* 。 内点法只能用来求解具有不等式约束的优化问题。二二. . 惩罚函数的形式惩罚函数的形式：其中：惩罚（加权）因子其中：惩罚（加权）因子降低系数降低系数c：0c1例： 用内点法求的约束最优解。解: 首先构造内点惩罚函数:用解析法求函数的极小值，运用极值条件： 联立求解得：时不满足约束条件应舍去 。无约束极值点为：当 内点法的迭代过程在可行域内进行，“障碍项”的作用是阻止迭代点越出可行域。三三. . 步骤：步骤：1.选取合适的初始点 x(0) ，以及 r(0)、c、计算精度 1、2 ，令 k=0；

7、 2. 构造惩罚（新目标）函数；3. 调用无约束优化方法，求新目标函数的最优解 xk* 和 (xk , r(k) ) ；4.判断是否收敛：运用终止准则若均满足，停止迭代，有约束优化问题的最优点为 x* = xk*；若有一个准则不满足，则令 并转入第 3 步，继续计算。四四. . 几个参数的选择：几个参数的选择：2.惩罚因子初始值惩罚因子初始值r(0)的选择：的选择：1. 初始点初始点x(0)的选择的选择：要求： 在可行域内； 不要离约束边界太近。如太靠近某一约束边界，构造的惩罚函数可能由于障碍项的值很大而变得畸形，使求解无约束优化问题发生困难.方法： 人工估算，需要校核可行性； 计算机随机产生

8、，也需校核可行性。惩罚因子的初值应适当，否则会影响迭代计算的正常进行。一般而言，太大，将增加迭代次数；太小，会使惩罚函数的性态变坏，甚至难以收敛到极值点。对于不同的问题，都要经过多次试算，才能决定一个适当 r0。3. 降低系数降低系数c的选择：的选择： 在构造序列惩罚函数时，惩罚因子r是一个逐次递减到0的数列，相邻两次迭代的惩罚因子的关系为 : 式中的c称为惩罚因子的缩减系数，c为小于1的正数。一般的看法是，c值的大小在迭代过程中不起决定性作用，通常的取值范围在0.10.7之间。4.收敛条件：收敛条件：五五. . 方法评价：方法评价：l 用于目标函数比较复杂，或在可行域外无定义的场合下：l由于

9、优化过程是在可行域内逐步改进设计方案，故在解决工程问题时，只要满足工程要求，即使未达最优解，接近的过程解也是可行的；l初始点和序列极值点均需严格满足所有约束条件；l不能解决等式约束问题。六六. . 举例：举例：盖板问题盖板问题bhtstf 设计一个箱形截面的盖板。设计一个箱形截面的盖板。已知：长度已知：长度l0=600cm，宽度宽度b=60cm，侧板厚度侧板厚度ts=0.5cm，翼板厚度为翼板厚度为tf(cm)，高高度为度为h(cm)，承受最大的单位载荷承受最大的单位载荷q=0.01Mpa。要求：在满足强度、刚度和稳定性等条件下，设计一个最轻结构。要求：在满足强度、刚度和稳定性等条件下，设计一

10、个最轻结构。3.优化方法优化方法：4. 选用内点惩罚法，惩罚函数形式为：选用内点惩罚法，惩罚函数形式为： 调用调用Powell法求序列无约束优化极值，以逐渐逼近原问题的极值法求序列无约束优化极值，以逐渐逼近原问题的极值点。点。1.设计分析设计分析：（略）：（略）2.数学模型：数学模型：4.求解过程分析：求解过程分析：4.3 4.3 外点惩罚函数法外点惩罚函数法 ( (衰减函数法）衰减函数法）一一. . 基本思想：基本思想： 外点法将新目标函数 ( x , r ) 构筑在可行域 D 外，随着惩罚因子 r(k) 的不断递增，生成一系列新目标函数 (xk ,r(k)，在可行域外逐步迭代，产生的极值点

11、 xk*(r(k) 序列从可行域外部趋向原目标函数的约束最优点 x* 。4外点法可以用来求解含不等式和等式约束求解含不等式和等式约束的优化问题。二二. . 惩罚函数的形式：惩罚函数的形式： 外点法的迭代过程在可行域之外进行，惩罚项的作用是迫使迭代点逼近约束边界或等式约束曲面。例： 用外点法求解下列有约束优化问题解：惩罚函数为：对上式求偏导，得r0.01-0.80975-50.00000-24.9650-49.99770.1-0.459695.00000-2.2344-4.947410.23607-0.500000.96310.1295100.83216-0.050002.30682.00011

12、0000.99800-0.000502.66242.6582108/38/3无约束目标函数极小化问题的最优解系列为：当惩罚因子渐增时，由下表可看出收敛情况。三三. . 参数选择：参数选择：1.r(0)的选择的选择:r (0) 过大，会使惩罚函数的等值线变形或偏心，求极值困难。 r (0) 过小，迭代次数太多。2.x(0)的选择：的选择： 基本上可以在可行域内外，任意选择。3.递增系数递增系数r的选择的选择： 通常选择 5 10，可根据具体题目，进行试算调整。 四四. . 步骤：步骤： 2. 构造惩罚（新目标）函数，调用无约束优化方法，求新目标函数构造惩罚（新目标）函数，调用无约束优化方法，求新

13、目标函数的最优解的最优解xk*和和(xk,r(k)；3. 4.判断是否收敛：运用终止准则判断是否收敛：运用终止准则若均满足，停止迭代，有约束优化问题的最优点为若均满足，停止迭代，有约束优化问题的最优点为x*=xk*；若有一个准则不满足，则令若有一个准则不满足，则令并转入第并转入第2步，继续计算。步，继续计算。1.选择合适的初始点选择合适的初始点x(0)，并选择并选择r(0),a,1,2,0，令令k=0；五五. . 方法评价：方法评价：l 初始点原则上可任意选择初始点原则上可任意选择;l能解决等式约束问题能解决等式约束问题;l由于优化过程是在可行域外进行，故在解决工程问题时，过程由于优化过程是在

14、可行域外进行，故在解决工程问题时，过程解均不可行。解均不可行。内点法内点法:（1）始点必须为严格内点； （2）不适于具有等式约束的数学模型； （3）迭代过程中各个点均为可行设计方案； （4）一般收敛较慢； （5）初始罚因子要选择得当； （6）罚因子为递减，递减率c有0c1； 内点法和外点法的对比内点法和外点法的对比4.44.4 混合惩罚函数法混合惩罚函数法一一. . 基本思想基本思想： 采用内点法和外点法相结合的混合惩罚函数法，用内点法处理不采用内点法和外点法相结合的混合惩罚函数法，用内点法处理不等式约束，用外点法处理等式约束。可以用来求解含不等式和等式约等式约束，用外点法处理等式约束。可以用

15、来求解含不等式和等式约束的优化问题。束的优化问题。二二. . 惩罚函数的形式：惩罚函数的形式：一般既包括障碍项，也包括衰减项。一般既包括障碍项，也包括衰减项。4.54.5 随机方向搜索法随机方向搜索法一一. .基本思想：基本思想： 随机产生初始点，随机产生搜索方向随机产生初始点，随机产生搜索方向 S S(k)(k) ，进行搜索。进行搜索。 但要确保：但要确保： 新迭代点在可行域中；新迭代点在可行域中； 目标函数值的下降性。目标函数值的下降性。随机方向探索法的一般迭代随机方向探索法的一般迭代计算公式算公式为： X X(k+1(k+1)=X)=X(k(k)+aS)+aS(k(k) (k=0,1,2

16、,) (k=0,1,2,) ) 式中式中a a为步步长，S S(k(k) ) 为第第k k次迭代的随机探索方向。次迭代的随机探索方向。因此，随机方向探索法的因此，随机方向探索法的计算算过程可程可归结为：三三. .随机产生初始点随机产生初始点： 估计设计变量的上、下限：xil x i xiu ，i=1,2,n； 在区间0,1中产生伪随机数列 ri ， xi(0) = xil + ri ( xiu - xil )； 判断是否 gu (xi(0) ) 0；若满足，则 x(0) = xi(0) 若不满足，则转向。 二二. .随机数的产生：随机数的产生：1. 伪随机数： 用数学模型，从计算机（的随机数发

17、生器）中产生的随机数。2.随机数的特性 有较好的概率统计特性 抽样的随机性； 分布的均匀性； 前后数之间的独立性； 周期性长。四四. . 随机产生搜索方向：随机产生搜索方向： x(0)x(m)x(1)x(2)x(j)x(l)H(0)五五. . 步骤：步骤：均是，转判2X (k+1) 六六. . 方法评价：方法评价：优点：优点：l 对目标函数无性态要求；l 收敛快（当m足够大时）；l 不受维数影响，维数愈高，愈体现优点。缺点：缺点：l 对于严重非线性函数，只能得近似解；l 当m不够大时，解的近似程度大；l 对于非凸函数，有可能收敛于局部解。4.6 4.6 复合形法复合形法 复合形法是求解约束非线

18、性最优化问题的一种重要的直接方法。它来源于用于求解无约束非线性最优化问题的单纯形法，实际上是单纯形法在约束问题中的发展。 在求解无约束问题的单纯形法中，不需计算目标函数的梯度，而是靠选取单纯形的顶点井比较各顶点处目标函数值的大小，来寻找下一步的探索方向的。 在用于求解约束问题的复合形法中，复合形各顶点的选择和替换，不仅要满足目标函数值的下降，还应当满足所有的约束条件。一一. . 单纯形法：单纯形法：定义定义：基本思想基本思想： 以一个目标函数值较小的新点，以一个目标函数值较小的新点，代替原单纯形中目标函数值最大的顶代替原单纯形中目标函数值最大的顶点，组成新的单纯形，这样不断地迭点，组成新的单纯

19、形，这样不断地迭代，单纯形逐渐逼近最优点。代，单纯形逐渐逼近最优点。以二维以二维空间中的映射法为例空间中的映射法为例：X(1)=X(H)X(2)X(3)X(S)X(R)=X(4)X(5)X(6)在在n维空间中，由维空间中，由n+1个点组成的图形称单纯形。个点组成的图形称单纯形。X*二二. . 复合形法：复合形法：定义定义： 在 n 维空间中，由 kn+1 个点组成的多面体称为复合形。基本思想基本思想：说明：说明：l 单纯形是无约束优化方法，而复合形可用于约束优化的方法。l 因为顶点数较多，所以比单纯形更灵活易变。l 复合形只能解决不等式约束问题。l 因为迭代过程始终在可行域内进行，运行结果可靠

20、。 在可行域内构造一个具有k个顶点的初始复合形。对该复合形各顶点的目标函数值进行比较，去掉目标函数值最大的顶点（称最坏点），然后按一定法则求出目标函数值下降的可行的新点，并用此点代替最坏点，构成新的复合形，复合形就向最优点移动一步，直至逼近最优点。三三. . 迭代方法迭代方法：1.映射法映射法： 例：二维空间中，k=4，复合形是四面体 x(1)x(2)x(3)x(4)，计算得： f (x(1) ) f (x(2) ) f (x(3) ) 1，建议先取建议先取1.3。映射迭代公式映射迭代公式：x(R)=x(S)+(x(S)x(H)若求得的 x(R) 在可行域内，且 f (x(R) ) 5 时，k

21、 的取值可小些。4.74.7 可行方向法可行方向法一一. . 基本思想：基本思想： 在第 k+1 次迭代时，从 x(k) 点出发，寻找一个可行的搜索方向和合适的步长因子，从而得到一个可行、目标函数值下降的新点 x(k+1) ，再以此点出发，寻找新点，直至满足收敛条件，得到最优点 x* 。(k)的选择原则：的选择原则： 使新点 x(k+1) 在可行域内。S(k)的选择原则：的选择原则：必须是可行方向，即必须与所有适时约束的梯度方向成钝角。 必须是目标函数值下降的方向，即必须与目标函数的负梯度方向成锐角。同时满足以上两个条件的方向，称为同时满足以上两个条件的方向，称为适用可行方向适用可行方向。二二

22、. . 搜索策略：搜索策略： 可根据目标函数和约束函数的不同性态，可根据目标函数和约束函数的不同性态，选择不同的搜索策略。选择不同的搜索策略。边界反弹法边界反弹法： 第一次搜索为负梯度方向，终止于边界。以后各次搜索方向均为适用可行方向，以最大步长从一个边界反弹到另一个边界，直至满足 K-T 条件。 最优步长法：最优步长法： 第一次搜索为负梯度方向，终止于边界。第二次搜索沿适用可行方向作一维搜索以最优步长因子求得最优点。反复以上两步，直至得到最优点x*。贴边搜索法贴边搜索法： 第一次搜索为负梯度方向，终止于边界。以后各次搜索贴边（约束面）进行。 若适时约束面是切面，每次搜索到约束面的交集时，移至另一个约束面，直至收敛到最优点。 若可行域是凸集，约束面是非线性时，从x(k)点沿切线（面）方向s(k) 搜索，会进入非可行域。