机械优化设计之约束优化方法讲义课件

1、第五章 约束优化方法一.约束坐标轮换法二.约束随机方向法三.复合形法四.可行方向法五.罚函数法六.拉格朗日乘子法七.简约梯度法及广义简约梯度法2022/7/2815-1 优化方法的类型 2）间接法 1）直接法 -将迭代点限制在可行域内(可行性),步步降低目标函数值(下降性),直至到达最优点. 常用方法有:约束坐标轮换法,约束随机方向法,复合形法,可行方向法,线性逼近法等. -通过变换,将约束优化问题转化为无约束优化问题求解. 常用方法有: 罚函数法,拉格朗日乘子法等.（可解IP型问题）（可解各类问题）(按对约束条件的处理方法分)2022/7/2825-2 约束坐标轮换法一.基本思路 可取定步长

2、、加速步长和收缩步长,但不能取最优步长;1.依次沿各坐标轴方向-e1,e2,en方向搜索; 2.将迭代点限制在可行域内.对每一迭代点均需进行可行性和下降性检查.2022/7/283二.迭代步骤2022/7/284三.存在问题有时会出现死点, 导致输出“伪最优点”.* 为辨别真伪, 要用K-T条件进行检查.2022/7/2855-3 约束随机方向法基本思路若该方向适用、可行，则以定步长前进； 坐标轮换法有时会输出“伪最优点” ,用随机方向法可克服这一缺点. 若该方向不适用、可行，则产生另一方向；若在某处产生的方向足够多，仍无一适用、可行，则采用收缩步长；若步长小于预先给定的误差限则终止迭代。搜索

3、方向-采用随机产生的方向2022/7/286二.随机方向的构成1.用RND(X)产生n个随机数2. 将(0,1)中的随机数 变换到(-1,1)中去;3. 构成随机方向变换得:于是例: 对于三维问题:2022/7/287X0=X, F0=F=0, F0=F(X0)F=F（X）j =1K=K+1三.随机方向法 的迭代步骤是K=0, j=0产生随机方向=0.5否FF0j =0K m结 束X*=X0 ,F*=F0是否是否是否XD是否2022/7/2885-4 复合形法基本思路 在可行域内选取若干初始点并以之为顶点构成一个多面体(复合形),然后比较各顶点的函数值,去掉最坏点,代之以好的新点,并构成新的复

4、合形,以逼近最优点.有两种基本运算:1) 映射-在坏点的对侧试探新点:先计算除最坏点外各顶点的几何中心, 然后再作映射计算.2) 收缩-保证映射点的“可行”与“下降”X1为最坏点-映射系数常取 若发现映射点不适用、可行, 则将 减半后重新映射.2022/7/289二.初始复合形的构成1. 复合形顶点数K的选择建议: 小取大值, 大取小值2) 为避免降维, K应取大些; 但过大, 计算量也大.* 1) 为保证迭代点能逼近极小点, 应使2022/7/28102. 初始复合形顶点的确定 1) 用试凑方法产生-适于低维情况;2) 用随机方法产生用随机方法产生K个顶点 先用随机函数产生 个随机数 ,然后

5、变换到预定的区间 中去.这便得到了一个顶点,要连续产生K个顶点.2022/7/2811 将非可行点调入可行域内) 检查已获得的各顶点的可行性,若无一可行,则重新产生随机点;若有q个可行,则转下步.) 计算q个可行点点集的几何中心) 将非可行点逐一调入可行域内. 若仍不可行, 则重复此步骤, 直至进入可行域为止.2022/7/2812三. 终止判别条件各顶点与好点函数值之差的均方根应不大于误差限 不是十分可靠, 可改变 重作, 看结果是否相同.2022/7/2813比较复合形各顶点的函数值，找出好点XL，坏点XHXH=XR=0.5找出次坏点XSH ，XH=XSH满足终止条件？X*=XL ,F*=

6、F(XL)结 束四. 复合形法的 迭代步骤是否给定K，ai , bi i =1,2,n产生初始复合形顶点Xj , j=1,2,K计算复合形各顶点的函数值F(Xj), j=1,2,K是是是否否否XRDFR0,一般取为0.010.001); 2) -方向偏离系数(=0,对线性约束取为0, 其余取为1).-规格化条件2022/7/2819三.步长因子的确定1. 最优步长因子(迭代点为内点时使用) 下一迭代点如仍为内点, 继续进行, 直至迭代点到边界或域外时止.迭代公式:2. 试验步长因子将 在 处作泰勒展开, 仅取到线性项: (1) 定义目标函数相对下降量: (2)迭代公式 (3)(4)将(2)、(

7、3)代入(1)后整理得: 迭代点在边界附近偏域内一侧时使 用, 采用最有利的适用可行方向. 2) 按此法, 直至使迭代点进入约束容差带或至域外为止.* 1) 为保证 是 的一个邻近点, 的值不能取得太大. 通常2022/7/28202. 调整步长因子(将已出界的迭代点调回到边界上)(1) 约束边界容差带 在实际计算中,应给约束边界一个允许的误差限:式中, 通常取0.01-0.001;只要迭代点进入容差带, 即认为达到了边界.(2) 调整步长因子因 与 很接近, 可认为 在这两点间按线性变化:(1)为使新迭代点落在容差带中部, 取(2)于是有(3)* 还需检验该点是否在容差带内.若不满足,则)若

8、 ,则) 若 ,则 重复以上步骤,直至满足时止.2022/7/2821满足K-T条件？ 给定：内点X（0），fK=0 ，M=0 沿负梯度方向一维搜索得极小点X（K+1）求最有利的适用可行方向求试验步长因子tM=0K=K+1X*=X(K), F*=F(X*)结束是是是否否否求求调整步长因子否四.终止迭代准则 采用K-T条件,对J个起作用约束,求解线性方程组:M=1应为非负五.迭代步骤是2022/7/28225-6 惩罚函数法一. 概述1. 基本思想将约束问题 转化成无约束问题 求解惩罚函数可调参数* 构造惩罚函数 的基本要求: 惩罚项用约束条件构造; 到达最优点时,惩罚项的值为0; 当约束不满足

9、或未到达最优点时,惩罚项的值大于0.2. 分类 内点法-将迭代点限制在可行域内; 外点法-迭代点一般在可行域外; 混合法-将外点法和内点法结合起来解GP型问题.2022/7/2823二.SUMT内点法1.惩罚函数的构造原问题:s.t.可取式中, 1)* 当X趋于D的边界时, B(X)趋于无穷大, 故又称为障碍(围墙)函数;2022/7/28242) 罚因子为使 与原问题同解, 应使* 对于一个 , 求解一个无约束优化问题. 前一问题的结果为后一问题的初值, 故为系列无约束极小化方法(Sequential Unconstrained Minimization Technique).2022/7/

10、2825 输出X*，F*=F（X*）结束是2.SUMT内点罚函数法迭代步骤用无约束方法求 的极小点X*输入X0，r0, c, 否k=k+1, Xk=X*，rk=crkK=0, Xk=X0,2022/7/2826例:解: 惩罚函数在D内 , 对于固定的 , 令得r(k)x*f(x*)B(x*)1/22111.51/101.44720.72362.23610.94721/501.20.650.71/62501.01790.508955.90170.5179010.50.52022/7/2827r(k)x*f(x*)B(x*)1/22111.51/101.44720.72362.23610.9472

11、1/501.20.650.71/62501.01790.508955.90170.5179010.50.52022/7/28281) 初始点X0的确定(必须为内点)* 用现有机器参数作初值;* 用图解法;* 用随机方法;* 用内点法求内点.3. 应用内点法应注意的问题-X0, r(0), c 的确定2022/7/2829k=0, X(k)=X0 , r(k)=r0I2为空集计算指标集以X(K)为初始点, 求解得X*。输出是否任取X0, 给定 r0 , c, 2022/7/28302）罚因子的初值* 过大, 会使 的最优点比 X0 离真正的最优点更远; 过小,在域内的惩罚作用小, 在接近边界时则

12、突然加大使性态变坏, 且有可能使迭代点越出可行域. Fox 推荐3）递减系数C本书推荐0.10.5.2022/7/2831三. SUMT外点法1. 惩罚函数的构造考虑非线性规划问题:s.t.惩罚函数可取为2) 罚因子* 1) 时,惩罚项为0, 不惩罚; 时, 惩罚项大于0, 有惩罚作用.因 边界时,惩罚项中大括号中的值趋于0,为保证惩罚作用,应取2022/7/28322. SUMT外点法的迭代步骤给定X0，c, r0, 1, 2, 3k=0, r(k)=r0, X(K)=X0输出X*，F*=F（X*）结束是是是否否否求解 得极小点X*k=k+1r(k)=cr(k)X(k)=X* -初始点, 对

13、凸规划可任意给定;* -外点法点距精度; -等式约束允许的误差限; -不等式约束允许的误差限; -罚因子的放大系数;* 为使迭代点进入可行域, 可设约束容差带:2022/7/2833例:解: 惩罚函数在D外 , 对于固定的 , 令得r(k)x*f(x*)11.50.250.5101.909090.826540.909091001.990990.9802960.99009910001.9990010.9980030.9990012112022/7/28343. 外点法与内点法的比较1)外点法可解各类问题,内点法仅适于IP型问题;2)外点法的初始点可任选,内点法的初始点必须为内点;3)外点法的极小

14、点系列一般在D外,内点法的极小点系列 在D内(全为可行点);2022/7/2835四. SUMT混合法 有等式约束时内点法不能用,要求迭代点始终满足不等式约束时外点法不能用.此时可将外点法和内点法结合起来解GP型问题.* 1) 迭代点应始终满足 2) Fiacco等人建议2022/7/28365-7 拉格朗日乘子法一.等式约束问题的拉格朗日乘子法s.t.1.建立拉氏函数2.在最优点处有如下n+q 个方程成立其解为2022/7/2837s.t.二.含不等式约束问题的拉格朗日乘子法1.建立拉氏函数 再用前述方法建立拉氏函数 对不等式约束引入松弛变量 , 使之成为等式约束:2022/7/28382.

15、在最优点处有如下 n+q+2p 个方程成立其解为2022/7/2839三.增广拉格朗日乘子法 采用拉格朗日乘子法时求解有难度,而罚函数法当迭代点接近边界时函数常有病态, 此法的思路是把两者结合起来.其增广拉格朗日函数为:特点: 1. 初始点可为非可行点;2. 因增加了可调参数 , 其收敛速度和稳定性都优于罚函数法.2022/7/28405-8 简约梯度法及广义简约梯度法思路：利用约束条件消去非独立变量，使问题简化，再沿简化后的目标函数的负梯度方向搜索.一 简约梯度法1.问题 s.t.2.简约梯度1）将问题降维基向量（状态）式中将X分成两部分：2022/7/2841非基向量（决策)对应的系数矩阵也分成两部分式中，B为对应于XB的m 阶方阵，且必须为满秩矩阵；C为对应于XN的 阶矩阵；于是，（1）故2022/7/28422）求简约梯度（2）式中,3.迭代计算1）迭代公式（3）2022/7/2843* (1) 在迭代中需保证各分量值大于或等于零; (2) 当 且 时, 因 , 必有 , 不可行. 写成分量的形式：（4）迭代方向应作修正：(当 , 时)(在一般情况下)（5）2022/7/28442）步长因子的确定(1) 若各分量值 大