正交约束优化问题的非光滑算法

This project is devoted to the nonsmooth algorithms for optimal problems with orthogonality constraints and constrained optimal problems with orthogonality constraints. Optimal problems with orthogonality constraints has many important applications in fields such as data science, statisticas, molecular simulation and electronic structures computations. Now some results on unconstrained smooth problems over orthogonality constraints has been established well. Since in real applictions the objective function is always nonsmooth and constrained, it is necessary to study nonsmooth constrained problems on manifolds. One goal of this project is to generalize the theory and algorithm of (1)trust region method (2) bundle method (3) subgradient method to optimal problems with orthogonality constraints. Because real world models such as sparse principal components analysis and sparse linear discriminant analysis always have nonsmooth objective functions, we will apply these methods to such models. Another goal of this project is to study the constrained optimal problems with orthogonality constraints. Since trust region methods is the best algorithms for smooth problems on manifolds and constrained trust region methods on Euclidean space also exists, we will generalize these methods to optimal problems to problems with orthogonality constraints.

本项目主要研究正交约束优化问题的非光滑算法和有约束的正交约束优化问题。正交约束优化问题在数据科学、统计学、分子模拟、电子结构计算等领域上有着重要应用。目前，信赖域算法在正交约束问题的无约束光滑问题计算效果非常良好。但是因为很多实际应用问题都是非光滑的并且带有约束，研究非光滑算法和约束流形优化问题成为必需。本项目的一个研究目标是非光滑算法，本项目将以欧式空间的(1)信赖域算法(2)束方法(3)次梯度算法为基础，把这些欧式空间的理论和算法推广到正交流约束优化问题的非光滑算法。因为稀疏主成分分析和稀疏线性判别分析等统计模型都是非光滑的，本项目还要将这些算法应用到这些模型中。另一个研究目标是研究有约束的正交约束优化问题。鉴于信赖域方法目前是无约束光滑流形优化问题中计算效果最好的，同时欧式空间带约束的信赖域方法已经存在，本项目致力于把欧式空间带约束的信赖域方法推广到正交约束优化问题。

目前流形优化的研究是国内外优化工作者研究的热点之一。本项目主要研究正交约束这种特殊的流形上的优化问题，给出正交流形上的光滑问题与非光滑问题的快速算法和收敛性的理论分析。本项目同时也研究一般性的黎曼流形上的算法和理论分析。. 本项目得到的主要成果包括以下几个方面：1. 特殊正交约束流形上的理论与算法，其中包括信赖域问题、多个球面约束问题、Stiefel 流形上的迹商求和问题与线性相应问题。信赖域子问题是球面上的二次规划，球面约束是最经典的正交流形。对于信赖域问题的 Lanczos 算法，我们给出了理论分析，根据分析给出一个新的终止条件，在此条件下，信赖域算法的收敛速度得到很大提升。对于多个球面的约束，我们给出了一个滤子积极集算法，在一定条件下证明了算法的超线性收敛性。数值实验表明，这个算法是一个高效稳定的算法。对于Stiefel 流形上的迹商求和问题，我们给出了一个自适应迭代格式，并且证明了算法的收敛性。数值实验表明，这个目前迹商求和问题的速度最快的算法。线性响应问题在分子结构计算这个方向有着重要的应用，我们给出了这个问题子空间算法的一个Ritz 值逼近结果。2. 一般性黎曼流形上的非光滑优化理论分析与子空间算法。对于一般性的黎曼流形，我们给出了非光滑优化问题的最优性条件。在另一篇论文中，我们给出了一个黎曼流形上的有限内存秩1信赖域子空间算法。3.对于大型二阶锥互补问题，我们证明了矩阵分裂算法的线性收敛。数值实验表明，我们的矩阵分裂算法是目前速度最快的算法。如果问题是大型稀疏的，我们给出了Krylov 子空间算法，这个算法进而对一般的非线性优化问题的Krylov 子空间算法，都有一定的启发。我们还对拟凸二阶锥互补问题的解集，进行分析并给出了一些有趣的结果。4. 对一类凸优化问题，我们证明了 ADMM 的线性收敛。这类凸优化问题包括了分片二次规划、稀疏二次规划等一系列问题。