南 京 航 空 航 天 大 学硕 士 学 位 论 文一 类 变 分 不 等 式 问 题 的 数 值 解 法姓 名 ： 段 景 涛申 请 学 位 级 别 ： 硕 士专 业 ： 运 筹 学 与 控 制 论指 导 教 师 ： 殷 洪 友2010-12南 京 航 空 航 天 大 学 硕 士 学 位 论 文摘 要变 分 不 等 式 问 题 是 目 前 数 学 领 域 备 受 关 注 的 热 点 之 一 ， 在 数 学 、 物 理 、 经 济 学和 工 程 科 学 中 有 着 广 泛 的 应 用 背 景 。本 文 主 要 研 究 如 何 求 解 凸 多 面 体 上 的 变 分 不 等 式 问 题 。 首 先 将 凸 多 面 体 上 的 变分 不 等 式 问 题 转 换 为 互 补 问 题 ， 在 此 基 础 之 上 提 出 了 两 种 预 测 校 正 算 法 。 第 一 种 是修 正 的 投 影 算 法 ， 即 在 每 一 次 迭 代 运 算 中 进 行 预 测 和 校 正 两 次 投 影 运 算 。 与 以 往 方法 相 比 ， 新 的 算 法 在 预 测 步 中 更 好 的 利 用 了 已 求 解 分 量 的 信 息 ， 并 且 给 出 了 新 的Armijo 搜 索 准 则 ； 在 校 正 步 中 亦 给 出 了 最 优 步 长 。 第 二 种 方 法 是 基 于 逼 近 点 算 法 的LQP 预 测 校 正 算 法 ， 即 在 每 次 迭 代 运 算 中 先 用 LQP 方 法 求 得 一 预 测 点 ， 然 后 再 通 过投 影 法 进 行 一 次 校 正 。 与 以 往 方 法 相 比 ， 新 的 算 法 在 校 正 步 中 没 有 继 续 使 用 LQP 方法 ， 而 是 使 用 投 影 法 进 行 校 正 ； 这 就 综 合 了 LQP 算 法 和 投 影 法 的 优 点 。 两 种 新 算 法仅 仅 要 求 函 数 连 续 单 调 即 可 ， 这 拓 宽 了 它 的 应 用 范 围 。 最 后 ， 文 中 给 出 了 满 足 一 定约 束 条 件 的 收 敛 性 证 明 ； 并 通 过 数 值 实 验 说 明 了 两 种 算 法 的 有 效 性 。本 文 共 分 为 五 章 ， 各 章 内 容 安 排 如 下 ： 第 一 章 是 绪 论 部 分 ， 介 绍 变 分 不 等 式 问题 的 定 义 及 各 种 解 法 概 述 ， 并 介 绍 了 本 文 主 要 的 研 究 内 容 ； 第 二 章 是 修 正 的 投 影 预测 校 正 算 法 ， 给 出 求 解 单 调 变 分 不 等 式 的 新 的 预 测 校 正 算 法 ； 第 三 章 是 修 正 的 LQP预 测 校 正 算 法 ， 给 出 了 算 法 的 具 体 步 骤 及 收 敛 性 证 明 ； 第 四 章 是 数 值 试 验 ， 目 的 是通 过 实 验 来 验 证 算 法 的 有 效 性 。 第 五 章 是 总 结 ， 不 但 对 全 文 做 出 总 结 ， 而 且 对 未 来的 研 究 工 作 给 出 展 望 。关 键 词 ： 变 分 不 等 式 ， 互 补 问 题 ， 投 影 法 ， 逼 近 点 算 法 ， 对 数 二 次 逼 近 法I一 类 变 分 不 等 式 问 题 的 数 值 解 法AbstractVariational inequality problem is one of the focal point problems paid close attention by scholarsin the field of mathematics. It has been widely used in mathematics, physics, economics andengineering sciences.In this paper, we mainly study how to solve the variational inequality problem in convexpolyhedron. The paper first transforms the variational inequality problem in convex polyhedron to acomplementary problem. On this basis, we proposed two kinds of prediction-correction methods. Thefirst one is the modified projection method. At each iteration, it needs two projection operations.Compared with previous methods, the new method is better use of the components that have beensolved and gives the new Armijo criteria in the prediction step. It also gives the optimal steps in thecorrection. The second one is a lagarithmic-quadratic proximal(LQP) prediction-correction methodwhich is based on the proximal point algorithm. At each iteration, we first find a predictor with theLQP method. Then we correct the predictor with the projection method. Compared with previousmethods, the new algorithm does not continue to use the LQP method, but using the projectionmethod in the correction step. It combines the advantages of the LQP algorithm and the projection.For two kinds of new algorithm the only requirement is that the funtion is continuous and monotone,which broadens the scope of application. Finally, the convergences are proved when they satisfycertain constraints. The numerical experiments show that the two algorithms are effective.The paper contains five parts. The first part is the introduction. In this section, the definition ofvariational inequality and the overview of various methods are introduced. In section two, themodified prediction-correction method for monotone variational inequality is given. Section three isthe modified LQP prediction-correction method. In this section, the paper gives the specific steps ofthe algorithm and the proof of convergence. The fourth part is numerical test, which aims to verify theconvergence of the algorithm. The fifth part is a summary. The paper not only offers a summary of thefull text, but also gives prospect of future research.Keywords: Variational inequality, Complementary problem, Projection method, Proximal pointalgorithm, Lagarithmic-Quadratic Proximal methodII承 诺 书本 人 声 明 所 呈 交 的 硕 士 学 位 论 文 是 本 人 在 导 师 指 导 下 进行 的 研 究 工 作 及 取 得 的 研 究 成 果 。 除 了 文 中 特 别 加 以 标 注 和 致谢 的 地 方 外 ， 论 文 中 不 包 含 其 他 人 已 经 发 表 或 撰 写 过 的 研 究 成果 ， 也 不 包 含 为 获 得 南 京 航 空 航 天 大 学 或 其 他 教 育 机 构 的 学 位或证书而使用过的材料。本 人 授 权 南 京 航 空 航 天 大 学 可 以 将 学 位 论 文 的 全 部 或 部分 内 容 编 入 有 关 数 据 库 进 行 检 索 ， 可 以 采 用 影 印 、 缩 印 或 扫 描等复制手段保存、汇编学位论文。（保密的学位论文在解密后适用本承诺书）作 者 签 名 ：日 期 ：是 指 ： 求 向 量 x C ， 使 得F (x* ) (x x* ) 0 ，其中 C 是 R 的非空闭凸子集， F 是 R R 的连续映射。若 F 为线性函数，则称为线性变， 即 求 x R ， 使 得 F (x ) 0 ， x ） F (x ) 0 ， 其 中 F 是 R R（等 式 问 题 的 求 解 主 要 使 用 迭 代 算 法 。 九 十 年 代 以 前 迭 代 算 法 格 式 主 要 为 ： 给 定 x C ， 求 解 变分不等式子问题 VI (C, F ) ，并将其解作为下一迭代点，其中映射 F 是映射 F 的某一近似。根 据 映 射 F 的 构 造 可 分 为 线 性 方 法 和 非 线 性 方 法 两 大 类 。线 性 方 法 是 指 求 解 一 系 列 变 分 不 等 式 子 问 题 VI (C, F ) ， 即 求 x C 满 足F k (x* ) (x x* ) 0 ，其 中 F (x) F (x ) A(x )(x x ) 为 线 性 函 数 ， A(x ) 为 n 阶 矩 阵 。 根 据 A(x ) 的 不 同 线 性南 京 航 空 航 天 大 学 硕 士 学 位 论 文第 一 章 绪 论1.1 变 分 不 等 式 问 题 的 概 述变 分 不 等 式 问 题 1-8 *T x C （ 1.1.1）n n n分 不 等 式 问 题 ； 否 则 为 非 线 性 变 分 不 等 式 问 题 。 变 分 不 等 式 问 题 首 先 由 Hartman 和 Stampacchia9在 1966 年 提 出 ， 最 初 是 用 来 研 究 偏 微 分 方 程 的 。 目 前 是 数 学 领 域 备 受 关 注 的 热 点 之 一 ， 在 数 学 、物 理 、 经 济 学 和 工 程