求解整体最优化问题的涨落算法

D0I:10.13374/j.issm1001-053x.1989.03.030 北京科技大学学报 第11卷第3期 Vol.1I No.3 1989年5升 Journal of University of Science and Technology Beijing May 1989 求解整体最优化问题的涨落算法 李宗元蒋延辉 (运筹学数研室) 摘要：本文提出了求整体最优解的一种新算法。这个算法对一类花围其广的工 程优化问题（维数≤5~6）较为有液。文中给出了算法及收敛性、最优性条件、计算尖施的 若干建议，以及计算实例。 关键词：整体最优化，涨落算法，多维数值积分 The Up-Down Algorithm for Solving Global Optimization Problems Li Zongyuan Jiang Yenhuei ABSTRACT:A new algorithm which is called the Up-down Algorithm,for solving a global optimization probiem is given.The algorithm is more efficient for a class of engincering optimization problems that have a dimension n5~6. The algorithm and its convergence,optimization condition,some suggestions about the computation,and the examples are given. KEY WORDS:global optimization,Up-Down algorithm,multiple numerical integration 本文讨论非线性规划模型 (P) Maxf(x) D={x|g(x)0xER·} XED 这里，f:R"+R多 g:R-Rm 的整体最优解问题。 这是在最优化领城中的一一个颇具理论意义与应用价值的研究课题，也是一个闲难的课題。 1988一07一22收稿 284

第 卷第 期 北 京 科 年 、 少 技 大 学 ，‘ 若 报 ， 。 尹尸 求解整体最优化问题 的涨落算法 ， 李宗元 蒋延辉 嘴 运 冷学 软研室 尸 摘 要 本文提出 户护求 整体最 优解的 一 种新 算法 。 这 个算法对 一 类 范 困 甚犷 ‘ 的 卜 程 优 化问题 维 效乓 较 为 有 效 。 文 中给 出 了算法 及收 效性 、 最 优性 条件 、 计算实 施 若千 建 议 ， 以 及计算实例 。 关镇 词 整体最 优化 ， 涨落算法 ， 多维 数值 积分 一 ‘ 夕夕“ ” 夕 ” “ 曰碑‘ 一 ， 走 · 一 泛 一 “ ， ， 一 ， · ， 一 ， 本文 讨 论非线性 规划模 型 ‘ 一 、 任 ’ 这 里 ， 左 ” 一， ’ ” 一卜 。 的整体最 优解 问题 。 这是 在最 优化领 域中的一 个颇具理 论意 义与 应 用价 值 的研 究 课题 ， 也是 一 个困难 的课题 。 一 一 收 稿 尸 DOI ：10．13374／j ．issn1001－053x．1989．03．030

近20年来已取得不少成果，但尚不成熟。 70年代初，A.Goldstein【1」提出了一个用于寻找一维多项式的整体最优解的算法，而 后，Brain和Shuberts2将其推广到多维多项式。它们属于这个课题的早期工作。 l975年后，Dixon和Shuberts作了很好的工作(2~4'。推进了这个课题的研究 70年代末到80年代，陆续产生了一些新算法，许多算法也得到进一步的研究，如随机向 量法〔5)，隧道函数法【8了，填充函数法(7)等。我国学者用测度论方法对此课题进行的研究 工作也很有特色。这些算法各有所长，同时也兼有某些不足。例如： Rinnoogkan和Timmer的随机向量法【s)简单实用，但可靠性较差，不能保证产生整体 最优解，只能在概率意义下收敛。 Levy和Gomez的隧道函数法(The Tuneling Function Melhod),其要点是：由一 个可行解x°开始，先求出一个局部最优解x,然后求解非线性方程∫(x)=f(x*)得一个解 x,x°=x,重新开始，直至找出最终解。隧道函数法构思巧妙，理论上能保证得到整体 最优解。但其计算量强烈依赖于初始点的选择，而且在每一阶段均要求解一个非线性方程， 一般说来，这是一个计算量大而又相当困难的问题。再者，该算法要求“整体最优解唯一”， 在实际应用时，显得过于苛刻。 本文提出另一种构思，称为“涨落算法”(The Up-down Algorithm)。此算法不要 求整体最优解唯一，方法简明可靠，能保证收敛于整体最优解，无需求解非线性方程，当模 型的维数小于或等于5~6时较为有效，计算量也不很大。 1基本假设与算法 对模型(P)作如下基本假设： ①可行域D为R"中的一个紧集。这样，总可找到常向量A∈R,B∈R,及超立方体 V={x{x∈R",B≤x≤A} 使得D二V。由下面讨论可知，假设D为R·中的超立方体，并不失一般性。 ②f(x)为D上的单值连续函数。 ③f(x)≥0x∈D。 ④已知f(x)在D上的一个上界L,即已知常数L>0,使得f(x)≤Lx∈D。 涨落算法的基本构思： Stage1。(整体淹没阶段) 取初始点x°∈D,计算f(x),则有I≤f(x)=M≤L 取1=(L+I)/2,并构造新函数： 于(x)={ 当f(x)≤1 (x) 当f(x)>1 即f(x)=(f(x)-1{+f(x)+1)/2 计算积分：△=∫，〔L-了(x)]dD 285

近 年来 已取 得不 少成果 ， 但尚不成熟 。 年代初 ， 〔 ‘ 〕 提 出 了一 个 用于 寻找 一 维多项 式的整体最 优解的算法 ， 而 后 ， 和 将其推 广到 多维 多项 式 。 它 们 属于 这 个课题 的早期工 作 。 年 后 ， 和 作 很好的工作 〔 一 〕 。 推 进 了这 个课题 的研 究 。 年 代 末到 年代 ， 陆续 产生 了一 些新算法 ， 许 多算法 也 得 到进一 步的研 究 ， 如随 机 勺 量法 〔 ’ ， 隧 道 函 数法 〔 “ 〕 ， 填充函数 法 石 ’ 等 。 我 国学 者用 测 度论方法 对此 课题 进行 的研完 工 作也很有特色 。 这 些 算法各有所 长 ， 同 时也 兼有某些 不 足 。 例如 。 和 的随机 向 量法 〔 ” ’ 简单 实 用 ， 但 可 靠性较差 ， 不能 保证产生 整本 最 优解 ， 只能 在概率意义下收 敛 。 、 · 少 ， 和 的隧道 函数法 金 ， 其 要点是 由一 个 可行解‘ “ 开 始 ， 先求 出一个局 部最 优解 ‘ ， 然后 求解非线 性 方程 习 二 得 一 个解 ， 二 。 二 ， 重 新开 始 ， 直 至找 出最 终解 。 隧 道 函数法 构思 巧妙 ， 理 论 上能 保 证得到 整本 最 优解 。 但其计算量 强烈 依赖于初始点的选择 ， 而且 在每 一阶段 均要 求解 一 个非线 性方程 ， 一般说来 ， 这是一个计算量大而 又相 当困难 的 问题 。 再 者 ， 该 算法要求 “ 整体最 优解 唯一 ” ， 在实际 应 用时 ， 显得过于苛刻 。 本文 提 出另一种 构思 ， 称 为 “ 涨 落 算法 ” 一 。 此 算法 不 要 求整体最 优解 唯一 ， 方法 简明可靠 ， 能 保 证收 敛于 整体最 优解 ， 无需求解非线 性方程 ， 当模 型 的维数小于 或等于 一 时较为有效 ， 计算量 也不 很大 。 基本假设与算法 对 模型 作如 下基本假设 ① 可行域 为 ” 中的一个紧集 。 这 样 ， 总 可找到常向量 任 ， 任 ’ ， 及 超 立方体 犷 二 二 任 ’ ， 劣 成 使 得刀 里 犷 。 由下 面 讨论可知 ， 假设 为 “ 中的超 立方体 ， 并不 失一般性 。 ② 二 为 上的单值连续 函数 。 ③ 乡 任 。 ④ 已知 在 上 的一个上 界 ， 即 已知常 数 ， 使 得 毛 二 任 涨落算法 的基本构思 。 整体淹没 阶段 取初 始点 。 任 ， 计算 二 。 ， 则有 簇 二 “ 毛 取 乙 十 ， 并构造新函数 了 二 卜 ‘ 、 二 当 二 镇 当 二 即 二 一 计算积分 △ 丁 。 〔 一 丁 ，〕

(L-I)·D(D兼记为可行域的体积) 比较判断△与(L-1)D的大小 若1，△<(L-1)D 由f(x)的连续性知，必存在x三D, 使得∫(x)>7 这时，令1：=1、L保持不变，重新计算，1：=(L+)/2 并重复此过程。 若2，△=(L-1)D 由f(x)的连续性知，必存在x∈D,使得f(x).1 这时，令L:=1,1保持不变，重新计算I:=(L+)/2 并重复此过程，直至△<(L-I)D 如果△<(L-1)D总不出现，且(L-)<ε，则停x:=x° 检验(L-I),若L-I<e(ε预先给定) 则转入Stage2,若否，继续进行S1age】. Stage2,(局部搜素阶段) 在D中任取￥，￥满足f(￥)>1 这里的【为Stage 1终止时的相应值。 以x为初始点，对∫(x)施行局部搜素 即 MaxF (x)=If(x)-11+/(x)+T XED 2 得最优解x,并计算∫(x) 最优性判别，即判断 ∫7 ()dx=/D? 若是，则停x*:=x 若有，则x°：=x 1:=f(x)返回Stage1, 2算法实施中的若干问題 2,1计算前对模型的预处理 任模型(P)中，假定行域D为有界闭集。为方便数值积分，可将其变换为R中的超立 方体。 286

及 一 · 兼记为可行 域 的 体积 比较判 断 △与 一 的大小 若 刃 ， 一 由 二 的 连续性知 ， 必 仔在 泛 ， 使 得 这 时 ， 令 二 ， 保持不 变 ， 重 新 计算 ， 十 并重 复此 过程 。 若 营 ， 么 一 由 二 的 连 续性 知 ， 必 存 在 任 ， 使 得 二 一 几 这 时 ， 令 ， 保持 不 变 ， 重 新计 算 十 并重 复此过程 ， 直 至△ 一 如 果 △ 一 几总不 出现 ， 几 一 。 ， 则停二 。 检验 一 若 一 。 则转 入 ， 若 否 ， 局 部搜索阶段 预 先给定 继续 进行 在 中 任取 ， 满 足 这 里的 为 终 止时 的相 应值 。 以 为初 始点 ， 对 八 施 行局 部 搜索 〔 劣 得最 优解 ， 井 计算 最优性 判别 ， 即 判断 了。别 二 ‘补 若是 ， 则 停 ’ 若 否 ， 则 “ 。 二 二 “ 返 回 。 算法实施 中的 若千问短 。 计算前 对棋 型 的 预 处 理 在模 型 尸 中 ， 假 定 可行域 为 有界闭 集 。 为 方 便 数值积 分 ， 可将 坟变换 为 “ 中 的 超 立 方体

作变量置换： 在∫eD-5111中 令x,=v-1十w-L+-14-1y:=1,2,…n 2 2 这个变换的Jacabiz行列式 1=应（2"1）≠0 则∫.f)dD=∫J,9yy…y.y…dy. 故在本文的讨论中假定可行域为R”中的超立方体，而且不失其一般性。 2.2初始点的选择 (1)在Stage1中，初始点x°可任取D中一点，在为改进设计而构造的工程优化模型中， 不妨取原设计参数为初始点，在大多数情况下效果较好。 (2)在Stage2中，可利用Stage1中的信息来选定一个进行局部搜索的初始点x。事实 上，在计算第一个积分△1=∫，CL-于(x)门dD时，已存贮了N个抽样点P1,P,…Pw, 及相应的f(P,)值。故可由Stage1结束时的1值与f(P:)=1,2…N比较，任意选出一个 满足f(x)>1的点，记作P,x:=P即可。 2.3初始上界L的选定 若为工程优化设计模型，可借助专业理论与实际经验来选定。若为一般模型，可根据 f(x)的结构作出估计，或选定一个相当大的正数进行试算。计算实践表明，L的恰当选取会 显著减少计算量。 3两个定理 我们给出与本文直接有关的两个定理。 〔定理1]（整体淹没阶段的收敛定理）在基本假设下，涨落算法的整体淹没阶段将产 生两个序列{L.}和{1.}，它们均以f(x)在D上的最大值f(x)为极限，且收敛比为1/2。 证明：由算法可知：序列{I.}单调上升，且有上界L,即1nL,序列{L。}单调下 降，且有下界L即Ln≥L。故lim1,与limL.均存在。 又由算法知： L.-1.=2(L-)n=1,2… 故limL,=lim1.,将其极限值记为m。 287

作 变量置换 在 二 刀 “ ‘ ’ ‘ ’ 之 ‘ “ 一 ’ ‘ ” 一 ” ’ 二 二 … 二 。 … 二 。 中 “ “ 一 一 令， ‘ 刀 ‘ 一 “ ‘ 一 ， 一 ， 。 一二 一 三 了一戈 ’ ’ ， 艺， ’ “ ” 这 个变换 的 行 列式 二 方 了 一 旦上 〔 些二、 、 笋 。 · 、 贝。 二 ‘ ‘ … ’ 。 夕 ， 夕 一 ， 。 ， ， … 少 ， 故 在本文 的讨论 中假定可 行域 为 ’ 中的超立方 体 ， 而且不 失其 一 般性 。 初 始 点 的选择 在 中 ， 初 始点二 “ 可 任取 中一 点 。 在 为改进设 计而 构造 的工程 优化 模型 中 ， 不妨取原设计参数 为初始点 ， 在大多数情 况下效果较好 。 在 中 ， 可 利 用 中的信息 来选 定 一 个进 行局部搜 索的初始点 二 。 事实 上 ， 在计 算第一 个积分△ 丁 。 〔 “ 一 〕 姗 ， 已存贮 个 抽 ” ， 尸 ， ” · 尸， ， 及 相应 的 尸 ‘ 值 。 故 可 由 结 束时 的 值 与 尸 ‘ ， ” 比较 ， 任意选 出一个 满足 幼 的 点 ， 记作尸 ， 即可 。 。 初 始上 界 的选 定 若为工 程优化 设 计模型 ， 可借 助专业理论 与实际 经验 来选 定 。 若 为一 般 模 型 ， 可根据 的结 构作 出估计 ， 或选定 一 个相 当大 的 正数 进 行试 算 。 计算实践表 明 ， 的恰 当选取 会 显著减少 计算 量 。 两 个 定 理 我们给 出与本 文直接有关 的两个定理 。 〔定理 〕 整体淹没 阶段 的收 敛 定理 在基本假设下 ， 涨落算法 的整体淹没 阶段 将产 生两 个序 列 王 。 和 二 ， 它 们均以 劝 在 上的 最大值 为极限 ， 且 收敛 比为 证明 由算法可知 序 列 二 单调 上 升 ， 且有 上界 ， 即 。 序列 王 单调下 降 ， 且有下 界 即 李 。 故 与 均存 在 。 又 由算法知 。 一 川， 二 一卫一 一 。 二 ” “ 一 止 故 ， 二 ， 将 其极限值记 为 尽

今证：m=f(x) 事实上，由{L,}与{1.}的产生可知： 对任意的x∈D,有∫(x)≤L.,从而 f(x)≤L.,类此，f(x)≥1. 所以f(x)limL.=m,f(x)>liml.=m 故m=f(x) 显见，{L.-1.}→0的收敛比为1/2 证毕 〔定理2〕（涨落算法整体最优性的判别定理）在基本假设下，若x·是一个局部极大值 点，则x是整体最大值点的充要条件是： ∫f(x)dD=fx)D 证明：先证必要性：已知x为∫(x)在D上的整体最大值点，故由f(x)的构造法可知 f(x)三f(x)x∈D 所以，∫，f(xdD=fx)D 再证充分性：用反证法。若x·不是f(x)在D上的最大值点（则必存在x∈D,使得f(x◆） >f(x)。从而，由f(x)在D上的连续性可知：必存在x·的-邻域6(x·,:),使得在 (x",e)nD上，均有 f(x)>f (x) 改写∫，了(x)dD: ∫，f(x)dD=∫7()dD,+∫nf(x)dD 这里，D,=8(x,e)nD,D,=D\8(x",e) 而∫了(x)dD>f(x)D1:∫。2f(x)dD,>fx)D, 放有∫。f(x)dD>f(x)D+D,)=f(x)D 与已知条件矛盾 证毕 4有关多维数值积分的讨论 在算法涉及多维数值积分计算，因此，有必要讨论一下有关的计算方法、精度及计算量。 4.1精度及计算量估计 不失一般性，设可行域D为n维单位超立方体：0一x,”1i=1,2…n。将每维的 〔0,1〕m等分，则子超立方体的个数N为：N=m· 用适当的方法（例如下面推荐的等分布列方法）选取N个积分点P,P2,…Pw。计算： 288

今 证 。 二 二 事 实上 ， 由 。 与 的产生可 知 对 任意的 〔 ， 有了 习 ， 从而 叹 ， 类此 ， 二 》 所以 二 ， 二 故 二 显 见 ， 。 一 ， 的收敛 比为 〔定理 〕 涨落算法整体最优性 的判别定理 点 ， 则二 是整体 最大值 点的充 要条件是 证毕 在基本假设下 ， 若 是 一 个 局 部极大值 了 二 ‘， ” · 证明 先 证 必 要性 已知 ， 为 幻 在 上 的整休 最大值 点 ， 故 由 的构造 法可 知 二 劣 劣 任 所以 ， 丁 。 了‘ ， 二 “ ， ” · 再证充分性 用 反 证法 。 若 不 是了 幻 在 上 的最大值 点 则必 存 在二 ， 任 ， 使 得 二 二 二 。 从而 ， 由 幻 在 上的连续性 可知 必 存在 砂 的 一 邻域 叔 ， ， 使 得在 占 二 ， 月 上 ， 均有 八 改 写 丁 。 了 ， 丁 。 了 丁 。 了‘ ， 了 。 了‘ ， 这 里 ， ， 二 二 ， 。 ， 晒 二 ， 而 丁 。 了‘ ， “ 二 ” · ， 丁 。 了‘ ， 卜 “ ” · ” 故有 丁 。 ‘二 ， ‘ ” 〔 ， ‘ “ ” · 与 已知 条件 矛盾 证毕 有关多维数值积分的 讨论 在算法涉及 多维数值 积 分计算 ， 因此 ， 有必 要讨 论一下 有关 的计算方法 、 精度及计算量 。 精 度及 计算， 估 计 不 失一般性 ， 设可 行域 为 维 单位 超 立 方体 〔 ， 〕 。 等分 ， 则 子超 立方 体 的个数 为 。 ’ 用 适 当的方法 例如 下面推 荐的 等分布列方法 义 ， 二 。 将每维的 选取 个积分点尸 ， ， 尸 ， …尸二 。 计算