中文

Operations Research Transactions >

2023 , Vol. 27 >Issue 4: 153 - 165

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2023.04.008

Stochastic approximation methods for nonconvex constrained optimization

Expand
  • 1. Peng Cheng Laboratory, Shenzhen 518066, Guangdong, China

Received date: 2023-04-30

  Online published: 2023-12-07

Fold

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

Cite this article

Xiao WANG . Stochastic approximation methods for nonconvex constrained optimization[J]. Operations Research Transactions, 2023 , 27(4) : 153 -165 . DOI: 10.15960/j.cnki.issn.1007-6093.2023.04.008

References

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.
Options
Outlines

/

〈 〉