约束优化方法白版PPT课件.ppt

第五章有约束优化方法 5 1引言 5 2随机方向法 5 3复合形法 5 4可行方向法 5 5惩罚函数法 5 6序列二次规划法 1 5 1引言 机械优化设计中的问题 大多数属于约束优化设计问题 其数学模型为 2 上一章讨论的都是无约束条件下非线性函数的寻优方法 但在实际工程中大部分问题的变量取值都有一定的限制 也就是属于有约束条件的寻优问题 与无约束问题不同 约束问题目标函数的最小值是满足约束条件下的最小值 即是由约束条件所限定的可行域内的最小值 只要由约束条件所决定的可行域必是一个凸集 目标函数是凸函数 其约束最优解就是全域最优解 否则 将由于所选择的初始点的不同 而探索到不同的局部最优解上 在这种情况下 探索结果经常与初始点的选择有关 为了能得到全局最优解 在探索过程中最好能改变初始点 有时甚至要改换几次 3 1 直接法直接法包括 网格法 复合形法 随机试验法 随机方向法 可变容差法和可行方向法 2 间接法间接法包括 罚函数法 内点罚函数法 外点罚函数法 混合罚函数法 广义乘子法 广义简约梯度法和约束变尺度法等 根据求解方式的不同 约束优化设计问题可分为 直接解法 间接解法 4 直接解法通常适用于仅含不等式约束的问题 思路是在m个不等式约束条件所确定的可行域内 选择一个初始点 然后决定可行搜索方向d且以适当的步长 进行搜索 得到一个使目标函数值下降的可行的新点 即完成一次迭代 再以新点为起点 重复上述搜索过程 直至满足收敛条件 步长 可行搜索方向 可行搜索方向 当设计点沿该方向作微量移动时 目标函数值将下降 且不会越出可行域 5 间接解法的基本思路是按照一定的原则构造一个包含原目标函数和约束条件的新目标函数 即将原约束优化问题转化成为一个或一系列的无约束优化问题 再对新的目标函数进行无约束优化计算 从而间接地搜索到原约束问题的最优解 6 5 2随机方向法 基本思想 利用计算机产生的随机数所构成的随机方向进行搜索 产生的新点必须在可行域内 即满足直接法的特性 随机方向法 是约束最优化问题的一种常用的直接求解方法 它和随机梯度法 Gauss Seidel法等都属于约束随机法 7 其基本原理如图所示 在约束可行域S内选取一个初始点X 0 在不破坏约束的条件下以合适的步长a 沿X 0 点周围几个不同的方向 以某种形式产生的随机方向 进行若干次探索 并计算各方向上等距离 步长a 点的函数值 找出其中的最小值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 直至取得约束好点 如此循环下去 当迭代的步长已经很小时 则表明已经逼近约束最优点 达到计算精度要求时 即可结束迭代计算 8 图约束随机方向探索法的基本原理 9 随机方向探索法的一般迭代计算公式为 X k 1 X k aS k k 0 1 2 式中a为步长 S k 为第k次迭代的随机探索方向 因此 随机方向探索法的计算过程可归结为 10 复合形法是求解约束非线性最优化问题的一种重要的直接方法 它来源于用于求解无约束非线性最优化问题的单纯形法 实际上是单纯形法在约束问题中的发展 如前所述 在求解无约束问题的单纯形法中 不需计算目标函数的梯度 而是靠选取单纯形的顶点井比较各顶点处目标函数值的大小 来寻找下一步的探索方向的 在用于求解约束问题的复合形法中 复合形各顶点的选择和替换 不仅要满足目标函数值的下降 还应当满足所有的约束条件 5 3复合形法 11 基本思想 在可行域中选取K个设计点 n 1 K 2n 作为初始复合形的顶点 比较各顶点目标函数值的大小 去掉目标函数值最大的顶点 称最坏点 以坏点以外其余各点的中心为映射中心 用坏点的映射点替换该点 构成新的复合形顶点 反复迭代计算 使复合形不断向最优点移动和收缩 直至收缩到复合形的顶点与形心非常接近 且满足迭代精度要求为止 12 令 X 4 X 0 X 0 X H 称X 4 为映射点 记为X R 为映射系数 通常取 1 3 可根据实际情况进行缩减 取次好点和好点连线的中点为X 0 一般情况下 映射点的函数值比坏点的函数值要小 即F X R F X H 若满足可行域 则用X R 代替X H 构成新的复合形 如此反复迭代直到找到最优解 在可行域内任选三个初始点X 1 X 2 X 3 连接这三点形成一个三角形 此三角形称为初始复合形 计算各个顶点函数值F X 1 F X 2 F X 3 找出最大值 记为坏点X H 最小值 记为最好点X L 在次好点和好点连线与坏点反向一侧的各点应具有较小的目标值 13 在迭代过程中 按映射系数 1 3得到的映射点 不一定满足适用性和可行性 如出现此情况 将映射系数减半 重新取得X R 使它满足适用性和可行性 14 一 初始复合形的构成复合形的顶点K通常取n 1 K 2n个 对于维数较低的优化问题 由于顶点数目较少 可试凑几个可行点作为复合形的顶点 对于维数较高的问题 采用随机方法 先产生K个随机点 然后再把非可行点逐一调入可行域内 1 产生K个随机点xi ai i bi ai i 1 2 n i为 0 1 区间内产生的均匀分布的随机数 需要n个随机数产生一个点X 1 同样 产生其它的随机点X 2 X 3 X K 15 2 将非可行点调入可行域将产生的K个随机点进行判断是否在可行域内 重新排列 将可行点依次排在前面 如有q个顶点X 1 X 2 X q 是可行点 其它K q个为非可行点 对X q 1 将其调入可行域的步骤是 1 计算q个点集的中心X s 2 将第q 1点朝着点X s 的方向移动 按下式产生新的X q 1 即X q 1 X s 0 5 X q 1 X s 16 这个新点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个点就构成了初始复合形 17 二 复合形法的迭代步骤 1 构造初始复合形 2 计算各顶点的函数值F X j j 1 2 K 选出好点X L 和坏点X H 3 计算坏点外的其余各顶点的中心点X 0 18 4 计算映射点X R 检查X R 是否在可行域内 若X R 为非可行点 将映射系数减半后再按上式改变映射点 直到X R 进入可行域内为止 19 5 构造新的复合形计算映射点的函数值F X R 并与坏点的函数值F X H 比较 可能存在两种情况 1 映射点优于坏点F X R F X H 在此情况 用X R 代替X H 构成新的复合形 20 再转回本步骤的开始处 直到构成新的复合形 2 映射点次于坏点F X R F X H 这种情况由于映射点过远引起的 减半映射系数 若有F X R F X H 这又转化为第一种情况 21 6 判断终止条件1 各顶点与好点函数值之差的均方根值小于误差限 即 2 各顶点与好点的函数值之差的平方和小于误差限 即 3 各顶点与好点函数值差的绝对值之和小于误差限 即 如果不满足终止迭代条件 则返回步骤2继续进行下一次迭代 否则 可将最后复合形的好点X L 及其函数值F X L 作为最优解输出 22 23 方法特点 1 复合形法是求解约束非线性最优化问题的一种直接方法 仅通过选取各顶点并比较各点处函数值的大小 就可寻找下一步的探索方向 但复合形各顶点的选择和替换 不仅要满足目标函数值下降的要求 还应当满足所有的约束条件 2 复合形法适用于仅含不等式约束的问题 24 可行方向是求解大型不等式约束优化问题的主要方法之一 基本思想 这种方法的基本原理是在可行域内选择一个初始点 当确定了一个可行方向d和适当的步长后 按式 5 4可行方向法 进行迭代计算 迭代点既不超出可行域 又使目标函数的值有所下降 在不断调整可行方向的过程中 使迭代点逐步逼近约束最优点 25 可行方向法的搜索策略 即 26 图1 10 27 1 可行方向法的搜索策略 第一步迭代都是从可行的初始点出发 沿点的负梯度方向 将初始点移动到某一个约束面 只有一个起作用的约束时 上 或约束面的交集 有几个起作用的约束时 上 28 根据约束函数和目标函数的不同性状 分别采用以下几种策略继续搜索 1新点在可行域内的情况 29 2新点在可行域外的情况 30 3沿线性约束面的搜索 31 4沿非线性约束面的搜索 32 2 产生可行方向的条件 可行方向是指沿该方向作微小移动后 所得到的新点是可行点 且目标函数值有所下降 可行方向应满足两个条件 1 可行 2 下降 1 可行条件 方向的可行条件是指沿该方向作微小移动后 所得到的新点为可行点 33 2 下降条件 方向的下降条件是指沿该方向作微小移动后 所得新点的目标函数值是下降的 34 满足可行和下降条件 即式 位于约束曲面在点xk的切线和目标函数等值线在点xk的切线所围成的扇形区内 该扇形区称为可行下降方向区 同时成立的方向称可行方向 35 3 可行方向的产生方法 满足可行 下降条件的方向位于可行下降扇形区内 在扇形区内寻找一个最有利的方向作为本次迭代的搜索方向 1 优选方向法 由条件 求一个以搜索方向d为设计变量的约束优化问题 s t 各函数均为设计变量dk的线性函数 因此该式为一个 线性 规划问题 36 当xk点目标函数的负梯度方向不满足可行条件时 可将方向投影到约束面 或约束面的交集 上 得到投影向量dk P 投影算子 为nXn阶矩阵 G 起作用约束函数的梯度矩阵 nXJ阶矩阵 2 梯度投影法 37 4 步长的确定 确定的步长应使新的迭代点为可行点 且目标函数具有最大的下降量 约束一维搜索 1 取最优步长从xk点出发 沿dk方向进行一维最优化搜索 取得最优步长 计算新点x的值 38 取到约束边界的最大步长从xk点出发 沿dk方向进行一维最优化搜索 得到的新点x为不可行点 改变步长 使新点x返回到约束面上来 使新点x恰好位于约束面上的步长称为最大步长 39 约束一维搜索 与以前所讲过的一维搜索相比 约束一维搜索的特点在于 确定初始区间时 对产生的每一个探测点都进行可行性判断 如违反了某个或某些约束条件 就必须减少步长因子 以使新的探测点落在最近的一个约束曲面上或约束曲面的一个容许的区间内 0 x 1 x 2 x k d k x k 1 g 2 x 0 g 1 x 0 a d k a M d k x 40 如得到的相邻三个探测点都是可行点 而且函数值呈 大 小 大 变化 则与前面一维搜索相同 两端点所决定的区间就是初始区间 接着缩小区间直到一维最小点 如最后得到的探测点落在约束曲面的一个容限之内 而且函数值比前一点的小 则该点就是一维极小点 41 收敛条件 2 设计点xk满足库恩 塔克条件 1 设计点xk及约束允差满足 42 例题5 1 用可行方向法求约束优化问题 解 1 取初始点 则取作用约束集 Jk 1 43 2 寻找最优方向 即解一个以可行方向为设计变量的规划问题 1 d1 d2 用图解法 最优方向 44 3 沿d0方向进行一维搜索 x1在约束边界g3 x 0上 g3 x1 0 4 第二次迭代 用梯度投影法确定可行方向 迭代点x的目标函数负梯度 不满足方向的可行条件 将投影到约束边界g3 x 0上 投影算子 由上式可求得 45 本次迭代方向 D为沿约束边界g3 x 0的方向 求最佳步长 求得 46 g5 x 0 6 8 x1 x2 g4 x 0 g3 x 0 g2 x 0 g1 x 0 x0 d0 47 4 收敛判断 由于 Jk 3 5 代入K T条件 48 49 基本思想 通过构造罚函数把约束问题转化为一系列无约束最优化问题 进而用无约束最优化方法去求解 这类方法称为序列无约束最小化方法 简称为SUMT法 5 5惩罚函数法 50 将有约束的优化问题转化为无约束优化问题来求解 前提 一是不能破坏约束问题的约束条件 二是使它归结到原约束问题的同一最优解上去 构成一个新的目标函数 称为惩罚函数 51 从而有 惩罚项必须具有以下极限性质 求解该新目标函数的无约束极小值 以期得到原问题的约束最优解 按一定的法则改变罚因子r1和r2的值 求得一序列的无约束最优解 不断地逼近原约束优化问题的最优解 52 根据约束形式和定义的泛函及罚因子的递推方法等不同 罚函数法可分为内点法 外点法和混合罚函数法三种 这种方法是1968年由美国学者A V Fiacco和G P Mcormick提出的 把不等式约束引入数学模型中 为求多维有约束非线性规划问题开创了一个新局面 53 内点法 这种方法将新目标函数定义于可行域内 序列迭代点在可行域内逐步逼近约束边界上的最优点 内点法只能用来求解具有不等式约束的优化问题 对于只具有不等式约束的优化问题 转化后的惩罚函数形式为 或 54 rk是惩罚因子 它是一个由大到小且趋近于0的正数列 即 由于内点法的迭代过程在可行域内进行 障碍项 的作用是阻止迭代点越出可行域 由 障碍项 的函数形式可知 当迭代点靠近某一约束边界时 其值趋近于0 而 障碍项 的值陡然增加 并趋近于无穷大 好像在可行域的边界上筑起了一道 高墙 使迭代点始终不能越出可行域 显然 只有当惩罚因子时 才能求得在约束边界上的最优解 55 罚因子的作用是 由于内点法只能在可行域内迭代 而最优解很可能在可行域内靠近边界处或就在边界上 此时尽管泛函的值很大 但罚因子是不断递减的正值 经多次迭代 接近最优解时 惩罚项已是很小的正值 56 例5 2用内点法求 的约束最优解 解 用内点法求解该问题时 首先构造内点惩罚函数 用解析法求函数的极小值 运用极值条件 联立求解得 57 无约束极值点为 当 58 59 1 初始点x0的选取 使用内点法时 初始点应选择一个离约束边界较远的可行点 如太靠近某一约束边界 构造的惩罚函数可能由于障碍项的值很大而变得畸形 使求解无约束优化问题发生困难 2 惩罚因子初值r0的选取 惩罚因子的初值应适当 否则会影响迭代计算的正常进行 一般而言 太大 将增加迭代次数 太小 会使惩罚函数的性态变坏 甚至难以收敛到极值点 无一般性的有效方法 对于不同的问题 都要经过多次试算 才能决定一个适当r0 3 惩罚因子的缩减系数c的选取 在构造序列惩罚函数时 惩罚因子r是一个逐次递减到0的数列 相邻两次迭代的惩罚因子的关系为 60 式中的c称为惩罚因子的缩减系数 c为小于1的正数 一般的看法是 c值的大小在迭代过程中不起决定性作用 通常的取值范围在0 1 0 7之间 4 收敛条件 61 算法步骤 1 选择可行域内初始点X 0 2 选取初始罚因子r 0 与罚因子降低系数c 并置K 0 3 求min x K r K 解出最优点xK 4 当K 0转步骤5 否则转步骤6 5 K K 1 r K 1 r K xK 10 xK 并转步骤3 6 按终止准则判别 若满足转步骤7 否则转步骤5 7 输出最优解 X F 停止计算 62 63 2 外点法 外点法是从可行域的外部构造一个点序列去逼近原约束问题的最优解 外点法可以用来求解含不等式和等式约束的优化问题 外点惩罚函数的形式为 r是惩罚因子 外点法的迭代过程在可行域之外进行 惩罚项的作用是迫使迭代点逼近约束边界或等式约束曲面 由惩罚项的形式可知 当迭代点x不可行时 惩罚项的值大于0 64 例5 3用外点法求解下列有约束优化问题 解 惩罚函数为 对上式求偏导 得 65 无约束目标函数极小化问题的最优解系列为 当惩罚因子渐增时 由下表可看出收敛情况 66 67 内点法和外点法的简单比较内点法的特点 1 始点必须为严格内点 2 不适于具有等式约束的数学模型 3 迭代过程中各个点均为可行设计方案 4 一般收敛较慢 5 初始罚因子要选择得当 6 罚因子为递减 递减率c有01 68 3 混合法 混合法是用内点法处理不等式约束 用外点法处理等式约束 可以用来求解含不等式和等式约束的优化问题 混合惩罚函数的形式为 r是惩罚因子 混合法具有内点法的特点 迭代过程在可行域之内进行 参数的选择同内点法 69 惩罚函数法原理简单 算法易行 且分内点法 外点法和混合法三种 各有特点 适用范围广 需要和有效的无约束优化方法结合使用 因此该方法也是应用较多的有约束优化方法 70 5 6序列二次规划法 序列二次规划法的基本原理是将原问题转化为一系列二次规划子问题 对于 相对应的拉格朗日函数为 在xk点作泰勒展开 取二次近似表达式 71 令 拉格朗日函数的一阶导数为 Hk用变尺度矩阵Bk来代替 将等式约束函数在xk作泰勒展开 取线性近似式 72 构成二次规划子问题 求解上述二次规划子问题 得到的d就是搜索方向 沿搜索方向进行一维搜索确定步长 最终得到原问题的最优解 对具有不等式约束的非线性规划问题 构成二次规划子问题为 73 求解时 在每次迭代中应对不等式约束进行判断 保留其中的起作用约束 除掉不起作用的约束 将起作用的约束纳入等式约束中 这样 其中不等式约束的子问题和只具有等式约束的子问题保持了一致 74 蒙特卡洛优化方法 介绍 对于约束优化问题 最理想的当然是得到严格意义上的真正全局最优解 然而 要做到这一点往往是不现实的 有的问题 例如非凸的非线性规划问题 至今在理论上还没有一种算法能保证得到全局最优解 有些问题 如凸规划 虽然从理论上讲可以得全局最优解 但是在实际计算中 也只能逼近最优解 且计算量往往很大 在实际工作中 人们往往希望只用较少的计算量就找到有较大概率保证的近似最优解