题目：稀疏主成分问题的算法研究

  主成分分析（PCA）作为一种数据分析与降维工具被广泛地应用在各个工程领域。但主成分通常是所有原变量的线性组合，很难被解释。稀疏PCA则在主成分模型的基础上添加稀疏性条件，即?1（或?0）约束（或惩罚），增加主成分载荷中的零元素个数，从而使主成分易于解释。
  在应用中，为了有效地得到稀疏主成分，研究者结合稀疏性要求与主成分模型，提出了多种稀疏主成分模型。本文选择含?1罚函数形式与含?1约束形式的稀疏主成分模型作为研究对象。这两类模型的最大特点是都属于非凸规划，且所含的?1范数是非光滑的。
  针对含?1罚函数形式的稀疏PCA模型，本文提出了两种求解方法：梯度−次梯度投影法和非单调梯度法。梯度−次梯度投影法以目标函数中光滑部分的梯度与非光滑部分的次梯度之和为搜索方向，并通过广义Armijo准则得到迭代步长。该算法步骤简单，易于实现，仅就稀疏度与方差而言，对于大规模问题也能求解。非单调梯度法则是来源于Lu和Zhang提出的增广拉格朗日方法，不同的是，非单调梯度法不考虑稀疏主成分间的相关性以及对应载荷向量间的正交性，对稀疏主成分采用单个求解的方式。由于该方法仅相当于求解增广拉格朗日方法中一个子问题，因此降低了算法的复杂性并缩短算法所需的运行时间。非单调梯度法虽然不能保证每个迭代方向都是下降方向，但却能保证目标值在整个迭代过程的下降性，且算法的收敛性是可以证明的。大规模的数值实验表明，当对稀疏主成分间的相关性以及对应载荷向量间的正交性要求不高时，通过调整参数，可以使非单调梯度法得到的稀疏主成分的稀疏度与方差几乎与增广拉格朗日法得到的一样，但非单调梯度法所需的运行时间小于增广拉格朗日法。
  针对含?1约束形式的稀疏PCA模型，为了进一步体现已有的新双正松弛中的互补条件，本文提出了一种称为NEW松弛的半定松弛方法。该方法可以为稀疏PCA问题提供一个上界，且这个上界小于等于已有松弛方法提供的上界。