拉格朗日正则化方法与线性规划原-对偶算法的研究

摘要

该论文主要对拉格朗日正则化方法和线性规划原-对偶算法进行了研究,其中,前者是一种特殊的光滑化方法,为该文线性规划原-对偶内点和非内点算法的建立提供了基础.极大熵方法是解有限极大极小问题的一种有效光滑化法,它通过在极大极小问题的拉格朗日函数上引进Shannon信息熵作正则项,给出一致逼近极大值函数的光滑函数.因该函数所具有的优良性质,使其在求解各类优化问题中得到了广泛的应用.该文从两个方面发展了这种熵正则化方法,即将其从极大极小问题推广到一般不等式约束优化问题上和用一般函数代替熵函数作正则项,建立新的正则化方法.该文上篇共含四章,主要进行拉格朗日正则化法的研究.第一章为绪论,简单描述了熵正则化方法与罚函数法的研究现状;第二章,针对有限极大极小问题,通过研究熵正则化方法与指数(乘子)罚函数方法之间的关系,揭示熵正则方法的数学本质;第三章将极大熵方法推广到一般不等式约束优化问题上,建立了拉格朗日正则化方法;第四章利用第三章建立的拉格朗日正则化方法,给出一种构造罚函数的统一框架,并通过具体的罚和障碍函数例子加以说明.下篇由后四章组成.第五章简单回顾了线性规划及内点法,并重点介绍了原-对偶路径跟踪内点算法.第六章研究了对标准中心化方程实施代数等价变换的作用,并特别就对数变换情形,建立一个不可行大步原-对偶路径跟踪内点算法,同时给出其收敛性及复杂性界限分析.第七章,通过构造一个新的邻近度量函数,提出一个具有自调节功能的原-对偶路径跟踪内点算法,并将其与线性规划软件LIPSOL和彭等人的McIPM进行数值比较,证实了该算法的有效性;第八章,基于NCP函数及其光滑函数,建立求解线性规划的非内点原-对偶路径跟踪算法,并给出相应的全局及局部收敛性分析.

目录

文摘

英文文摘

符号说明

上篇拉格朗日正则化方法

第一章绪论

§1.1熵正则化方法

§1.2罚函数方法

§1.3本文的主要工作

§1.4预备知识

第二章有限极大极小问题的熵正则化方法

§2.1引言

§2.2极大熵方法的一致逼近光滑作用

§2.3熵正则化方法与指数(乘子)罚函数方法的关系

§2.4极大熵方法与BEN TAL等人的光滑化法的关系

§2.5熵正则化方法中的几个问题

§2.6小结

第三章约束优化问题的拉格朗日正则化方法

§3.1引言

§3.2约束优化问题的熵正则化方法

§3.3拉格朗日正则化方法

§3.4拉格朗日正则化方法的收敛性分析

§3.5凸规划的拉格朗日正则化与非线性扰动

§3.6小结

第四章构造罚函数的统一框架

§4.1引言

§4.2构造罚函数的统一框架

§4.3构造罚函数的具体实例

§4.4小结

下篇线性规划的原-对偶路径跟踪算法

第五章绪论

§5.1线性规划内点法的概述

§5.2原-对偶路径跟踪内点法

§5.3本文的主要工作

第六章基于代数等价变换的原-对偶路径跟踪算法

§6.1引言

§6.2 SELF-REGULAR邻近度量法的分析

§6.3等价代数变换与相应的邻近度量和搜索方向

§6.4基于对数变换的不可行原-对偶路径跟踪内点算法

§6.5小结

第七章自调节的原-对偶路径跟踪内点法

§7.1引言

§7.2一个新的邻近性度量函数

§7.3一个具有自调节功能的原-对偶路径跟踪内点算法

§7.4算法的实施与数值比较

§7.5小结

第八章基于NCP函数的非内点原-对偶路径跟踪法

§8.1引言

§8.2非内点原-对偶法的基本思想

§8.3基于方程组(8.10)的非内点原-对偶路径跟踪算法

§8.4基于方程(8.11)的非内点原-对偶路径跟踪算法

§8.5算法的实施与数值比较

§8.6小结

第九章总结与展望

参考文献

博士期间发表论文情况

论文的创新点摘要

致谢