随机非线性优化的算法及理论研究

Stochastic nonlinear optimization problems arise in many application fields, such as machine learning, statistics, big data analysis. Since these problems normally contain some parameters with uncertainties, or need to deal with huge scale sampling data, classic optimization techniques based on accurate function values and gradients are no longer applicable. Stochastic approximation methods attract much attention due to fewer sampling data and lower computational cost at each iteration. However, current study still faces some difficulties and challenges: 1) Existing works focus on convex problems or problems with simple convex constraints, while for general nonconvex stochastic nonlinear programming, especially problems with nonconvex constraints, there has been very few works. 2) The study on some algorithms, such as trust region algorithms and stochastic quasi-Newton methods, has not been thoroughly clear. Hence, through overcoming the difficulties caused by stochastic information this project will study stochastic trust region methods, theoretical properties of stochastic quasi-Newton methods (including suplinear convergence and second-order convergence) as well as algorithms for solving general nonsmooth stochastic optimization problems and nonconvex constrained stochastic optimization problems.

随机非线性优化模型广泛出现在机器学习、统计、大数据分析等领域。这类问题通常依赖于不确定性的参数或超大规模的样本数据，而传统的优化算法往往需要计算函数的精确函数值和梯度，因此很难有效处理这类问题。随机近似算法由于在每步迭代中随机采样少量数据，迭代复杂度非常低，引起了广泛关注。然而，随机信息的采用给算法设计和理论分析带来了很大的困难，目前随机非线性优化的研究仍面临挑战：1）已有的工作主要研究凸问题或有特殊结构的问题，而对于非凸问题，尤其带有非凸约束的问题，相关的研究工作很少。2)对已有的算法，如信赖域算法、随机拟牛顿算法等，的性质刻画尚不完善。因此，本项目将克服随机信息产生的困难，深入研究基于随机近似的信赖域算法，随机拟牛顿算法的理论性质（如超线性收敛性和二阶收敛性等），以及求解非光滑问题和非凸约束问题的随机近似算法等。

本项目针对随机优化的数值计算方法进行了深入的研究。随机非线性优化广泛地出现于机器学习、大数据分析、深度学习、 统计等领域。在这些领域中构建出的模型，它们往往涉及不确定的参数，或者要处理大规模的样本数据，从而导致了模型的函数是基于随机变量或者基于巨大规模的样本数据定义的。然而，因此，精确地计算模型函数的信息将十分地困难、耗时，从而使得传统的求解确定型非线性优化问题的基于精确函数值以及梯度值的算法将不再适用。受此启发，我们在本项目中对几类随机非线性优化模型进行了研究。主要成果总结如下：1）针对非线性方程组设计了随机二阶算法并在理论上刻画了算法的全局收敛性、计算复杂性、收敛速度等理论。克服了随机二阶信息计算、收敛速度分析等困难。2）研究了基于方差下降、拟牛顿更新等策略的随机近似方法，针对多种类型的复合优化模型设计了非光滑优化算法，有效平衡了在算法设计时对于子问题构造和有效求解的要求。3）研究了非凸约束随机优化的单循环原始对偶算法及其计算复杂性理论，克服了非凸约束的存在以及问题精确信息的缺失带来的困难；针对图像处理中的结构性非凸约束优化模型，设计了同时具有严谨的理论保证和鲁棒的数值表现的求解算法。相关论文发表在SIAM J. Imaging Sci.、J. Sci. Comp、Comp. Optim. Appl.等图像处理、计算数学、运筹优化的国际知名期刊上，并得到了国内外学者的关注和引用。项目负责人也因此多次应邀参加国内外高水平学术会议并作报告，包括工业与应用数学国际会议与SIAM优化年会分组报告等。另外，项目负责人在项目执行期间先后入选了中国科学院青年创新促进会会员、广东省珠江人才计划青年拔尖人才、深圳市鹏城孔雀特聘计划等。