    doi: 10.3934/jimo.2019053

## Differential equation method based on approximate augmented Lagrangian for nonlinear programming

 School of Mathematics, Zhejiang Ocean University, Key Laboratory of Oceanographic Big Data Mining & Application of Zhejiang Province, Zhoushan, Zhejiang 316022, China

* Corresponding author: Hongying Huang

Received  May 2018 Revised  February 2019 Published  May 2019

Fund Project: The research is supported by the National Natural Science Foundation of China under Grant Nos.61673352 and 11771398

This paper analyzes the approximate augmented Lagrangian dynamical systems for constrained optimization. We formulate the differential systems based on first derivatives and second derivatives of the approximate augmented Lagrangian. The solution of the original optimization problems can be obtained at the equilibrium point of the differential equation systems, which lead the dynamic trajectory into the feasible region. Under suitable conditions, the asymptotic stability of the differential systems and local convergence properties of their Euler discrete schemes are analyzed, including the locally quadratic convergence rate of the discrete sequence for the second derivatives based differential system. The transient behavior of the differential equation systems is simulated and the validity of the approach is verified with numerical experiments.

Citation: Li Jin, Hongying Huang. Differential equation method based on approximate augmented Lagrangian for nonlinear programming. Journal of Industrial & Management Optimization, doi: 10.3934/jimo.2019053
##### References:
  K. J. Arrow and L. Hurwicz, Reduction of constrained maxima to saddle point problems, in Proceedings of the 3rd Berkeley Symposium on Mathematical Statistics and Probability, (eds. J.Neyman), University of California Press, Berkeley, (1956), 1–20. Google Scholar  D. P. Bertsekas, Constrained Optimization and Lagrange Multiplier Methods, , in Computer Science and Applied Mathematics, Academic Press Inc, New York, 1982. Google Scholar  D. P. Bertsekas, Nonlinear Programming, Athena Scientific, 1999. Google Scholar  Yu. G. Evtushenko, Numerical Optimization Techniques, Optimization Software, New York, 1985. doi: 10.1007/978-1-4612-5022-7.  Google Scholar  Yu. G. Evtushenko and V. G. Zhadan, Barrier-projective methods for nonlinear programming, Comp.Math. Math. Phys., 34 (1994), 579-590. Google Scholar  Yu. G. Evtushenko and V. G. Zhandan, Stable barrier-projection and barrier-Newton methods in nonlinear programming, Comput. Optim. Appl., 3 (1994), 289-303.  doi: 10.1007/BF01299205.  Google Scholar  Yu. G. Evtushenko and V. G. Zhandan, Stable barrier-projection and barrier-Newton methods for linear and nonlinear programming, in Algorithms for Continuous Optimization(eds.E. Spedicato), Kulwer Academic Publishers, 434 (1994), 255–285. Google Scholar  Yu. G. Evtushenko, Two numerical methods of solving nonlinear programming problems, Sov. Math. Dokl., 15 (1974), 420-423.   Google Scholar  A. V. Fiacco and G. P. McCormick, Sequential Unconstrained Minimization Techniques, in Nonlinear Programming, John Wiely, New York, 1968. Google Scholar  M. Hestenes, Multiplier and gradient methods, J.Optim.Theor.Appl., 4 (1969), 303-320.  doi: 10.1007/BF00927673.  Google Scholar  W. Hock and K. Schittkowski, Test Examples for Nonlinear Programming Codes, in Lecture Notes Economics and Mathematical Systems, Springer-Verlag, Berlin Heidelberg-New York, 1981. doi: 10.1007/BF00934594.  Google Scholar  X. X. Huang, K. L. Teo and X. Q. Yang, Approximate augmented Lagrangian functions and nonlinear semidefinite programs, Acta Mathematica Sinica (English Series), 22 (2006), 1283-1296.  doi: 10.1007/s10114-005-0702-6.  Google Scholar  A. Ioffe, Necessary and sufficient conditions for a local minimum 3: Second-order conditions and augmented duality, SIAM J. Control Optim., 17 (1979), 266-288.  doi: 10.1137/0317021.  Google Scholar  L. Jin, L. W. Zhang and X. T. Xiao, Two differential equation systems for equality-constrained optimization, Appl. Math. Comput., 190 (2007), 1030-1039.  doi: 10.1016/j.amc.2006.11.041.  Google Scholar  L. Jin, L. W. Zhang and X. T. Xiao, Two differential equation systems for inequality constrained optimization, Appl. Math. Comput., 188 (2007), 1334-1343.  doi: 10.1016/j.amc.2006.10.085.  Google Scholar  L. Jin, A stable differential equation approach for inequality constrained optimization problems, Appl. Math. Comput., 206 (2008), 186-192.  doi: 10.1016/j.amc.2008.09.007.  Google Scholar  L. Jin, H. X. Yu and Z. S. Liu, Differential systems for constrained optimization via a nonlinear augmented Lagrangian, Appl. Math. Comput., 235 (2014), 482-491.  doi: 10.1016/j.amc.2014.02.097.  Google Scholar  P. Q. Pan, New ODE methods for equality constrained optimization (1)-equations, J. Comput. Math., 10 (1992), 77-92. Google Scholar  M. J. D. Powell, A method for non-linear constraints in minimizations problems in optimization, in (eds. R. Fletcher), (1969), 283–298. Google Scholar  R. T. Rockafellar, Augmented Lagrangians and applications of the proximal point algorithm in convex programming, Math.Oper.Res., 1 (1976), 97-116.  doi: 10.1287/moor.1.2.97.  Google Scholar  R. T. Rockafellar, Monotone operators and the proximal point algorithm, SIAM J.Control Optim., 14 (1976), 877-898.  doi: 10.1137/0314056.  Google Scholar  R. T. Rockafellar, Augmented Lagrange multiplier functions and duality in nonconvex programming, SIAM J. Control, 12 (1974), 268-285.  doi: 10.1137/0312021.  Google Scholar  R. T. Rockafellar, Lagrange multipliers and optimality, SIAM Rev., 35 (1993), 183-238.  doi: 10.1137/1035044.  Google Scholar  H. Yamadhita, A differential equation approach to nonlinear programming, Math. Prog., 18 (1980), 155-168.  doi: 10.1007/BF01588311.  Google Scholar  L. W. Zhang, A modified version to the differential system of Evtushenko and Zhanda for solving nonlinear programming, in Numerical Linear Algebra and Optimization(eds.Ya-xiang Yuan), Science Press, (1999), 161–168. Google Scholar  L. W. Zhang, Q. Li and X. Zhang, Two differential systems for solving nonlinear programming problems, OR Trans., 4 (2000), 33-46.   Google Scholar

show all references

##### References:
  K. J. Arrow and L. Hurwicz, Reduction of constrained maxima to saddle point problems, in Proceedings of the 3rd Berkeley Symposium on Mathematical Statistics and Probability, (eds. J.Neyman), University of California Press, Berkeley, (1956), 1–20. Google Scholar  D. P. Bertsekas, Constrained Optimization and Lagrange Multiplier Methods, , in Computer Science and Applied Mathematics, Academic Press Inc, New York, 1982. Google Scholar  D. P. Bertsekas, Nonlinear Programming, Athena Scientific, 1999. Google Scholar  Yu. G. Evtushenko, Numerical Optimization Techniques, Optimization Software, New York, 1985. doi: 10.1007/978-1-4612-5022-7.  Google Scholar  Yu. G. Evtushenko and V. G. Zhadan, Barrier-projective methods for nonlinear programming, Comp.Math. Math. Phys., 34 (1994), 579-590. Google Scholar  Yu. G. Evtushenko and V. G. Zhandan, Stable barrier-projection and barrier-Newton methods in nonlinear programming, Comput. Optim. Appl., 3 (1994), 289-303.  doi: 10.1007/BF01299205.  Google Scholar  Yu. G. Evtushenko and V. G. Zhandan, Stable barrier-projection and barrier-Newton methods for linear and nonlinear programming, in Algorithms for Continuous Optimization(eds.E. Spedicato), Kulwer Academic Publishers, 434 (1994), 255–285. Google Scholar  Yu. G. Evtushenko, Two numerical methods of solving nonlinear programming problems, Sov. Math. Dokl., 15 (1974), 420-423.   Google Scholar  A. V. Fiacco and G. P. McCormick, Sequential Unconstrained Minimization Techniques, in Nonlinear Programming, John Wiely, New York, 1968. Google Scholar  M. Hestenes, Multiplier and gradient methods, J.Optim.Theor.Appl., 4 (1969), 303-320.  doi: 10.1007/BF00927673.  Google Scholar  W. Hock and K. Schittkowski, Test Examples for Nonlinear Programming Codes, in Lecture Notes Economics and Mathematical Systems, Springer-Verlag, Berlin Heidelberg-New York, 1981. doi: 10.1007/BF00934594.  Google Scholar  X. X. Huang, K. L. Teo and X. Q. Yang, Approximate augmented Lagrangian functions and nonlinear semidefinite programs, Acta Mathematica Sinica (English Series), 22 (2006), 1283-1296.  doi: 10.1007/s10114-005-0702-6.  Google Scholar  A. Ioffe, Necessary and sufficient conditions for a local minimum 3: Second-order conditions and augmented duality, SIAM J. Control Optim., 17 (1979), 266-288.  doi: 10.1137/0317021.  Google Scholar  L. Jin, L. W. Zhang and X. T. Xiao, Two differential equation systems for equality-constrained optimization, Appl. Math. Comput., 190 (2007), 1030-1039.  doi: 10.1016/j.amc.2006.11.041.  Google Scholar  L. Jin, L. W. Zhang and X. T. Xiao, Two differential equation systems for inequality constrained optimization, Appl. Math. Comput., 188 (2007), 1334-1343.  doi: 10.1016/j.amc.2006.10.085.  Google Scholar  L. Jin, A stable differential equation approach for inequality constrained optimization problems, Appl. Math. Comput., 206 (2008), 186-192.  doi: 10.1016/j.amc.2008.09.007.  Google Scholar  L. Jin, H. X. Yu and Z. S. Liu, Differential systems for constrained optimization via a nonlinear augmented Lagrangian, Appl. Math. Comput., 235 (2014), 482-491.  doi: 10.1016/j.amc.2014.02.097.  Google Scholar  P. Q. Pan, New ODE methods for equality constrained optimization (1)-equations, J. Comput. Math., 10 (1992), 77-92. Google Scholar  M. J. D. Powell, A method for non-linear constraints in minimizations problems in optimization, in (eds. R. Fletcher), (1969), 283–298. Google Scholar  R. T. Rockafellar, Augmented Lagrangians and applications of the proximal point algorithm in convex programming, Math.Oper.Res., 1 (1976), 97-116.  doi: 10.1287/moor.1.2.97.  Google Scholar  R. T. Rockafellar, Monotone operators and the proximal point algorithm, SIAM J.Control Optim., 14 (1976), 877-898.  doi: 10.1137/0314056.  Google Scholar  R. T. Rockafellar, Augmented Lagrange multiplier functions and duality in nonconvex programming, SIAM J. Control, 12 (1974), 268-285.  doi: 10.1137/0312021.  Google Scholar  R. T. Rockafellar, Lagrange multipliers and optimality, SIAM Rev., 35 (1993), 183-238.  doi: 10.1137/1035044.  Google Scholar  H. Yamadhita, A differential equation approach to nonlinear programming, Math. Prog., 18 (1980), 155-168.  doi: 10.1007/BF01588311.  Google Scholar  L. W. Zhang, A modified version to the differential system of Evtushenko and Zhanda for solving nonlinear programming, in Numerical Linear Algebra and Optimization(eds.Ya-xiang Yuan), Science Press, (1999), 161–168. Google Scholar  L. W. Zhang, Q. Li and X. Zhang, Two differential systems for solving nonlinear programming problems, OR Trans., 4 (2000), 33-46.   Google Scholar Performances of the cost function and the objective function in Problem 100 Performances of the cost function and the objective function in Problem 113
numerical results
 Test n p q IT $S(z)$ $f(x^*)$ $F(x^*)$ P.71 4 10 1 349 8.125604 $\times10^{-10}$ 17.014 17.0140173 P.53 5 13 3 127 1.175666 $\times10^{-11}$ 4.0930 4.093023 P.100 7 4 0 967 3.829630$\times10^{-12}$ 678.6796 680.6300573 P.113 10 8 0 991 2.452665$\times10^{-12}$ 24.3062 24.306291
 Test n p q IT $S(z)$ $f(x^*)$ $F(x^*)$ P.71 4 10 1 349 8.125604 $\times10^{-10}$ 17.014 17.0140173 P.53 5 13 3 127 1.175666 $\times10^{-11}$ 4.0930 4.093023 P.100 7 4 0 967 3.829630$\times10^{-12}$ 678.6796 680.6300573 P.113 10 8 0 991 2.452665$\times10^{-12}$ 24.3062 24.306291
  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  Chunrong Chen, T. C. Edwin Cheng, Shengji Li, Xiaoqi Yang. Nonlinear augmented Lagrangian for nonconvex multiobjective optimization. Journal of Industrial & Management Optimization, 2011, 7 (1) : 157-174. doi: 10.3934/jimo.2011.7.157  Chunlin Wu, Juyong Zhang, Xue-Cheng Tai. Augmented Lagrangian method for total variation restoration with non-quadratic fidelity. Inverse Problems & Imaging, 2011, 5 (1) : 237-261. doi: 10.3934/ipi.2011.5.237  Chunrong Chen. A unified nonlinear augmented Lagrangian approach for nonconvex vector optimization. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 495-508. doi: 10.3934/naco.2011.1.495  Xueyong Wang, Yiju Wang, Gang Wang. An accelerated augmented Lagrangian method for multi-criteria optimization problem. Journal of Industrial & Management Optimization, 2020, 16 (1) : 1-9. doi: 10.3934/jimo.2018136  Qingsong Duan, Mengwei Xu, Yue Lu, Liwei Zhang. A smoothing augmented Lagrangian method for nonconvex, nonsmooth constrained programs and its applications to bilevel problems. Journal of Industrial & Management Optimization, 2019, 15 (3) : 1241-1261. doi: 10.3934/jimo.2018094  Xi-Hong Yan. A new convergence proof of augmented Lagrangian-based method with full Jacobian decomposition for structured variational inequalities. Numerical Algebra, Control & Optimization, 2016, 6 (1) : 45-54. doi: 10.3934/naco.2016.6.45  Yuan Shen, Wenxing Zhang, Bingsheng He. Relaxed augmented Lagrangian-based proximal point algorithms for convex optimization with linear constraints. Journal of Industrial & Management Optimization, 2014, 10 (3) : 743-759. doi: 10.3934/jimo.2014.10.743  Giuseppe Buttazzo, Filippo Santambrogio. Asymptotical compliance optimization for connected networks. Networks & Heterogeneous Media, 2007, 2 (4) : 761-777. doi: 10.3934/nhm.2007.2.761  Yong Xia, Yu-Jun Gong, Sheng-Nan Han. A new semidefinite relaxation for $L_{1}$-constrained quadratic optimization and extensions. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 185-195. doi: 10.3934/naco.2015.5.185  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  Qian Liu, Xinmin Yang, Heung Wing Joseph Lee. On saddle points of a class of augmented lagrangian functions. Journal of Industrial & Management Optimization, 2007, 3 (4) : 693-700. doi: 10.3934/jimo.2007.3.693  Yong Xia. New sufficient global optimality conditions for linearly constrained bivalent quadratic optimization problems. Journal of Industrial & Management Optimization, 2009, 5 (4) : 881-892. doi: 10.3934/jimo.2009.5.881  Changjun Yu, Kok Lay Teo, Liansheng Zhang, Yanqin Bai. On a refinement of the convergence analysis for the new exact penalty function method for continuous inequality constrained optimization problem. Journal of Industrial & Management Optimization, 2012, 8 (2) : 485-491. doi: 10.3934/jimo.2012.8.485  Wei Zhu, Xue-Cheng Tai, Tony Chan. Augmented Lagrangian method for a mean curvature based image denoising model. Inverse Problems & Imaging, 2013, 7 (4) : 1409-1432. doi: 10.3934/ipi.2013.7.1409  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  Jean-Baptiste Burie, Ramsès Djidjou-Demasse, Arnaud Ducrot. Slow convergence to equilibrium for an evolutionary epidemiology integro-differential system. Discrete & Continuous Dynamical Systems - B, 2017, 22 (11) : 0-0. doi: 10.3934/dcdsb.2019225  Juan Carlos Marrero, David Martín de Diego, Ari Stern. Symplectic groupoids and discrete constrained Lagrangian mechanics. Discrete & Continuous Dynamical Systems - A, 2015, 35 (1) : 367-397. doi: 10.3934/dcds.2015.35.367  Xiaodi Bai, Xiaojin Zheng, Xiaoling Sun. A survey on probabilistically constrained optimization problems. Numerical Algebra, Control & Optimization, 2012, 2 (4) : 767-778. doi: 10.3934/naco.2012.2.767  Ying Gao, Xinmin Yang, Kok Lay Teo. Optimality conditions for approximate solutions of vector optimization problems. Journal of Industrial & Management Optimization, 2011, 7 (2) : 483-496. doi: 10.3934/jimo.2011.7.483

2018 Impact Factor: 1.025