研究工作_Code

复合函数优化算法与理论

半光滑牛顿算法

复合凸优化问题是稀疏优化，低秩矩阵恢复，信号和图像处理，机器学习，数据分析中最常见的模型形式之一，涵盖光滑和非光滑问题，无约束和约束优化问题。近年来人们发展了大量的一阶最优化方法，这些算法的特点是简单容易实现，但一定迭代步数之后收敛有可能变得显著缓慢甚至停滞。观察到近似点梯度算法实际上定义了某种不动点迭代映射，从求解一阶算法对应的单个非线性方程组的角度，我们系统发展了自适应半光滑牛顿算法。虽然这些方程组是不可微的，但它们是半光滑的。由于相应算子的单调性，雅可比矩阵是半正定的。我们证明了算法收敛到全局最优解的性质，分析了局部快速收敛性。该算法能有效求解大规模半定规划问题，在最优控制，电子工程，机械设计等很多学科中有广泛的应用。由于半正定约束具有很强的非线性，这类凸规划问题即使在矩阵维数仅是几千的时候也非常难解。算法软件包SSNSDP实现了MATLAB和C语言版本，根据迭代情况在一阶算法ADMM/DRS和半光滑牛顿法之间自适应切换，在很多测试问题上表现优异。

相关论文：

Xiao Xiantao, Li Yongfeng, Wen Zaiwen, Zhang Liwei; A Regularized Semi-Smooth Newton Method with Projection Steps for Composite Convex Programs; Journal of Scientific Computing; 2018, Vol 76, No. 1, pp 364-389

Li Yongfeng, Wen Zaiwen, Yang Chao, Yuan Yaxiang; A Semi-smooth Newton Method For semidefinite programs and its applications in electronic structure calculations; SIAM Journal on Scientific Computing; Vol 40, No. 6, 2018, A4131–A4157

Chen Ziang, Andre Milzarek, Wen Zaiwen; A Trust-Region Method For Nonsmooth Nonconvex Optimization, arXiv: 2002.08513

Wen Zaiwen, Donald Goldfarb, Yin Wotao; Alternating Direction Augmented Lagrangian Methods for semidefinite programming; Mathematical Programming Computation; 2 (2010) 203-230.

随机半光滑牛顿/拟牛顿算法

机器学习及深度学习中的很多优化问题的目标函数经常是随机变量的期望或者很多相似函数的和形式, 可能还包含非光滑正则化项。尽管随机梯度型算法在很多机器学习任务中能很好的完成任务，但是很多应用中存在收敛速度慢的缺点，利用二阶信息是一种加速梯度算法的常用手段。结合半光滑牛顿法和近似点梯度法，对光滑函数部分的梯度和海瑟矩阵进行抽样，我们首次发展了非光滑优化的随机半光滑牛顿法，设计了测试牛顿步是否接受的全局策略，从而保证了算法的全局收敛性；证明了当迭代点靠近最优点时，牛顿步总能被接受，以很高概率具有R-线性或R-超线性收敛速度。该算法和分析也被推广到随机拟牛顿法，在目标函数项数和变量数量同时达到千万级别的问题上，结合坐标下降策略，能有效提高随机梯度算法的效率，降低高阶算法的迭代复杂度并且提升收敛速度。

相关论文：

Andre Milzarek, Xiao Xiantao, Cen Sicong, Wen Zaiwen, Michael Ulbrich; A stochastic semi-smooth Newton method for nonsmooth nonconvex optimization, SIAM Journal on Optimization, Vol 29, No. 4, pp. 2916–2948, 2019

Yang Minghan, Andre Milzarek, Wen Zaiwen, Zhang Tong; A Stochastic Extra-Step Quasi-Newton Method for Nonsmooth Nonconvex Optimization, arXiv: 1910.09373

深度学习拟牛顿算法

深度学习近年来革命性的技术突破，给很多应用场景带来了巨大的性能提升，比如计算机视觉、自然语言处理、自动驾驶等。深度学习所依赖的神经网络结构由许多类似的结构层叠加而成，其参数量巨大并且神经网络所表示的函数高度非凸。因此，求解一个神经网络所产生的优化问题需要大量的计算，常用的优化方法是随机一阶算法，训练一个超大型的神经网络甚至需要耗费几周或更长的时间。高昂的计算代价成为了深度学习技术推广发展的一个瓶颈，如何降低训练成本及训练时间，成为人们非常关注的问题。深度学习的二阶优化算法结合一阶和二阶模型和算法信息，很可能能够缓解这一问题。我们提出了一种新型结构化随机拟牛顿算法，保留海瑟矩阵中计算相对简单或容易近似部分，利用拟牛顿方法近似计算相对昂贵甚至不可访问的部分，从而能够产生更好的迭代方向。该方法不仅在理论上有一定的收敛保证，而且在数值上也展现了很好的效果。

相关论文：

会议投稿中

强化学习信赖域算法

强化学习是人工智能的重要基石之一，结合计算能力的大幅提升，计算机视觉、自然语言处理、自动驾驶等人工智能领域进入了井喷式的创新阶段。很多强化学习问题可以用马尔可夫决策模型来描述，因素包括状态集、动作集、状态转移概率、回报函数、折扣因子。策略指在每个状态下给出动作决定或者选择动作的概率分布。对当前任务选择策略，通过与环境的不断交互使得利益最大化，由价值函数评估策略。当动作集较大时，通常用深层神经网络函数来近似表示策略。当参数空间较大时，可以用基于梯度的优化算法完成监督学习近似策略和价值函数的任务，训练出复杂且表达性强的策略。这些问题的目标函数特点是多次随机模拟产生，我们充分利用价值函数和策略函数的特点发展了随机信赖域算法。从而得到扩展性更好和理论保证良好的算法，为大规模复杂任务提供可靠的理论和算法基础。

相关论文：

Zhao Mingming, Li Yongfeng, Wen Zaiwen, A stochastic trust region framework for policy optimization, ArXiv: 1911.11640

低秩矩阵优化子空间算法

在机器学习、统计、信号处理等很多科学工程问题和实际应用中，一大类优化问题都涉及矩阵变量，对此类问题的多数一阶算法都依赖特征值/奇异值分解运算。由于这两种分解通常需要较大的运算量，实际能求解的问题规模受到很大限制。我们对矩阵变量为低秩的情形进行了深入研究，提出了低秩矩阵优化子空间算法框架。该框架利用了迭代矩阵所处于低维特征子空间这一结构特点，将传统算法中的特征值分解等运算替换为对该特征子空间的更新，且在子空间更新中采用了多项式加速技术来获得更好的子空间近似，最后将子空间更新步和优化迭代步交替进行。该框架可以很方便的与很多传统优化算法结合。在理论方面证明了当多项式次数取值合适时，子空间算法框架可达到和原算法相同的收敛阶，但每次迭代的时间大幅度减小。基于此框架开发了 PFOpt 软件包，数值结果表明其在协方差矩阵估计问题、核范数优化问题、最大特征值优化问题上有良好的效果。

相关论文：

Li Yongfeng, Liu Haoyang, Wen Zaiwen, and Yuan Yaxiang, Low-rank Matrix Optimization Using Polynomial-filtered Subspace Extraction, SIAM Journal on Scientific Computing, accepted

流形优化算法与理论

流形优化牛顿/拟牛顿算法

流形约束优化泛指变量落在某种微分流形的优化模型，比如正交矩阵组成的集合称为Stiefel流形或Grassmann流形。它描述了计算和应用数学，统计学，机器学习，数据科学和材料科学等等很多领域中的重要科学问题，包括线性与非线性特征值问题，电子结构计算，玻色-爱因斯坦凝聚，低温电子显微镜(冷冻电镜)，相位恢复，p-调和流理论，组合优化问题的松弛解等等。这些问题的研究曾获多项诺贝尔物理奖和化学奖。流形约束的存在是这些非凸优化问题的算法设计和理论分析的主要困难。我们发展了流形约束优化的自适应正则化牛顿算法和结构化拟牛顿法。在子问题构造中，使用目标函数在欧式空间的二阶泰勒展开加上合适的正则化项但保持流形约束。而正则化项的自适应更新主要用来调节子问题对原目标函数的近似程度和保证收敛性。当子问题用牛顿法求解时，能有效利用负曲率信息，避免算法停滞在鞍点。严格证明了算法的全局收敛性和局部超线性收敛性。该子问题的构造方式不需要向量移动，特别是当目标函数的海瑟矩阵计算代价较高时，能灵活的使用拟牛顿近似，如保留计算简单的部分而近似昂贵的部分仍然保持好的理论性质。

Hu Jiang, Jiang Bo, Lin Lin, Wen Zaiwen, Yuan Yaxiang, Structured Quasi-Newton Methods for Optimization with Orthogonality Constraints, SIAM Journal on Scientific Computing, Vol. 41, No. 4, pp. A2239-A2269

Hu Jiang, Andre Milzarek, Wen Zaiwen, Yuan Yaxiang; Adaptive Quadratically Regularized Newton Method for Riemannian Optimization; SIAM Journal on Matrix Analysis and Applications; Vol 39, No. 3, 2018, pp 1181-1207

Jiang Bo, Meng Xiang, Wen Zaiwen, Chen Xiaojun, An exact penalty approach for optimization with nonnegative orthogonality constraints, arXiv: 1907.12424

Zhang Haixiang, Andre Milzarek, Yin Wotao, Wen Zaiwen; On the geometric analysis of a quartic-quadratic optimization problem under a spherical constraint, arXiv: 1908.00745

Wen Zaiwen, Yin Wotao; A Feasible method for Optimization with Orthogonality Constraints; Mathematical Programming; 142(2013), 397-434

特征值优化子空间算法

特征值分解和奇异值分解是正交约束优化问题的特例。在低秩矩阵优化，数据挖掘，主成份分析和数据降维技术等新型问题经常要求处理大规模稠密或带某些特殊结构的矩阵，其快速计算需要大力发展。我们发展了特征值分解和奇异值分解的快速算法，发展了能同步并行完全避免正交化步骤的模型，使得算法完全基于并行效率高的矩阵乘法等运算。基于低秩分解的高斯-牛顿算法算法形式很简单，计算方便。当要分解的矩阵比较低秩时，该算法的优势更加明显。其复杂度跟梯度法类似但具有Q线性收敛性。观察到很多迭代算法求解特征值的瓶颈是低维稠密矩阵特征值分解的RR过程，发展了统一的增广子空间算法框架，尽可能多的用矩阵－矩阵之间的乘法运算而尽量减少RR过程，分析了其收敛速度。结合经典特征值计算里的多项式加速和deflation等技术，理论上只需使用1次RR过程就能达到高精度。开发了软件包Arrabit，目前已经分别有C语言和Matlab 语言版本，其中C语言版本能够进行OpenMP多核并行和多节点MPI并行。数值试验表明新算法比经典的Krylov子空间算法有更好的并行效率。相应的软件包Arrabit在很多问题上比经典的软件包ARPACK、SLEPc和FEAST经常更有效。

Wen Zaiwen, Zhang Yin; Accelerating Convergence by Augmented Rayleigh-Ritz Projections For Large-Scale Eigenpair Computation; SIAM Journal on Matrix Analysis and Applications; Vol 38, No. 2 (2017), pp. 273-296

Liu Xin, Wen Zaiwen, Zhang Yin; An Efficient Gauss-Newton Algorithm for Symmetric Low-Rank Product Matrix Approximations; SIAM Journal on Optimization; Vol. 25, No. 3 (2015), 1571–1608

Liu Xin, Wen Zaiwen, Zhang Yin; Limited Memory Block Krylov Subspace Optimization for Computing Dominant Singular Value Decompositions; SIAM Journal on Scientific Computing; 35 (2013) A1641–A1668

电子结构计算算法

一类重要的正交约束问题来自非线性特征值问题，如模拟物质微观结构的Kohn-Sham（KS）方程。非线性特征值问题寻找相互正交的特征向量满足非线性特征方程，而带正交约束优化问题则在相同约束下极小化目标函数。两者之间以最优性条件为桥梁相互连接，共同描述物理系统的稳定状态。实际上自洽场迭代可以理解为极小化KS总能量泛函的近似牛顿算法，对KS总能量泛函海瑟矩阵复杂的部分不予考虑。我们推导了该复杂部分的具体形式。虽然该部分不适合显式存储，但其与向量乘法的运算简单可行。我们使用完整的海瑟矩阵提高牛顿法的可靠性，并且添加正则化项保证牛顿法的收敛性。因此该方法不仅在效率上经常能优于自洽场迭代，而且能在自洽场迭代失败的算例中也保证较快的收敛速度。

Tian Tonghua, Cai Yongyong, Wu Xinming, Wen Zaiwen, Ground states and their characterization of spin-F Bose-Einstein condensates, SIAM Journal on Scientific Computing

Wu Xinming, Wen Zaiwen, Bao Weizhu; A regularized Newton method for computing ground states of Bose-Einstein condensates; Journal of Scientific Computing; Vol. 73, No. 1, 2017, pp 303–329

Michael Ulbrich, Wen Zaiwen, Yang Chao, Dennis Klockner, Lu Zhaosong; A Proximal Gradient Method for Ensemble Density Functional Theory; SIAM Journal on Scientific Computing; Vol 37, No. 4 (2015), A1975–A2002

Zhang Xin, Zhu Jinwei, Wen Zaiwen, Zhou Aihui; Gradient-type Optimization Methods for Electronic Structure Calculation; SIAM Journal on Scientific Computing; Vol. 36, No. 3 (2014), pp. C265–C289

电子结构计算自洽场迭代收敛性

我们研究了离散KS密度泛函的几个经典理论问题。建立了KS总能量极小化问题与KS方程之间解的一些等价性关系，推导了非零电荷密度的下界。求解KS方程使用最广的算法是所谓的自洽场迭代，即反复求解相关线性特征值问题。长期以来，自洽场迭代在理论和计算上都没有收敛保证。我们将KS方程看成关于势函数的不动点方程，使用谱算子理论显示推导了其Jacobian矩阵，分析Kohn-Sham总能量的二阶泰勒展开，以及估计哈密尔顿矩阵与海色矩阵之间的关系，证明了如果哈密尔顿矩阵特征值有充分大的间隙并且交叉关联能的二阶导数一致有界，则自洽场迭代能从任意初始点收敛并且有局部线性收敛速度。虽然这些条件比较严格，但这些分析仍然为自洽场迭代提供了一些定性分析。

Liu Xin, Wang Xiao, Wen Zaiwen, Yuan Yaxiang; On the Convergence of the Self-Consistent Field Iteration in Kohn-Sham Density Functional Theory; SIAM Journal on Matrix Analysis and Applications; Vol. 35, No. 2(2014), pp. 546–558