《一类最优化问题的算法设计》由会员分享，可在线阅读，更多相关《一类最优化问题的算法设计（42页珍藏版）》请在金锄头文库上搜索。
1、南 京 航 空 航 天 大 学硕 士 学 位 论 文一 类 最 优 化 问 题 的 算 法 设 计姓 名 ： 曹 静申 请 学 位 级 别 ： 硕 士专 业 ： 运 筹 学 与 控 制 论指 导 教 师 ： 殷 洪 友20080301南 京 航 空 航 天 大 学 硕 士 学 位 论 文摘 要最 优 化 是 一 门 应 用 相 当 广 泛 的 学 科 ， 它 在 航 空 航 天 、 生 命 科 学 、 水 利 科 学 、地 球 科 学 、 工 程 技 术 等 自 然 科 学 领 域 和 经 济 金 融 学 等 科 学 领 域 有 着 广 泛 和 重 要 的应 用 。 经 济 学 中 的 人 力
2、 资 源 管 理 ， 货 物 的 调 配 以 及 工 程 中 的 很 多 问 题 归 根 结 底 是寻 求 一 个 数 学 模 型 的 最 优 解 。 本 文 主 要 研 究 一类特 殊 的 含 不 等 约 束 的 最 优 化 问题 。本 文 提 出 了 一 类 新 的 函 数 ， 定 义 为 半 正 定 函 数 。 利 用 这 类 函 数 将 原 问 题 转 化为 无 约 束 最 优 化 和 含 等 式 约 束 的 最 优 化 问 题 ， 分 别 设 计 了 算 法 并 进 行 了 数 值 实 验验 证 了 算 法 的 有 效 性 。 讨 论 了 子 问 题 的 全 局 优 化 算 法 ，
3、构 造 了 一 类 填 充 函 数 ， 并设 计 了 算 法 。 针 对 这 类 最 优 化 问 题 ， 提 出 了 拟 填 充 函 数 的 概 念 ， 并 构 造 了 拟 填 充函 数 ， 设 计 了 相 应 的 算 法 。 具 体 内 容 如 下 ：本 论 文 包 括 以 下 六 部 分 ：第 一 章 ， 首 先 介 绍 了 问 题 提 出 的 背 景 以 及 目 前 的 研 究 现 状 。第 二 章 ， 对 求 解 最 优 化 问 题 的 局 部 优 化 算 法 和 全 局 优 化 算 法 进 行 了 一 个 简单 的 综 述 。第 三 章 ， 提 出 了 半 正 定 函 数 的 概 念
4、 并 讨 论 了 它 的 性 质 ， 给 出 了 一 些 半 正 定 函数 的 例 子 。 利 用 半 正 定 函 数 构 造 了 算 法 ， 并 进 行 了 数 值 实 验 。第 四 章 ， 研 究 了 算 法 的 子 问 题 的 全 局 最 优 算 法 ， 提 出 了 一 类 填 充 函 数 ， 设 计了 算 法 。第 五 章 ， 提 出 了 拟 填 充 函 数 的 概 念 ， 设 计 了 一 个 拟 填 充 函 数 ， 并 设 计 了 算 法 。第 六 章 ， 对 本 工 作 的 简 单 总 结 ， 指 出 了 工 作 中 存 在 的 不 足 和 对 未 来 工 作 的 展望 。关键词：
5、最 优 化 算 法 ， 半 正 定 函 数 ， 填 充 函 数 ， 拟 填 充 函 数 。i一 类 最 优 化 问 题 的 算 法 设 计AbstractOptimization is a very useful subject. It can be used in the field of aeronauticsand astronautics, life science, engineering science and financial science. In this thesiswe investigate a special kind of constrained optimiza
6、tion.In this article we propose a new type of function, which is called a semi-positivefunction. We use this function to make another function, then we can turn the originalproblem into another one. We give algorithms and numerical results. Then weinvestigate the sub-problem. Also we propose the def
7、inition of quasi-filled function.We propose a quasi-filled function and design algorithm. It mainly contains thefollowing six chapters:In the first Chapter, we give a brief introduction for the research background andcurrent situation.Chapter 2 is a summarization of local optimization algorithms and
8、 globaloptimization algorithms.Chapter 3, firstly, we propose the definition of semi-positive function, then weuse this function construct algorithms and do numerical experiments.Chapter 4, in this part, we use filled function to solve sub-problem. Weconstruct an algorithm.Chapter 5, in this part, w
9、e propose the definition of quasi-filled function, andgive a quasi-filled function.Chapter 6, a conclusion is simply given. Some deficiencies in our work arepointed out and a future investigation is also discussed.Key words: optimization, semi-positive function, filled function, quasi-filledfunction
10、.ii承诺书本 人 郑 重 声 明 ： 所 呈 交 的 学 位 论 文 ， 是 本 人 在 导 师 指 导 下 ， 独 立进 行 研 究 工 作 所 取 得 的 成 果 。 尽 我 所 知 ， 除 文 中 已 经 注 明 引 用 的 内 容外 ， 本 学 位 论 文 的 研 究 成 果 不 包 含 任 何 他 人 享 有 著 作 权 的 内 容 。 对 本论 文 所 涉 及 的 研 究 工 作 做 出 贡 献 的 其 他 个 人 和 集 体 ， 均 已 在 文 中 以 明确 方 式 标 明 。本 人 授 权 南 京 航 空 航 天 大 学 可 以 有 权 保 留 送 交 论 文 的 复 印 件
11、 ， 允许论文被查阅和借阅, 可以将学位论文的全部或部分内容编入有关数据 库 进 行 检 索 ， 可 以 采 用 影 印 、 缩 印 或 其 他 复 制 手 段 保 存 论 文 。(保 密 的 学 位 论 文 在 解 密 后 适 用 本 承 诺 书 )作 者 签 名 ：日 期 ：min F (x) x f (x) , x 0,x 0, 0.的一个最优化问题，即求解使得 min x f (x) 0 的点或者是近似点。因而研究这南 京 航 空 航 天 大 学 硕 士 学 位 论 文第 一 章 绪 论1.1 问 题 的 起 源最 优 化 是 一 门 应 用 相 当 广 泛 的 学 科 ， 它 在 航
12、 空 航 天 ， 生 命 科 学 ， 水 利 科 学 ，地 球 科 学 ， 工 程 技 术 等 自 然 科 学 领 域 和 经 济 金 融 学 等 科 学 领 域 有 着 广 泛 和 重 要 的应 用 。 经 济 学 中 的 人 力 资 源 管 理 ， 货 物 的 调 配 以 及 工 程 中 的 很 多 问 题 归 根 结 底 是寻 求 一 个 数 学 模 型 的 局 部 或 全 局 最 优 解 。 本 文 主 要 研 究 一 类 具 有 特 殊 形 式 的 最 优化 问 题 。考 虑 以 下 约 束 数 学 规 划 ：T（ P） s.t x 0 , （ 1.1）f (x) 0 .其 中 x
13、(x1, x2 , x3 L xn )T 是 n 维 列 向 量 ， f (x) ( f (x1), f (x2 ), f (x3 )L f (xn )T 是 连续 可 微 的 向 量 函 数 。这 一 问 题 是 有 着 深 厚 的 应 用 背 景 的 。 首 先 ， 该 问 题 可 以 看 作 是 由 求 解 带 约 束最 优 化 问 题 求 K-T 点 1或 者 近 似 K-T 点 转 化 而 来 的 。例 如 求 解 最 优 化 问 题min g(x) ,s.t x 0 . （ 1.2）其 中 g(x) (g(x1), g(x2 ), g(x3 ),L , g(xn )T 是 一 个
14、凸 向 量 函 数 ， 该 问 题 的 K-T 点应满 足 的 条 件 为 ：g(x) 0, T其 中 (1, 2 , 3,L n )T 。若 记 g(x) f (x) ， 则 上 述 问 题 就 化 为 形 如min xT f (x) ,s.t x 0 ,f (x) 0 .T个 问 题 本 身 就 具 有 重 要 的 意 义 。我 们 知 道 互 补 问 题 是 一 类 重 要 的 优 化 问 题 ， 它 在 经 济 学 ， 工 程 ， 物 理 ， 对 策1( )0x f x 。在 互 补 问 题 中 ， ( ) ( )x x f x 被 称 为 互补 问 题 的 效 益 函 数 ， 使 得
15、 ( ) 0x 的 x一 类 最 优 化 问 题 的 算 法 设 计论 ， 交 通 平 衡 等 领 域 均 有 着 广 泛 的 应 用 。 求 解 互 补 问 题 是 解 决 这 样 的 一 个 问 题 ：给 定 映 射 f (x) : Rn Rn ， 求 向 量 x R n ， 使 得 0 x f (x) 0 ,其 中 “ ”表 示TT称 为 互 补 问 题 的 零 效 解 。 那 么 互 补 问 题 就 可 以 转 化 为 求 解 最 优 化 问 题min (x) ,s.t x 0 ,f (x) 0的 零 效 解 或 近 似 零 效 解 。 而 这 种 形 式 就 等 价 于 我 们 前
16、面 描 述 的 问 题 （ P） 。而且当问 题 （ P） 的 最 优 值 为 零 时 ， 互 补 问 题 是 可 解 的 ， 此 时 问 题 （ P） 的 最 优 解 就 是 互补 问 题 的 解 。 若 可 以 通 过 分 析 需 要 求 解 的 互 补 问 题 的 一 些 性 质 得 到 互 补 问 题 是 可解的，则我们可以通过求解问题（P）来求解该互补问题，因此，我们的研究从这 方 面 来 讲 也 是 很 有 意 义 的 。1.2 研究现状目 前 研 究 约 束 最 优 化 问 题 的 算 法 有 很 多 ， 主 要 分 为 两 大 类 ， 总 体 上 分 为 局 部最 优 算 法 和 全 局 最 优 算 法 。对
