论文部分内容阅读
二次规划是一类重要的优化问题,在运筹学与经济数学中有着广泛的应用.凸二次规划作为其中的一类特例,其等价于一个带线性约束的单调变分不等式问题.在现实生活中,我们经常会碰到此类问题,例如,交通控制以及经济平衡问题等.对于此类问题,学者们已经给出了很多类型的数值算法,例如罚函数法、增广Lagrange乘子法、投影梯度方法和积极集法等.对于大规模凸二次规划问题,投影梯度方法是一类有效的算法,因为其可以迅速改变积极约束集的构成,并且易于程序实现.最近几十年来,人们对投影梯度方法作了大量研究,构造了很多有效的算法.
在文献[??]中的方法的启示下,本文提出了一类求解凸二次规划的自适应投影梯度方法,以尽量减少梯度值的使用并且避免线搜索.该方法采用新的步长选取策略,在每步的迭代中自动调节步长,以使得迭代步长始终保持在一个合理的范围内从而保证较快的收敛速度.该算法具有强收敛性和全局收敛性.在数值实验中,本文分别考虑了无约束凸二次规划和框形约束凸二次规划两种情形,并分别以BB算法和Adaptive BB算法作为比较对象数值结果表明,对于无约束凸二次规划问题,与BB算法相比,该自适应投影梯度方法可以在一个可接受的时间内收敛到最优解.对于框形约柬的凸二次规划问题,与Adaptive BB算法相比,该自适应投影梯度方法在保持较快的收敛速度的同时,避免了线搜索和调用函数值.另外,当问题的Hessian阵H的条件数保持不变而维数增加时,该算法保持了数值稳定性.
本文分为五个部分,第一章,简要介绍了变分不等式的基本形式,本文中将要考虑的问题,以及投影梯度方法的基本特性;第二章,介绍了投影映射的定义、基本性质和求解变分不等式的等价形式;第三章,首先说明了本文中算法的思想来源,然后给出了与算法相关的基本性质并证明了算法的全局收敛性;第四章,通过三个不同的算例来说明文中算法的特点;最后,我们总结全文并提出了一些进一步研究的参考意见.