《一种求解互补问题的光滑算法》由会员分享，可在线阅读，更多相关《一种求解互补问题的光滑算法（45页珍藏版）》请在金锄头文库上搜索。
1、南 京 航 空 航 天 大 学硕 士 学 位 论 文一 种 求 解 互 补 问 题 的 光 滑 算 法姓 名 ： 包 卫 军申 请 学 位 级 别 ： 硕 士专 业 ： 运 筹 学 与 控 制 论指 导 教 师 ： 殷 洪 友20060301南 京 航 空 航 天 大 学 硕 士 学 位 论 文摘 要互 补 问 题 的 理 论 和 算 法 在 经 济 学 ， 对 策 论 和 数 学 规 划 领 域 有 着 广 泛 的 应 用 ， 关 于互 补 问 题 的 研 究 一 直 是 非 线 性 科 学 和 计 算 科 学 的 热 点 问 题 ， 求 解 互 补 问 题 的 算 法 的 研究 也 取 得
2、 了 很 多 成 果 。 本 文 研 究 互 补 问 题 的 数 值 方 法 。 基 于 现 有 的 各 种 光 滑 牛 顿 法 的思 想 和 半 光 滑 理 论 ， 在 现 有 算 法 的 基 础 上 做 了 进 一 步 的 研 究 ， 首 先 针 对 著 名 的Fischer-Burmeister 互补函数提出一个新的光滑逼近函数，这个逼近函数是现有逼近 函 数 的 推 广 ， 同 时 研 究 了 逼 近 函 数 的 一 些 性 质 ， 然 后 利 用 该 函 数 将 求 解 互 补 问 题 转化 为 求 解 非 线 性 方 程 组 问 题 ， 进 而 利 用 光 滑 牛 顿 法 求 解
3、方 程 组 问 题 ， 从 而 给 出 了 一 个求 解 互 补 问 题 的 光 滑 牛 顿 法 。 本 文 还 引 入 了 新 的 控 制 函 数 ， 并 证 明 了 算 法 具 有 全 局 收敛 性 和 在 一 定 的 条 件 下 具 有 局 部 超 线 性 收 敛 性 ； 然 后 ， 在 第 一 个 算 法 的 基 础 上 ， 本 文利 用 已 有 的 光 滑 逼 近 函 数 提 出 了 另 外 一 个 新 的 算 法 ， 通 过 适 当 参 数 选 取 ， 证 明 了 新 的算 法 具 有 与 第 一 个 算 法 同 样 良 好 的 收 敛 性 质 ； 最 后 ， 通 过 数 值 计
4、算 说 明 了 算 法 的 高 效性 。全文共分为四章，各部分内容安排如下：第一章是绪论部分，介绍了互补问题的 应 用 背 景 和 近 年 来 有 关 互 补 问 题 求 解 方 法 的 研 究 成 果 ； 第 二 章 介 绍 了 与 互 补 问 题 相关 的 一 些 定 义 以 及 相 关 的 定 理 和 推 论 ； 第 三 章 是 本 文 的 重 点 ， 构 造 了 求 解 互 补 问 题 的一 类 光 滑 牛 顿 法 ， 从 理 论 上 证 明 了 算 法 的 全 局 收 敛 性 和 局 部 超 线 性 收 敛 性 ； 第 四 章 是数 值 实 验 ， 通 过 数 值 试 验 的 结 果
5、 进 一 步 证 明 了 算 法 的 可 行 性 和 有 效 性 。 最 后 一 章 是 对本 文 的 总 结 和 对 将 来 研 究 工 作 的 展 望 。关 键 词 ： 互 补 问 题 ， 非 光 滑 函 数 ， 光 滑 逼 近 ， 方 程 组 ， 光 滑 算 法 ， 收 敛 性i一 种 求 解 互 补 问 题 的 光 滑 算 法ABSTRACTTheories and algorithms of the complementarity problem have been widely used in thefield of economics, game theory and mathe
6、matical programming. The research on it isalways the hot spots in nonlinear and computational science. Many results have beenachieved. Our test deals with the numerical methods of the complementarity problem.Based on the concept of the smoothing Newton methods that exist and the semismooththeory, we
7、 do further research. First of all, we propose a new smooth approximationfunction of the famous Fischer-Burmeister function. And it is the generalization of theexisted approximation function. At the same time, we study some of its attributes. Then weuse it to convert the complementarity problem into
8、 nonlinear equations. And we use thesmoothing Newton method to solve the equations. We also introduce a control function,prove the global convergence, and prove the local superlinear convergence under someconditions. Then we propose another new algorithm by using an existed approximationfunctions, w
9、hich has the same characters as the first algorithms does. Finally, the result ofthe numerical experiments indicates the efficiency of the first algorithm.The paper contains four parts. In the first chapter, the application background and themain algorithms of the complementarity problems is introdu
10、ced. In Chapter 2, some basicdefinitions and theories of complementarity problems are introduced. The 3rd chapter isthe most important part of this paper, in which a new class of smoothing Newton method isdetailed, also the global and local superlinear convergence is established for the method. Inth
11、e 4th chapter, we propose some numerical experiment, and the results show theeffectiveness of the proposed algorithms. In the last chapter, we conclude the paper.Keywords: complementarity problem, nonsmooth functions, smooth approximation ,equations, smooth algorithms, convergence承 诺 书本 人 郑 重 声 明 ：
12、所 呈 交 的 学 位 论 文 ， 是 本 人 在 导 师 指 导 下 ， 独 立 进行 研 究 工 作 所 取 得 的 成 果 。 尽 我 所 知 ， 除 文 中 已 经 注 明 引 用 的 内 容 外 ，本 学 位 论 文 的 研 究 成 果 不 包 含 任 何 他 人 享 有 著 作 权 的 内 容 。 对 本 论 文 所涉 及 的 研 究 工 作 做 出 贡 献 的 其 他 个 人 和 集 体 ， 均 已 在 文 中 以 明 确 方 式 标明 。本 人 授 权 南 京 航 空 航 天 大 学 可 以 有 权 保 留 送 交 论 文 的 复 印 件 ， 允 许论 文 被 查 阅 和 借
13、阅 ,可 以 将 学 位 论 文 的 全 部 或 部 分 内 容 编 入 有 关 数 据 库进 行 检 索 ， 可 以 采 用 影 印 、 缩 印 或 其 他 复 制 手 段 保 存 论 文 。(保 密 的 学 位 论 文 在 解 密 后 适 用 本 承 诺 书 )作 者 签 名 ：日 期 ：x 0, r(x) Mx q 0, x r(x) 0 ， （ 1.1） 连 续 可 微 。 本 文 将 非 线 性 互 补 问 题 (1.2)记 为 NCP(F ) 。min c, x c x, b , c s.t. y 0, A y c, y 设 z , f (z) z b Ax b c A yyT x
14、 c y b c x b y 。南 京 航 空 航 天 大 学 硕 士 学 位 论 文第 一 章 绪 论1.1 互 补 问 题 的 引 入互 补 问 题 的 理 论 和 算 法 在 经 济 学 ， 对 策 论 和 数 学 规 划 领 域 有 着 广 泛 的 应 用 。 如 均衡 网 络 设 计 ， 信 号 最 优 化 问 题 ， 对 策 中 的 博 弈 问 题 以 及 数 学 规 划 中 的 K-T 条 件 常 常都 涉 及 到 解 互 补 问 题 。 由 于 互 补 问 题 与 非 线 性 科 学 和 许 多 实 际 问 题 密 切 相 关 ， 从 二 十世 纪 六 十 年 代 以 后 ，
15、互 补 问 题 的 理 论 和 算 法 研 究 一 直 是 基 础 数 学 和 计 算 数 学 领 域 中 的一 个 热 点 课 题 ， 有 关 互 补 问 题 的 算 法 不 断 涌 现 。互 补 问 题 可 以 分 为 线 性 互 补 问 题 和 非 线 性 互 补 问 题 。线 性 互 补 问 题 是 指 ： 求 向 量 x n， 使 得 ：T其 中 M (mij ) nn 为 给 定 常 数 矩 阵 ， q (q1,., qn )T n 为 给 定 的 常 向 量 。非 线 性 互 补 问 题 是 指 ： 求 向 量 x n， 使 得 ：其 中 F : n nx 0, F (x) 0,
16、 xT F (x) 0 ， (1.2)互 补 问 题 广 泛 存 在 于 最 优 化 问 题 中 ， 最 优 化 中 的 许 多 问 题 都 可 以 转 化 为 互 补 问 题求 解 ， 下 面 分 别 给 出 说 明 。 线 性 规 划考 虑 原 始 的 线 性 规 划 问 题 （ PLP）：其中 A mn m nT，s.t.x 0, Ax b。 它 的 对 偶 问 题 （ DLP） 为max b, y bT y T m 。设 x0 ， y0 分 别 是 （ PLP） 和 （ DLP） 的 可 行 解 ， 则 x0 ， y0 同 为 最 优 解 的 充 要 条 件是 ： c, x b, y 。
