几类对称锥互补问题的算法研究

论文摘要

对称锥互补问题（SCCP）是一类重要的均衡优化问题,具有内容新、理论丰富和应用背景广泛等特点.他为标准非线性互补问题（NCP）、二阶锥互补问题（SOCCP）、半定互补问题（SDCP）提供了统一框架,与组合优化、鲁棒优化、不确定优化、博弈与均衡理论等分支有密切的联系.本论文主要利用欧几里德若当代数技术,建立了求解几类SCCP的光滑牛顿法,包括求解单调SCCP、其特殊情形单调SOCCP和非单调SCCP.另外,讨论了SCCP价值函数的一些性质.光滑牛顿法求解SCCP,首先利用互补函数,如常见的最小值函数或者FB互补函数,将SCCP转化为一个非光滑非线性方程组.然后在互补函数中引入一个光滑因子构造出一个光滑函数,利用此光滑化互补函数来逼近以前的互补函数.通过求解光滑方程组来达到求解原非光滑方程组的目的,其中光滑因子作为光滑方程组中的一个变量.最后利用牛顿法求解所转化的光滑方程组.本论文取得的主要结果可概括为如下:对于单调SCCP,基于对称扰动Chen-Harker-Kanzow-Smale（CHKS）光滑函数提出一个预估校正光滑牛顿法.证明算法所生成的点列在解集仅为非空的条件下有界,因而得到算法的全局收敛性.在适当的假设下,证明了算法的局部超线性收敛性.另外将一类二阶锥规划的新光滑函数推广到SCCP中,研究了该类新光滑函数的性质,并基于此光滑函数建立求解单调SCCP的一步光滑牛顿法,分析了算法的适定性以及全局和局部超线性收敛性.对于单调SOCCP,基于一类含参数互补函数的光滑函数,提出了求解SOCCP的一步光滑牛顿法.分析了算法适定性和收敛性,并且通过一个数值矩阵例子,说明光滑牛顿法在求解非单调的P0-SOCCP时,牛顿方程可能会无解.最后,通过数值试验分析了参数对数值效果的影响.对于非单调具有笛卡尔P性质的对称锥线性互补问题（SCLCP）,基于CHKS光滑函数提出一个求解该类非单调SCLCP的光滑牛顿法,分析了在函数P满足Cartesain P0性质时牛顿方程的可解性,证明了迭代点的邻域在函数P满足Cartesain性质时的有界性.从而得到算法的适定性和收敛性.对于非单调具有笛卡尔P0性质的SCLCP,基于CHKS光滑函数提出一个求解该类非单调SCLCP的正则光滑牛顿法,分析了算法适定性和收敛性.另外,基于对称扰动Fischer-Burmeister（FB）光滑函数提出了一个光滑牛顿法,当函数P满足Cartesain P0性质时,证明了牛顿方程的可解性和目标函数的强制性.从而,得到算法所生成点列的有界性.最后分析了算法的适定性和收敛性.基于欧几里德若当代数技术,提出了SCCP的一类新价值函数,在适当条件下讨论了该类价值函数水平集的有界性,并且基于该类价值函数建立了SCCP解的一个全局误差界.这两个性质可以提供算法停止的准则和分析算法收敛性.另外,对于一类已有价值函数,本文提出了比已有条件更弱的条件,在该条件下这些价值函数的水平集有界,且基于这些价值函数建立了SCCP解得全局误差界.

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 对称锥互补问题的来源与背景
• 1.2 欧几里德若当代数
• 1.3 对称锥互补问题的研究进展与现状
• 1.4 光滑化牛顿法的研究进展与现状
• 1.5 本文的主要工作与结构安排
• 第二章 单调对称锥互补问题的光滑牛顿法
• 2.1 光滑函数及其性质
• 2.2 预估校正光滑牛顿法
• 2.3 迭代点的有界性、收敛性分析及极大互补解
• 2.4 一步光滑牛顿法及收敛性分析
• 2.5 数值结果
• 2.6 小结
• 第三章 单调二阶锥互补问题的光滑牛顿法
• 3.1 引言
• 3.2 含参光滑函数及其性质
• 3.3 一步光滑牛顿法
• 3.4 一个重要的例子
• 3.5 收敛性分析
• 3.6 数值结果
• 3.7 小结
• 第四章 非单调对称锥线性互补问题的光滑牛顿法
• 4.1 引言
• 4.2 两类光滑函数及其性质
• 4.3 基于CHKS光滑函数的光滑牛顿法及其收敛性分析
• 4.4 正则光滑牛顿法（RSNA）及其收敛性
• 4.5 基于对称扰动FB光滑函数的光滑牛顿法及其收敛性分析
• 4.6 小结
• 第五章 水平集有界性与全局误差界分析
• 5.1 一类新的价值函数
• 5.2 水平集有界性和全局误差界性质
• 5.3 含参正则价值函数全局误差界的条件
• 5.4 小结
• 结束语
• 致谢
• 参考文献
• 在读博士期间撰写（发表）的论文