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

research-article

An Inexact Sequential Quadratic Optimization Algorithm for Nonlinear Optimization

Authors:

Frank E. Curtis,

Travis C. Johnson,

Daniel P. Robinson, Andreas WächterAuthors Info & Claims

SIAM Journal on Optimization, Volume 24, Issue 3

Pages 1041 - 1074

https://doi.org/10.1137/130918320

Published: 01 January 2014 Publication History

Abstract

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 an inexact solution of a given quadratic optimization subproblem. We present a set of generic, loose conditions that the search direction (i.e., inexact subproblem solution) must satisfy so that global convergence of the algorithm for solving the nonlinear problem is guaranteed. The algorithm can be viewed as a globally convergent inexact Newton-based method. The results of numerical experiments are provided to illustrate the reliability of the proposed numerical method.

References

[1]

H. Y. Benson, Cute Models, http://www.orfe.princeton.edu/ rvdb/ampl/nlmodels/cute/index.html http://www.orfe.princeton.edu/$\sim$rvdb/ampl/nlmodels/cute/ http://www.orfe.princeton.edu/ rvdb/ampl/nlmodels/cute/index.htmlindex.html.

[2]

H. G. Bock, M. Diehl, P. Kühl, E. Kostina, J. P. Schiöder, and L. Wirsching, Numerical methods for efficient and fast nonlinear model predictive control, in Assessment and Future Directions of Nonlinear Model Predictive Control, R. Findeisen, F. Allgöwer, and L. T. Biegler, eds., Lecture Notes in Control and Inform. Sci. 358, Springer, Berlin, Heidelberg, 2007, pp. 163--179.

[3]

J. V. Burke, Descent methods for composite nondifferentiable optimization problems, Math. Programming, 33 (1985), pp. 260--279.

[4]

J. V. Burke, Second order necessary and sufficient conditions for convex composite NDO, Math. Programming, 38 (1987), pp. 287--302.

[5]

J. V. Burke, F. E. Curtis, and H. Wang, A Sequential Quadratic Optimization Algorithm with Fast Infeasibility Detection, Tech. Report 12T-012, COR@L Laboratory, Department of ISE, Lehigh University, 2012.

[6]

J. V. Burke and M. C. Ferris, A Gauss-Newton method for convex composite optimization, Math. Programming, 71 (1995), pp. 179--194.

[7]

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.

[8]

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.

[9]

R. H. Byrd, F. E. Curtis, and J. Nocedal, Infeasibility detection and SQP methods for nonlinear optimization, SIAM J. Optim., 20 (2010), pp. 2281--2299.

[10]

R. H. Byrd, N. I. M. Gould, J. Nocedal, and R. A. Waltz, An algorithm for nonlinear optimization using linear programming and equality constrained subproblems, Math. Program., 100 (2004), pp. 27--48.

[11]

R. H. Byrd, G. López-Calva, and J. Nocedal, A line search exact penalty method using steering rules, Math. Program., 133 (2012), pp. 39--73

[12]

R. H. Byrd, J. Nocedal, and R. A. Waltz, Steering exact penalty methods for nonlinear programming, Optim. Methods Softw., 23 (2008), pp. 197--213.

[13]

F. E. Curtis, J. Huber, O. Schenk, and A. Wächter, A note on the implementation of an interior-point algorithm for nonlinear optimization with inexact step computations, Math. Program., 136 (2012), pp. 209--227.

[14]

F. E. Curtis, J. Nocedal, and A. Wächter, A matrix-free algorithm for equality constrained optimization problems with rank deficient Jacobians, SIAM J. Optim., 20 (2009), pp. 1224--1249.

[15]

F. E. Curtis, O. Schenk, and A. Wächter, An interior-point algorithm for large-scale nonlinear optimization with inexact step computations, SIAM J. Sci. Comput., 32 (2010), pp. 3447--3475.

[16]

R. S. Dembo, S. C. Eisenstat, and T. Steihaug, Inexact Newton methods, SIAM J. Numer. Anal., 19 (1982), pp. 400--408.

[17]

M. Diehl, A. Walther, H. G. Bock, and E. Kostina, An adjoint-based SQP algorithm with quasi-Newton Jacobian updates for inequality constrained optimization, Optim. Methods Softw., 25 (2010), pp. 531--552.

[18]

R. Fletcher, Practical Methods of Optimization, 2nd ed., Wiley-Interscience, New York, 1987.

[19]

R. Fletcher, Stable reduced Hessian updates for indefinite quadratic programming, Math. Program., 87 (2000), pp. 251--264.

[20]

R. Fletcher and E. Sainz de la Maza, Nonlinear programming and nonsmooth optimization by successive linear programming, Math. Programming, 43 (1989), pp. 235--256.

[21]

R. Fourer, D. M. Gay, and B. W. Kernighan, AMPL: A Modeling Language for Mathematical Programming, 2nd ed., Brooks/Cole, Pacific Grove, CA, 2002.

[22]

N. I. M. Gould, Y. Loh, and D. P. Robinson, A filter method with unified step computation for nonlinear optimization, SIAM J. Optim., 24 (2014), pp. 175--209

[23]

N. I. M. Gould, D. Orban, and Ph. L. Toint, Cuter and SIFDEC: A constrained and unconstrained testing environment, revisited, ACM Trans. Math. Software, 29 (2003), pp. 373--394.

[24]

N. I. M. Gould and D. P. Robinson, A second derivative SQP method: Global convergence, SIAM J. Optim., 20 (2010), pp. 2023--2048.

[25]

N. I. M. Gould and D. P. Robinson, A second derivative SQP method: Local convergence and practical issues, SIAM J. Optim., 20 (2010), pp. 2049--2079.

[26]

N. I. M. Gould and D. P. Robinson, A second-derivative SQP method with a “trust-region-free” predictor step, IMA J. Numer. Anal., 32 (2012), pp. 580--601.

[27]

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

[28]

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

[29]

M. Heinkenschloss and L. N. Vicente, Analysis of inexact trust-region SQP algorithms, SIAM J. Optim., 12 (2001), pp. 283--302.

[30]

B. Houska and M. Diehl, A quadratically convergent inexact SQP method for optimal control of differential algebraic equations, Optimal Control Appl. Methods, 34 (2013), pp. 396--414.

[31]

A. F. Izmailov and M. V. Solodov, A truncated SQP method based on inexact interior-point solutions of subproblems, SIAM J. Optim., 20 (2010), pp. 2584--2613.

[32]

H. Jäger and E. W. Sachs, Global convergence of inexact reduced SQP methods, Optim. Methods Softw., 7 (1997), pp. 83--110.

[33]

F. John, Extremum problems with inequalities as side conditions, in Studies and Essays, Courant Anniversary Volume, K. O. Friedrichs, O. E. Neugebauer, and J. J. Stoker, eds., Wiley (Interscience), New York, 1948, pp. 187--204.

[34]

T. C. Johnson, C. Kirches, and A Wächter, An Active-Set Quadratic Programming Method Based on Sequential Hot-Starts, Tech. report, 2013; available online from http://www.optimization-online.org/DB_HTML/2013/10/4084.html http://www.optimization-online.org/DB$\_$HTML/2013/10/4084.html.

[35]

W. Karush, Minima of Functions of Several Variables with Inequalities as Side Constraints, Master's thesis, Department of Mathematics, University of Chicago, Chicago, IL, 1939.

[36]

H. W. Kuhn and A. W. Tucker, Nonlinear programming, in Proceedings of the Second Berkeley Symposium on Mathematical Statistics and Probability, J. Neyman, ed., University of California Press, Berkeley, CA, 1951, pp. 481--492.

[37]

F. Leibfritz and E. W. Sachs, Inexact SQP interior point methods and large scale optimal control problems, SIAM J. Control Optim., 38 (1999), pp. 272--293.

[38]

O. L. Mangasarian and S. Fromovitz, The Fritz John necessary optimality conditions in the presence of equality and inequality constraints, J. Math. Anal. Appl., 17 (1967), pp. 37--47.

[39]

J. L. Morales, A numerical study of limited memory BFGS methods, Appl. Math. Lett., 15 (2002), pp. 481--487.

[40]

J. L. Morales, J. Nocedal, and Y. Wu, A sequential quadratic programming algorithm with an additional equality constrained phase, IMA J. Numer. Anal., 32 (2012), pp. 553--579.

[41]

W. Murray and F. J. Prieto, A sequential quadratic programming algorithm using an incomplete solution of the subproblem, SIAM J. Optim., 5 (1995), pp. 590--640.

[42]

J. M. Ortega and W. C. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables, Classics Appl. Math. 30, SIAM, Philadelphia, PA, 2000.

[43]

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

[44]

A. Wächter 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.

[45]

A. Walther, A first-order convergence analysis of trust-region methods with inexact Jacobians, SIAM J. Optim., 19 (2008), pp. 307--325.

[46]

A. Walther, S. R. R. Vetukuri, and L. T. Biegler, A first-order convergence analysis of trust-region methods with inexact Jacobians and inequality constraints, Optim. Methods Softw., 27 (2012), pp. 373--389.

[47]

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

Cited By

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

Index Terms

An Inexact Sequential Quadratic Optimization Algorithm for Nonlinear Optimization
1. Mathematics of computing
  1. Mathematical analysis
    1. Mathematical 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

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 ...
An interior-point trust-funnel algorithm for nonlinear optimization

We present an interior-point trust-funnel algorithm for solving large-scale nonlinear optimization problems. The method is based on an approach proposed by Gould and Toint (Math Prog 122(1):155---196, 2010) that focused on solving equality constrained ...
A new superlinearly convergent algorithm of combining QP subproblem with system of linear equations for nonlinear optimization

In this paper, a class of optimization problems with nonlinear inequality constraints is discussed. Based on the ideas of sequential quadratic programming algorithm and the method of strongly sub-feasible directions, a new superlinearly convergent ...

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 24, Issue 3

2014

648 pages

ISSN:1052-6234

DOI:10.1137/sjope8.24.3

Issue’s Table of Contents

© 2014, Society for Industrial and Applied Mathematics.

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 January 2014

Author Tags

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
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

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

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents