非线性规划中的罚函数及填充函数方法

摘要

最优化理论和方法的出现可以追溯到十分古老的极值问题，然而，它成为一门独立的学科还是在上世纪40年代末．Dantzing在1947年提出求解一般线性规划问题的单纯形算法之后，随着工业革命、信息革命的不断深化，以及计算机技术的巨大发展，至今短短的几十年，它得到了迅猛的发展．现在，解线性规划、非线性规划以及随机规划、非光滑规划、多目标规划、几何规划、整数规划等各种最优化问题的理论研究发展迅速，新方法不断涌现，在经济、军事、科学技术等方面得到了广泛的应用，成为一门十分活跃的学科． 约束非线性规划问题广泛见于工程、国防、经济等许多重要领域．求解约束非线性规划问题的主要方法之一是把它化成无约束非线性规划问题，而罚函数方法和拉格朗日对偶方法是将约束规划问题无约束化的两种主要方法．罚函数方法通过求解一个或多个罚问题来得到约束规划问题的解，如果当罚参数充分大时，求单个罚问题的极小点是原约束规划问题的极小点，则称此罚问题中的罚函数为精确罚函数，否则称为序列罚函数．针对传统罚函数的定义而言，若罚函数是简单的、光滑的，则它一定是不精确的；若罚函数是简单的、精确的，则它一定是不光滑的；若罚函数是精确的、光滑的，则它一定是复杂的．因此我们的工作是对传统罚函数进行了改造，主要是引入了指数型罚函数和对数型罚函数，并在改造后的罚函数中增添了乘子参数，使之成为既是简单的、光滑的，又是精确的结果．我们把这类罚函数称为简单光滑乘子精确罚函数．所谓简单的，即罚函数中包含原问题中的目标函数和约束函数而不包含它们的梯度，若罚函数中包含有原问题中目标函数和约束函数的梯度，则称为是复杂的． 全局最优化是最优化一个重要分支．全局最优化算法，从算法的构造上大体可以分为确定型算法和随机型算法，例如，填充函数法、打洞函数法属于确定型算法；模拟退火法、遗传算法属于随机型算法．我们在这篇文章中也考虑非线性规划的全局最优化确定型算法．这篇文章的另一个主要目的就是，在研究己有确定型算法的基础上，尝试提出一些改进和创新，力图在算法效果方面有所提高，在理论方面有所深化．其详细内容如下： 本论文共五章：在第一章中，简要介绍了目前国内外关于罚函数、精确罚函数、乘子精确罚函数的研究工作；第二章提出一种带有指数、对数性质的乘子罚函数，并进行了一定的数值试验，取得了较好的计算效果；第三章介绍一种光滑的近似精确罚函数，从理论上证明它的近似精确性，为进一步研究打下了基础；第四章介绍了一种全局精确罚函数，在一定的假设下该函数具有全局的精确性；在第五章介绍了常见的填充函数法及给出一个新的填充修正打洞函数算法．对于一般无约束全局最优化问题，给出一个填充修正打洞函数的定义，它不同于传统的填充函数定义．在此基础上，提出了一个填充修正打洞函数和相应的算法，该算法降低了对参数的依赖，具有较好的可操作性．数值试验显示，该算法是有效和可靠的．

目录

文摘

英文文摘

声明

第一章基础知识及相关结论

§1.1基础知识

§1.2罚函数方法

§1.3精确罚函数方法

§1.4乘子精确罚函数方法

第二章乘子精确罚函数法

§2.1引言

§2.2主要结论

§2.3乘子λ*i的估计

§2.4算法及数值试验

第三章一类光滑的近似精确罚函数

§3.1引言

§3.2主要结果

§3.3算法及数值试验

第四章有约束极小化的另一全局近似精确光滑罚函数

§4.1引言

§4.2主要结果

§4.3算法及数值试验

第五章求全局最优化的填充修正打洞函数法

§5.1全局最优化的基础知识

§5.2填充函数法和打洞算法

§5.3填充函数法和修正打洞函数法的统一途径

§5.4算法和数值试验

§5.4.1数值试验中的搜索方向

§5.4.2算法FMTM

§5.5数值试验

§5.6结论

参考文献

作者攻读博士学位期间发表的论文

致谢