07第三章罚函数法及改进算法

第 3 章 罚函数法及改进算法 29 第 3 章 罚函数法及改进算法 3 1 引言引言 罚函数法是解决约束优化问题的重要方法 它的基本思想是用无约束 问题代替约束问题 因而无约束问题的目标函数必须是原来的目标函数与 约束函数的某种组合 类似线性规划中的 M 法求初始可行解 在原来的目 标函数上加上由约束函数组成的一个 惩罚项 来迫使迭代点逼近可行域 所以称为罚函数法 这样把约束问题转化成求解一系列的无约束极小点 通过有关的无约束问题来研究约束极值问题 从而使问题变的简单 许多 非线性约束优化方法都要用罚函数作为评价函数来评价一个点的好坏 这 在选择新点确定步长等方面都起着重要的作用 不同的罚项对算法影响很 大 根据罚项的不同可以分为以下几类 外罚函数法外罚函数法 对于问题 3 1 min f x 3 2 st 0 i c x 1 2 im 3 3 0 i c x 1 2 immn 其中为线性连续函数 n fRR 定义外罚函数为 3 4 L x f xP x f xQ x 3 5 Q x 11 min 0 mn ii ii m c xc x 通常取 这样定义的外罚函数法 当为可行点是 当 2 x 0Q x 不是可行点时 而且离可行域越远的值越大 它优点x 0Q x x Q x 是允许从可行域的外部逐步逼近最优点 但其明显的缺点是它需要求解一 燕山大学理学硕士毕业论文 30 系列无约束极小化问题 计算工作量很大 且由于其收敛速度仅是线性的 往往需要较长的时间才能找到问题的近似解 再考虑到实际中所使用的终 止准则 若实现不当 则算法很难找到约束问题的一个较好可行解 从而 不适用于那些要求严格可行性的问题 内罚函数法内罚函数法 它是针对不等式约束 3 1 3 3 提出的 基本思想是在约束区域的边界 筑起一道 墙 来 当迭代点靠近边界时 函数值陡然增大 于是最优点 被挡在可行域内部 这样产生的点列每个点都是可行点 通常定义内罚 k x 函数为 3 6 1 B xf xB x 3 7 1 1 m i i B x c x 要减弱的影响 故令逐渐增大 内罚函数法的好处是每次迭代的点 B x 都是可行点 当迭代到一定阶段时 可以被接受为一个较好的近似最优解 但是内点罚函数法要求初始点位于可行域的内部 除特殊情况外 确定这 样一个初始点并非易事 此外 由于内点罚函数不是处处有定义或不一定 存在全局极小 故无约束最优化问题中的线性搜索方法不再适用 另外 当接近可行域边界时 内点罚函数法必须修正通常的线性搜索方法 由于内点罚函数法不能处理等式约束 且寻求初始可行点的计算工作 量往往太大 因此 在实际中 为了求解一般的非线性约束优化问题 人 们往往将内点罚函数法与外点罚函数法结合起来适用 混合罚函数法混合罚函数法 混合罚函数法是针对问题 3 1 3 3 提出来的 当初始点给定后 对 0 x 等式约束和不被满足的那些不等式约束用外罚函数法 而被满足的那 0 x 0 x 些不等式约束用内罚函数法 通常定义混合罚函数为 3 8 1 11 i I i P xf xP x c x 第 3 章 罚函数法及改进算法 31 3 9 2 22 1 min 0 m ii ii I P xc xc x 1 0 1 2 i Ii c ximmn 2 0 1 2 i Ii c ximmn 精确罚函数法精确罚函数法 对于外点罚函数法和内点罚函数法来说 其工作量很大 收敛慢的主对于外点罚函数法和内点罚函数法来说 其工作量很大 收敛慢的主 要原因是它们需要求解一系列的无约束优化问题 要原因是它们需要求解一系列的无约束优化问题 而导致相应罚函数的无 约束极小化运算越来越难于精确执行 效率差则是因为需要罚因子趋于无效率差则是因为需要罚因子趋于无 穷大或零所带来的罚函数呈病态问题 穷大或零所带来的罚函数呈病态问题 由此自然想到 能否设计出一种罚设计出一种罚 函数函数 使得只要令其中的罚参数取适当的有限值后 该罚函数的无约束极 小点就恰好是原约束问题的最优解 从而克服外 内点罚函数法的缺点呢 通常称这样的罚函数为精确罚函数 对问题 3 1 3 3 定义如下 1 T m Cxcxcx ii cxc x 1 2 im min 0 ii cxc x 1 2 immn 对于罚函数 1 L 1 1 P xf xCx 其中是罚因子 如果0 则在二阶充分条件 0 T d W d 0d 0 T A d 的假定下可证是罚函数的局部严格极小点 所以罚函数也常称为x 1 L 1 L 精确罚函数 同理 罚函数也是精确罚函数 1 LL 1 P xf xCx 乘子罚函数法乘子罚函数法 内外罚函数法的缺点是需要罚因子趋于无穷大才能使求解罚函数的极 燕山大学理学硕士毕业论文 32 小和求解原向题等价 乘子罚函数法具有不要求初始点为严格内点 甚至 不要求其为可行点的特点 它利用近似 Lagrange 乘子 求其近似解 并且 逼近最优解 而不需要无穷大的罚因子 因此对它的研究有重要的理论和 实用价值 最早的乘子罚函数 又称为增广 Lagrange 函数 是由 Henstenes 1969 针 对等式约束问题 3 1 3 2 导出的 其形式为 3 10 2 2 T P xf xc xc x 增广 Lagrange 函数的另一种等价形式是在 1969 年由 Powell 提出的 它提 出对进行平移 即用代替 是参数 这种平移的好处 i c x ii c x i c x i 是不破坏的方向 由此 Powell 1969 得到罚函数 i c x 3 11 2 1 2 m T ii i P xf xc xc x 如果定义 则知式 3 10 与 3 11 只相差与无关的项 ii x 2 1 2 m i i 由于式 3 10 与 3 11 等价 故罚函数 3 10 也称为 Henstenes Powell 罚函数 我们看到通常都是用二次罚函数作为罚项 因此称之为二次罚函数乘 子法 然而 它的缺点是容易引起罚因子过大 造成罚函数的 Hesse 矩阵 严重病态 许多非线性约束优化方法都要用某个罚函数作为评价函数来评价一个 点的好坏 这在选择新点确定步长等方面都起着重要的作用 因此对不同 罚项的研究具有重要的理论和实际价值 近年来 许多研究者试图通过改 变罚项构造出新的罚函数 有效地避免罚因子过大引起的罚函数的 Hesse 矩阵严重病态的情况 第 3 章 罚函数法及改进算法 33 3 2 优化中的罚函数法优化中的罚函数法 对一般约束最优化问题 3 12 min f x 3 13 st 0 i c x 1 2 im 3 14 0 i c x 1 2 immn 定义定义 1 称 3 15 k L x k f xPx k f xQ x 为问题 3 12 3 14 的优化罚函数 为罚因子 其中罚项0 3 16 11 min 0 mn ii ii m Q xq c xqc x 其中且满足如下性质 q ttR 1 在中连续可微且为对称凸函数 q tR 2 对 当且仅当时 tR 0q t 0t 0q t 3 lim t q t lim t q t 若定义 min 0 i i i c x c x c x 1 2 1 2 im immn 则是可行点当且仅当 x 0 i c x 我们通过的极小点 其中为一定值 得到相应无约束极小点 k L x k 序列来逼近约束问题 3 12 3 14 的极小点 k x x 罚函数算法 罚函数算法 步 1 选定初始点为 选取初始惩罚因子 可取 惩罚因 0 x 1 0 1 1 子的放大系数 可取 置 1c 10c 1k 步 2 以为初始点 求解无约束问题 1k x min n k x R L x 燕山大学理学硕士毕业论文 34 其中 设其极小点为 k kk L xf xPxf xQ x k x 步 3 若 则就是所要求的最优解 停止 否则转下一步 kQ x k x 步 4 置 转步 2 1kk c 1kk 由罚项的特点 当趋向于无穷时 随着的不断增大 对每个不可k k 行点的惩罚也不断增大并趋向于无穷 因此 在对应于的无约束 kQ x k 极小化问题的最优解处 的值应不断减小 从而保证逐步趋于 k x kQ x k x 可行并最终达到问题 3 12 3 14 的最优解 由 的定义及极 Q x k L x 小点的含义 我们很容易证明下列结论 引理引理 1 给定 是 3 15 的解 则也是约束问题0 k k x k x 3 17 min n x R f x 3 18 st ii c x 1 2 in 的解 其中 i ik c x 证明证明 由的性质知在是增函数 且 q x 0 又因为为对称函数 所以 ii k q c xq c x q x 由此可得 ii kk q c xq c x iiq c xq c x ii k q c xq c x 对任何满足式 3 18 由的定义 我们有x k x 3 19 1 n i k i f xq c x 1 n i kkk i f xq c x 所以 3 20 1 n ii kkkkk i f xf xq c xq c xf xx 第 3 章 罚函数法及改进算法 35 故知是问题 3 17 3 18 的解 k x 证毕 由以上引理可知 若取充分小 则当算法迭代结束时 是问题 3 k x 12 3 14 的近似解 引理引理 2 对于由算法所产生的序列总有 k x 3 21 11 kkkk L xL x 3 22 1 kk Q xQ x 3 23 1 kk f xf x 其中 1k 证明证明 由和可知 L xf xQ x 1kk 11111 kkkkk L xf xQ x 111 kkkkk f xQ xL x 又因为是的极小点 所以对于任意总有 k x k L x x kkk L xL x 特别有 1 kkkk L xL x 由此可证得 3 21 因为和分别使和取极小 所以有 k x 1k x k L x 1 k L x 11 kkkkkk f xQ xf xQ x 1111 kkkkkk f xQ xf xQ x 由上式可得 11 kkkkk f xf xQ xQ x 111 kkkkk Q xQ xf xf x 由此可得 11 0 kkkk Q xQ x 由于 所以 3 22 成立 1 0 kk 最后 由式 3 21 和 3 22 得式 3 23 成立 证毕 定理定理 1 设非线性约束问题 3 12 3 14 的最优解存在 设由算法 k x 燕山大学理学硕士毕业论文 36 产生 且罚参数序列单调递增且趋于 则的任何极限点都是 k k x 问题 3 12 3 14 的可行域上的最优解 证明证明 设 又设是问题 3 12 3 14 的最优解 由于是 k xx x k x 无约束问题 min k Lx n xR 的解 由于可行 即 故有 x 0Q x kk kk LxLxf xQ xf x 即 k kkkk Lxf xQ xf x 由此可得 由于 故得 0 k k k f xf x Q x k xx k 且 f xf x 0Q x 即可行 且 但是问题 3 12 3 14 的解 因此也是问 x f xf x x x 题 3 12 3 14 的解 证毕 我们现在对于优化中的罚函数法进行一般类型的概况 并证明其收敛 性 但是需要说明的是其中不同种类的罚函数法在其收敛速度各有其不同 3 3 改进的罚函数法及收敛性改进的罚函数法及收敛性 3 3 1 改进的罚函数算法 罚函数法是解决约束优化问题的重要方法 它的基本思想是把约束优 第 3 章 罚函数法及改进算法 37 化问题转化成求解一系列的无约束极小化问题 通过有关的无约束问题来 研究约束极值问题 经常采用的方法之一是在原来的目标函数上加上由约 束函数组成的一个 惩罚项 来迫使迭代点逼近可行域 这种方法称为罚 函数法 如何选取罚函数 以加速迭代算法的收敛速度如何选取罚函数 以加速迭代算法的收敛速度 一直是约束优化 问题研究的热点问题 罚函数作为评价函数来评价一个点的好坏 这在选择新点确定步长等 方面都起着重要作用 不同罚项的选取 构成不同的罚函数 必然会对算 法产生不同的影响 因此对不同罚项的研究具有重要的理论和实用价值 对一般约束最优化问题 3 24 min f x 3 25 st 0 i c x 1 2 im 3 26 0 i c x 1 2 immn 通常使用的外函数形式为 L xf xQ x 其中罚项为 为 11 min 0 mn ii ii m Q xc xc x 1 1 参数 若取 我们称上述罚函数为二次罚函数 2 L x 问题 3 24 3 26 的可行域为R R x 0 1 2 i c xim 0 1 2 i c ximmn 显然 当为可行点时 当不是可行点时 而且x 0Q x x 0Q x 离可行域越远的值越大 它的优点是允许从可行域的外部逐步逼近x Q x 逼近最优点 但按上述定义的罚函数的缺点是 需要罚因子趋于无穷大 罚函数的缺点是 需要罚因子趋于无穷大 才可能使求解罚函数的极小和求解原问题等价 才可能使求解罚函数的极小和求解原问题等价 为了有效的改善这种罚函数 我们试图构造一种能够加速迭代算法收 敛的外罚函数法 本文提出一种用双曲正弦函数作罚项的罚函数本文提出一种用双曲正弦函数作罚项的罚函数 并由此 构建了双曲正弦罚函数法 不仅证明了该罚函数和算法的合理性及迭代点 列的收敛性 而且做了数值实验 结果表明本文中所提出的罚函数及对应 的算法可以在罚因子与二次罚函数方法中的罚因子相同的情况下 有着更 快的收敛速度 定义定义 1 称 燕山大学理学硕士毕业论文 38 3 27 L xf xP xf xQ x 为问题 3 24 3 26 的双曲正弦罚函数 为罚因子 其中罚项0 3 28 22 11 sinh sinh min 0 mn ii ii m Q xc xc x 其中 sinh 2 tt ee t tR 22 sinh 2 tt ee t tR 若定义 min 0 i i i c x c x c x 1 2 1 2 im immn 则是可行点当且仅当 x 0 i c x 我们通过一系列双曲正弦函数的极小点 其中为一定值 k L x k 得到相应无约束极小点 序列来逼近约束问题 3 24 3 26 的极小点 k x x 双曲正弦罚函数算法 双曲正弦罚函数算法 步步 1 选定初始点为选定初始点为 选取初始惩罚因子 选取初始惩罚因子 可取可取 惩罚因 惩罚因 0 x 1 0 1 1 子的放大系数 可取 置 1c 10c 1k 步 2 以为初始点 求解无约束问题 1k x min n k x R L x 其中 k kk L xf xPxf xQ x 设其极小点为 k x 步 3 若 则就是所要求的最优解 停止 否则转下一步 kQ x k x 步 4 置 转步 2 1kk c 1kk 3 3 2 收敛性证明及数值试验 第 3 章 罚函数法及改进算法 39 引理引理 1 设函数和由定义 1 定义 由算法产生 且罚参数序QP k x 列单调递增 则 k 1 1 kk Q xQ x 2 1 kk f xf x 3 1 1 kk kk LxLx 证明证明 由的定义知 1 k x 1 111 kk kk kk kk LxLx LxLx 上面的两式相加 得 11 0 kkkk Q xQ x 因此 即成立 1 kk Q xQ x 1 由得 2 111 kk kk LxLx 111 kkkkkk f xf xQ xQ xf x 即成立 2 由以及的定义得 3 L k x 111 kk kkkkk LxLxf xQ x 1 1111 k kkkk f xQ xLx 即成立 3 证毕 引理引理 2 设函数和由定义 1 定义 由算法产生 且罚参数序QP k x 列单调递增 记 则也是约束问题 k kk Q x k x 3 29 min f x st k Q x 的解 燕山大学理学硕士毕业论文 40 证明证明 设是问题 3 29 的可行点 我们有x 0 kk Q xQ x kk k LxLx k f xf x k f xf x 因此是问题 3 29 的解 k x 证毕 定理定理 1 设非线性约束问题 3 24 3 26 的最优解存在 设由算法 k x 产生 且罚参数序列单调递增且趋于 则的任何极限点都是 k k x 问题 3 24 3 26 的可行域上的最优解 证明证明 设 又设是问题 3 24 3 26 的最优解 由于是 k xx x k x 无约束问题 的解 由于可行 即 故有min k Lx n xR x 0Q x kk kk LxLxf xQ xf x 即 k kkkk Lxf xQ xf x 由此可得 由于 故得 0 k k k f xf x Q x k xx k 且 即可行 且 但是问题 3 f