An adaptive stochastic sequential quadratic programming with differentiable exact augmented Lagrangians

DOI10.1007/S10107-022-01846-ZzbMATH Open1518.90057arXiv2102.05320OpenAlexW3126903296MaRDI QIDQ6038658FDOQ6038658

Authors: Sen Na, Mihai Anitescu, Mladen Kolar 

Publication date: 2 May 2023

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/2102.05320

Recommendations

• Sequential quadratic optimization for nonlinear equality constrained stochastic optimization
• An active set SQP algorithm for a class of stochastic nonlinear programming
• A Sequential Quadratic Programming Algorithm Using an Incomplete Solution of the Subproblem
• scientific article; zbMATH DE number 3887439
• A stabilized SQP method: global convergence

zbMATH Keywords

sequential quadratic programmingstochastic optimizationaugmented Lagrangianexact penalty

Mathematics Subject Classification ID

Methods of successive quadratic programming type (90C55) Nonconvex programming, global optimization (90C26) Nonlinear programming (90C30) Stochastic programming (90C15)

Cites Work

• CUTEst: a constrained and unconstrained testing environment with safe threads for mathematical optimization
• Title not available (Why is that?)
• Robust Stochastic Approximation Approach to Stochastic Programming
• Sample size selection in optimization methods for machine learning
• Title not available (Why is that?)
• An introduction to matrix concentration inequalities
• User-friendly tail bounds for sums of random matrices
• SNOPT: An SQP Algorithm for Large-Scale Constrained Optimization
• Title not available (Why is that?)
• Asymptotic behavior of statistical estimators and of optimal solutions of stochastic optimization problems
• A New Class of Augmented Lagrangians in Nonlinear Programming
• Contributions to the theory of stochastic programming
• Sequential quadratic programming methods
• Stochastic optimization using a trust-region method and random models
• Convergence of trust-region methods based on probabilistic models
• On the asymptotics of constrained local \(M\)-estimators.
• Projected Newton Methods for Optimization Problems with Simple Constraints
• Stochastic processes. Theory for applications.
• Title not available (Why is that?)
• Estimation of the parameters of linear time series models subject to nonlinear restrictions
• Hybrid deterministic-stochastic methods for data fitting
• A stochastic line search method with expected complexity analysis
• Line search methods with variable sample size for unconstrained optimization
• Title not available (Why is that?)
• Probability
• Optimization methods for large-scale machine learning
• Recursive quadratic programming algorithm that uses an exact augmented Lagrangian function
• Adaptive sampling strategies for stochastic optimization
• Global convergence rate analysis of unconstrained optimization methods based on probabilistic models
• Stochastic Quasi-Newton Methods for Nonconvex Stochastic Optimization
• Sub-sampled Newton methods
• An investigation of Newton-sketch and subsampled Newton methods
• Exact and inexact subsampled Newton methods for optimization
• Complexity and global rates of trust-region methods based on probabilistic models
• Sequential quadratic optimization for nonlinear equality constrained stochastic optimization
• LSOS: Line-search second-order stochastic optimization methods for nonconvex finite sums

Cited In (12)

• Provably training overparameterized neural network classifiers with non-convex constraints
• Fully stochastic trust-region sequential quadratic programming for equality-constrained optimization problems
• A digital economy development index based on an improved hierarchical data envelopment analysis approach
• Hessian averaging in stochastic Newton methods achieves superlinear convergence
• An active set SQP algorithm for a class of stochastic nonlinear programming
• Inequality constrained stochastic nonlinear optimization via active-set sequential quadratic programming
• Accelerating stochastic sequential quadratic programming for equality constrained optimization using predictive variance reduction
• Sequential quadratic optimization for nonlinear equality constrained stochastic optimization
• Sequential quadratic optimization for stochastic optimization with deterministic nonlinear inequality and equality constraints
• Further results on implicit models with application to LQ adaptive optimization
• A sequential quadratic programming method with high-probability complexity bounds for nonlinear equality-constrained stochastic optimization
• Worst-case complexity of an SQP method for nonlinear equality constrained stochastic optimization

This page was built for publication: An adaptive stochastic sequential quadratic programming with differentiable exact augmented Lagrangians

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6038658)