非凸约束优化的随机近似算法

doi:10.15960/j.cnki.issn.1007-6093.2023.04.008

摘要/Abstract

摘要：

在人工智能、科学计算等领域，众多应用驱动的数学优化模型因依赖于庞大的数据集和/或不确定的信息而呈现出随机性、且伴有复杂非凸算子约束。于是精确计算模型中的函数信息往往代价高昂，同时非凸约束的存在也给模型求解和算法分析带来极大的挑战。近年来，结合模型的结构、利用函数的随机近似信息来设计、分析非凸约束优化算法开始引起关注。目前主流的求解非凸约束优化的随机近似算法主要分为三类：基于随机近似的罚方法、邻近点算法和随机序列二次规划算法。本文对这几类算法的研究进展进行梳理和总结，简要地介绍相关算法的设计思想和基本的理论性质，如渐近收敛性理论、复杂度理论等。

关键词: 随机近似, 非凸约束, 稳定点, 约束规格, 渐近收敛性, 复杂度

Abstract:

In many application fields such as artificial intelligence and scientific computing, application-driven mathematical optimization models often show randomness due to their dependence on large data sets and/or noisy data, and the model scale is large and accompanied by complex non-convex operator constraints. Thus it is normally expensive to get access to the exact function information of those models and can bring great challenges to algorithm design as well as theoretical analysis. In recent years, stochastic approximation algorithms for nonconvex constrained optimization have attracted much attention. Currently those algorithms can be separated into three categories: penalty methods based on stochastic approximations, proximal point algorithms and stochastic sequential quadratic programming algorithms. In this paper, we will briefly introduce latest progress on these types of algorithms, and present their algorithmic frameworks and theoretical properties including asymptotic convergence and complexity theory.

Key words: stochastic approximation, nonconvex constraints, critical point, constraint qualifications, asymptotic convergence, complexity

中图分类号:

O221.2

王晓. 非凸约束优化的随机近似算法[J]. 运筹学学报, 2023, 27(4): 153-165.

Xiao WANG. Stochastic approximation methods for nonconvex constrained optimization[J]. Operations Research Transactions, 2023, 27(4): 153-165.

参考文献 43

1	Ibaraki T , Katoh N . Resource Allocation Problems: Algorithmic Approaches[M]. Cambridge: MIT press, 1988.
2	Lan G . First-order and Stochastic Optimization Methods for Machine Learning[M]. Berlin: Springer, 2020.
3	Bertsekas D . Network Optimization: Continuous and Discrete Models[M]. Belmont: Athena Scientific, 1998.
4	Summers T , Warrington J , Morari M , et al. Stochastic optimal power flow based on conditional value at risk and distributional robustness[J]. International Journal of Electrical Power and Energy Systems, 2015, 72, 116- 125. doi: 10.1016/j.ijepes.2015.02.024
5	Shapiro A , Dentcheva D , Ruszczyński A . Lectures on Stochastic Programming: Modeling and Theory[M]. Philadelphia: Society for Industrial and Applied Mathematics, 2021.
6	Ravi S, Dinh T, Lokhande V, et al. Explicitly imposing constraints in deep networks via conditional gradients gives improved generalization and faster convergence[C]//Proceedings of the Thirty-Third AAAI, 2019: 4772-4779.
7	Nandwani Y, Pathak A, Singla P. A primal-dual formulation for deep learning with constraints[C]//Proceedings of Neural Information Processing Systems, 2019: 12157-12168.
8	Roy S K, Mhammedi Z, Harandi M. Geometry aware constrained optimization techniques for deep learning[C]//Proceedings of Computer Vision and Pattern Recognition, 2018: 4460-4469.
9	Chen C, Tung F, Vedula N, et al. Constraint-aware deep neural network compression[C]//Proceedings of the European Conference on Computer Vision, 2018: 400-415.
10	Fablet R , Chapron B , Drumetz L , et al. Learning variational data assimilation models and solvers[J]. Journal of Advances in Modeling Earth Systems, 2021, 13 (10): e2021MS002572. doi: 10.1029/2021MS002572
11	Nocedal J , Wright S . Numerical Optimization[M]. New York: Springer, 2006.
12	王奇超, 文再文, 蓝光辉, 等. 优化算法的复杂度分析[J]. 中国科学: 数学, 2020, 50 (9): 1271- 1336.
13	Cartis C , Gould N I , Toint P L . On the evaluation complexity of composite function minimization with applications to nonconvex nonlinear programming[J]. SIAM Journal on Optimization, 2011, 4, 1721- 1739.
14	Cartis C , Gould N I , Toint P L . On the complexity of finding first-order critical points in constrained nonlinear optimization[J]. Mathematical Programming, 2014, 144 (1): 93- 106.
15	Facchinei F , Kungurtsev V , Lampariello L , et al. Ghost penalties in nonconvex constrained optimization: Diminishing stepsizes and iteration complexity[J]. Mathematics of Operations Research, 2021, 46 (2): 595- 627. doi: 10.1287/moor.2020.1079
16	Lan G , Zhou Z . Algorithms for stochastic optimization with function or expectation constraints[J]. Computational Optimization and Applications, 2020, 76 (2): 461- 498. doi: 10.1007/s10589-020-00179-x
17	Wang R, Ding C. Robins-monro augmented lagrangian method for stochastic convex optimization[J]. 2022, arXiv: 2208.14019.
18	Xu Y . Primal-dual stochastic gradient method for convex programs with many functional constraints[J]. SIAM Journal on Optimization, 2020, 30 (2): 1664- 1692. doi: 10.1137/18M1229869
19	Zhang L , Zhang Y , Xiao X , et al. Stochastic approximation proximal method of multipliers for convex stochastic programming[J]. Mathematics of Operations Research, 2023, 48 (1): 177- 193. doi: 10.1287/moor.2022.1257
20	Zhang L , Zhang Y , Wu J , et al. Solving stochastic optimization with expectation constraints efficiently by a stochastic augmented lagrangian-type algorithm[J]. Informs Journal on Computing, 2022, 34 (6): 2989- 3006. doi: 10.1287/ijoc.2022.1228
21	Wang X , Ma S , Yuan Y . Penalty methods with stochastic approximation for stochastic nonlinear programming[J]. Mathematics of Computation, 2017, 86, 1793- 1820.
22	Li Z, Chen P, Liu S, et al. Stochastic inexact augmented lagrangian method for nonconvex expectation constrained optimization[J]. 2022, arXiv: 2212.09513.
23	Wang X , Yuan Y . An augmented Lagrangian trust region method for equality constrained optimization[J]. Optimization Methods and Software, 2015, 30 (3): 559- 582. doi: 10.1080/10556788.2014.940947
24	Wang X , Zhang H . An augmented Lagrangian affine scaling method for nonlinear programming[J]. Optimization Methods and Software, 2015, 30 (5): 934- 964. doi: 10.1080/10556788.2015.1004332
25	Xu Y . First-order methods for constrained convex programming based on linearized augmented Lagrangian function[J]. INFORMS Journal on Optimization, 2021, 3 (1): 89- 117. doi: 10.1287/ijoo.2019.0033
26	Jin L , Wang X . A stochastic primal-dual method for a class of nonconvex constrained optimization[J]. Computational Optimization and Applications, 2022, 83, 143- 180. doi: 10.1007/s10589-022-00384-w
27	Campi M C , Garatti S . A sampling-and-discarding approach to chance-constrained optimization: Feasibility and optimality[J]. Journal of Optimization and Theory Applications, 2011, 148 (2): 257- 280. doi: 10.1007/s10957-010-9754-6
28	Seri R , Choirat C . Scenario approximation of robust and chance-constrained programs[J]. Journal of Optimization Theory and Applications, 2013, 158 (2): 590- 614. doi: 10.1007/s10957-012-0230-3
29	Jin L, Wang X. Stochastic nested primal-dual method for nonconvex constrained composition optimization[EB/OL]. (2022-08-14)[2023-04-19]. https://optimization-online.org/?p=19899.
30	Shi Q, Wang X, Wang H. A momemtum-based linearized augmented lagrangian method for nonconvex constrained stochastic optimization[EB/OL]. (2022-08-11)[2023-04-19]. https://optimization-online.org/?p=19870.
31	Boob D , Deng Q , Lan G . Stochastic first-order methods for convex and nonconvex functional constrained optimization[J]. Mathematical Programming, 2022, 197, 215- 279.
32	Ma R, Lin Q, Yang T. Quadratically regularized subgradient methods for weakly convex optimization with weakly convex constraints[C]//Proceedings of the 37th International Conference on Machine Learning, 2020: 6554-6564.
33	Boob D, Deng Q, Lan G. Level constrained first order methods for function constrained optimization[J]. 2022, arXiv: 2205.08011.
34	Berahas A , Curtis F , Robinson D , et al. Sequential quadratic optimization for nonlinear equality constrained stochastic optimization[J]. SIAM Journal on Optimization, 2021, 31, 1352- 1379. doi: 10.1137/20M1354556
35	Curtis F, O'Neill M J, Robinson D. A stochastic sequential quadratic optimization algorithm for nonlinear equality constrained optimization with rank-deficient jacobians[J]. 2021, arXiv: 2106.13015.
36	Curtis F, O'Neill M J, Robinson D. Inexact sequential quadratic optimization for minimizing a stochastic objective function subject to deterministic nonlinear equality constraints[J]. 2021, arXiv: 2107.03512.
37	Berahas A , Shi J , Yi Z , et al. Accelerating stochastic sequential quadratic programming for equality constrained optimization using predictive variance reduction[J]. Computational Optimization and Applications, 2023, 86 (1): 79- 116. doi: 10.1007/s10589-023-00483-2
38	Na S , Anitescu M , Kolar M . An adaptive stochastic sequential quadratic programming with differentiable exact augmented lagrangians[J]. Mathematical Programming, 2022, 199, 721- 791.
39	Fang Y, Na S, Kolar M. Fully stochastic trust-region sequential quadratic programming for equality-constrained optimization problems[J]. 2022, arXiv: 2211.15943.
40	Na S, Anitescu M, Kolar M. Inequality constrained stochastic nonlinear optimization via active-set sequential quadratic programming[J/OL]. (2023-03-02)[2023-04-19]. Mathematical Programming, DOI: 10.1007/s10107-023-01935-7.
41	Curtis F, O'Neill M J, Robinson D. Sequential quadratic optimization for stochastic optimization with deterministic nonlinear inequality and equality constraints[J]. 2023, arXiv: 2302.14790.
42	Curtis F, O'Neill M J, Robinson D. Worst-case complexity of an SQP method for nonlinear equality constrained stochastic optimization[J]. 2022, arXiv: 2112.14799.
43	Berahas A, Xie M, Zhou B. A sequential quadratic programming method with high probability complexity bounds for nonlinear equality constrained stochastic optimization[J]. 2023, arXiv: 2301.00477.

[1]	胡佳, 郭田德, 韩丛英. 小批量随机块坐标下降算法[J]. 运筹学学报, 2022, 26(1): 1-22.
[2]	徐姿, 张慧灵. 非凸极小极大问题的优化算法与复杂度分析[J]. 运筹学学报, 2021, 25(3): 74-86.
[3]	朱喜华, 常青青, 江波. 高阶优化算法分析简介[J]. 运筹学学报, 2019, 23(3): 63-76.
[4]	高雷阜, 闫婷婷. 均衡约束数学规划问题的一类广义Mond-Weir型对偶理论[J]. 运筹学学报, 2019, 23(2): 95-103.
[5]	孔令臣, 陈丙振, 修乃华, 戚厚铎. 高维约束矩阵回归问题[J]. 运筹学学报, 2017, 21(2): 31-38.
[6]	万龙. 有关单机两代理排序问题的两个结果[J]. 运筹学学报, 2015, 19(2): 54-60.
[7]	刘水霞, 陈国庆. 求解互补约束优化问题的乘子松弛法[J]. 运筹学学报, 2014, 18(4): 119-130.
[8]	万龙. 二阶数乘问题的一个最优算法[J]. 运筹学学报, 2014, 18(3): 99-103.
[9]	黎健玲, 谢琴, 简金宝. 均衡约束数学规划的约束规格和最优性条件综述[J]. 运筹学学报, 2013, 17(3): 73-85.
[10]	高敬振，高勃. 中国邮递员问题50年[J]. 运筹学学报, 2013, 17(1): 17-28.
[11]	刘水霞, 陈国庆. 互补约束优化问题的乘子序列部分罚函数算法[J]. 运筹学学报, 2011, 15(4): 55-64.