离散优化与连续优化的复杂性概念

收稿 日期： ２ ０ １ ７ － ０ ４ — ０ ４ 基金 项 目： 国家 自然科学基金 （ Ｎｏ ． １ １ ５ ７ １ ０ ２ ９ ） １ ．清 华大学数学科 学系 ， 北京 １ ０ ０ ０ ８ ４ ； Ｄ ｅ ｐ ａ ｒ ｔ ｍ ｅ ｎ ｔ ｏ ｆ Ｍａ ｔ ｈ ｅ ｍ ａ ｔ ｉ ｃ ａ ｌ Ｓ ｃ ｉ ｅ ｎ ｃ ｅ ｓ ， Ｔ ｓ ｉ ｎ ｇ ｈ ｕ ａ Ｕ ｎ ｉ ｖ ｅ ｒ ｓ ｉ ｔ ｙ
文『 ３ １ ． 人们 已经 熟悉 了 ＮＰ完全和 ＮＰ难这 些概 念， 并对 具有 ＮＰ完全和 ＮＰ难 问题 的难解 性 予 以广泛 接受 ．
内点 算法 首先 成 功地 解 决 了线 性规 划 的复 杂 性分 类 ［ ２ 】 ’ 将其 归 为 多项 式 时 间可解 问 题， 这 是优 化领 域 的划 时代 的成 果 ． 内点算法 的复杂 性结 论采 用 图灵机 的理论 体 系 ． 随 内 点算法 在更 为广泛 问题 中使 用 ， 它对 解 决连续 优化 问题 的优 势就 越 发显得 突 出 但 针 对离
０ 引 言
计 算 复 杂性 理 论成 熟 于 ２ ０ 世纪 ７ ０ 年 代 初 ］ ， 是 理论 计 算机 划 时代 的一 个成 果 ． 计 算 复 杂性 概 念 和 理论 非 常基 础 ，一直 吸 引研 究者 的关注 ． 美 国 Ｃ ｌ ａ ｙ 数 学所 ２ ０ ０ ０ 年 公 布 了２ １ 世 纪 的百万 美金 待解 ７ 个 问题 的第 一个就 是计 算复 杂性 理论 问题 ： Ｐ＝ ＮＰ ？ 优 化 问题 的研 究和 算法 设 计总 离 不开 复杂 性 的概念 ， 因此 离散 优 化和 连续 优化 领域 都 会用 到 多项 式 时 间 问题 ｆ 可解） 或 ＮＰ难 等概 念 ．近期 很 多连 续优 化领 域 的研 究 学者 愿 意用 Ｎ Ｐ 难 来说 明其 研 究 问题 的难 度 ， 但 在连 续优 化模 型 的数据 中或 可行 解 区域 中可能会 出现无 理数 或求 解算 法 中会 出现开 方或 指数 运算等 ， 如 何处 理这 些 的不 同？
Ａｂ ｓ ｔ ｒ ａ ｃ ｔ Ｃｏ ｍｐ ｌ ｅ ｘ ｉ ｔ ｙ ｃ ｏ ｎ ｃ ｅ ｐ ｔ ｓ ｏ ｒ ｉ ｅ ｎ ｔ ｅ ｄ ｆ ｒ ｏ ｍ ｔ ｈ ｅ ｔ ｈ ｅ ｏ ｒ ｅ ｔ ｉ ｃ ａ ｌ Ｔｕ ｒ ｉ ｎ ｇ ｍａ ｃ ｈ ｉ ｎ ｅ ａ ｒ ｅ ｗｉ ｄ ｅ ｌ ｙ ａ ｃ ｃ ｅ ｐ ｔ ｅ ｄ ｉ ｎ ｓ ｔ ｕ ｄ ｙ ｏ ｆ ｃ ｏ ｍｂ ｉ ｎ ａ ｔ ｏ ｒ ｉ ａ ｌ ｏ ｐ ｔ ｉ ｍｉ ｚ ａ ｔ ｉ ｏ ｎ ｐｒ ｏ ｂ ｌ ｅ ｍｓ ． Ｔｈ ｅ ｐｏ ｌ ｙ ｎ ｏ ｍｉ ａ ｌ ｌ ｙ ｃ ｏ ｍｐ ｕ ｔ ａ ｂｌ ｅ ａ ｎ ｄ ＮＰ・ ｈ ａ ｒ ｄ ｃ ｏ ｎ ｃ ｅ ｐ ｔ ｓ ａ ｒ ｅ ｆ ｒ ｅ ｑ ｕ ｅ ｎ ｔ ｌ ｙ ｕ ｓ ｅ ｄ ｉ ｎ ｒ ｅ ｃ ｅ ｎ ｔ ｐａ ｐ ｅ ｒ ｓ ｏ ｎ ｃ ｏ ｎ ｔ ｉ ｎ ｕ ｏ ｕ ｓ
离散优化 与连续优 化的复杂性概念冰
邢 文 训 ，
摘 要 问题 的 复 杂性 概 念 起 源 于 离 散 的 图 灵计 算 机 理 论 的 研 究 ， 在 离 散 优 化 问题 的研 究 中 被 广 泛 的接 受 ． 近 期 连 续 优 化 领 域 的很 多文 章 中提 及 ＮＰ难 这 个 概 念 ．从 而 来 对 比介 绍 离 散 优 化 和 连 续 优 化 研 究 中这 两 个 概 念 的差 异 ． 关键词 复杂性概念 ， 离散优化， 连续 优 化 中图 分 类 号 Ｏ２ ２ １ ， ＴＰ ３ ０ １ ． ５ ２ ０ １ ０数学分类号 ９ ０ Ｃ ６ ０ ， ６ ８ Ｑ２ ５
散 问题 的 图灵 机 复杂 性理 论 就无 法完 全 适应 连续 优 化 问题 ， 于 是 产生 了针 对 连续 问题 的 复杂性 概念 ［ ４ － ６ ］ ． 连续 问题 的复杂 性概 念 或 多或少 地模 仿 了离 散 问题 的复杂 性逻 辑 方法 ，由此 引发 了 离散优 化 问题研 究 学者和 连 续优 化 问题研 究学 者各 自的理解 和 描述 ． 般 优化 问题 可写 为 ｍｉ ｎ ｆ （ ｘ ） ｓ ． ｔ ．９ （ ｘ ） ≤０ ， （ １ ． １ ）
Ｋｅ ｙｗ ｏ ｒ ｄｓ ｃ ｏ ｍｐ ｌ ｅ ｘ ｉ ｔ ｙ ｃ ｏ ｎ ｃ ｅ ｐ ｔ ｓ ， ｃ ｏ ｍｂ ｉ ｎ ａ ｔ ｏ ｒ ｉ ａ ｌ ｏ ｐ ｔ ｉ ｍｉ ｚ ａ ｔ ｉ ｏ ｎ ，ｃ ｏ ｎ ｔ ｉ ｎ ｕ ｏ ｕ ｓ ｏ ｐ ｔ ｉ ｍｉ ｚ ａ －
ｔ ｉ ｏｎ
２ 期
离散优化与连续优化的复杂性概念
４ １
加 、减 、乘 、除 、比较 、 读 、写等 基本 运 算， 最 后得 到 问题 实例 的解答 ． 这些 基本 运算 的总
和称 为算 法对 实例 的计 算量 ． 因为 ＮＰ难 问题 的存 在 ， 算法 设计 分为 启发 式算 法和 精确 算法 ． 启 发式 算法 是指那 些 在 可接 受 的计算 复杂 性要 求 内， 给 出 问题 实例 的一个 解 的算 法 ， 这 个解 不 一定是 问题 的最 优解 ， 甚 至连 可行解 也 不是 ． 精 确算法 必 须给 出 问题 的最优解 ． 记 问题 为 Ｑ， 实例 为 ， 字长 为 ｓ （ ） ， 一 个 算法 Ａ的计 算量 为 Ｃ Ａ （ Ｉ ） ．若存 在 一个 多项 式 函数 ｐ （ ． ） 满足：
ｏ ｐ ｔ ｉ ｍｉ ｚ ａ ｔ ｉ ｏ ｎ ｐ ｒ ｏ ｂ ｌ ｅ ｍｓ ．Ｔｈ ｉ ｓ ｐ ａ ｐｅ ｒ ｐｒ ｅ ｓ ｅ ｎ ｔ ｓ ａ ｖ ｅ ｒ ｙ ｂ ｒ ｉ ｅ ｆ ｉ ｎ ｔ ｒ ｏ ｄ ｕ ｃ ｔ ｉ ｏ ｎ ｔ ｏ ｓ ｈ ｏ ｗ ｔ ｈ ｅ ｉ ｒ ｒ ｅ ｌ ａ － ｔ ｉ ｏ ｎ ｓ ｈ ｉ ｐ ａ ｎ ｄ ｄ ｉ ｆ ｅ ｒ ｅ ｎ ｃ ｅ ｕｓ ｅ ｄ ｉ ｎ ｔ ｈ ｅ ｔ ｗｏ ｉ ｆ ｅ ｌ ｄ ｓ ．
Ｃｏ ｍ ｐｌ ｅ ｘ ｉ ｔ ｙ ｃ ｏ ｎｃ ｅ ｐｔ ｓ ｆ ｏｒ ｃ ｏ ｍ ｂｉ ｎａ ｔ ｏｒ ｉ ａ ｌ ａ ｎｄ ｃ ｏ ｎ ｔ ｉ ｎｕｏ ｕｓ
ｏ ｐｔ ｉ ｍｉ ｚ ａ ｔ ｉ ｏ ｎ ｐｒ ｏ ｂｌ ｅ ｍｓ
ＸＩ ＮＧ Ｗｅ ｎ ｘ ｕ ｎ Ｉ ， ｔ
１ 实例规模 、 基本运算和可解概念
复杂 性理 论起源 于计 算机 理论 的研 究 ， 在 优化 问题 研 究中是 一个 非常基 础 的理 论， 早 期的工作可以追溯到 ２ ０ 世纪 ７ ０ 年代初 Ｃ ｏ ｏ ｋ 的一篇会议论文［ １ ］ ． 他基于 图灵机的模型假 设， 给 出 了多项 式 时 间规 约和 Ｎ Ｐ 完 全 的概 念 ．由此 我们 知道 有 一类 问题 迄 今为 止 还没 有 多 项式 时间算 法解 决该 问题 ． 在 图灵 机 的假 设 前提 下， 我们 假 设计 算机 只能存 储有 限位 二 进 制数据 和进 行有 限位计 算 ， 所 有实 例 的数据 都是整 数 或有 理数 ， 无理数 在计 算机 是 没法 精 确表 示 的． 对 于离 散最 优化 问题 ， 我们 不 但假 设其 所有 系数 是 整数 或有 理数 ， 还 要假 设 它 的最 优解在 计 算机 中可 以精 确 的表示 ， 且在 计 算机 中 占据 的规模 符合 要求 ． 对 于 离散 优化 问题 ，已形 成 了非常 系 统化 的计 算复 杂 性 理论 ， 详 细 的 内容 可 以参 考
１ ． １ 离 散 模 型
针对 离 散 问题 ， 计算 复杂 性 的理 论基 于 图灵机 模 型 ， 或称 为 ２ 进 制模 型 ． 对 于给 定 的 问题 ， 当问题 中 的变 量个 数 ， 系 数等 给 定后 ， 称 为 问题 的一个 实例 ．问题 是实 例 的统称 ， 实 例 是 问题 的一 个具 体表 现 ．图灵机 模 型要 求 实例 中的所 有 系数 是 整数 或 有理 数 ，目前 的 计算 机就 是这样 限定 和设置 的， 也 就有 了 ３ ２ 位和 ６ ４ 位机 的区别． 给 定一个 实例 后， 计 算机 以２ 进制 的方式 存 贮 实例 的 系数 ， 它们 在 计算 机 中 占据 的空 间大 小称 为 实例 的字长 或 规 模． 算法 针对 问题 而 设计 ， 但 以每 一个 实例 为实 现对 象 ． 算法对 计 算机 中存 储 的系 数进 行
Ｃｈｉ ｎｅ ｓ ｅ Ｌｉ ｂｒ ａ ｒ ｙ Ｃｌ ａｓ ｓ ｉ ｉｃ ｆ ａ ｔ ｉ ｏ ｎ ０２ ２ １ ． ＴＰ３ ０ １ ． ５
２ ０ １ ０ Ｍａ ｔ ｈ ｅ ｍａ ｔ ｉ ｃ ｓ Ｓ ｕ ｂ ｊ ｅ ｃ ｔ Ｃｌ ａ ｓ ｓ ｉ ｉ ｆ ｃ ａ ｔ ｉ ｏ ｎ ９ ０ Ｃ６ ０ ， ６ ８ Ｑ２ ５
２ ０ １ ７Ｏｐｅ ｒ ａ ｔ ｉ ｏ ｎ ｓ Ｒｅ ｓ ｅ ａ ｒ ｃ ｈ Ｔ ｒ ａ ｎ ｓ ａ ｃ ｔ ｉ ｏ ｎ ｓ
第２ １ 卷 第２ 期
Ｖｏ ｌ ＿ ２ １ ＮＯ ． ２
Ｄ Ｏ Ｉ ： １ ０ ． １ ５ ９ ６ ０ ／ ｊ ． ｃ ｎ ｋ ｉ ． ｉ ｓ ｓ ｎ ． １ ０ ０ ７ — ６ ０ ９ ３ ． ２ ０ １ ７ ． ０ ２ ． ０ ０ ５
Ｂｅ ｉ ｊ ｉ ｎ ｇ １ ０ ０ ０ ８ ４ ， Ｃｈ ｉ ｎ ａ
十通 信 作 者 Ｅ — ｍａ ｉ ｌ ： ｗ ｘ ｉ ｎ ｇ ＠ｍａ ｔ ｈ ． ｔ ｓ ｉ ｎ ｇ ｈ ｕ ａ ． ｅ ｄ ｕ ． ａ ｎ
４ ０
邢 文
２ １ 卷
本文 基 于读 者有 图灵 机 复杂 性理 论 的基 本 概念 ， 对于 计 算复 杂性 理 论 中一 些基 本 概 念， 如 判 定 问题 、实例 、算法 、多项 式时 间算 法与 问题 、 ＮＰ问题类 、 ＮＰ完全 和 Ｎ Ｐ难 ， 只 有在 需要 的时候才 给 出定义 ． 我们 仅 以离散最 优化 和连 续优 化 问题 ， 以对 比的方 式给 出各 自领域 的 复杂性 概念 ， 通 过 一些 简单 例子 来 理解 复杂 性在 这 两个 领 域 的差 异． 特别 针 对离 散优 化 问题 中的 多项 式 时 间 问题 和连 续优 化 问题 中 的多项 式时 间可 计算 性 问题进 行 比对解 释 ．
一
Ｘ ∈ Ｄ Ｃ ”
其 中 称 为 定义域 ， ｆ： ０ ５ 为 目标 函数 ， ｇ： ＿ ÷瓞 为 约束 函数．当 为 离散 点集 时， 优 化 问题 （ １ ． １ ） 称为 离散 优化 问题 或组 合最 优化 问题 ， 当 Ｄ为连 续 点集 时， 该 问题 称 为 连续 优化 问题 ． ＝｛ ∈７ ９ ｌ ９ （ ｘ ） ≤０ ） 称 为 问题 的可 行解 集合 ．
Ｃ Ａ （ Ｉ ） ＝ ０（ ｐ （ ｓ （ ） ） ） ， Ｖ Ｉ∈Ｑ ， 则称 Ａ是 问题 Ｑ的一个 多项 式 时 间算法 ， 简 称 多项 式 算法 ， 其 中“ ０” 表 示 被控 制 的含 义 ， 即存在 一个 与任 何 实例 无关 的正 常数 Ｏ ｌ 满 足
Ｃ Ａ （ Ｉ ） ≤ ｐ （ ｓ （ ） ） ， Ｖ Ｉ∈Ｑ