A nonmonotone trust-region method for generalized Nash equilibrium and related problems with strong convergence properties. (English) Zbl 1390.90515

Summary: The generalized Nash equilibrium problem (GNEP) is often difficult to solve by Newton-type methods since the problem tends to have locally nonunique solutions. Here we take an existing trust-region method which is known to be locally fast convergent under a relatively mild error bound condition, and modify this method by a nonmonotone strategy in order to obtain a more reliable and efficient solver. The nonmonotone trust-region method inherits the nice local convergence properties of its monotone counterpart and is also shown to have the same global convergence properties. Numerical results indicate that the nonmonotone trust-region method is significantly better than the monotone version, and is at least competitive to an existing software applied to the same reformulation used within our trust-region framework. Additional tests on quasi-variational inequalities (QVI) are also presented to validate efficiency of the proposed extension.


90C30 Nonlinear programming
65H10 Numerical computation of solutions to systems of equations


Full Text: DOI


[1] Bellavia, S; Macconi, M; Morini, B, An affine scaling trust-region approach to bound-constrained nonlinear systems, Appl. Numer. Math., 44, 180-257, (2003) · Zbl 1018.65067
[2] Bellavia, S; Macconi, M; Morini, B, STRSCNE: a scaled trust region solver for constrained nonlinear equations, Comput. Optim. Appl., 28, 31-50, (2004) · Zbl 1056.90128
[3] Bertsekas, D.P.: Nonlinear Programming, 2nd edn. Athena Scientific, Belmont (1999) · Zbl 1015.90077
[4] Calamai, PH; Moré, JJ, Projected gradient methods for linear constrained problems, Math. Program., 39, 93-116, (1987) · Zbl 0634.90064
[5] Dan, H; Yamashita, N; Fukushima, M, Convergence properties of the inexact Levenberg-Marquardt method under local error bound conditions, Optim. Methods Softw., 17, 605-626, (2002) · Zbl 1030.65049
[6] Dolan, ED; Moré, JJ, Benchmarking optimization software with performance profiles, Math. Program., 91, 201-213, (2002) · Zbl 1049.90004
[7] Dreves, A; Facchinei, F; Fischer, A; Herrich, M, A new error bound result for generalized Nash equilibrium problems and its algorithmic application, Comput. Optim. Appl., 59, 63-84, (2014) · Zbl 1307.91117
[8] Dreves, A; Facchinei, F; Kanzow, C; Sagratella, S, On the solution of the KKT conditions of generalized Nash equilibrium problems, SIAM J. Optim., 21, 1082-1108, (2011) · Zbl 1230.90176
[9] Facchinei, F; Kanzow, C; Sagratella, S, QVILIB: a library of quasi-variational inequality test problems, Pac. J. Optim., 9, 225-250, (2013) · Zbl 1267.65078
[10] Facchinei, F; Kanzow, C; Sagratella, S, Solving quasi-variational inequalities via their KKT conditions, Math. Program., 114, 369-412, (2014) · Zbl 1293.65100
[11] Facchinei, F; Kanzow, C, Generalized Nash equilibrium problems, Ann. Oper. Res., 175, 177-211, (2010) · Zbl 1185.91016
[12] Facchinei, F; Kanzow, C; Karl, S; Sagratella, S, The semismooth Newton method for the solution of quasi-variational inequalities, Comput. Optim. Appl., 62, 85-109, (2015) · Zbl 1331.90083
[13] Fan, J; Yuan, Y, On the quadratic convergence of the Levenberg-Marquardt method without nonsingularity assumption, Computing, 74, 23-39, (2005) · Zbl 1076.65047
[14] Fischer, A; Herrich, M; Schönefeld, K, Generalized Nash equilibrium problems—recent advances and challenges, Pesquisa Operacional, 34, 521-558, (2014)
[15] Fischer, A; Shukla, PK; Wang, M, On the inexactness level of robust Levenberg-Marquardt methods, Optimization, 59, 273-287, (2010) · Zbl 1196.65097
[16] Herrich, M.: Local convergence of Newton-type methods for nonsmooth constrained equations and applications. Ph.D. Thesis, Institute of Mathematics, Technical University of Dresden, Germany (2014) · Zbl 1030.65049
[17] Izmailov, AF; Solodov, MV, On error bounds and Newton-type methods for generalized Nash equilibrium problems, Comput. Optim. Appl., 59, 201-218, (2014) · Zbl 1307.91118
[18] Kanzow, C; Steck, D, Augmented Lagrangian methods for the solution of generalized Nash equilibrium problems, SIAM J. Optim., 26, 2034-2058, (2016) · Zbl 1351.65037
[19] Kanzow, C; Yamashita, N; Fukushima, M, Levenberg-Marquardt methods with strong local convergence properties for solving nonlinear equations with convex constraints, J. Comput. Appl. Math., 172, 375-397, (2004) · Zbl 1064.65037
[20] Qi, L; Tong, XJ; Li, DH, Active-set projected trust-region algorithm for box-constrained nonsmooth equations, J. Optim. Theory Appl., 120, 601-625, (2004) · Zbl 1140.65331
[21] Toint, PL, Non-monotone trust-region algorithms for nonlinear optimization subject to convex constraints, Math. Program., 77, 69-94, (1997) · Zbl 0891.90153
[22] Tong, XJ; Qi, L, On the convergence of a trust-region method for solving constrained nonlinear equations with degenerate solutions, J. Optim. Theory Appl., 123, 187-211, (2004) · Zbl 1069.65055
[23] Yamashita, N; Fukushima, M, On the rate of convergence of the Levenberg-Marquardt method, Computing, 15, 239-249, (2001) · Zbl 1001.65047
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.