More Web Proxy on the site http://driver.im/

research-article

Sequential Quadratic Optimization for Nonlinear Equality Constrained Stochastic Optimization

Authors:

Albert S. Berahas,

Frank E. Curtis,

Daniel Robinson,

Baoyu ZhouAuthors Info & Claims

SIAM Journal on Optimization, Volume 31, Issue 2

Pages 1352 - 1379

https://doi.org/10.1137/20M1354556

Published: 01 January 2021 Publication History

Abstract

Sequential quadratic optimization algorithms are proposed for solving smooth nonlinear optimization problems with equality constraints. The main focus is an algorithm proposed for the case when the constraint functions are deterministic, and constraint function and derivative values can be computed explicitly, but the objective function is stochastic. It is assumed in this setting that it is intractable to compute objective function and derivative values explicitly, although one can compute stochastic function and gradient estimates. As a starting point for this stochastic setting, an algorithm is proposed for the deterministic setting that is modeled after a state-of-the-art line-search SQP algorithm but uses a stepsize selection scheme based on Lipschitz constants (or adaptively estimated Lipschitz constants) in place of the line search. This sets the stage for the proposed algorithm for the stochastic setting, for which it is assumed that line searches would be intractable. Under reasonable assumptions, convergence (resp., convergence in expectation) from remote starting points is proved for the proposed deterministic (resp., stochastic) algorithm. The results of numerical experiments demonstrate the practical performance of our proposed techniques.

References

[1]

D. P. Bertsekas, Network Optimization: Continuous and Discrete Models, Athena Scientific Belmont, MA, 1998.

[2]

J. T. Betts, Practical Methods for Optimal Control and Estimation Using Nonlinear Programming, SIAM, Philadelphia, 2010.

[3]

I. Bongartz, A. R. Conn, N. Gould, and P. L. Toint, Cute: Constrained and unconstrained testing environment, ACM Trans. Math. Software, 21 (1995), pp. 123--160.

[4]

L. Bottou, F. E. Curtis, and J. Nocedal, Optimization methods for large-scale machine learning, SIAM Rev., 60 (2018), pp. 223--311.

[5]

R. H. Byrd, F. E. Curtis, and J. Nocedal, An inexact SQP method for equality constrained optimization, SIAM J. Optim., 19 (2008), pp. 351--369.

[6]

R. H. Byrd, F. E. Curtis, and J. Nocedal, An inexact Newton method for nonconvex equality constrained optimization, Math. Program., 122 (2010), pp. 273--299.

[7]

R. H. Byrd, J. C. Gilbert, and J. Nocedal, A trust region method based on interior point techniques for nonlinear programming, Math. Program., 89 (2000), pp. 149--185.

[8]

R. H. Byrd, M. E. Hribar, and J. Nocedal, An interior point algorithm for large-scale nonlinear programming, SIAM J. Optim., 9 (1999), pp. 877--900.

[9]

C. Chen, F. Tung, N. Vedula, and G. Mori, Constraint-aware deep neural network compression, in Proceedings of the ECCV, 2018, pp. 400--415.

[10]

A. R. Conn, N. I. M. Gould, and P. L. Toint, LANCELOT: A Fortran Package for Large-Scale Nonlinear Optimization, Springer, New York, 1992.

[11]

R. Courant, Variational methods for the solution of problems of equilibrium and vibrations, Bull. Amer. Math. Soc., 49 (1943), pp. 1--23.

[12]

F. E. Curtis and D. P. Robinson, Exploiting negative curvature in deterministic and stochastic optimization, Math. Program. Ser. B, 176 (2019), pp. 69--94.

[13]

E. D. Dolan and J. J. Moré, Benchmarking optimization software with performance profiles, Math. Program., 91 (2002), pp. 201--213.

[14]

R. Fletcher, Practical Methods of Optimization, John Wiley & Sons, Chichester, UK, 1987.

[15]

S. P. Han, A globally convergent method for nonlinear programming, J. Optim. Theory Appl., 22 (1977), pp. 297--309.

[16]

S. P. Han and O. L. Mangasarian, Exact penalty functions in nonlinear programming, Math. Program, 17 (1979), pp. 251--269.

[17]

E. Hazan and H. Luo, Variance-reduced and projection-free stochastic optimization, in Proceedings of the International Conference on Machine Learning, 2016, pp. 1263--1271.

[18]

M. R. Hestenes, Multiplier and Gradient Methods, J. Optim. Theory Appl., 4 (1969), pp. 303--320.

[19]

S. Kumar Roy, Z. Mhammedi, and M. Harandi, Geometry aware constrained optimization techniques for deep learning, in Proceedings of CVPR, 2018, pp. 4460--4469.

[20]

F. Kupfer and E. W. Sachs, Numerical solution of a nonlinear parabolic control problem by a reduced SQP method, Comput. Optim. Appl., 1 (1992), pp. 113--135.

[21]

F. Locatello, A. Yurtsever, O. Fercoq, and V. Cevher, Stochastic Frank-Wolfe for composite convex minimization, in Proceedings of NeurIPS, 2019, pp. 14269--14279.

[22]

H. Lu and R. M. Freund, Generalized stochastic Frank-Wolfe algorithm with stochastic “substitute” gradient for structured convex optimization, Math. Program., 187 (2021), pp. 317--349.

[23]

Y. Nandwani, A. Pathak, and P. Singla, A primal-dual formulation for deep learning with constraints, in Proceedings of NeurIPS, 2019, pp. 12157--12168.

[24]

Y. Nesterov, Introductory Lectures on Convex Optimization, Appl. Optim., Springer, New York, 2004.

[25]

J. Nocedal and S. Wright, Numerical Optimization, Springer Ser. Oper. Res. Financ. Eng., Springer, New York, 2006.

[26]

M. J. D. Powell, A Method for Nonlinear Constraints in Minimization Problems, in Optimization, R. Fletcher, ed., Academic Press, New York, 1969, pp. 283--298.

[27]

M. J. D. Powell, A fast algorithm for nonlinearly constrained optimization calculations, in Numerical Analysis, Lecture Notes in Math., Springer, New York, 1978, pp. 144--157.

[28]

S. N. Ravi, T. Dinh, V. S. Lokhande, and V. Singh, Explicitly imposing constraints in deep networks via conditional gradients gives improved generalization and faster convergence, in Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 33, 2019, pp. 4772--4779.

[29]

S. J. Reddi, S. Sra, B. Póczos, and A. Smola, Stochastic Frank-Wolfe methods for nonconvex optimization, in Proceedings of the 54th Annual Allerton Conference, IEEE, 2016, pp. 1244--1251.

[30]

T. Rees, H. S. Dollar, and A. J. Wathen, Optimal solvers for pde-constrained optimization, SIAM J. Sci. Comput., 32 (2010), pp. 271--298.

[31]

A. Shapiro, D. Dentcheva, and A. Ruszczyński, Lectures on Stochastic Programming: Modeling and Theory, SIAM, Philadelphia, 2009.

[32]

Y. L. Tong, The Multivariate Normal Distribution, Springer, New York, 2012.

[33]

A. Wächter and L. T. Biegler, Line search filter methods for nonlinear programming: Motivation and global convergence, SIAM J. Optim., 16 (2005), pp. 1--31.

[34]

A. Waechter and L. T. Biegler, On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Math. Program., 106 (2006), pp. 25--57.

[35]

R. B. Wilson, A Simplicial Algorithm for Concave Programming, Ph.D. thesis, Graduate School of Business Administration, Harvard University, Cambridge, MA, 1963.

[36]

M. Zhang, Z. Shen, A. Mokhtari, H. Hassani, and A. Karbasi, One sample stochastic Frank-Wolfe, in Proceedings of AISTATS, 2020, pp. 4012--4023.

Cited By

Grieshammer MPflug LStingl MUihlein A(2024)The continuous stochastic gradient method: part I–convergence theoryComputational Optimization and Applications10.1007/s10589-023-00542-887:3(935-976)Online publication date: 1-Apr-2024
https://dl.acm.org/doi/10.1007/s10589-023-00542-8
Curtis FO’Neill MRobinson D(2024)Worst-case complexity of an SQP method for nonlinear equality constrained stochastic optimizationMathematical Programming: Series A and B10.1007/s10107-023-01981-1205:1-2(431-483)Online publication date: 1-May-2024
https://dl.acm.org/doi/10.1007/s10107-023-01981-1
Huang YLin QOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Oracle complexity of single-loop switching subgradient methods for non-smooth weakly convex functional constrained optimizationProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3668801(61327-61340)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3668801
Show More Cited By

Index Terms

Sequential Quadratic Optimization for Nonlinear Equality Constrained Stochastic Optimization
1. Mathematics of computing
  1. Mathematical analysis
    1. Mathematical optimization
      1. Continuous optimization
2. Theory of computation
  1. Design and analysis of algorithms
    1. Mathematical optimization
      1. Continuous optimization

Index terms have been assigned to the content through auto-classification.

Recommendations

An Inexact Sequential Quadratic Optimization Algorithm for Nonlinear Optimization

We propose a sequential quadratic optimization method for solving nonlinear optimization problems with equality and inequality constraints. The novel feature of the algorithm is that, during each iteration, the primal-dual search direction is allowed to be ...
Worst-case complexity of an SQP method for nonlinear equality constrained stochastic optimization
Abstract
A worst-case complexity bound is proved for a sequential quadratic optimization (commonly known as SQP) algorithm that has been designed for solving optimization problems involving a stochastic objective function and deterministic nonlinear ...
Accelerating convergence of a globalized sequential quadratic programming method to critical Lagrange multipliers
Abstract
This paper concerns the issue of asymptotic acceptance of the true Hessian and the full step by the sequential quadratic programming algorithm for equality-constrained optimization problems. In order to enforce global convergence, the algorithm is ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image SIAM Journal on Optimization

SIAM Journal on Optimization Volume 31, Issue 2

DOI:10.1137/sjope8.31.2

Issue’s Table of Contents

© 2021, Society for Industrial and Applied Mathematics.

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 January 2021

Author Tags

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Grieshammer MPflug LStingl MUihlein A(2024)The continuous stochastic gradient method: part I–convergence theoryComputational Optimization and Applications10.1007/s10589-023-00542-887:3(935-976)Online publication date: 1-Apr-2024
https://dl.acm.org/doi/10.1007/s10589-023-00542-8
Curtis FO’Neill MRobinson D(2024)Worst-case complexity of an SQP method for nonlinear equality constrained stochastic optimizationMathematical Programming: Series A and B10.1007/s10107-023-01981-1205:1-2(431-483)Online publication date: 1-May-2024
https://dl.acm.org/doi/10.1007/s10107-023-01981-1
Huang YLin QOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Oracle complexity of single-loop switching subgradient methods for non-smooth weakly convex functional constrained optimizationProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3668801(61327-61340)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3668801
Hong INa SMahoney MKolar MKrause ABrunskill ECho KEngelhardt BSabato SScarlett J(2023)Constrained optimization via exact augmented lagrangian and randomized iterative sketchingProceedings of the 40th International Conference on Machine Learning10.5555/3618408.3618943(13174-13198)Online publication date: 23-Jul-2023
https://dl.acm.org/doi/10.5555/3618408.3618943
Berahas AShi JYi ZZhou B(2023)Accelerating stochastic sequential quadratic programming for equality constrained optimization using predictive variance reductionComputational Optimization and Applications10.1007/s10589-023-00483-286:1(79-116)Online publication date: 19-Apr-2023
https://dl.acm.org/doi/10.1007/s10589-023-00483-2
Sun SNocedal J(2023)A trust region method for noisy unconstrained optimizationMathematical Programming: Series A and B10.1007/s10107-023-01941-9202:1-2(445-472)Online publication date: 24-Mar-2023
https://dl.acm.org/doi/10.1007/s10107-023-01941-9
Na SAnitescu MKolar M(2023)Inequality constrained stochastic nonlinear optimization via active-set sequential quadratic programmingMathematical Programming: Series A and B10.1007/s10107-023-01935-7202:1-2(279-353)Online publication date: 2-Mar-2023
https://dl.acm.org/doi/10.1007/s10107-023-01935-7
Xu CLiu WChen Y(2022)A DES-based group decision model for group decision making with large-scale alternativesApplied Intelligence10.1007/s10489-021-02950-x52:12(13456-13477)Online publication date: 1-Sep-2022
https://dl.acm.org/doi/10.1007/s10489-021-02950-x
Na SAnitescu MKolar M(2022)An adaptive stochastic sequential quadratic programming with differentiable exact augmented lagrangiansMathematical Programming: Series A and B10.1007/s10107-022-01846-z199:1-2(721-791)Online publication date: 30-Jun-2022
https://dl.acm.org/doi/10.1007/s10107-022-01846-z

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents