• Previous Article
    A smoothing Newton method for generalized Nash equilibrium problems with second-order cone constraints
  • NACO Home
  • This Issue
  • Next Article
    A sixth order numerical method for a class of nonlinear two-point boundary value problems
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]

Radu Ioan Boţ, Anca Grad, Gert Wanka. Sequential characterization of solutions in convex composite programming and applications to vector optimization. Journal of Industrial & Management Optimization, 2008, 4 (4) : 767-782. doi: 10.3934/jimo.2008.4.767

[2]

Songqiang Qiu, Zhongwen Chen. An adaptively regularized sequential quadratic programming method for equality constrained optimization. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-14. doi: 10.3934/jimo.2019075

[3]

Zhong Tan, Qiuju Xu, Huaqiao Wang. Global existence and convergence rates for the compressible magnetohydrodynamic equations without heat conductivity. Discrete & Continuous Dynamical Systems - A, 2015, 35 (10) : 5083-5105. doi: 10.3934/dcds.2015.35.5083

[4]

Michela Eleuteri, Pavel Krejčí. An asymptotic convergence result for a system of partial differential equations with hysteresis. Communications on Pure & Applied Analysis, 2007, 6 (4) : 1131-1143. doi: 10.3934/cpaa.2007.6.1131

[5]

Huijiang Zhao, Yinchuan Zhao. Convergence to strong nonlinear rarefaction waves for global smooth solutions of $p-$system with relaxation. Discrete & Continuous Dynamical Systems - A, 2003, 9 (5) : 1243-1262. doi: 10.3934/dcds.2003.9.1243

[6]

Jishan Fan, Fucai Li, Gen Nakamura. Convergence of the full compressible Navier-Stokes-Maxwell system to the incompressible magnetohydrodynamic equations in a bounded domain. Kinetic & Related Models, 2016, 9 (3) : 443-453. doi: 10.3934/krm.2016002

[7]

Francesca Bucci, Igor Chueshov, Irena Lasiecka. Global attractor for a composite system of nonlinear wave and plate equations. Communications on Pure & Applied Analysis, 2007, 6 (1) : 113-140. doi: 10.3934/cpaa.2007.6.113

[8]

Takashi Narazaki. Global solutions to the Cauchy problem for the weakly coupled system of damped wave equations. Conference Publications, 2009, 2009 (Special) : 592-601. doi: 10.3934/proc.2009.2009.592

[9]

Daniela Calvetti, Erkki Somersalo. Microlocal sequential regularization in imaging. Inverse Problems & Imaging, 2007, 1 (1) : 1-11. doi: 10.3934/ipi.2007.1.1

[10]

Virginia Agostiniani, Rolando Magnanini. Symmetries in an overdetermined problem for the Green's function. Discrete & Continuous Dynamical Systems - S, 2011, 4 (4) : 791-800. doi: 10.3934/dcdss.2011.4.791

[11]

Chun-Hsiung Hsia, Chang-Yeol Jung, Bongsuk Kwon. On the global convergence of frequency synchronization for Kuramoto and Winfree oscillators. Discrete & Continuous Dynamical Systems - B, 2019, 24 (7) : 3319-3334. doi: 10.3934/dcdsb.2018322

[12]

Qing Liu, Armin Schikorra. General existence of solutions to dynamic programming equations. Communications on Pure & Applied Analysis, 2015, 14 (1) : 167-184. doi: 10.3934/cpaa.2015.14.167

[13]

Ye Chen, Keith W. Hipel, D. Marc Kilgour. A multiple criteria sequential sorting procedure. Journal of Industrial & Management Optimization, 2008, 4 (3) : 407-423. doi: 10.3934/jimo.2008.4.407

[14]

Zhenbo Wang, Shu-Cherng Fang, David Y. Gao, Wenxun Xing. Global extremal conditions for multi-integer quadratic programming. Journal of Industrial & Management Optimization, 2008, 4 (2) : 213-225. doi: 10.3934/jimo.2008.4.213

[15]

Jing Quan, Zhiyou Wu, Guoquan Li. Global optimality conditions for some classes of polynomial integer programming problems. Journal of Industrial & Management Optimization, 2011, 7 (1) : 67-78. doi: 10.3934/jimo.2011.7.67

[16]

Paul B. Hermanns, Nguyen Van Thoai. Global optimization algorithm for solving bilevel programming problems with quadratic lower levels. Journal of Industrial & Management Optimization, 2010, 6 (1) : 177-196. doi: 10.3934/jimo.2010.6.177

[17]

Fuchen Zhang, Xiaofeng Liao, Chunlai Mu, Guangyun Zhang, Yi-An Chen. On global boundedness of the Chen system. Discrete & Continuous Dynamical Systems - B, 2017, 22 (4) : 1673-1681. doi: 10.3934/dcdsb.2017080

[18]

Yang Li, Yonghong Ren, Yun Wang, Jian Gu. Convergence analysis of a nonlinear Lagrangian method for nonconvex semidefinite programming with subproblem inexactly solved. Journal of Industrial & Management Optimization, 2015, 11 (1) : 65-81. doi: 10.3934/jimo.2015.11.65

[19]

Xiantao Xiao, Liwei Zhang, Jianzhong Zhang. On convergence of augmented Lagrangian method for inverse semi-definite quadratic programming problems. Journal of Industrial & Management Optimization, 2009, 5 (2) : 319-339. doi: 10.3934/jimo.2009.5.319

[20]

Dugan Nina, Ademir Fernando Pazoto, Lionel Rosier. Global stabilization of a coupled system of two generalized Korteweg-de Vries type equations posed on a finite domain. Mathematical Control & Related Fields, 2011, 1 (3) : 353-389. doi: 10.3934/mcrf.2011.1.353

 Impact Factor: 

Metrics

  • PDF downloads (7)
  • HTML views (0)
  • Cited by (1)

Other articles
by authors

[Back to Top]