BFGS方法及其在求解约束优化问题中的应用

论文摘要

本文研究求解无约束非凸问题的BFGS方法以及求解非线性约束问题的序列二次规划（SQP）方法，既约Hessian SQP方法，序列二次约束二次规划（SQCQP）方法．我们首先在第1章简单介绍将要研究的问题的背景和已有结果．在第2章，我们研究BFGS方法在求解无约束非凸问题时的收敛问题．众所周知，BFGS方法是求解无约束优化问题的拟牛顿法中最有效的方法之一，它具有很好的数值效果及快速的收敛性，然而采用精确线性搜索或非精确的Wolfe型线性搜索或Armijo线性搜索的BFGS方法在求解非凸函数的极小化问题时并不一定全局收敛．本文通过在拟牛顿方程中使用扰动策略提出了一种扰动BFGS方法．我们证明采用Wolfe型非精确线性搜索扰动BFGS方法求解非凸函数的极小化问题具有全局收敛性并且具有局部超线性收敛速度，而且保持BFGS方法的仿射不变性．我们的数值实验表明扰动BFGS方法比BFGS方法及修正BFGS方法具有更好的数值效果．BFGS方法中的校正公式经常被其它优化方法所使用并被用来求解非线性方程组，约束优化问题，随机规划问题以及半无限规划问题等。我们在第3-5章里研究通过BFGS校正公式分别与SQP方法，既约Hessian SQP方法，SQCQP方法等的结合来求解一般的约束优化问题．在第3章，我们研究SQP方法在较弱条件下的收敛问题．已有的关于SQP算法的全局收敛性研究结果通常要求拟牛顿矩阵序列一致正定和有界，然而是否存在满足该条件的拟牛顿法尚不清楚．利用扰动技术与BFGS校正技术的有效结合，我们提出了一种扰动SQP方法，并证明所提出的扰动SQP方法在较弱的约束品性下保持全局收敛性，特别地，全局收敛性不要求拟牛顿矩阵的一致正定性和有界性．此外，我们也研究了没有使用扰动技术的SQP方法的全局收敛问题，提出了确保SQP方法收敛的若干策略，其中包括一个新的拟牛顿矩阵校正公式和一个关于罚参数的有效校正准则．数值实验表明这些策略的使用使SQP方法具有更好的数值效果．SQP方法通常被用来求解中小规模的约束问题，因此，我们在第4章研究求解较大规模问题的既约Hessian SQP方法．已有的既约Hessian SQP方法通常只能求解等式约束问题，而且它们的全局收敛分析要求约束函数的梯度向量是线性无关的以及拉格朗日函数的既约Hessian矩阵序列是一致正定的．使用前一条件的主要原因在于已有的拟牛顿校正公式只能产生具有固定阶的拟牛顿矩阵序列，而同时这种校正公式对既约Hessian SQP方法的全局收敛性起着重要的作用．因此，我们提出了一个产生的拟牛顿矩阵的阶可变化的校正公式，然后在此基础上，我们提出了求解一般等式约束问题（可以是退化问题）的修正既约Hessian SQp方法，并且在没有假定上述两个条件的情形下，我们证明修正既约Hessian SQP方法是全局收敛的．而且将这种方法推广然后用来求解不等式约束问题并获得了全局收敛性结果，该方法的优点是可以求解既有等式约束又有不等式约束的较大规模问题，有效克服了已有的这类方法在求解含不等式约束问题时所遇到的困难与限制．在第5章，我们研究求解不等式约束问题的序列二次约束二次规划（SQCQP）方法．众所周知，传统的SQP方法通常会产生Maratos效应，阻碍了算法的快速收敛性．近年来，许多学者提出了使用约束函数的一阶和二阶信息的SQCQP方法，这类方法能有效地避免Maratos效应因而具有较快的收敛速度．然而已提出的SQCQP方法存在某些局限性，要么算法的全局收敛性条件太强，要么算法的全局收敛性没有保证，要么只能求解凸规划问题或约束函数是凸函数的问题．利用扰动技术或BFGS校正技术，我们提出两个求解一般不等约束问题的SQCQP方法，并证明它们在较弱的条件下仍然全局收敛，而且具有至少超线性收敛速度．在第6章，我们针对前面各章提出的算法进行数值实验，数值结果表明所提出的算法比已有的同类算法更有效，有效地支持了本文的算法．

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 预备知识
• 1.2 研究背景及进展
• 1.3 本文的主要工作与创新点
• 1.4 符号表
• 第2章 求解无约束问题的扰动BFGS方法
• 2.1 扰动策略与方法描述
• 2.2 全局收敛性分析
• 2.3 局部超线性收敛性分析
• 第3章 求解非线性约束问题的SQP方法
• 3.1 求解等式约束问题的扰动SQP方法
• 3.2 SQP方法的全局收敛策路
• 第4章 求解非线性约束问题的既约Hessian SQP方法
• 4.1 求解等式约束问题的修正既约Hessian SQP方法
• 4.2 求解退化等式约束问题的既约Hessian SQP方法
• 4.3 求解不等式约束问题的既约Hessian SQP方法
• 第5章 求解非线性不等式约束问题的SQCQP方法
• 5.1 修正的SQCQP方法
• 5.2 使用BFGS校正公式的SQCQP方法
• 第6章 数值实验
• 6.1 算法2.1的数值实验结果及分析
• 6.2 算法3.1的数值实验结果及分析
• 6.3 算法3.2的数值实验结果及分析
• 6.4 算法4.1的数值实验结果及分析
• 6.5 算法4.2的数值实验结果及分析
• 结论
• 参考文献
• 附录A（攻读学位期间所发表和已完成的学术论文目录）
• 致谢