运筹学学报 >
2023 , Vol. 27 >Issue 4: 153 - 165
DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2023.04.008
非凸约束优化的随机近似算法
收稿日期: 2023-04-30
网络出版日期: 2023-12-07
基金资助
国家自然科学基金(12271278);鹏城实验室重大攻关项目(PCL2022A05)
Stochastic approximation methods for nonconvex constrained optimization
Received date: 2023-04-30
Online published: 2023-12-07
在人工智能、科学计算等领域，众多应用驱动的数学优化模型因依赖于庞大的数据集和/或不确定的信息而呈现出随机性、且伴有复杂非凸算子约束。于是精确计算模型中的函数信息往往代价高昂，同时非凸约束的存在也给模型求解和算法分析带来极大的挑战。近年来，结合模型的结构、利用函数的随机近似信息来设计、分析非凸约束优化算法开始引起关注。目前主流的求解非凸约束优化的随机近似算法主要分为三类：基于随机近似的罚方法、邻近点算法和随机序列二次规划算法。本文对这几类算法的研究进展进行梳理和总结，简要地介绍相关算法的设计思想和基本的理论性质，如渐近收敛性理论、复杂度理论等。
王晓 . 非凸约束优化的随机近似算法[J]. 运筹学学报, 2023 , 27(4) : 153 -165 . DOI: 10.15960/j.cnki.issn.1007-6093.2023.04.008
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.
| 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. |
| 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. |
| 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. |
| 16 | Lan G , Zhou Z . Algorithms for stochastic optimization with function or expectation constraints[J]. Computational Optimization and Applications, 2020, 76 (2): 461- 498. |
| 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. |
| 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. |
| 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. |
| 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. |
| 24 | Wang X , Zhang H . An augmented Lagrangian affine scaling method for nonlinear programming[J]. Optimization Methods and Software, 2015, 30 (5): 934- 964. |
| 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. |
| 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. |
| 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. |
| 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. |
| 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. |
| 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. |
| 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. |
/
| 〈 |
|
〉 |
