September  2020, 16(5): 2267-2281. 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, 2020, 16 (5) : 2267-2281. doi: 10.3934/jimo.2019053
References:
[1]

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

[2]

D. P. Bertsekas, Constrained Optimization and Lagrange Multiplier Methods, , in Computer Science and Applied Mathematics, Academic Press Inc, New York, 1982.  Google Scholar

[3]

D. P. Bertsekas, Nonlinear Programming, Athena Scientific, 1999.  Google Scholar

[4]

Yu. G. Evtushenko, Numerical Optimization Techniques, Optimization Software, New York, 1985. doi: 10.1007/978-1-4612-5022-7.  Google Scholar

[5]

Yu. G. Evtushenko and V. G. Zhadan, Barrier-projective methods for nonlinear programming, Comp.Math. Math. Phys., 34 (1994), 579-590.   Google Scholar

[6]

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

[7]

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

[8]

Yu. G. Evtushenko, Two numerical methods of solving nonlinear programming problems, Sov. Math. Dokl., 15 (1974), 420-423.   Google Scholar

[9]

A. V. Fiacco and G. P. McCormick, Sequential Unconstrained Minimization Techniques, in Nonlinear Programming, John Wiely, New York, 1968.  Google Scholar

[10]

M. Hestenes, Multiplier and gradient methods, J.Optim.Theor.Appl., 4 (1969), 303-320.  doi: 10.1007/BF00927673.  Google Scholar

[11]

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

[12]

X. X. HuangK. 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

[13]

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

[14]

L. JinL. 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

[15]

L. JinL. 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

[16]

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

[17]

L. JinH. 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

[18]

P. Q. Pan, New ODE methods for equality constrained optimization (1)-equations, J. Comput. Math., 10 (1992), 77-92.   Google Scholar

[19]

M. J. D. Powell, A method for non-linear constraints in minimizations problems in optimization, in (eds. R. Fletcher), (1969), 283–298.  Google Scholar

[20]

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

[21]

R. T. Rockafellar, Monotone operators and the proximal point algorithm, SIAM J.Control Optim., 14 (1976), 877-898.  doi: 10.1137/0314056.  Google Scholar

[22]

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

[23]

R. T. Rockafellar, Lagrange multipliers and optimality, SIAM Rev., 35 (1993), 183-238.  doi: 10.1137/1035044.  Google Scholar

[24]

H. Yamadhita, A differential equation approach to nonlinear programming, Math. Prog., 18 (1980), 155-168.  doi: 10.1007/BF01588311.  Google Scholar

[25]

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

[26]

L. W. ZhangQ. Li and X. Zhang, Two differential systems for solving nonlinear programming problems, OR Trans., 4 (2000), 33-46.   Google Scholar

show all references

References:
[1]

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

[2]

D. P. Bertsekas, Constrained Optimization and Lagrange Multiplier Methods, , in Computer Science and Applied Mathematics, Academic Press Inc, New York, 1982.  Google Scholar

[3]

D. P. Bertsekas, Nonlinear Programming, Athena Scientific, 1999.  Google Scholar

[4]

Yu. G. Evtushenko, Numerical Optimization Techniques, Optimization Software, New York, 1985. doi: 10.1007/978-1-4612-5022-7.  Google Scholar

[5]

Yu. G. Evtushenko and V. G. Zhadan, Barrier-projective methods for nonlinear programming, Comp.Math. Math. Phys., 34 (1994), 579-590.   Google Scholar

[6]

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

[7]

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

[8]

Yu. G. Evtushenko, Two numerical methods of solving nonlinear programming problems, Sov. Math. Dokl., 15 (1974), 420-423.   Google Scholar

[9]

A. V. Fiacco and G. P. McCormick, Sequential Unconstrained Minimization Techniques, in Nonlinear Programming, John Wiely, New York, 1968.  Google Scholar

[10]

M. Hestenes, Multiplier and gradient methods, J.Optim.Theor.Appl., 4 (1969), 303-320.  doi: 10.1007/BF00927673.  Google Scholar

[11]

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

[12]

X. X. HuangK. 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

[13]

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

[14]

L. JinL. 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

[15]

L. JinL. 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

[16]

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

[17]

L. JinH. 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

[18]

P. Q. Pan, New ODE methods for equality constrained optimization (1)-equations, J. Comput. Math., 10 (1992), 77-92.   Google Scholar

[19]

M. J. D. Powell, A method for non-linear constraints in minimizations problems in optimization, in (eds. R. Fletcher), (1969), 283–298.  Google Scholar

[20]

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

[21]

R. T. Rockafellar, Monotone operators and the proximal point algorithm, SIAM J.Control Optim., 14 (1976), 877-898.  doi: 10.1137/0314056.  Google Scholar

[22]

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

[23]

R. T. Rockafellar, Lagrange multipliers and optimality, SIAM Rev., 35 (1993), 183-238.  doi: 10.1137/1035044.  Google Scholar

[24]

H. Yamadhita, A differential equation approach to nonlinear programming, Math. Prog., 18 (1980), 155-168.  doi: 10.1007/BF01588311.  Google Scholar

[25]

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

[26]

L. W. ZhangQ. Li and X. Zhang, Two differential systems for solving nonlinear programming problems, OR Trans., 4 (2000), 33-46.   Google Scholar

Figure 1.  Performances of the variable $ x $ and $ z $ in Problem 71
Figure 2.  Performances of the variable $ x $ and $ z $ in Problem 53
Figure 3.  Performances of the variable $ x $ and $ z $ in Problem 100
Figure 4.  Performances of the variable $ x $ and $ z $ in Problem 113
Figure 5.  Performances of the variable x and z in Problem 100
Figure 6.  Performances of the cost function and the objective function in Problem 100
Figure 7.  Performances of the variable x and z in Problem 113
Figure 8.  Performances of the cost function and the objective function in Problem 113
Table 1.  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
[1]

Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023

[2]

Mohsen Abdolhosseinzadeh, Mir Mohammad Alipour. Design of experiment for tuning parameters of an ant colony optimization method for the constrained shortest Hamiltonian path problem in the grid networks. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 321-332. doi: 10.3934/naco.2020028

[3]

Pavol Bokes. Exact and WKB-approximate distributions in a gene expression model with feedback in burst frequency, burst size, and protein stability. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021126

[4]

V. Vijayakumar, R. Udhayakumar, K. Kavitha. On the approximate controllability of neutral integro-differential inclusions of Sobolev-type with infinite delay. Evolution Equations & Control Theory, 2021, 10 (2) : 271-296. doi: 10.3934/eect.2020066

[5]

Zehui Jia, Xue Gao, Xingju Cai, Deren Han. The convergence rate analysis of the symmetric ADMM for the nonconvex separable optimization problems. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1943-1971. doi: 10.3934/jimo.2020053

[6]

Eduardo Casas, Christian Clason, Arnd Rösch. Preface special issue on system modeling and optimization. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021008

[7]

Jun Moon. Linear-quadratic mean-field type stackelberg differential games for stochastic jump-diffusion systems. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021026

[8]

Nizami A. Gasilov. Solving a system of linear differential equations with interval coefficients. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2739-2747. doi: 10.3934/dcdsb.2020203

[9]

Abdulrazzaq T. Abed, Azzam S. Y. Aladool. Applying particle swarm optimization based on Padé approximant to solve ordinary differential equation. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2021008

[10]

Bin Pei, Yong Xu, Yuzhen Bai. Convergence of p-th mean in an averaging principle for stochastic partial differential equations driven by fractional Brownian motion. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 1141-1158. doi: 10.3934/dcdsb.2019213

[11]

Yongjian Liu, Qiujian Huang, Zhouchao Wei. Dynamics at infinity and Jacobi stability of trajectories for the Yang-Chen system. Discrete & Continuous Dynamical Systems - B, 2021, 26 (6) : 3357-3380. doi: 10.3934/dcdsb.2020235

[12]

Yinsong Bai, Lin He, Huijiang Zhao. Nonlinear stability of rarefaction waves for a hyperbolic system with Cattaneo's law. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021049

[13]

Zengyun Wang, Jinde Cao, Zuowei Cai, Lihong Huang. Finite-time stability of impulsive differential inclusion: Applications to discontinuous impulsive neural networks. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2677-2692. doi: 10.3934/dcdsb.2020200

[14]

Kehan Si, Zhenda Xu, Ka Fai Cedric Yiu, Xun Li. Open-loop solvability for mean-field stochastic linear quadratic optimal control problems of Markov regime-switching system. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021074

[15]

Shoufeng Ji, Jinhuan Tang, Minghe Sun, Rongjuan Luo. Multi-objective optimization for a combined location-routing-inventory system considering carbon-capped differences. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021051

[16]

Wenjuan Zhao, Shunfu Jin, Wuyi Yue. A stochastic model and social optimization of a blockchain system based on a general limited batch service queue. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1845-1861. doi: 10.3934/jimo.2020049

[17]

Patrick Henning, Anders M. N. Niklasson. Shadow Lagrangian dynamics for superfluidity. Kinetic & Related Models, 2021, 14 (2) : 303-321. doi: 10.3934/krm.2021006

[18]

Izumi Takagi, Conghui Zhang. Existence and stability of patterns in a reaction-diffusion-ODE system with hysteresis in non-uniform media. Discrete & Continuous Dynamical Systems, 2021, 41 (7) : 3109-3140. doi: 10.3934/dcds.2020400

[19]

Xu Pan, Liangchen Wang. Boundedness and asymptotic stability in a quasilinear two-species chemotaxis system with nonlinear signal production. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021064

[20]

Yuri Chekanov, Felix Schlenk. Notes on monotone Lagrangian twist tori. Electronic Research Announcements, 2010, 17: 104-121. doi: 10.3934/era.2010.17.104

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (121)
  • HTML views (578)
  • Cited by (0)

Other articles
by authors

[Back to Top]