大规模稀疏优化问题的理论与算法

Many urgent large-scale optimization problems emerge prominently with the rapid development of modern science and technology, social economy and national defense. Sparsity is an intrinsic, yet important feature with rich mathematical theory in large-scale optimization. This project aims to study the theory and algorithms for large-scale optimization with sparsity features in three aspects: (i) the investigation of the optimality conditions, stability and sensitivity, duality theory, relaxation and approximation theory, and computational complexity for sparse nonlinear optimization with general constraints, and low rank semidefinite matrix and tensor optimization problems; (2) the design of a few globally convergent, stable and efficient optimization algorithms for these models; (3) their applications in some large-scale practical problems, such as 3D color face recognition, imaging and image analysis, network localization and financial risk management, and the development of practical and efficient mathematical software. This project is scientific significant and extremely valuable, not only for providing new theory and methods for large-scale sparse optimization, but also for offering new elements and opportunities for the cross and integration of optimization, information science, data science and computing technology.

随着现代科学技术、社会经济和军事国防的快速发展，涌现出大量迫切需要解决的大规模最优化问题。稀疏性是大规模最优化问题中一个自然而又重要的特征，蕴涵着丰富的数学理论。本项目旨在开展具有稀疏特征的大规模优化理论与算法研究，主要内容包括：（1）针对一般约束条件下稀疏非线性优化、低秩半定矩阵优化和低秩半定张量优化模型，研究其最优性条件、稳定性、对偶理论、松弛或者光滑逼近理论、计算复杂性理论；（2）设计求解这些模型的几类优化算法，使之具有全局收敛性、稳定性、快速性；（3）对新算法进行数值实验并将其应用在3D彩色人脸识别、成像与图像分析、网络定位分析、金融风险管理等实际问题中，编制实用有效的数值软件。该项目的实施不仅能为求解大规模稀疏最优化问题提供新理论和新方法，而且也可为最优化、信息科学、数据科学、计算机科学技术的交叉融合提供新元素，具有重要的科学意义和实用价值。

随着现代科学技术、社会经济和军事国防的快速发展，涌现出大量迫切需要解决的大规模最优化问题。稀疏性是大规模最优化问题中一个自然而又重要的特征，蕴涵着丰富的数学理论。本项目旨在开展大规模稀疏优化理论与算法研究，获得如下三个方面的结果：（i）在稀疏优化（L0）理论方面，我们建立了L0最优变量选择理论、一阶和二阶最优性条件、对偶理论，并给出L0正则与L0约束优化之间关系特征，以及低秩优化一阶和二阶最优性条件；（ii）在稀疏优化算法方面，设计出多个具有公开代码的新算法，如H-ADMM、HFPA、IIHT、NHTP, 特别是H-ADMM，不仅发展/建立了两块、三块、多块ADMM算法，而且证明了收敛性、线性收敛速率、计算复杂性，增强了ADMM实用功能，丰富了ADMM算法理论；（iii）在应用软件方面，我们把稀疏低秩优化理论和算法应用到机器学习等实际问题中，开发出多个求解器，如多维标度降维优化器（SQREDM）、逻辑回归分类优化器（L0-GPGN）、支持向量机分类优化器(L0/1-ADMM)。这些结果不仅为求解大规模稀疏优化问题提供了新理论和新方法，而且也为最优化、信息科学、数据科学、计算机科学技术的交叉融合提供了新元素，具有重要的科学意义和实用价值。