论文部分内容阅读
在实际生活中,有许多问题可以用变分不等式来刻画,包括凸优化问题,鞍点问题,互补问题,经济平衡问题,交通规划等.目前,已有一系列的求解变分不等式问题的方法,如交替方向法、临近点算法、投影收缩算法、牛顿法和内点法等.这些方法在信息工程、经济管理等诸多领域有着广泛应用.近年来,最优化领域的一个研究热点是解决一类有特殊结构,规模大的问题,这类问题大量存在于计算机科学、信息学、统计学、金融学等学科中,如压缩感应、图像处理、机器学习等问题.本文主要针对一些有结构的大规模的问题,基于变分不等式理论设计一些一阶算法,并对其中的一些算法给出复杂性证明.在第一章和第二章中,我们回顾了变分不等式的源问题,如,凸优化问题,有可分结构的带线性约束的凸优化问题,鞍点问题,互补问题,给出了解变分不等式的几个重要的算法和几个应用问题,以及复杂性分析中用到的(?)最优解的定义.并给出后面的讨论所需用的投影的性质,几个重要不等式,定义和记号,以及基本概念.交替方向法是一类求解有可分结构凸优化问题的有效方法,它在应用领域已取得了相当的认可.经典的交替方向法是针对凸优化问题的目标函数为两个变量的情形.临近点算法通过在凸优化问题的目标函数中加入临近点项,使得凸优化问题的条件理论上变好,有很好的收敛性结果,然而经典的临近点算法并不容易实现.在第三章中我们给出一种定制的临近点算法,即在原始问题中加上临近点项,如果取特殊的参数,在求解子问题的时候就成为了交替方向法,这样它具有临近点算法的优点,即有收敛性质,实现时,又可以通过交替方向法来实现.同时,对这个算法我们给出了复杂性分析,说明这个算法具有O(1/t)的收敛速率.在图像处理中,有些问题可以转化成求解鞍点问题.在第四章中,我们考虑了解这类问题的一种原始对偶算法.在原有的算法的基础上,我们放松了参数的选取范围,构造了新的下降方向,我们给出了收敛性结果,同时数值例子表明,经改进后的算法,有更好的表现.对于单调的Lipschitz连续的变分不等式,外梯度方法是一个简单,有效的方法,且由于它的格式简单,外梯度方法在很多实际问题中得到广泛的应用.投影收缩法跟外梯度方法类似,每次迭代分预测步和校正步,主要的区别是在两步的计算中,外梯度方法使用同样的步长,而投影梯度法允许步长选择不同的参数,所以投影梯度法一般都比外梯度方法的数值结果来得好.2005年,Nemirovski给出了外梯度方法的复杂性分析,证明了外梯度方法具有O(1/t)的收敛速率,本文给出了投影梯度法的复杂性分析,说明投影梯度法也有O(1/t)的收敛速率,同时,通过分析,发现在校正步中可以步长因子进一步松弛,获得更好的收敛速率.