资源预览内容
第1页 / 共42页
第2页 / 共42页
第3页 / 共42页
第4页 / 共42页
第5页 / 共42页
第6页 / 共42页
第7页 / 共42页
第8页 / 共42页
第9页 / 共42页
第10页 / 共42页
亲,该文档总共42页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
南 京 航 空 航 天 大 学硕 士 学 位 论 文一 类 最 优 化 问 题 的 算 法 设 计姓 名 : 曹 静申 请 学 位 级 别 : 硕 士专 业 : 运 筹 学 与 控 制 论指 导 教 师 : 殷 洪 友20080301南 京 航 空 航 天 大 学 硕 士 学 位 论 文摘 要最 优 化 是 一 门 应 用 相 当 广 泛 的 学 科 , 它 在 航 空 航 天 、 生 命 科 学 、 水 利 科 学 、地 球 科 学 、 工 程 技 术 等 自 然 科 学 领 域 和 经 济 金 融 学 等 科 学 领 域 有 着 广 泛 和 重 要 的应 用 。 经 济 学 中 的 人 力 资 源 管 理 , 货 物 的 调 配 以 及 工 程 中 的 很 多 问 题 归 根 结 底 是寻 求 一 个 数 学 模 型 的 最 优 解 。 本 文 主 要 研 究 一类特 殊 的 含 不 等 约 束 的 最 优 化 问题 。本 文 提 出 了 一 类 新 的 函 数 , 定 义 为 半 正 定 函 数 。 利 用 这 类 函 数 将 原 问 题 转 化为 无 约 束 最 优 化 和 含 等 式 约 束 的 最 优 化 问 题 , 分 别 设 计 了 算 法 并 进 行 了 数 值 实 验验 证 了 算 法 的 有 效 性 。 讨 论 了 子 问 题 的 全 局 优 化 算 法 , 构 造 了 一 类 填 充 函 数 , 并设 计 了 算 法 。 针 对 这 类 最 优 化 问 题 , 提 出 了 拟 填 充 函 数 的 概 念 , 并 构 造 了 拟 填 充函 数 , 设 计 了 相 应 的 算 法 。 具 体 内 容 如 下 :本 论 文 包 括 以 下 六 部 分 :第 一 章 , 首 先 介 绍 了 问 题 提 出 的 背 景 以 及 目 前 的 研 究 现 状 。第 二 章 , 对 求 解 最 优 化 问 题 的 局 部 优 化 算 法 和 全 局 优 化 算 法 进 行 了 一 个 简单 的 综 述 。第 三 章 , 提 出 了 半 正 定 函 数 的 概 念 并 讨 论 了 它 的 性 质 , 给 出 了 一 些 半 正 定 函数 的 例 子 。 利 用 半 正 定 函 数 构 造 了 算 法 , 并 进 行 了 数 值 实 验 。第 四 章 , 研 究 了 算 法 的 子 问 题 的 全 局 最 优 算 法 , 提 出 了 一 类 填 充 函 数 , 设 计了 算 法 。第 五 章 , 提 出 了 拟 填 充 函 数 的 概 念 , 设 计 了 一 个 拟 填 充 函 数 , 并 设 计 了 算 法 。第 六 章 , 对 本 工 作 的 简 单 总 结 , 指 出 了 工 作 中 存 在 的 不 足 和 对 未 来 工 作 的 展望 。关键词:最 优 化 算 法 , 半 正 定 函 数 , 填 充 函 数 , 拟 填 充 函 数 。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 optimization.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 definition 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 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, we 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.ii承诺书本 人 郑 重 声 明 : 所 呈 交 的 学 位 论 文 , 是 本 人 在 导 师 指 导 下 , 独 立进 行 研 究 工 作 所 取 得 的 成 果 。 尽 我 所 知 , 除 文 中 已 经 注 明 引 用 的 内 容外 , 本 学 位 论 文 的 研 究 成 果 不 包 含 任 何 他 人 享 有 著 作 权 的 内 容 。 对 本论 文 所 涉 及 的 研 究 工 作 做 出 贡 献 的 其 他 个 人 和 集 体 , 均 已 在 文 中 以 明确 方 式 标 明 。本 人 授 权 南 京 航 空 航 天 大 学 可 以 有 权 保 留 送 交 论 文 的 复 印 件 , 允许论文被查阅和借阅, 可以将学位论文的全部或部分内容编入有关数据 库 进 行 检 索 , 可 以 采 用 影 印 、 缩 印 或 其 他 复 制 手 段 保 存 论 文 。(保 密 的 学 位 论 文 在 解 密 后 适 用 本 承 诺 书 )作 者 签 名 :日 期 :min F (x) x f (x) , x 0,x 0, 0.的一个最优化问题,即求解使得 min x f (x) 0 的点或者是近似点。因而研究这南 京 航 空 航 天 大 学 硕 士 学 位 论 文第 一 章 绪 论1.1 问 题 的 起 源最 优 化 是 一 门 应 用 相 当 广 泛 的 学 科 , 它 在 航 空 航 天 , 生 命 科 学 , 水 利 科 学 ,地 球 科 学 , 工 程 技 术 等 自 然 科 学 领 域 和 经 济 金 融 学 等 科 学 领 域 有 着 广 泛 和 重 要 的应 用 。 经 济 学 中 的 人 力 资 源 管 理 , 货 物 的 调 配 以 及 工 程 中 的 很 多 问 题 归 根 结 底 是寻 求 一 个 数 学 模 型 的 局 部 或 全 局 最 优 解 。 本 文 主 要 研 究 一 类 具 有 特 殊 形 式 的 最 优化 问 题 。考 虑 以 下 约 束 数 学 规 划 :T( P) s.t x 0 , ( 1.1)f (x) 0 .其 中 x (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 是 一 个 凸 向 量 函 数 , 该 问 题 的 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 被 称 为 互补 问 题 的 效 益 函 数 , 使 得 ( ) 0x 的 x一 类 最 优 化 问 题 的 算 法 设 计论 , 交 通 平 衡 等 领 域 均 有 着 广 泛 的 应 用 。 求 解 互 补 问 题 是 解 决 这 样 的 一 个 问 题 :给 定 映 射 f (x) : Rn Rn , 求 向 量 x R n , 使 得 0 x f (x) 0 ,其 中 “ ”表 示TT称 为 互 补 问 题 的 零 效 解 。 那 么 互 补 问 题 就 可 以 转 化 为 求 解 最 优 化 问 题min (x) ,s.t x 0 ,f (x) 0的 零 效 解 或 近 似 零 效 解 。 而 这 种 形 式 就 等 价 于 我 们 前 面 描 述 的 问 题 ( P) 。而且当问 题 ( P) 的 最 优 值 为 零 时 , 互 补 问 题 是 可 解 的 , 此 时 问 题 ( P) 的 最 优 解 就 是 互补 问 题 的 解 。 若 可 以 通 过 分 析 需 要 求 解 的 互 补 问 题 的 一 些 性 质 得 到 互 补 问 题 是 可解的,则我们可以通过求解问题(P)来求解该互补问题,因此,我们的研究从这 方 面 来 讲 也 是 很 有 意 义 的 。1.2 研究现状目 前 研 究 约 束 最 优 化 问 题 的 算 法 有 很 多 , 主 要 分 为 两 大 类 , 总 体 上 分 为 局 部最 优 算 法 和 全 局 最 优 算 法 。对
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号