约束最优化程序设计

D01I:10.13374/i.issn1001053x.1981.04.006 北京钢铁学院学报 1981年第4期 约束最优化程序设计 计算机应用室吴缕庚 摘 要 本文介绍了约束最优化问题求解的惩罚函数法(SUMT调用P。WeI1法)， 附有程序框图及用ALGOL语言编制的过程。文中简要介绍了该方法的基本思想， 对“惩罚”的实质和近似求解进行了分析，提出了Po well法的两个加速收敛的条 件以及每一计算步骤的整止准则。文中还附有使用本过程的简要说明与计算实例。 最优化方法近年得到了迅速的发展，它研究从尽可能多的可行设计方案中，寻求最佳设 计方案的方法。在现代控制理论、系统工程和计算机辅助设计等方面已经成为不可缺少的组 成部分。这门学科是在实物模型、数学规划论和电算技术等理论基础上，进行综合分析的计 算系统。目前，在国内外许多技术领域得到了广泛的应用，并取得了显著的效果。最优设计 方法，首先将所研究的实物模型转换为一定格式的数学模型，再送入最优化方法的电算程 序，在电子计算机上计算求解，得出最佳设计方案。 本文用ALGOL语言编制的惩罚函数法求解约束最优化问题的过程，在一九七九年八月 试算通过后，已陆续在冶金机械、矿山机械、机械设计与机械制造等方面计算出了正确的结 果，并写出了专题报告。经过二年来的上机计算实践证明：程序简单、易于掌握、运算迅 速、结果正确，适用于中小题目的计算和求解非线性方程组的问题。 一、基本思想 1.惩罚函数法(SUMT调用P。weI1让)就是将约束最优化问题转化为一系列无约 束最优化问题来求解，即序列无约束极小化方法一SUMT(Seguential Unco nstrained Minimization Technigue)法。这个方法的实质是将约束条件，即对等约束函数Hv(x) 和不等约束函数Gu()乘一个或几个可变化的数列一加权参数r(惩罚因子)，再与原目 标函数F()按照某种假设条件，构造成一系列新的无约束目标函数Φ(X,),称它为惩 罚函数(Penalty Function)。用比较成熟的无约束最优化求解的方法求得惩罚函数 Φ(x,)的最优化解，以此作为原目标函数F()的约束近似解。 构造惩罚函数Φ（又，）的形式分为内点法、外点法和混合点法。内点法是将惩罚函数 ”本文在编写过程中得到了陈立周同志和冶金机械教研室同志的指导和帮助。 61

北 京 钢 铁 学 院 学 报 年第 期 约 束 最 优 化 程 序 设 计 ‘ 计 算机应用 室 吴 继 庚 摘 要 本 文介 绍 了约束 最 优化 问题 求解 的 惩罚 函数法 调 用 法 ， 附有程序框 图及 用 语 言编制的过程 。 文 中简要介 绍 了该方 法 的塞 本思想 ， 对 “ 惩 罚” 的实质 和近 似 求解进行 了分 析 ， 提 出了 法 的两 个加 速 收敛 的条 件 以及 每一 计算步骤 的终 止 准则 。 文 中还 附 有使 用本过 程 的 简要说 明与计 算实 例 。 最 优化方法近 年得 到了迅速 的发展 ， 它研究 从尽可 能 多的 可 行设计方案 中 ， 寻求最佳设 计 方案 的方 法 。 在 现代控 制 理论 、 系统 工 程 和 计 算机 辅助设 计 等方面 已经 成为不 可 缺 少 的 组 成 部分 。 这 门学科 是在 实物模 型 、 数学 规 划论和 电算技 术等理论基 础 ， 进 行 综 合 分析 的 计 算 系统 。 目前 ， 在 国 内外许 多技 术领域 得 到 了广 泛 的 应 用 ， 并取 得 了显著 的 效 果 。 最 优设计 方 法 ， 首 先将所研究 的 实物模 型 转 换 为一 定 格 式 的 数学 模 型 ， 再 送 入 最优化方 法 的 电算程 序 ， 在 电子计 算机 上计 算求解 ， 得 出最佳 设计 方案 。 本文 用 语 言编 制 的惩 罚 函 数 法求解约束 最优化 问题 的过 程 ， 在 一 九七九年八月 试算通过 后 ， 已陆 续在 冶金机械 、 矿 山机械 、 机械设计 与机械 制造 等方面计算 出了正 确的 结 果 ， 并写 出了专题 报告 。 经过 二 年来 的 上机计 算实践 证 明 程 序简单 、 易 于 掌握 、 运算迅 速 、 结果正 确 ， 适 用 于 中小 题 目的计 算和 求解非线性方程组 的 问 题 。 一 、 基 本 思 想 惩罚 函 数 法 调 用 法 就 是 将 约束 最 优化 问题 转化 为一 系列 无 约 束最优化 ’ 题 来求解 ， 即序 列无 约束极小 化方 法一 。 。 法 。 这 个方 法 的 实质 是 将约束 条件 ， 即对 等约 束函 数 ， 了 和 不等约束 函 数 了 乘一 个 或几 个 可 变化 的 数列 — 加 权 参数 惩罚 因子 ， 再 与原 目 标函数 室 按 照 某 种假设 条件 ， 构造 成一 系列 新 的 无 约束 目标 函 数 巾 《了 ， ， 称 它 为惩 罚函数 。 用 比较 成熟的 无 约束最 优化求 解 的方 法求得 惩罚 函数 巾 了 ， 的 最 优化解 ， 以 此作 为原 目标 函 数 了 的 约束 近似解 。 构造 惩罚 函数 中 又 ， 的 形 式 分 为 内点 法 、 外点 法和 混合点 法 。 内点 法是 将惩罚 函数 本 文在编写过 程 中得 到 了陈立 周 同志和 冶金机械 教研 室 同 志的指导 和 帮助 。 DOI ：10．13374／j ．issn1001—053x．1981．04．006

定义在可行区内，从一个初始可行点逐步近近最优点。它的形式为： Φ（区，r)=F(☒）+r21/Gu(☒) 或 中区，r)=F()+r21n(Gu(x) u= 其中： Gu()>0,(u=1,2,…,m), 式中可变化的惩罚因子r是一个递减数列：r(o!>r()>r(2)>…>r)。每确定-一 个r值就有一个Φ（又，）无约束函数求解的过程。由于r是一组变化的数列，因此就有一系 列的无约束函数Φ(，)的求解过程。所以惩罚函数法就是将约束最优化问题转化为一系 列的无约束最优化问题求解的方法。由内点法的定义可以看出，初始点(、迭代过程中 的各点X()以及最终优化点()等都在可行区内，因此，它的解是安全、保守、可靠的。 但对于设计变量较多，约束条件又复杂的题目，人为寻求一个可行的初始点x()是较困难 的。相反，外点法是将惩罚函数定义在非可行区，即从一个非可行的初始点x《),逐步迭 代逼近最优点，而最优点又（并非在可行区内，因此它的解是非可靠的、不安全的。但它 对初始点？()要求不严格，而且还能处理等约束问题。它的表达形式是： Φ（区，r)=F()+r2(Gu(x)2 U -1 其中： Gu()≥0(u=1,2,…,m) 式中惩罚因子r是一个递增数列r(o)<r)<r(2)<…<r()。 对于上述内点法与外点法所存在的问题，目前在实际应用中都已得到解决。如在内点法 中加入随机选择初始可行点的功能，在外点法中将可行区的范围缩小等措施，都是行之有效 的方法。 混合点法即是将外点法能处理等约束条件的特点，加到安全可靠的内点法中来，形成了 现在常用的罚函数法。 已知设计变量驱=〔x1,x2,…,Xn)T 求解目标函数F() 满足不等约束函数Gu(区)≥0(u=1,2,…,m)和等约束函数Hv(又)=0(y=1,2, …,p)（p<n)的约束条件下极小值的问题。 按照某些假设条件，混合点法罚函数的构造形式是： oX=F0+r8G+:总H,X 1 由上式可知惩罚函数Φ（又，）具有如下四条极限性质： limr (K)=0 K+四 lr三Gu()=0（u=1,2,…,m） 西〔H,(r=01,2,p） limΦ(x,r(x)=F(x) ◆西 上述性质揭示了罚函数的实质，即当惩罚因子(x)由一个初值逐渐递减变化趋近于零 62

定义在 可行 区 内 ， 从一 个初 始可行 点逐 步 遇 近 最 优点 。 它的形 式 为 中 了 ， 了 乙 二 巾 又 ， 又 乙 二 土 了 叉 其 中 了 二 ， ， · … ， 式 中可 变 化的 惩罚 因子 是一个递减 数列 。 ‘ “ … … 。 每确定一 个 值就 有一 个 中 了 ， 无 约束 函数求解的过 程 。 由于 是一 组 变化的数列 ， 因此就有一 系 列 的无 约束 函数 中 了 ， 的 求解过 程 。 所 以 惩 罚 函 数法就 是 将约 束最优化 问题转化 为一 系 列 的无 约束 最优化 问题 求解 的方 法 。 由 内点 法 的 定 义可 以 看 出 ， 初 始点 了 “ 、 迭 代过 程 中 的 各点 叉 川 以 及最终 优化 点 了 阁 等都在 可 行 区 内 ， 因 此 ， 它 的解是 安全 、 保 守 、 可 靠 的 。 但 对于设计 变量 较 多 ， 约束 条件 又 复杂的 题 目 ， 人 为寻 求一 个可 行 的 初 始点 了 。 是 较 困 难 的 。 相反 ， 外点 法 是 将惩罚 函数定 义在 非可行 区 ， 即 从一个 非可 行 的初 始点 了 “ ， 逐 步 迭 代逼 近 最 优点 ， 而 最 优点 了 侧 并 非在 可行 区 内 ， 因此 它的解是 非可靠 的 、 不安全 的 。 但 它 对 初始点了 《 “ 》 要求不严 格 ， 而且还 能 处 理等 约束问题 。 它 的 表达 形 式是 中 了 ， 二 又 又 “ 丁 其 中 了 全 。 ， ， … … ， 式 中惩罚 因子 是一 个递 增 数列 《 “ 》 ‘ 《 空》 … … 。 对于 上述 内点 法 与外点 法所 存在 的 问题 ， 目前在 实际应用 中都 巳得 到解决 。 如在 内点 法 中加 入 随机选择 初始可行点 的功 能 ， 在 外点 法 中将可行 区的 范 围缩小 等措施 ， 都是 行之有效 的方 法 。 ’ 混合 点 法 即是 将外点 法能处 理 等约束 条件 的特点 ， 加 到安全可靠的 内点 法中来 ， 形成 了 现在 常用 的 罚 函数法 。 巳 知设计 变量了 二 〔 ，， ， … … ， · 〕 丁 求解 目标 函数 了 满足 不 等约束 函数 了 之 。 三 ， ， … … ， … … ， 的 约束 条件下 极 小值的 问题 。 和 等约束 函数 ， 了 二 ， 按照 某些假设 条件 ， 混 合点 法罚 函数 的 构造 形式 是 、 。 、 皿 中 ， 一 以 人 十 。分 石 又下 一 十 沙 〔 ， 了 〕 由上式 可 知 惩罚 函数 中 了 ， 具有如 下 四 条极 限性 质 卜 茱， 。 里 份 ， 又 戈“ 上， 艺， ” ” “ ’ 夕 申 万目 上 ， ， 二 一 、 、 蔺六 ， · 人 ” 一 二 。 ‘ 二 ‘ ， “ ， ” ‘ ” ” ” ， 中 了 ， 又 上述性 质 揭示 了罚 函数 的 实质 ， 即 当惩罚 因子 由一 个 初值逐 渐 递 减 变化趋近于零

时，惩罚项r)21/Gu(区)和(1/红(K1)上〔H,():也趋近于零，最后使新目标函数 中（区，r(K))的值趋近于原目标函数F()的约束解。因此，罚函数的解Σ(）就是原目标 函数F(区)的约束近似解。 对于罚函数中(X,r())在无约束最优化求解过程中，约束条件是如何起到限制设计 变量不会超界呢？试看，约束函数Gu(X)≥0和H,(X)=0经过数学变换，在罚函数 (又，r(K)中构成了两个惩罚项r(K)21/Gu(区)与(1√r)公(H,(),当r(为 某一个定值时，如果某个设计变量区()在变化过程中趋近于边界约束条件或性能约束条件， 即将要破坏某些不等约束条件时，使得G,(区)≈0，则1/G,(X)→0，相应r(K)21/G.(X) u=1 项变得很大，促使函数中（又，r(x)值猛然增加，而且G,()值越小，则中（又，r(x))值 就越大。这个变化相当于在约束边界上筑起了一道“高墙”，而且这道“高墙”是越来越 高。因此，迫使设计变量在一维搜索变化时，不会再沿着使罚函数Φ（又，r(x))值增加的 方向发展，也就不会使设计变量再超越约束条件的限制。至此，惩罚项r()∑1/G。()将 1 起到了不等约束的作用。同理，另一惩罚项(1√灯)公(Hv()2的函数值，是随着设 计变量又()越远离最优化点时而增大，而且距离越远此项值越大，也会促使罚函数Φ(， r(K))值猛然增加，同样也筑起了一道“高墙”，必然使设计变量()在一维搜索变化时， 向着使罚函数中（区，(）)值减小的方向变化，至此，也起到了等约束的作用。从而可以看 到罚函数法近似求解的过程以及约束条件是如何起作用的。这两个特点就是罚函数法的“惩 罚实质”。 目前，将约束最优化问题转化为一系列的无约束最优化问题求解的方法很多，惩罚函数 Φ（区，「）的构型方案也很多。这里采用的公式是： 0(x,)=F+r2G+cH,) 此公式简单、易懂，在实际应用中是成功的。 关于如何选取惩罚因子r的初始值r〔)，有关资料介绍的理论和公式是较多的。但这里 人为的给定一个初始值r()≥1的数，在实际应用中再进行调整变化。经验证明：r()取小 值时，使得罚函数构型次数减少，节省计算时间，但容易使其计算结果精度偏低或造成计算 失败。相反，()取值过大，虽然罚函数构型次数增加，多耗机时，但它对罚函数的每次构 型是有利的。对于惩罚因子r(K)值数列递减变化的规律，可用一个固定的小于1的系数C逐 次去乘r(K),即得到迭代公式rK+)=r(K)*C。经验证明：C的取值范围可在0.1~0.5之 间，或者取值更小C=0.01~0.1。 2.在无约束最优化方法中，虽然种类繁多，但实质上多数是利用一维搜索（将多元函 数看作是一元函数，求解最佳值)迭代求解的方法，其迭代公式是： 又(K+1)=又(K)+a(K)8(K) 其中：《K+)一迭代后所求新点 (K)一一迭代前原始初点 a)一选代中优化步长 3(x)一迭代中优化方向 63

时 ， 惩罚 项 乙 了 和 侧 “ 丫 中 又 ， ’ 的值 趋近于原 目标 函数 了 函数 又 的 约束近 似解 。 〔 ， 又 的 约束解 。 〕 “ 也趋 近 于零 ， 最后 使新 目标 函数 因此 ， 罚 函数 的解 了 剐 就 是原 目标 名二 对于罚 函数 中 了 ， 在 无 约束最优化 求解过 程 中 ， 约束 条件是如何起 到限 制设计 变量 不会超界 呢 试 看 ， 约束 函数 了 七 。 和 ， 又 二 。 经 过 数学 变换 ， 尔 又 ， ‘ ， 中构 成 了 两个 惩罚项 ‘ ， 会 。 了 与 训 ‘ ， 亡〔 了 〕 ， ， 盆 在 罚 函数 当 为 某一个定 值 时 ， 如 果 某个 设计 变量又 ‘ 在 变化过 程 中趋 近 于边 界 约束 条件或性 能 约束 条件 ， 即将要 破坏 某些 不 等约束 条件 时 ， 使得 叉 “ ， 项变得很大 ， 促 使 函数 中 了 ， 《 值 猛然增加 ， 就 越 大 。 这个变化相 当于在 约束边 界 上筑 起 了一道 则一 ， 了 ， 二 ， 相应 。 又 而且 ， 了 值越 小 ， 则 中 又 ， 值 “ 高墙 ” ， 而且 这道 “ 高 。 因 此 ， 迫使设计 变 量在 一维 搜索变化时 ， 不 会再沿 着使罚 函数 中 又 ， 方 向发展 ， 也 就 不会使设计 变量再超越 约束 条件 的 限 制 。 至 此 ， 惩罚项 《 “ 》 高墙 ” 是 越 来越 ‘ 值 增加 的 兄 。 又 将 起 到了不 等约束 的 作用 。 同 理 ， 另一 惩罚 项 、 二 ，亡〔 了 〕 的 函骊植 ， 是 随 着设 计变 量 了 ‘ 》 越远 离最 优化 点 时而增大 ， 而且 距 离越 远此 项值 越 大 ， 也 会促 使罚 函数 中 又 ， “ 值 猛然增加 ， 同样 也筑 起 了一道 “ 高墙” ， 必 然 使设计 变 量了 ‘ 在 一 维 搜 索变化 时 ， 向 着使 罚 函数 中 了 ， 值减 小 的 方 向变化 ， 至 此 ， 也 起 到 了等 约束 的 作用 。 从 而可 以 看 到罚 函数 法近 似 求解的 过 程 以 及约束 条件 是如 何起 作用 的 。 这 两 个特点就 是 罚 函数 法 的 “ 惩 罚 实质 ” 。 目前 ， 将 约束 最 优化 问题 转化为一 系列 的无 约束最优 化 问题 求解的方 法很 多 ， 惩罚 函数 中 又 ， 的 构型 方 案 也 很 多 。 这 里 采 用 的公 式是 中 又 ， 叉 乙 面郊 上 ， ， ， 一 、 一万 一 二 、 ，乙· 吸入 此公式简单 、 易懂 ， 在 实际应 用 中是 成功的 。 、 关于和何选取 惩罚 因子 的初 始值 ‘ 。 ， 有关 资料介绍的 理论和 公式 是 较 多的 。 但这 里 人 为的 给定一个初始值 。 全 的 数 ， 在 实际应 用 中再进 行 调 整变化 。 经 验证 明 “ 取 小 值 时 ， 使得罚 函数 构型 次数减 少 ， 节 省计算时 间 ， 但 容 易使其计算结 果精度 偏低 或造 成计算 失 败 。 相反 ， 。 取 值过 大 ， 虽 然罚 函数构型 次数增 加 ， 多耗 机 时 ， 但 它对 罚 函 数 的 每 次构 型 是有利 的 。 对于 惩罚 因子 值 数列 递 减变化 的规 律 ， 可用一 个固定 的小于 的 系数 逐 次去乘 “ ， 即得 到迭代公 式 ’ 。 经 验证 明 的取 值 范 围可在 之 间 ， 或者取 值 更小 。 在 无 约束 最优 化方 法 中 ， 虽然种 类繁 多 ， 但 实质 上 多数是 利用一 维 搜索 将多元 函 数看作是一 元 函数 ， 求解最佳值 迭 代求解 的 方 法 ， 其 迭 代公 式 是 叉 千 ’ 又 习 其 中 了《 盆 ’ — 迭代后所 求新点 了 “ — 迭代前原始 初点 砂幻 — 迭代 中优化 步 长 百旧 — 迭代 中优化方 向

在每一次送代过程中，都是以原始初点()出发，沿着本次迭代优化方向和优化步长， 得到一个新点X(K+),这样反复迭代求新点，最后即可得到满足一定精度要求的无约束最 优化解。上述选代过程的关键是：每迭代一次都要寻求本次迭代过程中的最优化方向3(“)和 最优化步长α()。关于求解3(K)与a()的方法很多，各有其特点。本文选择最优化方向的 方法是改进的共轭方向法-一P。me11法，选择最优化步长的方法是二次插值法。 ,PoWe11法是在共轭方向法的基础上，为了加快迭代收敛速度，提出了如下的分析： (1)经过一轮一维搜索迭代求解后，所求新的方向(+)在共轭方向法中就直接迹用 了，箭Pgwl1法要经过分析判断，然后再决定是否取舍方向(a+),其判断条件是： f,<f:与 (f-2f2+f,)(f1-f2-△m)<0.5△m(f1-f,)2· 式中：「1，「，f,分别为一轮搜素过程中初始点的函数值，终止点的函数值和反射点的函数 值。△m为相邻两维函数值之差的最大值。 上述两式同时成立时，则选取方向+)为共轭方向，否则仍用原来的方向矩阵进行 下一轮的一维搜索。 (2)在选用共轭方向8(+)后，共轭方向法则用(a+)取代最前面的方向8()。而 Poe1i法则采用淘汰相邻两维函数值之差最大值△m所对应的那个方向(m),即是用(h+), 排列在原方向矩阵的最后一列，再删掉原方向矩阵中8()列向量，形成新的方向矩阵：，··： 8),8(2),…,8(-1),8(+),…,8(n),8(n+1) 其中：△m=m8xlf,-1-f,.i=1,2,…,n 由此可见，PoWI1法中采用上述两个分析后，即可比共轭方向法具有更快的收敛速 度。 二次插值方法是求解最优化步长的常用方法，其所用的公式为： a=0.5(a1+a3-c1/c2) c1=(fs-f,)/(a3-.a1) cz=((f2-f,)/(a2-a)-c)/(a2-as) 式中，a1,cz,as为一维搜索中二次插值各点值，f:,fz,f,为各插值点所对应的插值函 数值，α“为二次插值的极值点，即为所求的最优化步长。 3。求解终止准则： ,关于二次插值求解最优化步长α酱时的终止准则是： ,<e If:-f<e a2-a<e Q2-a3<e1 其中任意一个条件成立时，即可终止求解。 关于Powel1法求解惩罚函数Φ（哀，r(K)的无约束最优化问题极小化解的终止准则 是： 2(x{0)-x)2<e1 关于惩罚函数中（又，r《x))的求解逐步趋近于原目标函数F()的解，：是随着惩罚因 子r(x)值数列的递减变化而不断逼近。其求解终止准则是： 64

、 布每一 次迭代过 程 中 ， 都是 以原始初点了 ‘ ’ 出发 ， 沿 着本次迭代优化方向和 优化步长 ， 得到‘ 个新点了‘ “ ，， ‘ 这样反 复迭代 求新点 ， 最后 即可得 到满足一定精度 要求的无 约束最 优化解 。 上述迭代过程的关键是 每迭代一 次都要寻求本次迭代过程 中的 最优化方向 习《 “ 》 和 最优化步 长 。 关于求解 习《 “ 与 《 的方 法很 多 ， 各有其特点 。 本文选择 最优化方向的 方法是 改进 的共垅方 向法— 法 ， 选择 最优化步长的方法是二次插值法 。 。 ， 法是在共婉方 向法的基 础 上 ， 为了加 快迭 代收敛 速度 ， 提出了如下的分析 经过一轮尸维搜索迭代 求解后 ， 所求新的方向 百 “ 十 ’ 在共辘方 向法中 就 直接选用 了 ， 翁户。 场 法要经过分析判 断 ， 然后再 决定是 否取舍方向习‘ ， ，，， 其 判断条件是 。 与 「 一 一 一 △二 八二 一 ， ’ ‘ 式中 ， ’ ， 王 分 别为一 轮搜家过 程 中初始点的 函数值 ， 终止点的 函数值和反射点的函数 澎 △ 为相邻两维 函数值 之差 的 最大值 。 ‘ 上述两式 同时 成立 时 ， 则选取 方 向 厚 “ ‘ 》 为共辘方 向 ， 否 则仍用原来 的方向矩阵进行 下一轮 的一 维 搜声 。 在 选 用共辘方 向 刘 ” “ 后 ， 共扼方向 法则用 习 ” “ 取 代 最前 面 的方 向 习《 ‘ 。 而 。 中 “ 法则采用淘汰相邻 两维 函数值 之差 最大值△二 所对应的那 个方 向到 ， ， 即是 用习《卜 ‘ 排 列在 原方向矩 阵的 最后 一 列 ， 再删掉原方 向矩 阵中否 列 向量 ， 形 成新 的方向 矩 阵 · 习川 ， 习 艺 ， · ‘ · … ， 习 一 ’ ， 习 山 ‘ 》 ， … … ， 习 ” ， 习 “ “ 其 中 △二 二 ‘ 一 一 称 ， ， … … ， “ 由此可见 ， 。 法 中采 用 上述 两个 分析后 ， 即可 比共扼方向法 具有更快的收敛速 度 。 ’ 土次插值方法是 求解最优化步长的 常用方法 ， 其所用 的公式为 名 二 。 一 ， 一 一 通 一 一 一 一 式中 ， 。 ， 。 为一维搜索 中二次插值 各点值 ， ， 为各插值点所对应 的插值函 数值 ， 为二次指值的极值点 ， 即 为所 求的 最优化步长 。 ’ 求解终止准 则 ‘ 关于二次插值求解最优化步长 时的终止准则是 ， 一 ‘ ， ， 一 了一二 戈 一 一 吸 一 ‘ 】 已 其 中任 意一个条件成立 时 ， 即可终止 求解 。 一 。 关 于 法求解 惩罚函数 巾 了 ， 《 的无 约束 最优化 问题极小化解 的 终止准则 是 艺 。 ’ 一 “ ’ 。 关于 惩罚 函数 巾 又 ， 《 ‘ 的 求解逐 步趋近于原 目标 函数 叉 的解 ， 一 是 随着惩罚 因 子 《 “ 值数 列 的递减 变化而 不 断逼 近 。 其求解终止 准则是

中w,t)Φ”r)|<e: Φ(X(k+,rK+叮) 上述各式中的e1与e2皆为给定精度值，本文取值为：e1=107,e2=103 二、程序设计 1.程序框图： 送原始数駟 开始 结東 输出最终结果 是 送初始值Ra)下o) RR.C 下OM-FO<FPS () 随机选点了 是 CYCLE=0 1OF1Φ(X,r) X点行吗 SDX10 是 SDX>EPSI ISN 1 I+1 Xs-2Xm-下。 :次橘值求： 不-X。 X1T)+T:,K) DFMDF F3(又，r) DFII F2中(X,r) 是1 D1=F1-F2 DF>DFM 兄否选取北轭方向 5,K1及，K1(i<m) 8t(iSm) 次断作求T: F32 行 ix+t)=XA1+T1。 FO+F2 FO=F3 (下，r) 了=N N.Y.Y SUT--'u11方边r航网 65

中 了 ‘ ‘ ， ‘ ， 一 中 区 竺生竺二业 — 一几琢丈 一 ， ， 上述 各式 中的 。 与。 皆为给 定精度 值 ， 人 本文取 值 为 。 ， 一 。 一 程 序设 计 程 序棍 图 送原 始数拟 结 束 输 出最 终结 果 二矛「一 ‘ 一﹃编 送 初 始依 “ 又《 。 丈乍 「 一 ’ 随 机选 点 了 乏 二 、 ，丫弓 是 犷 李 令 巾 又 又点下，丁行 ，‘玉 佘 。 是 ， 是 字 二次插 谊求 ‘ ’ 巾 了 。 一 了 。 凡 “ ‘ ’ 令 了 一 又 。 ‘ “ · ‘ 、 、 又‘ “ ’ ‘ ’ 云 ‘士 ’ 之 宇 犷 乍 尔巾 文 守 中 了 是 、 ” 、一 ‘ 。 、 犷二 ￡ 一 了 卜 是 否 选 取 共辘 方向 否 ， ，中 尺 ‘ 否 “ 、 华 凡 里 苏 ， 是 一 二次 播 仇求 ， 讼 否 是 “ ， ‘ ， ’ ’ 习 。 ， 、 叹瓦 、 〔 。 了 二 犷 字 ‘工 又 又 牛 入 万 ， 李 了 ’ 一 一 ， 。 、 扒 仃 程 丫报 日 场卜