[所有分类]第五章 约束优化方法.ppt

第五章约束优化方法 5 1约束最优解及其一阶必要条件 5 2随机方向法 5 3复合形法 5 4可行方向法 5 5内惩罚函数法 5 6外惩罚函数法 5 7混合惩罚函数法 5 8扩展内惩罚函数法 5 1约束最优解及其一阶必要条件 机械优化设计中的问题 大多数属于约束优化设计问题 其数学模型为 实际工程中大部分问题的变量取值都有一定的限制 也就是属于有约束条件的寻优问题 与无约束问题不同 约束问题目标函数的最小值必须是满足约束条件 即是由约束条件所限定的可行域内的最小值 只要由约束条件所决定的可行域是一个凸集 目标函数是凸函数 其约束最优解就是全域最优解 否则 将由于所选择的初始点的不同 而探索到不同的局部最优解上 在这种情况下 探索结果经常与初始点的选择有关 为了能得到全局最优解 在探索过程中最好能改变初始点 有时甚至要改换几次 1 直接法直接解法通常适用于仅含不等式约束的问题 思路 是在m个不等式约束条件所确定的可行域内 选择一个初始点 然后决定可行搜索方向sk且以适当的步长 k 进行搜索 得到一个使目标函数值下降的可行的新点 即完成一次迭代 再以新点为起点 重复上述搜索过程 直至满足收敛条件 根据求解方式的不同 约束优化设计问题可分为 直接解法 间接解法 直接法主要包括 随机方向法 复合形法和可行方向法 其迭代过程中 每一次的新迭代点X K 1 都要经过可行性和适用性条件的检验 可行性条件是指新迭代点X K 1 必须在可行域内 即满足 适用性条件是指新迭代点X K 1 的目标函数值较前一点是下降的 即满足 特点 在可行域内进行 若可行域是凸集 目标函数是定义在凸集上的凸函数 则收敛到全局最优点 否则 结果与初始点有关 凸集 非凸集 2 间接法目的 将有约束优化问题转化为无约束优化问题方法 以原目标函数和加权的约束函数共同构成一个新的目标函数 x r1 r2 成为无约束优化问题 通过不断调整加权因子 产生一系列 函数的极小点序列xk r1k r2k k 0 1 2 逐渐收敛到原目标函数的约束最优解 间接法主要包括 内点罚函数法 外点罚函数法和混合罚函数法 扩展内惩罚函数法 新目标函数 其中 惩罚项 加权因子 惩罚因子 r1 k r2 k 无约束优化问题 函数的极小点序列x k r1 k r2 k k 0 1 2 其收敛必须满足 5 2随机方向法 基本思想 随机产生初始点X 0 随机产生搜索方向S k 进行搜索 但要确保 新迭代点在可行域中 目标函数值的下降性 随机方向法 是约束最优化问题的一种常用的直接求解方法 一 随机方向的构成在计算机语言所适用的函数库中 都有一种随机函数 可以产生0 1之间的均匀分布的随机数 利用产生的随机数构成随机方向 若利用在 0 1 之间产生的随机数 i 1 2 n 构成单位矢量S 方法如下 把随机数 转化为另一区间 1 1 之间的随机数然后由随机数yi构成以下随机方向 由于随机数yi在区间 1 1 内产生 所构成的随机方向矢量S一定是在超球面空间里均匀分布且模等于1的单位矢量 如图5 1所示的二维问题 首先选定可行初始点X 0 利用随机函数构成随机方向S 1 按给定的初始步长h h0沿S 1 方向取得试探点 检查点X 1 的适用性和可行性 即检查 二 随机方向法 图5 1随机方向法 直至达到某迭代点不能同时满足适用性和可行性条件时停止 退回到前一点作为该方向搜索中的最终成功点 记作X 1 进而 将X 1 作为新的始点X 0 X 1 再产生另一随机方向S 2 重复以上过程 得到沿S 2 方向的最终成功点X 2 如此循环 点列X 1 X 2 必将逼近于约束最优点X 若两者均满足 X作为新的起点 继续按上述迭代式在S 1 方向上取得新点 重复上述步骤 迭代点可沿S 1 方向前进 1 若在某个换向转折点处 如图中的X 1 点 沿某搜索方向的试探点目标函数值增大或越出可行域 则弃去该方向 再产生另一随机方向作试探 试探成功就前进 试探失败再重新产生新的随机方向 2 当在某个转折点处沿m个 预先限定的次数 随机方向试探均失败 如图中点X 2 则说明以此点为中心 h0为半径的圆周上各点都不是适用 可行的 此时可将初始步长h0缩半后继续试探 直到f k 1 f k 且沿m个随机方向都试探失败时 则最后一个成功点 如图中的X 3 点 就是到达预定精度要求的约束最优点 迭代即可结束 3 m是预先规定在某转折点处产生随机方向所允许的最大数目 对于性态不好的目标函数或可行域有狭长弯道的问题 m应取较大的值 以提高解题的成功率 约束随机方向法的搜索方向比较灵活 当预定的随机方向限定数m足够大时 无 病态 问题出现 一般都能求出最优点 图5 2随机方向法程序框图 三举例例 用约束随机方向法求解 解 人工选取一初始点X0 5 5 T 初始点在可行域内 相应的目标函数值为F X0 50 第一次迭代1 产生两个伪随机数 求出第一个随机方向 生成两个伪随机数 由此得第一个随机方向为 2 求第一个迭代点 第一个迭代点表达式为 式中a为步长 将X1的表达式代入目标函数中 进行一维搜索 令目标函数对步长a的一阶导数为0 即可求出沿e1方向的最优步长 第一个迭代点为 3 检验X1点是否满足约束条件g X1 2 4 2 5 6 14 12 X1满足约束条件 是可行点 相应的目标函数值为 第二次迭代以X1为初始点 继续使用e1方向直到不满足可行性和适用性条件 再重新生成随机搜索方向e2 以下过程略 目标函数值下降 随机方向法方法评价 优点 1对目标函数无性态要求 2收敛快 当随机方向限定数m足够大时 3不受维数影响 维数愈高 愈体现优点 缺点 1对于严重非线性函数 只能得近似解 2当m不够大时 解的近似程度大 3对于非凸函数 有可能收敛于局部解 复合形法是求解约束非线性最优化问题的一种重要的直接方法 不需计算目标函数的梯度 而是靠选取复合形的顶点井比较各顶点处目标函数值的大小 来寻找下一步的探索方向的 在用于求解约束问题的复合形法中 复合形各顶点的选择和替换 不仅要满足目标函数值的下降 还应当满足所有的约束条件 5 3复合形法 比较复合形各顶点目标函数值的大小 去掉目标函数值最大的顶点 称最坏点 以坏点以外其余各点的形心为映射中心 用坏点的映射点替换该点 构成新的复合形顶点 一 复合形法基本思想 在n维空间中 由n 1 k 2n个点组成的多 边 面体称为复合形 以新的复合形顶点 代替原复合形中的最坏点 组成新的复合形 以不断的迭代 使新复合形逐渐逼近最优点 例如 设有一约束优化问题的数学模型是该目标函数的等值线和可行域的几何图形如图5 3所示 用复合形法求该问题的约束最优解的过程如下 令 X R X S X S X H 称X R 为映射点 为映射系数 通常取 1 3 可根据实际情况进行缩减 取次好点和好点连线的中点为X S 一般情况下 映射点的函数值比坏点的函数值要小 即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 在次好点和好点连线与坏点反向一侧的各点应具有较小的目标值 二 初始复合形的构成复合形的顶点K n 1个 对于维数较低的优化问题 由于顶点数目较少 可试凑几个可行点作为复合形的顶点 对于维数较高的问题 采用随机方法 先产生K个随机点 然后再把非可行点逐一调入可行域内 最终使K个随机点都成为可行点而构成初始复合形 复合形的产生可以 1 人工选择初始复合形 2 随机产生初始复合形 xi ai i bi ai i 1 2 n用这n个随机数xi作为坐标的点X就是一个随机点 这第一个点记作X 1 同样 产生其它的随机点X 2 X 3 X K 产生K个随机点 根据随机数产生的标准函数 可以在 0 1 开区间内产生均匀分布的随机数 i 利用该随机数可产生变量xi在给定界限ai xi bi内的随机数 因每产生一个随机点 需要n个随机数 因此 产生k个随机点总共需要连续发生K n个随机数 2 将非可行点调入可行域用上述方法产生的K个随机点 并不一定都是可行的 但是 只要它们中间有一个点在可行域内 就可以用一定的方法将非可行点逐一调入可行域 将产生的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 这个新点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个点就构成了初始复合形 三 复合形法的迭代步骤 1 构造初始复合形 2 计算各顶点的函数值F X j j 1 2 K 选出好点X L 和坏点X H 3 计算坏点外的其余各顶点的中心点X s 4 计算映射点X R 检查X R 是否在可行域内 若X R 为非可行点 将映射系数减半后再按上式改变映射点 直到X R 进入可行域内为止 5 构造新的复合形计算映射点的函数值F X R 并与坏点的函数值F X H 比较 可能存在两种情况 1 映射点优于坏点 F X R F X H 在此情况 用X R 代替X H 构成新的复合形 2 映射点次于坏点 F X R F X H 这种情况由于映射点过远引起的 减半映射系数 若有F X R F X H 这又转化为第一种情况 若经过多次的映射系数减半 仍不能使映射点优于坏点 则说明该映射方向不利 此时 应改变映射方向 取对次坏点的映射 再转回本步骤的开始处 直到构成新的复合形 6 判断终止条件1 各顶点与好点函数值之差的均方根值小于误差限 即 2 各顶点与好点的函数值之差的平方和小于误差限 即 3 各顶点与好点函数值差的绝对值之和小于误差限 即 如果不满足终止迭代条件 则返回步骤2继续进行下一次迭代 否则 可将最后复合形的好点X L 及其函数值F X L 作为最优解输出 例 用复合形法求解约束优化问题 迭代精度为0 01 课堂练习 解 n 2 取复合形顶点数k 2n 4 人为给出4个复合形顶点 经检验4个顶点均在可行域内 2进行迭代 获得新的复合形 求4个点的目标函数值 知 计算除坏点外所有顶点的中心XC 经检验XC在可行域内 求XH的映射点XR 取映射系数为1 3 经检验 映射点XR在可行域内 因F XR 5 1092 F XH 故用映射点替换X3 构成新的复合形 4个点的目标函数值为 最坏点为X4 最好点为X3 3检验迭代终止条件用各顶点与好点的目标函数之差的均方根小于误差作为终止迭代条件 即 若满足以上条件 XL为最优解 对于本题 不满足迭代终止条件 需继续迭代 在新的复合形中重复上述过程 复合形方法评价 1 复合形法 仅通过选取各顶点并比较各点处函数值的大小 就可寻找下一步的探索方向 但复合形各顶点的选择和替换 不仅要满足目标函数值下降的要求 还应当满足所有的约束条件 计算简单 不必求导 占内存小 随着维数的增加 效率大大下降 2 复合形法适用于仅含不等式约束的问题 3 因为迭代过程始终在可行域内进行 运行结果可靠 可行方向法是解决具有不等式约束优化问题的直接搜索法之一 对于问题 基本思想 5 4可行方向法 从任一可行点X K 出发 寻找一个恰当的方向S K 和一个合适的步长因子a K 于是产生的新迭代点为 使其满足 即在每次迭代中都保证搜索方向是在可行域内进行 称为可行方向 并且目标函数值必须稳步地下降方向 称为适用方向 满足上述两个条件的方向称为适用可行方向 迭代点沿着一系列适用可行方向移动 从而得到一系列的逐步改进的可行点X K 此搜索方法称为可行方向法 该方法的关键是在迭代过程中不断寻找既适用又可行的方向 具体算法由两部分组成 1确定一个适当的步长 2选择一个可行方向 步长 k 的选择原则 使新点x k 1 在可行域内 S k 的选择原则 必须保证搜索方向是在可行域内进行 即必须与所有适时约束的梯度方向成钝角 必须是目标函数值下降的适用方向 即必须与目标函数的梯度方向成钝角 同时满足以上两个条件的方向 称为适用可行方向 图5 4适用可行区域 一 基本搜索过程首先在可行域内取一初始点X 0 初始的搜索方向取X 0 点的目标函数的最速下降方向 即 对于域内任一可行点来说 负梯度方向总是一种适用可行方向 沿S 0 方向进行一维搜索 得最优步长为a 0 则第一个迭代点为X 1 所在的位置可能是下述三种情况之一 在可行域的内部 在容许的约束边界上 已越出可行域 即落入非可行域 如果发生情况 则通过一定的计算取得新的步长 使其迭代点返回至可行域的边界上 见图5 5 图5 5沿负梯度迭代的步长 于是上述三种情况就归结为两种情况 一种是X 1 点在可行域的内部 而非边界上 另一种是X 1 点落在可行域的边界上 如果X 1 点是在可行域的内部 则下一次迭代仍沿X 1 点的负梯度方向进行 一般地 对于不在约束边界上的域内点X K 下一次迭代总沿该点的负梯度方向进行一维搜索 a K 取为最优步长a 即a K a 其迭代式为直至迭代点落在约束边界上或越出某约束边界为止 如果X 1 点是在可行域边界上或是由边界以外调回到边界上 则下一次不再采用负梯度为搜索方向 而采用一个适用可行方向S K 若取a K 是在S K 方向上的一个适当大小的步长 则有 使点X K 1 仍在可行域内 且目标函数值下降 一般情况 这种搜索是沿着起作用约束的边界以割线方式逐步逼近最优点 由上述可行方向法的基本搜索过程可知 如何寻求适用可行方向和适当的步长 使迭代点逼近约束最优点 这是可行方向法要解决的两个基本问题 二 适用可行方向的数学条件1 适用性条件前面已经指出 搜索方向S K 满足适用性条件是指目标函数F X 沿该方向是下降的 若用方向导数的概念来描述 即目标函数F X 在X K 点沿S K 的方向导数应小于零 即 式中 cosa1 cosa2 cosan是矢量S K 与各坐标轴夹角的余弦 即方向余弦 或简记为 这说明 凡与目标函数负梯度矢量 成锐角的方向 都能满足适用性要求 图5 6 图5 6适用性条件的几何意义 2 可行性条件所谓满足可行性条件是指沿该方向一定有可行点存在 由X K 点出发 沿S K 方向 取适当步长a K 则 该点必须在可行域内 实际上 可行点与非可行点的标志是该点的约束函数值 若X K 点的所有约束函数值都小于零 则它是可行域内部的可行点 若X K 点的某个约束函数值或某几个约束函数值等于零或接近于零 则该点是在边界上的可行点 这一个或几个约束是X K 点的起作用约束 起作用约束函数的负梯度为 则条件可用矩阵表示为 这说明 为满足可行性要求 搜索矢量 与起作用约束 的夹角应为锐角 如图5 7所示 函数的梯度矢量 图5 7可行性条件的几何意义 3 适用可行方向的数学条件综上所述 为使搜索方向成为适用可行方向 其数学条件为同时满足不等式 这一条件的几何解释见图5 8 图5 8 a 是J 1的情况 适用可行方向 必须在一个既与 又与 成锐角的扇形空间x内 图5 8 b 是J 2 又与 成锐角构成的扇形空间 x2是既与 又与 成锐角而构成的扇形空间 适用可行方向 必须是在 的情况 X K 点起作用的约束是g1 X 与g2 X x1是既与 两个扇形空间x1 x2的公共区域x 即x1 之内 图5 8适用可行方向的几何解释 三 可行方向法的搜索策略 第一步迭代都是从可行的初始点出发 沿点的负梯度方向 将初始点移动到某一个约束面 只有一个起作用的约束时 上 或约束面的交集 有几个起作用的约束时 上 1 最优步长法 第一次搜索为负梯度方向 终止于边界 第二次搜索沿适用可行方向作一维搜索以最优步长因子求得最优点 反复以上两步 直至得到最优点x 图5 9最优步长法 2 边界反弹法 第一次搜索为负梯度方向 终止于边界 以后各次搜索方向均为适用可行方向 以最大步长从一个边界反弹到另一个边界 直至满足K T条件 图5 9边界反弹法 3 贴边搜索法 第一次搜索为负梯度方向 终止于边界 以后各次搜索贴边 约束面 进行 若适时约束面是切面 每次搜索到约束面的交集时 移至另一个约束面 直至收敛到最优点 沿线性约束面的搜索 图5 10贴边搜索法 若可行域是凸集 约束面是非线性时 从xk点沿切线 面 方向搜索 会进入非可行域 建立约束面的容差带 从x k 出发 沿s k 方向搜索到s k 方向与g x 0的交点x 后 再沿适时约束的负梯度方向返回约束面的x k 1 点 四 步长因子的确定 确定的步长应使新的迭代点为可行点 且目标函数具有最大的下降量 约束一维搜索 1 取最优步长因子x 从xk点出发 沿sk方向进行一维最优化搜索 取得最优步长 计算新点xk 1的值 图5 11迭代点为可行点 2 取到约束边界的最大步长从xk点出发 沿sk方向进行一维最优化搜索 得到的新点x为不可行点 改变步长 使新点x返回到约束面上来 使新点xk 1恰好位于约束面上的步长称为最大步长 图5 12新点x为不可行点 约束一维搜索 与以前所讲过的一维搜索相比 约束一维搜索的特点在于 对产生的每一个探测点都进行可行性判断 如违反了某个或某些约束条件 就必须减少步长因子 以使新的探测点落在最近的一个约束曲面上或约束曲面的一个容许的区间内 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 图5 13容许的区间 收敛条件 2 设计点xk满足库恩 塔克条件 1 设计点xk及约束允差满足 例 已知约束优化问题 课堂练习 试从第k次的迭代点Xk 12 T出发 沿由 1 1 区间随机数0 562和 0 254所确定的方向进行搜索 完成一次迭代 获取一个新的迭代点Xk 1 并作图画出目标函数的等值线 可行域和本次迭代的搜索路线 例 已知约束优化问题 课堂练习 试以X10 21 T X20 41 T和X30 33 T为复合形的初点 用复合形法进行两次迭代计算 一 惩罚函数法基本思想 通过构造惩罚函数把约束问题转化为一系列无约束最优化问题 进而用无约束最优化方法去求解 这类方法称为序列无约束最小化方法 SUMT sequentialunconstrainedminimizationtechnique 5 5内惩罚函数法 将有约束的优化问题转化为无约束优化问题来求解 前提 1不能破坏约束问题的约束条件 2使它归结到原约束问题的同一最优解上去 构成一个新的目标函数 称为惩罚函数 从而有 惩罚项必须具有以下极限性质 求解该新目标函数的无约束极小值 以期得到原问题的约束最优解 按一定的法则改变惩罚因子r1 k 和r2 k 的值 求得一序列的无约束最优解 不断地逼近原约束优化问题的最优解 根据约束形式和定义及惩罚因子的递推方法等不同 罚函数法可分为内惩罚函数法 外惩罚函数法和混合惩罚函数法三种 这种方法是1968年由美国学者A V Fiacco和G P Mcormick提出的 把不等式约束引入数学模型中 为求多维有约束非线性规划问题开创了一个新局面 二 内惩罚函数法 内点法 这种方法将新目标函数定义于可行域内 其初始点和产生的迭代点必然也在可行域内 此法称为内惩罚函数法 此法是求解不等式约束最优化问题的一种十分有效的方法 对于只具有不等式约束的优化问题 转化后的惩罚函数形式为 或 说明 rk是惩罚因子 它是一个由大到小且趋近于0的正数列 即 由于内点法的迭代过程在可行域内进行 惩罚项 的作用是阻止迭代点越出可行域 由 惩罚项 的函数形式可知 当迭代点靠近某一约束边界时 其值趋近于0 而 惩罚项 的值陡然增加 并趋近于无穷大 好像在可行域的边界上筑起了一道 高墙 使迭代点始终不能越出可行域 显然 只有当惩罚因子时 才能求得在约束边界上的最优解 惩罚因子的作用 由于内点法只能在可行域内迭代 而最优解很可能在可行域内靠近边界处或就在边界上 此时尽管泛函的值很大 但惩罚因子是不断递减的正值 经多次迭代 接近最优解时 惩罚项已是很小的正值 例5 1用内点法求 的约束最优解 解 用内点法求解该问题时 首先构造内点惩罚函数 用解析法求函数的极小值 运用极值条件 联立求解得 无约束极值点为 当 例5 2 用内罚函数法求解下列约束优化问题 解 构造内罚函数为 用解析法求极值 k 0f x 1 1 初始点x0的选取 使用内点法时 初始点应选择一个离约束边界较远的可行点 如太靠近某一约束边界 构造的惩罚函数可能由于障碍项的值很大而变得畸形 使求解无约束优化问题发生困难 2 惩罚因子初值r0的选取 惩罚因子的初值应适当 否则会影响迭代计算的正常进行 一般而言 太大 将增加迭代次数 太小 会使惩罚函数的性态变坏 甚至难以收敛到极值点 对于不同的问题 都要经过多次试算 才能决定一个适当r0 3 惩罚因子的缩减系数c的选取 在构造序列惩罚函数时 惩罚因子r k 是一个逐次递减到0的数列 相邻两次迭代的惩罚因子的关系为 式中的c称为惩罚因子的缩减系数 c为小于1的正数 一般的看法是 c值的大小在迭代过程中不起决定性作用 通常的取值范围在0 1 0 7之间 4 收敛条件 算法步骤 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 停止计算 5 内点法特点内点法只适用不等式约束优化问题 由于内点法是在可行域内部进行搜索 所以初始点必须是可行域内部的可行点 内点法的突出优点在于每个迭代点都是可行点 当迭代到一定的阶段时 尽管迭代点还没有达到最优点 但也可以被接受为一个较好的近似解 在机械优化设计问题中 这种近似解虽非最优点 但比初始方案已经有很大的改进 如果已能较好地符合工程设计的要求 则可以被接受作为一种最优设计 从而设计者可以主动灵活地从迭代点序列中选取一个合适的点 作为工程的实用解 例 用内点法求下面问题的最优解 课堂练习 并作图画出目标函数的等值线 可行域 5 6外惩罚函数法 外点法是从可行域的外部构造一个点序列去逼近原约束问题的最优解 外点法可以用来求解含不等式和等式约束的优化问题 对于约束的优化问题 构造外惩罚函数的常见形式如下 式中 惩罚因子r K 规定取正 与内点法不同的是在优化过程中r K 取为递增序列 即 由原目标函数与惩罚项组成 在可行域的内部及边界上有 在非可行域则有 将原目标函数加大 使等值面抬高 惩罚因子r K 愈大 增加愈烈 抬高的愈显著 对几个问题的讨论1 初始点的选取由上述外点法的特点不难看出 外点法的初始点x 0 可以任意选取 即在可行域或非可行域上选取皆可 2 初始惩罚因子r 0 和递增系数c的选取在外点法中 初始惩罚因子r 0 选的是否恰当对算法的成败和计算速度仍有着显著的影响 因此选取时要谨慎 当选r 0 取过小 求解的次数将增多 收敛速度慢 若r 0 选的过大 则在非可行域中 罚函数比原目标函数要大得多 特别在起作用约束边界处产生尖点 函数性态变坏 从而限制了某些约束优化方法的使用 使计算失败 递增系数c的取值 一般影响不太显著 但也不宜取得过大 通常c 5 10 在实际计算中 r 0 c的选取经常是通过若干次试算而选取的 3 约束容差带如前所述 用外点法求解时 由于惩罚函数的无约束最优点列是从可行域外部向约束最优点逼近的 所以最终取得的最优点一定是在边界的非可行域一侧 严格地说 它是一个非可行点 这对某些工程问题是不允许的 为了解决这一问题 在约束边界的可行域一侧加一条容差带 这就相当于将约束条件改为 式中 u是容差量 一般取 u 10 3 10 4 4 终止条件与内点法相同 算法步骤及流程图1 在n维空间任取初始点x 0 2 选取初始惩罚因子r 0 递增系数c 并置K 0 3 求 取得最优点 4 当K 0转步骤 5 否则转步骤 6 5 K K 1 并转步骤 3 6 按终止准则判别 若满足则转步骤 7 否则转步骤 5 7 输出最优解 停止计算 例5 3用外点法求解st 的最优解 解 构成惩罚函数 对于任意给定的惩罚因子r k 0 用解析法求的无约束极小点 即 由上面可知 当逐渐增大r k 值 直至趋近于无穷大时 X r k 逼近原约束问题的最优解 x2 x1 例5 4 用外点法求解st 的最优解解构成惩罚函数 得到约束极值点 即 得 无约束极值点沿直线从约束区域外向最优点收敛 用外惩罚函数法解等式约束优化问题 设有二维等式约束优化问题 函数图形见图 x1 x2 10 0直线是该约束优化问题的可行域 这条直线以外的整个平面为非可行域 目标函数的等值线与直线x1 x2 10 0的切点是该问题的最优点 按外点法构造惩罚函数 该惩罚函数是由原目标函数及惩罚项组成 在可行域上 惩罚项的值为零 惩罚函数的值与原目标函数的值相同 而在非可行域上惩罚项的值恒为正 惩罚函数大于原目标函数 即在可行域外惩罚项起到了惩罚作用 惩罚因子r K 越大 则惩罚的作用越大 随着惩罚因子r K 的增大过程 求出惩罚函数的无约束最优点列 在的过程中 则点列将趋于原约束优化的最优解X 此例可以推广到一般具有等式约束优化的问题 构成外惩罚函数如下 式中 惩罚因子r K 规定为正 且是递增数列 即r 0 r 1 r 2 惩罚项 在可行域上惩罚项为零 在非可行域上惩罚项恒为正 随着r K 的增大 其惩罚项的惩罚作用也越大 惩罚函数是由原目标函数与惩罚项组成 在可行域上 惩罚函数与原目标函数值相等 即 在非可行域上 由于惩罚项的值恒为正 将使 随着r K 的增大 致使 为使罚因子r K 是递增数列 令 c是惩罚因子的递增系数 c 1 罚函数解等式约束优化问题的求解过程及基本参数的选择与前述用外点法解不等式约束优化问题相同 外点法特点 外惩罚函数法既可解不等式约束优化问题 也可解等式约束优化问题 这是其重要优点 另外一个优点是其初始点X 0 可以任选 即在可行域中或非可行域均可 其确定是系列无约束最优点是非可行点 对于工程设计一般是不可取的