第五章_惩罚函数法.ppt

《第五章_惩罚函数法.ppt》由会员分享，可在线阅读，更多相关《第五章_惩罚函数法.ppt（51页珍藏版）》请在金锄头文库上搜索。

1、5 3 4 5 3 4 惩罚函数法惩罚函数法 惩罚函数法简介惩罚函数法简介 内点法内点法 外点法外点法 混合法混合法 总结总结 惩罚函数法简介惩罚函数法简介 惩罚函数法是一种使用很广泛 很有效的间接法 基本原理 基本原理 把约束优化问题转化成无约束优化问题来求解 把约束优化问题转化成无约束优化问题来求解 两个前提条件 两个前提条件 一是不破坏原约束的约束条件一是不破坏原约束的约束条件 二是最优解必须归结到原约束问题的最优解上去二是最优解必须归结到原约束问题的最优解上去 按照惩罚函数的构成方式 惩罚函数法分为三种 按照惩罚函数的构成方式 惩罚函数法分为三种 外点法 内点法 混合法外点法 内点法

2、混合法 惩罚项惩罚项 r r k k m m k k 罚因子罚因子 惩罚函数惩罚函数 5 3 4 1 5 3 4 1 内点法内点法 引例 引例 设有一维不等式约束优化问题的数学模型设有一维不等式约束优化问题的数学模型 S T 由图可见 目标函数的可行域为由图可见 目标函数的可行域为x bx b 在可行域内目标函数 在可行域内目标函数 单调上升 它的最优解显然是单调上升 它的最优解显然是 x b F ab 对引例的惩罚函数进行分析 以对内点法有初步认识 对引例的惩罚函数进行分析 以对内点法有初步认识 本问题是不等式约束优化问题 故只有一项惩罚项本问题是不等式约束优化问题 故只有一项惩罚项 一个罚

3、因子 一个罚因子 规定罚因子规定罚因子 为某一正数 当迭代点是在可行域内为某一正数 当迭代点是在可行域内 时 则惩罚项的值必为正值 因此必有时 则惩罚项的值必为正值 因此必有 而且 当x越趋近于约束边界时 由于惩罚项 增大 所以罚函数 的值越大 当x b时 罚函 数的值将趋近于 因此 当初始点取在可行域内 求 函数 的极小值时 只要适当控制搜索步长 防止迭代点跨入非可行域 则所搜索到的无约束极小点 x 必可保持在可行域内 若对于罚因子的取值由初始的 逐渐变小 时 惩罚函数 愈逼近于原目标函数F x 罚 函数曲线越来越接近于原F x ax直线 如图所示 对 应罚函数 的最优点列 不断趋近于原约

4、束优化问题的最优点x b 小结小结 由以上可见 如果选择一个可行点作初 始点 令其罚因子 由大变小 通过求罚函数 的一系列最优点 显见 无约束最优点序列将逐渐趋近于原约 束优化问题的最优点x 内点罚数法的形式及特点 内点罚数法的形式及特点 具有不等式约束的优化问题的数学模型具有不等式约束的优化问题的数学模型 u 1 2 p 构造如下形式的内点罚函数构造如下形式的内点罚函数 S T 关于惩罚因子规定为正 即关于惩罚因子规定为正 即 且在优化过程中 且在优化过程中 是减小的 为确保为递减数列 取常数是减小的 为确保为递减数列 取常数C C 0 C 1 称系数称系数C C为为罚因子降低系数罚因子降低

5、系数 0或 关于惩罚项关于惩罚项 由于在可行域内有 由于在可行域内有 且且 永远取正值 故在可行域内惩罚项永为正 永远取正值 故在可行域内惩罚项永为正 的值越小则惩罚项的值越小 的值越小则惩罚项的值越小 由于在约束边界上有由于在约束边界上有 因此 当设计点趋 因此 当设计点趋 于边界时 惩罚项的值将趋于无穷大 由此可知 在可于边界时 惩罚项的值将趋于无穷大 由此可知 在可 行域内 始终有行域内 始终有 当当 时时 却有 却有 所以整个最 所以整个最 优化的实质就是用罚函数优化的实质就是用罚函数 去逼近原目标函数去逼近原目标函数F x F x 当设计点逐渐由内部趋近于边界时 由于惩罚项无穷当设计

6、点逐渐由内部趋近于边界时 由于惩罚项无穷 增大 则罚函数也将无穷增大 增大 则罚函数也将无穷增大 从函数图形上来看 犹如在可行域的边界上筑起一从函数图形上来看 犹如在可行域的边界上筑起一 道陡峭的高墙 使迭代点自动保持在可行域内 用此办道陡峭的高墙 使迭代点自动保持在可行域内 用此办 法来保证搜索过程自始至终不离开可行域 所以 内点法法来保证搜索过程自始至终不离开可行域 所以 内点法 也常称为也常称为围墙函数法围墙函数法 内点罚函数法的求解过程内点罚函数法的求解过程 为了用惩罚函数为了用惩罚函数 去逼近原目标函数去逼近原目标函数F x F x 则要用则要用F x F x 及及 构造一个无约束优

7、化问题的数学模型构造一个无约束优化问题的数学模型 选取初始点 原约束优化问题的内点 选取初始点 原约束优化问题的内点 初始罚 初始罚 因子因子 罚因子降低系数 罚因子降低系数C C 用无约束优化方法求上式无 用无约束优化方法求上式无 约束优化问题的最优解 约束优化问题的最优解 所得解为所得解为 当 当k k在增大的过程中 得到惩罚函数的无在增大的过程中 得到惩罚函数的无 约束最优点列为约束最优点列为 点列中各点均在可行域内部 随着点列中各点均在可行域内部 随着k k 的过程 的过程 点列将趋近于原约束问题的最优解点列将趋近于原约束问题的最优解x x 即 即 x 由此可知 内点法的序列无约束最优

8、点由此可知 内点法的序列无约束最优点 是在可行域内是在可行域内 部且趋近于约束最优点部且趋近于约束最优点x x 的 的 内点罚函数还可以按如下形式构成内点罚函数还可以按如下形式构成 初始点 初始点x x 0 0 的选取 的选取 由于内点法的搜索是在可行域内进行 显然初始点必须由于内点法的搜索是在可行域内进行 显然初始点必须 是域内可行点 须满足是域内可行点 须满足 确定初始点常用如下两种方法确定初始点常用如下两种方法 自定法自定法 即根据设计者的经验或已有的计算资料自行决即根据设计者的经验或已有的计算资料自行决 定某一可行点作为初始点 定某一可行点作为初始点 搜索法搜索法 任选一个设计点任选一

9、个设计点 为初始点 通过对初始点为初始点 通过对初始点 约束函数值的检验 按其对每个约束的不满足程度加以调约束函数值的检验 按其对每个约束的不满足程度加以调 整 将整 将 点逐步引入到可行域内 成为可行初始点 点逐步引入到可行域内 成为可行初始点 这就是搜索法 这就是搜索法 关于几个参数的选择 关于几个参数的选择 初始罚因子初始罚因子r r 0 0 的选取 的选取 如果如果 值选得值选得太大太大 则在一开始罚函数的惩罚项的 则在一开始罚函数的惩罚项的 值将远远超出原目标函数的值 因此 它的第一次无约束极值将远远超出原目标函数的值 因此 它的第一次无约束极 小点将远离原问题的约束最优点 在以后的

10、迭代中 需要很小点将远离原问题的约束最优点 在以后的迭代中 需要很 长时间的搜索才能使序列无约束极小点逐渐向约束最优点逼近 长时间的搜索才能使序列无约束极小点逐渐向约束最优点逼近 如果如果 值选得值选得太小太小 则在一开始惩罚项的作用甚小 则在一开始惩罚项的作用甚小 而在可行域内部惩罚函数而在可行域内部惩罚函数 与原目标函数与原目标函数F x F x 很相近 很相近 只在约束边界附近罚函数值才突然增高 这样 使其罚函数只在约束边界附近罚函数值才突然增高 这样 使其罚函数 在在约束边界附近出现深沟谷地 罚函数的性态变得恶劣 在在约束边界附近出现深沟谷地 罚函数的性态变得恶劣 如下图 对于有深沟谷

11、地性态差的函数 不仅搜索所需的如下图 对于有深沟谷地性态差的函数 不仅搜索所需的 时间长 而且很难使迭代点进入最优的邻域 以致极易使时间长 而且很难使迭代点进入最优的邻域 以致极易使 迭代点落入非可行域而导致计算的失败 迭代点落入非可行域而导致计算的失败 r 0 1 50 或 递减系数递减系数C C的选择的选择 罚因子递减系数罚因子递减系数C C的选择 一般认为对算法的成败影响的选择 一般认为对算法的成败影响 不大 规定不大 规定0 C 10 C 1 若若C C值选得值选得较小较小 罚因子下降快 可以减少无约束优化 罚因子下降快 可以减少无约束优化 的次数 但因前后两次无约束最优点之间的距离较

12、远 有的次数 但因前后两次无约束最优点之间的距离较远 有 可能使后一次无约束优化本身的迭代次数增多 而且使序可能使后一次无约束优化本身的迭代次数增多 而且使序 列最优点的间隔加大 对约束最优点的逼近不利 列最优点的间隔加大 对约束最优点的逼近不利 相反 若相反 若C C值取得值取得较大较大 则无约束优化次数就要增多 则无约束优化次数就要增多 通常建议取通常建议取C 0 1 0 5C 0 1 0 5 终止准则 终止准则 随着罚因子随着罚因子 的值不断减小 罚函数的序列无约的值不断减小 罚函数的序列无约 束最优点将越来越趋近于原约束优化问题的最优点 束最优点将越来越趋近于原约束优化问题的最优点 设

13、惩罚函数设惩罚函数 的无约束最优点列为的无约束最优点列为 对应的罚函数值为对应的罚函数值为 终止准则可用下述两者之一终止准则可用下述两者之一 相邻两次惩罚函数无约束最优点之间的距离已足够的小 相邻两次惩罚函数无约束最优点之间的距离已足够的小 设设 1 1 为收敛精度 一般取为收敛精度 一般取 1 1 10 10 4 4 10 10 5 5 则需要满足 则需要满足 相邻两次惩罚函数值的相对变化量已足够小 相邻两次惩罚函数值的相对变化量已足够小 设设 2 2 为收敛精度 一般取为收敛精度 一般取 2 2 10 10 3 3 10 10 4 4 则需要满足 则需要满足 算法步骤 算法步骤 构造内点惩

14、罚函数构造内点惩罚函数 选择可行初始点选择可行初始点 初始罚因子 初始罚因子 罚因子降低系 罚因子降低系 数数C C 收敛精度 收敛精度 与与 置 置k 0k 0 求无约束优化问题 求无约束优化问题 有最优点有最优点 当当k 0k 0时转步骤时转步骤 否则转步骤 否则转步骤 置置k k 1k k 1 并转步骤 并转步骤 由终止准则 若满足则转步骤由终止准则 若满足则转步骤 否则转 否则转 输出最优解输出最优解 x x F F 内点法流程图内点法流程图 给定 给定 x x 0 0 D rD r 0 0 C C 1 1 2 2 k 0k 0 K 0 K 0 入口入口 用无约束优化方法求罚函数用无约

15、束优化方法求罚函数 的优化点的优化点 出口出口 内点罚函数的特点 内点罚函数的特点 内点法只适用于解不等式约束优化问题 由于内点法内点法只适用于解不等式约束优化问题 由于内点法 需要在可行域内部进行搜索 所以初始点必须在可行域需要在可行域内部进行搜索 所以初始点必须在可行域 内部选取可行设计点 内部选取可行设计点 内点法的突出优点在于每个迭代点都是可行点内点法的突出优点在于每个迭代点都是可行点 因此 当迭代达到一定阶段时 尽管尚没有达到最优点 因此 当迭代达到一定阶段时 尽管尚没有达到最优点 但也可以被接受为一个较好的近似解 但也可以被接受为一个较好的近似解 5 3 4 2 5 3 4 2 外

16、点法外点法 外点法可以解不等式约束优化问题或等式约束优化问题外点法可以解不等式约束优化问题或等式约束优化问题 引例 引例 设有一维不等式优化问题的数学模型设有一维不等式优化问题的数学模型 用外点法构造惩罚函数 具体构造形式如下用外点法构造惩罚函数 具体构造形式如下 x b x1C 1 并令 并令 惩罚项惩罚项 的含义可用另一形式表示的含义可用另一形式表示 当gu x 0 x D 当gu x 0 0 罚因子递增系数罚因子递增系数C 1C 1 对于对于r r k k 为某一值 同过对惩罚函数的无约束求优 可 为某一值 同过对惩罚函数的无约束求优 可 得最优点得最优点 随着 随着k k的增大 得无约束最优点列的增大 得无约束最优点列 在在k k 的过程中 点列将趋近于原问题的最优点的过程中 点列将趋近于原问题的最优点 实线为原目标实线为原目标 函数等值线函数等值线 虚线为罚函数虚线为罚函数 等值线等值线 总结总结 由上图可见 两种等值线在可行域内部及边界上是重合由上图可见 两种等值线在可行域内部及边界上是重合 的 而在非可行域中 罚函数的等值线升高了 即的 而在非可行域中 罚函数的等值线升高