Differential equation method based on approximate augmented Lagrangian for nonlinear programming

Li Jin; Hongying Huang

doi:10.3934/jimo.2019053

Article Contents

2020, Volume 16, Issue 5: 2267-2281. Doi: 10.3934/jimo.2019053

This issue Previous Article Improved SVRG for finite sum structure optimization with application to binary classification Next Article Two nonparametric approaches to mean absolute deviation portfolio selection model

Differential equation method based on approximate augmented Lagrangian for nonlinear programming

Li Jin and
Hongying Huang^,

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
^* Corresponding author: Hongying Huang

Received: May 2018

Revised: February 2019

Early access: May 2019

Published: August 2020

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

Abstract Full Text(HTML) Figure(8) / Table(1) Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 90C30, 90C48; Secondary: 90C59.

Citation:

Full Text(HTML)

Figure 1. Performances of the variable $ x $ and $ z $ in Problem 71

Download: Full-size image PowerPoint slide

Figure 2. Performances of the variable $ x $ and $ z $ in Problem 53

Download: Full-size image PowerPoint slide

Figure 3. Performances of the variable $ x $ and $ z $ in Problem 100

Download: Full-size image PowerPoint slide

Figure 4. Performances of the variable $ x $ and $ z $ in Problem 113

Download: Full-size image PowerPoint slide

Figure 5. Performances of the variable x and z in Problem 100

Download: Full-size image PowerPoint slide

Figure 6. Performances of the cost function and the objective function in Problem 100

Download: Full-size image PowerPoint slide

Figure 7. Performances of the variable x and z in Problem 113

Download: Full-size image PowerPoint slide

Figure 8. Performances of the cost function and the objective function in Problem 113

Download: Full-size image PowerPoint slide

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

| Show Table

DownLoad: CSV

Related Papers

Cited by

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.
[2]	D. P. Bertsekas, Constrained Optimization and Lagrange Multiplier Methods, , in Computer Science and Applied Mathematics, Academic Press Inc, New York, 1982.
[3]	D. P. Bertsekas, Nonlinear Programming, Athena Scientific, 1999.
[4]	Yu. G. Evtushenko, Numerical Optimization Techniques, Optimization Software, New York, 1985. doi: 10.1007/978-1-4612-5022-7.
[5]	Yu. G. Evtushenko and V. G. Zhadan, Barrier-projective methods for nonlinear programming, Comp.Math. Math. Phys., 34 (1994), 579-590.
[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.
[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.
[8]	Yu. G. Evtushenko, Two numerical methods of solving nonlinear programming problems, Sov. Math. Dokl., 15 (1974), 420-423.
[9]	A. V. Fiacco and G. P. McCormick, Sequential Unconstrained Minimization Techniques, in Nonlinear Programming, John Wiely, New York, 1968.
[10]	M. Hestenes, Multiplier and gradient methods, J.Optim.Theor.Appl., 4 (1969), 303-320. doi: 10.1007/BF00927673.
[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.
[12]	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.
[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.
[14]	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.
[15]	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.
[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.
[17]	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.
[18]	P. Q. Pan, New ODE methods for equality constrained optimization (1)-equations, J. Comput. Math., 10 (1992), 77-92.
[19]	M. J. D. Powell, A method for non-linear constraints in minimizations problems in optimization, in (eds. R. Fletcher), (1969), 283–298.
[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.
[21]	R. T. Rockafellar, Monotone operators and the proximal point algorithm, SIAM J.Control Optim., 14 (1976), 877-898. doi: 10.1137/0314056.
[22]	R. T. Rockafellar, Augmented Lagrange multiplier functions and duality in nonconvex programming, SIAM J. Control, 12 (1974), 268-285. doi: 10.1137/0312021.
[23]	R. T. Rockafellar, Lagrange multipliers and optimality, SIAM Rev., 35 (1993), 183-238. doi: 10.1137/1035044.
[24]	H. Yamadhita, A differential equation approach to nonlinear programming, Math. Prog., 18 (1980), 155-168. doi: 10.1007/BF01588311.
[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.
[26]	L. W. Zhang, Q. Li and X. Zhang, Two differential systems for solving nonlinear programming problems, OR Trans., 4 (2000), 33-46.