导　　师： 李兴斯

学科专业： G0105

授予学位： 博士

作　　者： ;

机构地区： 大连理工大学

摘　　要： 该文主要研究求解互补问题的有效算法.从20世纪60年代互补问题的提出到现在,尤其是最近20多年来,互补问题发展非常迅速.并且出现了各种形式的互补问题.互补问题被广泛地应用于工程、经济和运筹学中.对互补问题的研究可以分为理论和算法.前者主要研究问题解的存在性、唯一性、稳定性以及灵敏度分析等性质.后者集中研究如何构造有效算法及其理论分析.该文旨在有效算法方面的研究.第一章概述了互补问题的各种形式及其在工程、经济和运筹学中的应用,同时分类介绍了求解互补问题的几种主要算法,并将作者的工作穿插在相关算法里做了简要介绍.第二章首先介绍了信息论中的熵、最大熵原理、最小叉熵原理.然后针对带不等式约束的非线性规划问题,给出一个lagrange正则化(摄动)方法,该方法有效地克服了线性lagrange函数难于在对偶变量空间直接求解的困难.文中分别以shannon熵函数和kullback叉熵函数作为摄动函数,导出其对偶函数分别是原问题的指数罚函数和指数乘子罚函数.这样就在lagrange摄动和指数罚函数之间搭起了一座桥梁.然后文中把这种方法应用到有限维极大极小问题的一个等价非线性规划问题,得到了相应的光滑函数,且与用最大熵原则和最小叉熵原则得到的凝聚函数相同.由于求解线性互补问题的内点法可以看作是线性规划原-对偶内点法的一个自然推广,在第三章开头首先介绍了内点法.然后,基于极大极小问题的均衡作用,构造了一个新的效益函数(势函数),并以其梯度为零代替一般内点法中的互补条件方程.基于这组方程,文中建立了一个求解线性互补的不可行内点算法,并分析了它的多项式复杂度.数值结果表明参数起到了自调整作用.第四章细化了chen-xiu求解线性互补问题的一步非内点延拓算法,并且推广到非线性互补问题.得到了与chen-xiu同样的全局线性收敛,推广了chen-xiu的局部超线性收敛到局部二次收敛.在一定意义下,光滑化函数是延拓算法的核心.该章尝试用叉熵函数来光滑化极小化ncp函数.建立了一个求解单调线性互补问题的非内点延拓算法.其数值结果非常好,部分的好于文中提到的不可行路径跟踪算法.基于非线性互补问题的一个等价不动点格式,第五章分别用shannon熵函数和kullback熵函数光滑化max函数.文中分别给出了两个迭代算法,并与paul tseng的外梯度投影法进行了数值比较.第七章通过计算验证了文中提出的几个算法.首先,对文中提出的不可行路经跟踪算法3.3、算法6.1与zhang yin的不可行路经跟踪算法进行了数值比较.其次,给出了第四章中用kullback叉熵光滑化ncp函数的一个非内点延拓算法4.2的数值结果.最后,对基于shannon熵光滑化和kullback叉熵光滑化的迭代算法与paul tseng的外梯度法进行了数值比较.最后,作者总结了全文,并对下一步的研究工作做了展望.

关 键 词： 互补问题 内点法 延拓算法 中心路径 代数等价路径 光滑化 熵 叉熵 最大熵原理 最小叉熵原理

分 类 号： [O221.2]

领　　域： [理学] [理学]