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