强次可行方法与序列二次约束二次规划算法的研究

论文摘要

最优化在工程设计、生产管理、交通运输、政府决策等重要领域日益得到广泛的应用,因此更加快速有效的最优化算法成为迫切需求。序列二次规划(SQP)算法是求解非线性约束优化最有效的算法之一,而可行SQP算法又是其中一类重要的算法,因为它能产生可行迭代点序列,故在工程设计和实时控制等方面有着十分重要的实际应用。然而可行SQP算法的较大缺陷就是需要一个可行初始迭代点,而通常计算一个可行点不是一个容易的工作。为此,简金宝教授近年提出了一个强次可行方向法,并成功应用于可行SQP算法。该方法能从任意初始点开始,能保证迭代的可行性单调增加,且一旦迭代点落入可行域即变成可行方向法。然而,强次可行方向法中仍然有一些问题亟待解决,如:能否在理论上保证在经过有限次迭代之后迭代点落入可行域;在理论分析当中一些较强的假设条件能否去掉或者减弱;数值计算量能否进一步减少等。在过去三四十年里SQP方法的研究得到了极大的完善,然而当要求解的问题非线性程度比较高时,如人造卫星轨道问题,SQP方法可能进程较为缓慢,甚至会失败。于是近年来一些学者专门针对该类问题提出了一种有效的方法,称为序列二次约束二次规划(SQCQP)方法。与SQP方法相比,SQCQP方法每步迭代只需求解一个二次约束二次规划(QCQP)子问题,并且在不需要任何方向修正的情况下可以克服Maratos效应,达到超线性收敛性。由于QCQP子问题是原问题的二次近似,因此相对于SQP方法中的二次规划(QP)子问题而言,QCQP子问题对原问题的近似程度要好,从而SQCQP方法预期的数值效果要比SQP方法好。本学位论文首先结合强次可行方向法,SQP方法和SQCQP方法的思想,分别给了一个强次可行SQP算法和一个强次可行SQCQP算法。然后专门针对目前SQCQP方法中存在的缺陷,提出了两个新的SQCQP算法。本论文共分为六章,各章内容简要介绍如下。第一章主要介绍了强次可行方向法的思想,可行SQP方法和SQCQP方法的研究进展,以及QCQP子问题的求解方法。第二章结合强次可行方向法和可行SQP方法的思想,提出了一个新的强次可行SQP算法。通过构造新的修正方向和设计新的Armijio型曲线搜索,提出的算法弥补了传统强次可行SQP算法的多个缺陷。首先能在理论上保证算法经过有限次迭代之后,迭代点落入可行域,之后自动变为可行SQP算法,并由此克服了一个较强的假设条件(即最大约束违背函数是QP子问题解的高阶)。其次,去掉了严格互补条件。最后,由于两个修正方向均由简单的显式产生,而且包含的逆矩阵是一样的,从而极大减少了计算量。算法具备全局和超线性收敛性。初步的数值试验说明该算法是稳定有效的。第三章结合强次可行方向法和可行模松弛SQCQP方法的思想,提出了一个强次可行模松弛SQCQP算法。通过对线搜索和QCQP子问题精心的构造,算法能从任意初始点开始,并保证有限步之后迭代点落入可行域。算法每次迭代只需求解一个凸QCQP子问题,且无需任何修正方向就能得到算法的全局、超线性及拟二次收敛性。数值试验说明算法的数值效果与测试的SQP算法相比有一定的优越性。第四章提出了一个新的罚函数型SQCQP算法。算法引入了一个简单的非单调罚参数调整技术,该技术仅利用QCQP子问题中有界约束的KKT乘子来更新罚参数,因为当把QCQP转化为二阶锥规划求解时,对应于二次约束的乘子往往比较难获取。该技术还允许罚参数在早期迭代减小,从而缓解了因罚参数增大过快而导致罚函数及子问题性态变差的问题。此外,我们利用了工作集技术剔除了QCQP子问题中局部不相关的约束,从而极大地减少了计算量。在不需要假设目标和约束函数为凸的情况下,算法是全局、超线性及二次收敛性的。初步的数值试验表明算法对测试的算例要比SQP方法优越。第五章结合增广Lagrange函数线搜索技术和SQCQP方法的思想,提出了一个增广Lagrange函数型SQCQP算法。算法中构造了一个新型的凸QCQP子问题,该子问题不仅始终有可行解,而且通过应用积极约束集技术避免了那些局部不相关的梯度和(近似)Hesse阵的计算,从而减少了计算量。步长由Armijio型线搜索产生,罚参数允许减小。在适当的假设下,算法不需要任何修正方向就具有全局、超线性及二次收敛性。此外,与以往SQCQP算法不同的是,该算法还能简单地推广到求解混合等式与不等式的一般约束优化,以及推广到非单调线搜索。第六章总结了本文的主要工作,并引出了一些需要进一步研究的问题。最后,值得指出的是,我们对本文中提出的两个SQCQP算法做了比较充分和完整的数值试验,而以往给出的SQCQP算法中,除了一个局部收敛的算法给出了一些初步的数值试验结果(而且当中还是把QCQP子问题当成一个一般的非线性规划问题来求解)外,其余算法都没有做数值试验,其主要原因可能在于QCQP子问题求解上的困难。

论文目录

• 摘要
• Abstract
• 符号说明
• 第一章 绪论
• §1.1 预备知识
• §1.2 强次可行方向法
• 1.2.1.强次可行方向法的思想
• 1.2.2.强次可行SQP方法
• §1.3 SQCQP方法
• 1.3.1.SQCQP方法研究进展
• 1.3.2.QCQP子问题的求解
• 第二章 一个新的强次可行序列二次规划算法
• §2.1 引言
• §2.2 算法及性质
• §2.3 全局收敛性分析
• §2.4 强收敛和超线性收敛性分析
• §2.5 算法的数值试验
• 第三章 强次可行模松弛序列二次约束二次规划算法
• §3.1 引言
• §3.2 算法的描述
• §3.3 全局收敛性分析
• §3.4 强收敛和超线性收敛性分析
• §3.5 算法的数值试验
• 第四章 带简单非单调罚参数的序列二次约束二次规划算法
• §4.1 引言
• §4.2 算法及性质
• §4.3 算法的全局收敛性
• §4.4 算法的强收敛与超线性收敛性
• §4.5 算法的数值试验
• 第五章 增广Lagrange函数型序列二次约束二次规划算法
• §5.1 引言
• §5.2 算法及性质
• §5.3 算法的全局收敛性
• §5.4 算法的超线性和二次收敛性
• §5.5 算法的推广
• 5.5.1.推广到混和等式与不等式约束问题
• 5.5.2.推广到非单调线搜索
• 第六章 结论
• 参考文献
• 作者攻读博士学位期间发表和已投稿的论文
• 致谢