A smoothing augmented Lagrangian method for nonconvex, nonsmooth constrained programs and its applications to bilevel problems

Qingsong Duan; Mengwei Xu; Yue Lu; Liwei Zhang

doi:10.3934/jimo.2018094

Article Contents

2019, Volume 15, Issue 3: 1241-1261. Doi: 10.3934/jimo.2018094

This issue Previous Article A hybrid inconsistent sustainable chemical industry evaluation method Next Article Bi-objective integrated supply chain design with transportation choices: A multi-objective particle swarm optimization

A smoothing augmented Lagrangian method for nonconvex, nonsmooth constrained programs and its applications to bilevel problems

1.
School of Mathematical Sciences, Dalian University of Technology, Dalian 116024, China
2.
School of Mathematics, Tianjin University, Tianjin, 300072, China
3.
School of Mathematical Sciences, Tianjin Normal University, Tianjin 300387, China

* Corresponding author: Mengwei Xu
* Corresponding author: Mengwei Xu

Received: July 2017

Revised: October 2017

Early access: June 2018

Published: April 2019

The second author is supported by NSFC grant 11601376. The third author is supported by NSFC grant 11601389, the Doctoral Foundation of Tianjin Normal University grant 52XB1513 and and 2017- Outstanding Young Innovation Team Cultivation Program of Tianjin Normal University grant 135202TD1703. The fourth author is supported by NSFC grant 11571059 and 11731013.

Abstract Full Text(HTML) Figure(0) / Table(2) Related Papers Cited by

Abstract

In this paper, we consider a class of nonsmooth and nonconvex optimization problem with an abstract constraint. We propose an augmented Lagrangian method for solving the problem and construct global convergence under a weakly nonsmooth Mangasarian-Fromovitz constraint qualification. We show that any accumulation point of the iteration sequence generated by the algorithm is a feasible point which satisfies the first order necessary optimality condition provided that the penalty parameters are bounded and the upper bound of the augmented Lagrangian functions along the approximated solution sequence exists. Numerical experiments show that the algorithm is efficient for obtaining stationary points of general nonsmooth and nonconvex optimization problems, including the bilevel program which will never satisfy the nonsmooth Mangasarian-Fromovitz constraint qualification.

Keywords:

Mathematics Subject Classification: 65K10, 90C26.

Citation:

Full Text(HTML)

Table 1. Mirrlees' problem

	(x^; y^)	d(x^; y^)
Algorithm 3.1	(1, 0.957504)	5.73e-006
SQP algorithm	(1.000002, 0.957598)	9.79e-005
SAL algorithm	(1.000905, 0.957459)	9.06e-004

| Show Table

DownLoad: CSV

Table 2. Example 4.4

	(x^; y^)	d(x^; y^)
Algorithm 3.1	(0.500003, 0.500003)	4.08e-006
SQP algorithm	(0.499996, 0.499996)	5.85e-006
SAL algorithm	(0.500000, 0.499995)	2.89e-005

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	ALGENCAN, http://www.ime.usp.br/＄\sim＄egbirgin/tango/.
[2]	R. Andreani, E. G. Birgin, J. M. Martínez and M. L. Schuverdt, On Augmented Lagrangian methods with general lower-level constraints, SIAM J. Optim., 18 (2007), 1286-1309. doi: 10.1137/060654797.
[3]	R. Andreani, E. G. Birgin, J. M. Martínez and M. L. Schuverdt, Augmented Lagrangian methods under the constant positive linear dependence constraint qualification, Math. Program., Ser. B, 111 (2008), 5-32. doi: 10.1007/s10107-006-0077-1.
[4]	R. Andreani, G. Haeser and M. L. Schuverdt, A relaxed constant positive linear dependence constraint qualification and applications, Math. Program., 135 (2012), 255-273. doi: 10.1007/s10107-011-0456-0.
[5]	J. F. Bard, Practical Bilevel Optimization: Algorithms and Applications, Kluwer Academic Publications, Dordrecht, Netherlands, 1998. doi: 10.1007/978-1-4757-2836-1.
[6]	D. P. Bertsekas, Constrained Optimization and Lagrangian Multiplier Methods, Academic Press, New York, 1982.
[7]	W. Bian and X. Chen, Neural network for nonsmooth, nonconvex constrained minimization via smooth approximation, IEEE Trans. Neural Netw. Learn. Syst., 25 (2014), 545-556. doi: 10.1109/TNNLS.2013.2278427.
[8]	E. G. Birgin, D. Fernández and J. M. Martínez, The boundedness of penalty parameters in an Augmented Lagrangian method with lower level constraints, Optim. Methods Soft., 27 (2012), 1001-1024. doi: 10.1080/10556788.2011.556634.
[9]	J. V. Burke and T. Hoheisel, Epi-convergent smoothing with applications to convex composite functions, SIAM J. Optim., 23 (2013), 1457-1479. doi: 10.1137/120889812.
[10]	J. V. Burke, T. Hoheisel and C. Kanzow, Gradient consistency for integral-convolution smoothing functions, Set-Valued Var. Anal., 21 (2013), 359-376. doi: 10.1007/s11228-013-0235-6.
[11]	B. Chen and X. Chen, A global and local superlinear continuation-smoothing method for $P_0$ and $R_0$ NCP or monotone NCP, SIAM J. Optim., 9 (1999), 624-645. doi: 10.1137/S1052623497321109.
[12]	X. Chen, Smoothing methods for nonsmooth, nonconvex minimization, Math. Program., 134 (2012), 71-99. doi: 10.1007/s10107-012-0569-0.
[13]	B. Chen and P. T. Harker, A non-interior-point continuation method for linear complementarity problems, SIAM J. Matrix Anal. Appl., 14 (1993), 1168-1190. doi: 10.1137/0614081.
[14]	X. Chen, L. Guo, Z. Lu and J. J. Ye, An augmented Lagrangian method for non-Lipschitz nonconvex programming, SIAM J. Numer. Anal., 55 (2017), 168-193. doi: 10.1137/15M1052834.
[15]	C. Chen and O. L. Mangasarian, A class of smoothing functions for nonlinear and mixed complementarity problems, Math. Program., 71 (1995), 51-70. doi: 10.1007/BF01592244.
[16]	X. Chen, R. S. Womersley and J. J. Ye, Minimizing the condition number of a gram matrix, SIAM J. Optim., 21 (2011), 127-148. doi: 10.1137/100786022.
[17]	F. H. Clarke, Optimization and Nonsmooth Analysis, Wiley-Interscience, New York, 1983.
[18]	F. H. Clarke, Yu. S. Ledyaev, R. J. Stern and P. R. Wolenski, Nonsmooth Analysis and Control Theory, Springer, New York, 1998.
[19]	A. R. Conn, N. I. M. Gould and Ph. L. Toint, A globally convergent augmented Lagrangian algorithm for optimization with general constraints and simple bound, SIAM J. Numer. Anal., 28 (1991), 545-572. doi: 10.1137/0728030.
[20]	A. R. Conn, N. I. M. Gould and Ph. L. Toint, Trust Region Methods, MPS/SIAM Series on Optimization, SIAM, Philadelphia, PA, 2000. doi: 10.1137/1.9780898719857.
[21]	F. E. Curtis, H. Jiang and D. P. Robinson, An adaptive augmented Lagrangian method for large-scale constrained optimization, Math. Program., 152 (2015), 201-245. doi: 10.1007/s10107-014-0784-y.
[22]	F. E. Curtis and M. L. Overton, A sequential quadratic programming algorithm for nonconvex, nonsmooth constrained optimization, SIAM J. Optim., 22 (2012), 474-500. doi: 10.1137/090780201.
[23]	S. Dempe, Foundations of Bilevel Programming, Kluwer Academic Publishers, 2002.
[24]	S. Dempe, Annotated bibliography on bilevel programming and mathematical programs with equilibrium constraints, Optim., 52 (2003), 333-359. doi: 10.1080/0233193031000149894.
[25]	M. R. Hestenes, Multiplier and gradient methods, J. Optim. Theory Appl., 4 (1969), 303-320. doi: 10.1007/BF00927673.
[26]	C. Kanzow, Some noninterior continuation methods for linear complementarity problems, SIAM J. Matrix Anal. Appl., 17 (1996), 851-868. doi: 10.1137/S0895479894273134.
[27]	LANCELOT, http://www.cse.scitech.ac.uk/nag/lancelot/lancelot.shtml.
[28]	G. H. Lin, M. Xu and J. J. Ye, On solving simple bilevel programs with a nonconvex lower level program, Math. Program., series A, 144 (2014), 277-305. doi: 10.1007/s10107-013-0633-4.
[29]	Z. Lu and Y. Zhang, An augmented Lagrangian approach for sparse principal component analysis, Math. Program. series A, 135 (2012), 149-193. doi: 10.1007/s10107-011-0452-4.
[30]	J. Mirrlees, The theory of moral hazard and unobservable behaviour: Part Ⅰ, Rev. Econ. Stud., 66 (1999), 3-22. doi: 10.1093/acprof:oso/9780198295211.003.0020.
[31]	A. Mitsos and P. Barton, A Test Set for Bilevel Programs, Technical Report, Massachusetts Institute of Technology, 2006.
[32]	B. S. Mordukhovich, Variational Analysis and Generalized Differentiation, Vol. 1: Basic Theory, Vol. 2: Applications, Springer, 2006.
[33]	Y. Nesterov, Smoothing minimization of nonsmooth functions, Math. Program., 103 (2005), 127-152. doi: 10.1007/s10107-004-0552-5.
[34]	J. V. Outrata, On the numerical solution of a class of Stackelberg problems, Z. Oper. Res., 34 (1990), 255-277. doi: 10.1007/BF01416737.
[35]	M. J. D. Powell, A method for nonlinear constraints in minimization problems, in Optimization(eds. R. Fletcher), 283-298, London and New York, 1969. Academic Press
[36]	R. T. Rockafellar, Convex Analysis, Princeton University Press, New Jersey, 1970.
[37]	R. T. Rockfellar, A dual approach to solving nonlinear programming problems by unconstrained optimization, Math. Program., 5 (1973), 354-373. doi: 10.1007/BF01580138.
[38]	R. T. Rockfellar, Augmented Lagrange multiplier functions and duality in nonconvex programming, SIAM J. Con., 12 (1974), 268-285. doi: 10.1137/0312021.
[39]	R. T. Rockfellar, Monotone operators and the proximal point algorithm, SIAM J. Con. Optim., 14 (1976), 877-898. doi: 10.1137/0314056.
[40]	R. T. Rockafellar and R. J.-B. Wets, Variational Analysis, Springer, Berlin, 1998. doi: 10.1007/978-3-642-02431-3.
[41]	K. Shimizu, Y. Ishizuka and J. F. Bard, Nondifferentiable and Two-Level Mathematical Programming, Kluwer Academic Publishers, Boston, 1997. doi: 10.1007/978-1-4615-6305-1.
[42]	S. Smale, Algorithms for solving equations, In: Proceedings of the International Congress of Mathematicians, Berkeley, CA., (1986), 172-195
[43]	L. N. Vicente and P. H. Calamai, Bilevel and multilevel programming: A bibliography review, J. Global Optim., 5 (1994), 291-306. doi: 10.1007/BF01096458.
[44]	M. Xu and J. J. Ye, A smoothing augmented Lagrangian method for solving simple bilevel programs, Compu. Optim. App., 59 (2014), 353-377. doi: 10.1007/s10589-013-9627-7.
[45]	M. Xu, J. J. Ye and L. Zhang, Smoothing sequential quadratic programming method for solving nonconvex, nonsmooth constrained optimization problems, SIAM J. Optim., 25 (2015), 1388-1410. doi: 10.1137/140971580.
[46]	M. Xu, J. J. Ye and L. Zhang, Smoothing augmented Lagrangian method for nonsmooth constrained optimization problems, J. Glob. Optim., 62 (2015), 675-694. doi: 10.1007/s10898-014-0242-7.
[47]	J. J. Ye and D. L. Zhu, Optimality conditions for bilevel programming problems, Optim., 33 (1995), 9-27. doi: 10.1080/02331939508844060.
[48]	J. J. Ye and D. L. Zhu, A note on optimality conditions for bilevel programming problems, Optim., 39 (1997), 361-366. doi: 10.1080/02331939708844290.
[49]	J. J. Ye and D. L. Zhu, New necessary optimality conditions for bilevel programs by combining MPEC and the value function approach, SIAM J. Optim., 20 (2010), 1885-1905. doi: 10.1137/080725088.