非线性优化问题的罚函数算法和拟Newton算法

最优化可以追溯到求解极值问题。它最初是求解某些数学问题的最优解,即从众多的方案中选出最优方案。上世纪40年代末,最优化理论和方法成为一门独立的学科。自从Dantzig在1947年提出求解线性规划问题的单纯形算法之后,求解非线性规划、随机规划、多目标规划、半定规划等多种最优化问题的理论研究得到长足发展,新方法不断涌现。 最优化方法中,解决约束非线性规划问题的一种思路是化成无约束非线性规划问题,最常用的两种方法是罚函数方法和拉格朗日乘子方法。由于罚函数的精确性和可微性难于同时满足。因此本文针对传统罚函数的结构改进,将优化函数化为既精确又光滑的函数类型。同时得到了相关理论,提出一种含参数的罚函数算法,并对算法进行数值实验,结果显示算法效果明显提高。 拟Newton法是求解非线性无约束优化问题的最有效、理论上也是最成熟的算法之一。在拟Newton方法中,拟Newton方程的结构起着至关重要的作用。最初的拟Newton方程仅仅利用了目标函数的一阶导数信息,而忽略了目标函数值信息。因此,很多人对拟Newton方程进行了研究,并取得了较好的成果。所以基于修正拟Newton方程成为拟Newton算法发展的一个研究热点。本文提出两种非单调线性搜索技术,修正得到三类拟Newton方法,同时证明了全局收敛性,且对算法进行了数值实验,结果表明数值效果较好。 本文结构安排如下: 第一章绪论首先介绍最优化的基本知识和非单调线性搜索技术,随后介绍精确罚函数研究和发展现状、拟Newton法的理论和研究现状,最后给出本文的研究成果。 第二章提出一种新的含参数精确罚函数算法,并在前人研究基础之上给出新的精确罚定理,一方面在理论上研究精确罚函数的近似精确性,另一方面进行数值实验来验证方法的可行性。 第三章提出一种无约束优化问题的对角稀疏拟Newton算法,采用了新的非单调线性搜索技术,在每次迭代中利用对角矩阵近似校正矩阵,使得每次的存储量和工作量大为减少。并对拟Newton方程进行了校正,利用更多的目标函数信息。在一般假设条件下,证明了算法的全局收敛性和超线性收敛性。数值实验表明了算法的可行性。 第四章提出一种非单调的线性搜索技术和修正的拟Newton方法,并证明了该算法在此线性搜索下对非凸极小化问题的全局收敛性,建立了算法的全局收敛性定理,数值结果表明,采用非单调搜索技术的拟Newton方法比原有单调的拟Newton方法的数值效果明显要好。 第五章基于李董辉和Fukushima提出的修正BFGS公式,提出一种修正的有限记忆拟Newton算法,证明了该算法在解决大规模极小化问题具有全局收敛性。进行数值实验验证算法的有效性,比标准有限记忆BFGS算法更优越。