
arXiv: 2102.05320
We consider solving nonlinear optimization problems with a stochastic objective and deterministic equality constraints. We assume for the objective that its evaluation, gradient, and Hessian are inaccessible, while one can compute their stochastic estimates by, for example, subsampling. We propose a stochastic algorithm based on sequential quadratic programming (SQP) that uses a differentiable exact augmented Lagrangian as the merit function. To motivate our algorithm design, we first revisit and simplify an old SQP method \citep{Lucidi1990Recursive} developed for solving deterministic problems, which serves as the skeleton of our stochastic algorithm. Based on the simplified deterministic algorithm, we then propose a non-adaptive SQP for dealing with stochastic objective, where the gradient and Hessian are replaced by stochastic estimates but the stepsizes are deterministic and prespecified. Finally, we incorporate a recent stochastic line search procedure \citep{Paquette2020Stochastic} into the non-adaptive stochastic SQP to adaptively select the random stepsizes, which leads to an adaptive stochastic SQP. The global "almost sure" convergence for both non-adaptive and adaptive SQP methods is established. Numerical experiments on nonlinear problems in CUTEst test set demonstrate the superiority of the adaptive algorithm.
60 pages, 24 figures
FOS: Computer and information sciences, exact penalty, augmented Lagrangian, Stochastic programming, Machine Learning (stat.ML), Numerical Analysis (math.NA), stochastic optimization, Nonconvex programming, global optimization, Statistics - Computation, Methods of successive quadratic programming type, Nonlinear programming, Statistics - Machine Learning, Optimization and Control (math.OC), FOS: Mathematics, Mathematics - Numerical Analysis, Mathematics - Optimization and Control, sequential quadratic programming, Computation (stat.CO)
FOS: Computer and information sciences, exact penalty, augmented Lagrangian, Stochastic programming, Machine Learning (stat.ML), Numerical Analysis (math.NA), stochastic optimization, Nonconvex programming, global optimization, Statistics - Computation, Methods of successive quadratic programming type, Nonlinear programming, Statistics - Machine Learning, Optimization and Control (math.OC), FOS: Mathematics, Mathematics - Numerical Analysis, Mathematics - Optimization and Control, sequential quadratic programming, Computation (stat.CO)
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 21 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
