论文部分内容阅读
许多实际问题可以转化成求解大规模可分凸规划问题。例如,信号处理、图像重建、机器学习和多阶段随机规划问题。许多著名学者,例如陶哲轩,Goldfarb, Candes对此类问题展开了深入的研究。因为此类问题所对应的可分凸规划问题的目标函数含多个算子(通常多于两个),经典的算子分裂方法,例如向前向后,Douglas-Rachford算法不能直接处理此类问题。另一方面,实际问题所需处理的变量维数庞大,采用二阶方法或普适的内点算法软件包SeDuMi或SDPT3都无法应对大型问题的求解需要。因此,我们以设计一阶算法为出发点,为此类问题量身定做有效的分裂算法。通过利用问题的特殊结构以及部分松弛等思想,将高维问题转化成低维子问题求解,以减轻高维带来的困难。在第一章中,我们首先介绍可分凸规划问题,以及设计分裂算法的目的。一些基本的概念,不等式和可分凸规划问题的变分刻画也将在本章给出。第二章详细给出了本文中提出的分裂算法的设计背景,期望解决的问题。主成分分析是一种常用的数据分析工具。当观测数据中哪怕只有一个元素存在巨大错误,经典的主成分分析的模型无法有效恢复出数据主成分。Candes等学者提出了稳健型主成分分析,它的凸松弛模型在一定条件下可以有效恢复出数据的主成分。然而,由于观测条件的限制,或观测成本的制约,当观测数据存在缺失,甚至同时遭受巨大错误和高斯型误差的破坏,面对此情形,我们提出了更加一般的模型。该模型通过等价变形可以转化成目标函数含三个算子的可分凸规划问题。由于目标函数可分,并带有等式约束,考虑基于增广拉格朗日方法的分裂算法是求解大型问题的有效途径。考虑到交替方向法是求解可分凸规划问题的有效方法,它在应用领域已取得了相当广泛的应用。对于求解可分凸规划的经典的交替方向法全局收敛性已经建立。对于多块变量(多于两块),直接推广交替方向法得到的算法我们称为交替分裂增广朗格朗日方法(ASALM)。我们首先采用了此方法求解了推广的稳健型主成分分析模型,数值效果显著,然而它的全局收敛性至今悬而未决。所以,我们进一步提出了一种具有全局收敛性的变化的交替分裂增广拉格朗日方法(VASALM)。由于我们的分裂算法充分利用了问题的特殊结构,所以对于大型问题,我们的方法非常有效和稳健。而且,用我们提出的模型所恢复出的低秩矩阵和稀疏元素都很精确,说明我们提出的模型也非常有效。在第三章中,我们针对目标函数含有m个算子的可分凸规划问题,提出一种新型分裂算法。该方法由于充分利用了每个凸算子的特殊性质,使得每个子问题都具有闭式解。这种分裂算法可以看成第二章中具有全局收敛性的VASALM方法的推广。当m=3,该方法就是VASALMo该方法与现存的一些基于预测校正的分裂算法相比,它的每一步无需校正主变量。我们通过图像恢复和矩阵分解等数值算例验证了该方法的有效性。在第四章中,我们设计了一个具有高斯回代步的交替方向法。该方法是为了直接推广交替方向法求解目标函数含多个可分算子的凸规划问题而产生的,算法框架是新颖的。它隶属于收缩算法的框架,具有全局收敛性。我们通过一些实际应用问题证明了它的数值有效性。