第五章_惩罚函数法.ppt

5 3 4惩罚函数法 惩罚函数法简介内点法外点法混合法总结 惩罚函数法简介 惩罚函数法是一种使用很广泛 很有效的间接法 基本原理 把约束优化问题转化成无约束优化问题来求解 两个前提条件 一是不破坏原约束的约束条件二是最优解必须归结到原约束问题的最优解上去 按照惩罚函数的构成方式 惩罚函数法分为三种 外点法 内点法 混合法 惩罚项 r k m k 罚因子 惩罚函数 5 3 4 1内点法 引例设有一维不等式约束优化问题的数学模型 S T 由图可见 目标函数的可行域为x b 在可行域内目标函数单调上升 它的最优解显然是 x b F ab 对引例的惩罚函数进行分析 以对内点法有初步认识 本问题是不等式约束优化问题 故只有一项惩罚项 一个罚因子 规定罚因子为某一正数 当迭代点是在可行域内时 则惩罚项的值必为正值 因此必有 而且 当x越趋近于约束边界时 由于惩罚项 增大 所以罚函数的值越大 当x b时 罚函数的值将趋近于 因此 当初始点取在可行域内 求函数的极小值时 只要适当控制搜索步长 防止迭代点跨入非可行域 则所搜索到的无约束极小点x 必可保持在可行域内 若对于罚因子的取值由初始的逐渐变小时 惩罚函数愈逼近于原目标函数F x 罚函数曲线越来越接近于原F x ax直线 如图所示 对应罚函数的最优点列不断趋近于原约束优化问题的最优点x b 小结 由以上可见 如果选择一个可行点作初始点 令其罚因子由大变小 通过求罚函数的一系列最优点 显见 无约束最优点序列将逐渐趋近于原约束优化问题的最优点x 内点罚数法的形式及特点 具有不等式约束的优化问题的数学模型 u 1 2 p 构造如下形式的内点罚函数 S T 关于惩罚因子规定为正 即 且在优化过程中是减小的 为确保为递减数列 取常数C 0 C 1 称系数C为罚因子降低系数 0 或 关于惩罚项 由于在可行域内有 且永远取正值 故在可行域内惩罚项永为正 的值越小则惩罚项的值越小 由于在约束边界上有 因此 当设计点趋于边界时 惩罚项的值将趋于无穷大 由此可知 在可行域内 始终有 当时 却有 所以整个最优化的实质就是用罚函数去逼近原目标函数F x 当设计点逐渐由内部趋近于边界时 由于惩罚项无穷增大 则罚函数也将无穷增大 从函数图形上来看 犹如在可行域的边界上筑起一道陡峭的高墙 使迭代点自动保持在可行域内 用此办法来保证搜索过程自始至终不离开可行域 所以 内点法也常称为围墙函数法 内点罚函数法的求解过程 为了用惩罚函数去逼近原目标函数F x 则要用F x 及构造一个无约束优化问题的数学模型 选取初始点 原约束优化问题的内点 初始罚因子 罚因子降低系数C 用无约束优化方法求上式无约束优化问题的最优解 所得解为 当k在增大的过程中 得到惩罚函数的无约束最优点列为 点列中各点均在可行域内部 随着k 的过程 点列将趋近于原约束问题的最优解x 即 x 由此可知 内点法的序列无约束最优点是在可行域内部且趋近于约束最优点x 的 内点罚函数还可以按如下形式构成 初始点x 0 的选取 由于内点法的搜索是在可行域内进行 显然初始点必须是域内可行点 须满足 确定初始点常用如下两种方法 自定法即根据设计者的经验或已有的计算资料自行决定某一可行点作为初始点 搜索法任选一个设计点为初始点 通过对初始点约束函数值的检验 按其对每个约束的不满足程度加以调整 将点逐步引入到可行域内 成为可行初始点 这就是搜索法 关于几个参数的选择 初始罚因子r 0 的选取 如果值选得太大 则在一开始罚函数的惩罚项的值将远远超出原目标函数的值 因此 它的第一次无约束极小点将远离原问题的约束最优点 在以后的迭代中 需要很长时间的搜索才能使序列无约束极小点逐渐向约束最优点逼近 如果值选得太小 则在一开始惩罚项的作用甚小 而在可行域内部惩罚函数与原目标函数F x 很相近 只在约束边界附近罚函数值才突然增高 这样 使其罚函数在在约束边界附近出现深沟谷地 罚函数的性态变得恶劣 如下图 对于有深沟谷地性态差的函数 不仅搜索所需的时间长 而且很难使迭代点进入最优的邻域 以致极易使迭代点落入非可行域而导致计算的失败 r 0 1 50 或 递减系数C的选择 罚因子递减系数C的选择 一般认为对算法的成败影响不大 规定0 C 1 若C值选得较小 罚因子下降快 可以减少无约束优化的次数 但因前后两次无约束最优点之间的距离较远 有可能使后一次无约束优化本身的迭代次数增多 而且使序列最优点的间隔加大 对约束最优点的逼近不利 相反 若C值取得较大 则无约束优化次数就要增多 通常建议取C 0 1 0 5 终止准则 随着罚因子的值不断减小 罚函数的序列无约束最优点将越来越趋近于原约束优化问题的最优点 设惩罚函数的无约束最优点列为 对应的罚函数值为 终止准则可用下述两者之一 相邻两次惩罚函数无约束最优点之间的距离已足够的小 设 1为收敛精度 一般取 1 10 4 10 5 则需要满足 相邻两次惩罚函数值的相对变化量已足够小 设 2为收敛精度 一般取 2 10 3 10 4 则需要满足 算法步骤 构造内点惩罚函数 选择可行初始点 初始罚因子 罚因子降低系数C 收敛精度与 置k 0 求无约束优化问题 有最优点 当k 0时转步骤 否则转步骤 置k k 1 并转步骤 由终止准则 若满足则转步骤 否则转 输出最优解 x F 内点法流程图 给定 x 0 D r 0 C 1 2 k 0 K 0 入口 用无约束优化方法求罚函数的优化点 出口 内点罚函数的特点 内点法只适用于解不等式约束优化问题 由于内点法需要在可行域内部进行搜索 所以初始点必须在可行域内部选取可行设计点 内点法的突出优点在于每个迭代点都是可行点 因此 当迭代达到一定阶段时 尽管尚没有达到最优点 但也可以被接受为一个较好的近似解 5 3 4 2外点法 外点法可以解不等式约束优化问题或等式约束优化问题 引例设有一维不等式优化问题的数学模型 用外点法构造惩罚函数 具体构造形式如下 x b x b S T 写成另一种形式 如上图 此处的惩罚函数也是由原目标函数F x 与惩罚项而组成 惩罚项中包含有可调整的参数r k 与约束函数 由惩罚项的构造可知 若迭代点在可行域的内部 惩罚项的值为0 惩罚函数值与原目标函数值相等 而若在非可行域 即可行域的外部 惩罚项是以约束函数的平方加大的 即迭代点违反约束越严重 惩罚项的值增加的越大 因此 在非可行域内 必有且罚因子r k 越大 惩罚作用越明显 由图 对于某r k 值 求出惩罚函数的最优点当取罚因子为递增数列 随k的增加 罚函数的无约束最优点序列为 该序列将趋近与原约束问题的最优点x x b 值得注意的是 尽管增加直至趋于无穷大 但最终的近似最优点x 仍在可行域的外部 即外点法构造的罚函数是使迭代点从可行域的外部逐渐逼近约束最优点 这正是外点法名称的由来 外点罚函数法的形式及特点 先讨论解不等式约束优化问题 设有不等式约束优化问题 u 1 2 p 构造外点法惩罚函数的常见形式 取正递增 S T 引入罚因子递增系数C 1 并令 惩罚项 的含义可用另一形式表示 当gu x 0 x D 当gu x 0 x D 在可行域内 包括边界 在非可行域 为递增函数 外点罚函数的求解过程 用外点罚函数去逼近原目标函数F x 构造一个无约束优化问题模型 x Rn 任选初始点x 0 初始法罚因子r 0 0 罚因子递增系数C 1 对于r k 为某一值 同过对惩罚函数的无约束求优 可得最优点 随着k的增大 得无约束最优点列 在k 的过程中 点列将趋近于原问题的最优点 实线为原目标函数等值线 虚线为罚函数等值线 总结 由上图可见 两种等值线在可行域内部及边界上是重合的 而在非可行域中 罚函数的等值线升高了 即只有在可行域外部惩罚项才起到惩罚的作用 r k 值越大 惩罚作用越大 由上b图可知 在起作用约束边界处罚函数等值线变得越密集和越陡峭 随r k 的增大 最优点列将越接近于原约束优化问题的最优点x 但须注意 近似的最优点是落在边界处非可行域一侧 对几个问题的讨论 1 初始点x 0 的选取 在可行域及非可行域内均可 2 初始罚因子r 0 和递增系数C的选取 外点法中 这两者的选择对算法的成败和计算速度有显著的影响 选取过小 则序贯无约束求解的次数就增多 收敛速度慢 反之 则在非可行域中 发函数比原目标函数要大得多 特别在起作用约束边界处产生尖点 函数性态变坏 从而限制了某些无约束优化方法的使用 致使计算失败 C的选取影响不大 通常C 5 10 3 约束容差带 最优点在非可行域内 是一个非可行点 这对某些工程是不允许的 因此 可在约束边界可行域一侧加一条容差带 相当于将约束条件改为 是容差量 通常 终止准则 随着罚因子的值不断增大 罚函数的序列无约束最优点将越来越趋近于原约束优化问题的最优点 设惩罚函数的无约束最优点列为 对应的罚函数值为 终止准则可用下述两者之一 相邻两次惩罚函数无约束最优点之间的距离已足够的小 设 1为收敛精度 一般取 1 10 4 10 5 则需要满足 相邻两次惩罚函数值的相对变化量已足够小 设 2为收敛精度 一般取 2 10 3 10 4 则需要满足 外点法流程图 给定 x 0 R r 0 C 1 2 k 0 k 0 入口 用无约束优化方法求罚函数的优化点 出口 算法步骤与流程图 求 得最优点 当k 0时转步骤 否则转步骤 置k k 1 并转步骤 由终止准则 若满足则转步骤 否则转 输出最优解 x F 停止计算 算法步骤 在n维空间任取初始点x 0 选取初始罚因子r 0 递增系数C 并置k 0 用外点罚函数法解等式约束优化问题 设有二维约束优化问题 h1 x x1 x2 10 0 如右图 h1 x 为该约束问题的可行域 这条直线以外的整个x1ox2平面为非可行域 目标函数等值线与该直线的切点为最优点 最优点 S T 按外点法的基本思想 构造惩罚函数 x D x D 在可行域上 惩罚项的值为零 惩罚函数值与原目标函数值相同 在非可行域上 惩罚函数的值恒为正 罚函数大于原目标函数 即在可行域外惩罚项起到了惩罚作用 在k 的过程中 点列将趋近于原问题的最优点 对于m k 随着k的增大 得无约束最优点列 推广到具有一般的等式约束优化问题 首先构造如下形式的外点惩罚函数 惩罚因子m k 规定取正 m 0 1 在可行域上值为零 非可行域上 值恒大于零 S T 5 3 4 3混合法 用罚函数法解决有等式约束和不等式约束的一般约束 GP型 优化问题的方法 把它称为混合惩罚函数法 简称混合法 1混合法惩罚函数的形式及特点 一般约束问题的优化模型 S T 用惩罚函数法将其转化为无约束优化问题 惩罚函数是由原目标函数及包含约束函数的惩罚项组成 由于该问题的约束条件包含不等式约束与等式约束两部分 因此 惩罚项也应由对应的两部分组成 对应等式约束部分的只有外点法一种形式 而对应不等式的约束部分有内点法或外点法两种形式 因此按照对不等式约束处理的方法不同 混合法惩罚函数也具有两种形式 内点形式的混合法 不等式约束部分按内点法形式处理的混合法 惩罚函数形式为 是递增序列 为了统一用一个罚因子r k 且又按内点法形式 即 0 C 1 上式可写为 外点形式的混合法 不等式约束部分按外点法形式处理的混合法 惩罚函数形式为 其中 罚因子r k 恒为正 且为递增序列 即 递增系数C 1 初始点可在Rn空间内任选 初始罚因子及递增系数参照外点法选取 2算法步骤及流程图 参照内点法与外点法 外点法 内点法 例题 设有二维一般约束优化问题 数学模型为 S T 目标函数等值线及约束曲线见下图 最优点x 既要在不等式约束包括的范围内 同时又必须在等式约束h x 0的直线上 试求该约束优化