论文部分内容阅读
对于两类问题:鞍点问题和约束优化问题,本文提出了几个简单的一阶算法。这两类问题在诸多领域广泛存在,例如图像恢复、高维统计、动力系统、经济、物理等领域。本文提出的所有算法均基于已有的一阶算法,这些一阶算法包括增广拉格朗日法,交替方向乘子法,临近点算法等。在第一章中,我们简单介绍了鞍点问题和约束优化问题已有的相关算法,以及研究这些问题的动机。在第二章中,我们介绍了一些重要的基本概念,例如凸函数、单调算子、投影以及变分不等式,同时也介绍了它们之间的一些相互关系。接下来是本文的主体部分,本文主体部分由两部分构成。第一部分包括第三章和第四章,主要讨论了鞍点问题及其相关算法。对于鞍点问题,原始对偶混合梯度算法是当今流行的一类求解算法,尤其是求解一些基本图像处理模型;然而在现有文献中,该算法仅在一些严格的步长条件下才能证明其收敛性。在第三章,就鞍点问题,我们重新考虑原始对偶混合梯度法的收敛性,并试着更好的理解如何选择步长。具体来说,我们先用一个极端简单的例子来说明当步长固定时,原始对偶混合梯度算法可能不收敛;接下来,我们将证明当鞍点问题中的一个函数是强凸时,固定步长的原始对偶混合梯度法是收敛的;实际上图像处理中的很多鞍点问题都能满足强凸条件。本章还证明了当步长取为常数时,该方法在最坏情况下的收敛速率。如果鞍点问题不满足强凸条件但其中一个问题是线性函数时,我们在第四章中进一步设计了一类基于临近点算法和收缩方法的有效算法。数值试验表明这个新算法对于一些实际问题是有效的。由第五章和第六章构成的第二部分致力于针对结构型约束优化的分解算法。通过拉格朗日乘子理论,虽然许多结构优化问题可以被转化为等价的鞍点问题,但如果机械套用第一部分的算法将忽略目标函数的结构,这可能会导致子问题难以求解,数值效果不好。增广拉格朗日法[7]是一类求解约束优化问题的经典算法。在这一部分,我们考虑如何改进增广拉格朗日算法来求解具有特殊结构的优化问题,并且尝试得到一些理论结果。在第五章,我们考虑三块的线性约束凸优化问题,在比文献[46]条件弱的前提下,我们第一个证明了三块的交替方向乘子法的收敛性。此外,为了加速三块的交替方向乘子法,我们提出了一个放松的交替方向乘子法,该方法需要额外计算最优步长,并且在宽松的条件下证明了它的全局收敛性。在第六章,我们考虑带有正交约束的l1-正则化优化问题。因为该问题目标函数含有非凸非光滑项且约束为正交约束,所以很难求解。基于增广拉格朗日法[2]和交替临近点法[5],我们提出了一类求解带有正交约束的l1-正则化优化问题的算法,并且证明了该方法的子序列收敛性质。