• Previous Article
    A sixth order numerical method for a class of nonlinear two-point boundary value problems
  • NACO Home
  • This Issue
  • Next Article
    A smoothing Newton method for generalized Nash equilibrium problems with second-order cone constraints
2012, 2(1): 19-29. doi: 10.3934/naco.2012.2.19

Global convergence of an SQP algorithm for nonlinear optimization with overdetermined constraints

1. 

Department of Applied Mathematics, Beijing University of Technology, Beijing 100124

2. 

Department of Applied Mathematics, Hebei University of Technology, Tianjin 300401

Received  March 2011 Revised  May 2011 Published  March 2012

A sequential quadratic programming (SQP) algorithm is presented for solving nonlinear optimization with overdetermined constraints. In each iteration, the quadratic programming (QP) subproblem is always feasible even if the gradients of constraints are always linearly dependent and the overdetermined constraints may be inconsistent. The $\ell_2$ exact penalty function is selected as the merit function. Under suitable assumptions on gradients of constraints, we prove that the algorithm will terminate at an approximate KKT point of the problem, or there is a limit point which is either a point satisfying the overdetermined system of equations or a stationary point for minimizing the $\ell_2$ norm of the residual of the overdetermined system of equations.
Citation: Chunlin Hao, Xinwei Liu. Global convergence of an SQP algorithm for nonlinear optimization with overdetermined constraints. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 19-29. doi: 10.3934/naco.2012.2.19
References:
[1]

R. Andreani, E. G. Birgin, J. M. Martinez and M. L. Schuverdt, Augmented Lagrangian methods under the constant positive linear dependence constraint qualification,, Math. Program., 111 (2008), 5.  doi: doi:10.1007/s10107-006-0077-1.  Google Scholar

[2]

N. Arora and L. T. Biegler, A trust region SQP algorithm for equality constrained parameter estimation with simple parameter bounds,, Comput. Optim. Appl., 28 (2004), 51.  doi: doi:10.1023/B:COAP.0000018879.40214.11.  Google Scholar

[3]

J. T. Betts, Very low-thrust trajectory optimization using a direct SQP method,, J. Comput. Appl. Math., 120 (2000), 27.  doi: doi:10.1016/S0377-0427(00)00301-0.  Google Scholar

[4]

J. V. Burke, A sequential quadratic programming method for potentially infeasible mathematical programs,, J. Math. Anal. Appl., 139 (1989), 319.  doi: doi:10.1016/0022-247X(89)90111-X.  Google Scholar

[5]

J. V. Burke and S. P. Han, A robust sequential quadratic programming method,, Math. Program., 43 (1989), 277.  doi: doi:10.1007/BF01582294.  Google Scholar

[6]

R. H. Byrd, F. E. Curtis and J. Nocedal, An inexact SQP method for equality constrained optimization,, SIAM J. Optim., 19 (2008), 351.  doi: doi:10.1137/060674004.  Google Scholar

[7]

R. H. Byrd, M. Marazzi and J. Nocedal, On the convergence of Newton iterations to non- \break stationary points,, Math. Program., 99 (2004), 127.  doi: doi:10.1007/s10107-003-0376-8.  Google Scholar

[8]

A. R. Conn, N. Gould and Ph. L. Toint, "Trust-Region Methods,", SIAM, (2000).  doi: doi:10.1137/1.9780898719857.  Google Scholar

[9]

H. Dai, "Matrix Theory,", Science Press, (2001).   Google Scholar

[10]

R. Fletcher, "Practical Methods for Optimization. Vol. 2: Constrained Optimization,", John Wiley and Sons, (1981).   Google Scholar

[11]

R. Fletcher, N. Gould, S. Leyffer, Ph. L. Toint and A. Wächter, Global convergence of a trust-region SQP-filter allgorithm for general nonlinear programming,, SIAM J. Optim., 13 (2002), 635.  doi: doi:10.1137/S1052623499357258.  Google Scholar

[12]

R. Fletcher and S. Leyffer, Nonlinear programming without a penalty function,, Math. Program., 91 (2002), 239.  doi: doi:10.1007/s101070100244.  Google Scholar

[13]

G. H. Golub and C. F. V. Loan, "Matrix Computation,", Third Edition, (1996).   Google Scholar

[14]

S. P. Han, A globally convergent method for nonlinear programming,, J. Optim. Theory Appl., 22 (1977), 297.  doi: doi:10.1007/BF00932858.  Google Scholar

[15]

M. Heinkenschloss and L. N. Vicente, Analysis of inexact trust-region SQP algorithms,, SIAM J. Optim., 12 (2002), 283.  doi: doi:10.1137/S1052623499361543.  Google Scholar

[16]

X. W. Liu, Global convergence on an active set SQP for inequality constrained optimization,, J. Comput. Appl. Math., 180 (2005), 201.  doi: doi:10.1016/j.cam.2004.10.012.  Google Scholar

[17]

X. W. Liu and J. Sun, A robust primal-dual interior point algorithm for nonlinear programs,, SIAM J. Optim., 14 (2004), 1163.  doi: doi:10.1137/S1052623402400641.  Google Scholar

[18]

X. W. Liu and Y. X. Yuan, A null-space primal-dual interior-point algorithm for nonlinear optimization with nice convergence properties,, Math. Program., 125 (2010), 163.  doi: doi:10.1007/s10107-009-0272-y.  Google Scholar

[19]

X. W. Liu and Y. X. Yuan, A sequential quadratic programming method without a penalty function or a filter for nonlinear equality constrained optimization,, SIAM J. Optim., 21 (2011), 545.  doi: 10.1137/080739884.  Google Scholar

[20]

W. Murray, Sequential quadratic programming methods for large-scale problems,, J. Comput. Optim. Appl., 7 (1997), 127.  doi: doi:10.1023/A:1008671829454.  Google Scholar

[21]

J. Nocedal and S. Wright, "Numerical Optimization,", Springer-Verlag New York, (1999).  doi: doi:10.1007/b98874.  Google Scholar

[22]

M. J. D. Powell, A fast algorithm for nonlinearly constrained optimization calculations,, in, (1977), 144.   Google Scholar

[23]

P. Spellucci, An SQP method for general nonlinear programs using only equality constrained subproblems,, Math. Program., 82 (1998), 413.  doi: doi:10.1007/BF01580078.  Google Scholar

[24]

G. W. Walster and E. R. Hansen, Computing interval parameter bounds from fallible measurements using overdetermined (Tall) systems of nonlinear equations,, Lecture Notes in, (2002), 171.   Google Scholar

[25]

S. J. Wright, Modifying SQP for degenerate problems,, SIAM J. Optim., 13 (2002), 470.  doi: doi:10.1137/S1052623498333731.  Google Scholar

[26]

Y. X. Yuan, On the convergence of a new trust region algorithm,, Numer. Math., 70 (1995), 515.  doi: doi:10.1007/s002110050133.  Google Scholar

show all references

References:
[1]

R. Andreani, E. G. Birgin, J. M. Martinez and M. L. Schuverdt, Augmented Lagrangian methods under the constant positive linear dependence constraint qualification,, Math. Program., 111 (2008), 5.  doi: doi:10.1007/s10107-006-0077-1.  Google Scholar

[2]

N. Arora and L. T. Biegler, A trust region SQP algorithm for equality constrained parameter estimation with simple parameter bounds,, Comput. Optim. Appl., 28 (2004), 51.  doi: doi:10.1023/B:COAP.0000018879.40214.11.  Google Scholar

[3]

J. T. Betts, Very low-thrust trajectory optimization using a direct SQP method,, J. Comput. Appl. Math., 120 (2000), 27.  doi: doi:10.1016/S0377-0427(00)00301-0.  Google Scholar

[4]

J. V. Burke, A sequential quadratic programming method for potentially infeasible mathematical programs,, J. Math. Anal. Appl., 139 (1989), 319.  doi: doi:10.1016/0022-247X(89)90111-X.  Google Scholar

[5]

J. V. Burke and S. P. Han, A robust sequential quadratic programming method,, Math. Program., 43 (1989), 277.  doi: doi:10.1007/BF01582294.  Google Scholar

[6]

R. H. Byrd, F. E. Curtis and J. Nocedal, An inexact SQP method for equality constrained optimization,, SIAM J. Optim., 19 (2008), 351.  doi: doi:10.1137/060674004.  Google Scholar

[7]

R. H. Byrd, M. Marazzi and J. Nocedal, On the convergence of Newton iterations to non- \break stationary points,, Math. Program., 99 (2004), 127.  doi: doi:10.1007/s10107-003-0376-8.  Google Scholar

[8]

A. R. Conn, N. Gould and Ph. L. Toint, "Trust-Region Methods,", SIAM, (2000).  doi: doi:10.1137/1.9780898719857.  Google Scholar

[9]

H. Dai, "Matrix Theory,", Science Press, (2001).   Google Scholar

[10]

R. Fletcher, "Practical Methods for Optimization. Vol. 2: Constrained Optimization,", John Wiley and Sons, (1981).   Google Scholar

[11]

R. Fletcher, N. Gould, S. Leyffer, Ph. L. Toint and A. Wächter, Global convergence of a trust-region SQP-filter allgorithm for general nonlinear programming,, SIAM J. Optim., 13 (2002), 635.  doi: doi:10.1137/S1052623499357258.  Google Scholar

[12]

R. Fletcher and S. Leyffer, Nonlinear programming without a penalty function,, Math. Program., 91 (2002), 239.  doi: doi:10.1007/s101070100244.  Google Scholar

[13]

G. H. Golub and C. F. V. Loan, "Matrix Computation,", Third Edition, (1996).   Google Scholar

[14]

S. P. Han, A globally convergent method for nonlinear programming,, J. Optim. Theory Appl., 22 (1977), 297.  doi: doi:10.1007/BF00932858.  Google Scholar

[15]

M. Heinkenschloss and L. N. Vicente, Analysis of inexact trust-region SQP algorithms,, SIAM J. Optim., 12 (2002), 283.  doi: doi:10.1137/S1052623499361543.  Google Scholar

[16]

X. W. Liu, Global convergence on an active set SQP for inequality constrained optimization,, J. Comput. Appl. Math., 180 (2005), 201.  doi: doi:10.1016/j.cam.2004.10.012.  Google Scholar

[17]

X. W. Liu and J. Sun, A robust primal-dual interior point algorithm for nonlinear programs,, SIAM J. Optim., 14 (2004), 1163.  doi: doi:10.1137/S1052623402400641.  Google Scholar

[18]

X. W. Liu and Y. X. Yuan, A null-space primal-dual interior-point algorithm for nonlinear optimization with nice convergence properties,, Math. Program., 125 (2010), 163.  doi: doi:10.1007/s10107-009-0272-y.  Google Scholar

[19]

X. W. Liu and Y. X. Yuan, A sequential quadratic programming method without a penalty function or a filter for nonlinear equality constrained optimization,, SIAM J. Optim., 21 (2011), 545.  doi: 10.1137/080739884.  Google Scholar

[20]

W. Murray, Sequential quadratic programming methods for large-scale problems,, J. Comput. Optim. Appl., 7 (1997), 127.  doi: doi:10.1023/A:1008671829454.  Google Scholar

[21]

J. Nocedal and S. Wright, "Numerical Optimization,", Springer-Verlag New York, (1999).  doi: doi:10.1007/b98874.  Google Scholar

[22]

M. J. D. Powell, A fast algorithm for nonlinearly constrained optimization calculations,, in, (1977), 144.   Google Scholar

[23]

P. Spellucci, An SQP method for general nonlinear programs using only equality constrained subproblems,, Math. Program., 82 (1998), 413.  doi: doi:10.1007/BF01580078.  Google Scholar

[24]

G. W. Walster and E. R. Hansen, Computing interval parameter bounds from fallible measurements using overdetermined (Tall) systems of nonlinear equations,, Lecture Notes in, (2002), 171.   Google Scholar

[25]

S. J. Wright, Modifying SQP for degenerate problems,, SIAM J. Optim., 13 (2002), 470.  doi: doi:10.1137/S1052623498333731.  Google Scholar

[26]

Y. X. Yuan, On the convergence of a new trust region algorithm,, Numer. Math., 70 (1995), 515.  doi: doi:10.1007/s002110050133.  Google Scholar

[1]

Karoline Disser. Global existence and uniqueness for a volume-surface reaction-nonlinear-diffusion system. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 321-330. doi: 10.3934/dcdss.2020326

[2]

Adel M. Al-Mahdi, Mohammad M. Al-Gharabli, Salim A. Messaoudi. New general decay result for a system of viscoelastic wave equations with past history. Communications on Pure & Applied Analysis, 2021, 20 (1) : 389-404. doi: 10.3934/cpaa.2020273

[3]

Mengni Li. Global regularity for a class of Monge-Ampère type equations with nonzero boundary conditions. Communications on Pure & Applied Analysis, 2021, 20 (1) : 301-317. doi: 10.3934/cpaa.2020267

[4]

Xavier Carvajal, Liliana Esquivel, Raphael Santos. On local well-posedness and ill-posedness results for a coupled system of mkdv type equations. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020382

[5]

Fathalla A. Rihan, Hebatallah J. Alsakaji. Stochastic delay differential equations of three-species prey-predator system with cooperation among prey species. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020468

[6]

Eduard Feireisl, Elisabetta Rocca, Giulio Schimperna, Arghir Zarnescu. Weak sequential stability for a nonlinear model of nematic electrolytes. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 219-241. doi: 10.3934/dcdss.2020366

[7]

Yahia Zare Mehrjerdi. A new methodology for solving bi-criterion fractional stochastic programming. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020054

[8]

Mathew Gluck. Classification of solutions to a system of $ n^{\rm th} $ order equations on $ \mathbb R^n $. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5413-5436. doi: 10.3934/cpaa.2020246

[9]

Thierry Horsin, Mohamed Ali Jendoubi. On the convergence to equilibria of a sequence defined by an implicit scheme. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020465

[10]

Christopher S. Goodrich, Benjamin Lyons, Mihaela T. Velcsov. Analytical and numerical monotonicity results for discrete fractional sequential differences with negative lower bound. Communications on Pure & Applied Analysis, 2021, 20 (1) : 339-358. doi: 10.3934/cpaa.2020269

[11]

Parikshit Upadhyaya, Elias Jarlebring, Emanuel H. Rubensson. A density matrix approach to the convergence of the self-consistent field iteration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 99-115. doi: 10.3934/naco.2020018

[12]

Haiyu Liu, Rongmin Zhu, Yuxian Geng. Gorenstein global dimensions relative to balanced pairs. Electronic Research Archive, 2020, 28 (4) : 1563-1571. doi: 10.3934/era.2020082

[13]

Jianhua Huang, Yanbin Tang, Ming Wang. Singular support of the global attractor for a damped BBM equation. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020345

[14]

Bernold Fiedler. Global Hopf bifurcation in networks with fast feedback cycles. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 177-203. doi: 10.3934/dcdss.2020344

[15]

Thomas Frenzel, Matthias Liero. Effective diffusion in thin structures via generalized gradient systems and EDP-convergence. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 395-425. doi: 10.3934/dcdss.2020345

[16]

Cheng He, Changzheng Qu. Global weak solutions for the two-component Novikov equation. Electronic Research Archive, 2020, 28 (4) : 1545-1562. doi: 10.3934/era.2020081

[17]

Touria Karite, Ali Boutoulout. Global and regional constrained controllability for distributed parabolic linear systems: RHum approach. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020055

[18]

Abdelghafour Atlas, Mostafa Bendahmane, Fahd Karami, Driss Meskine, Omar Oubbih. A nonlinear fractional reaction-diffusion system applied to image denoising and decomposition. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020321

[19]

Manil T. Mohan. First order necessary conditions of optimality for the two dimensional tidal dynamics system. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020045

[20]

Sumit Arora, Manil T. Mohan, Jaydev Dabas. Approximate controllability of a Sobolev type impulsive functional evolution system in Banach spaces. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020049

 Impact Factor: 

Metrics

  • PDF downloads (39)
  • HTML views (0)
  • Cited by (3)

Other articles
by authors

[Back to Top]