×

zbMATH — the first resource for mathematics

A descent algorithm for generalized complementarity problems based on generalized Fischer-Burmeister functions. (English) Zbl 1393.90122
Summary: We study an unconstrained minimization approach to the generalized complementarity problem \(\mathrm{GCP}(f,g)\) based on the generalized Fischer-Burmeister function and its generalizations when the underlying functions are \(C^1\). Also, we show how, under appropriate regularity conditions, minimizing the merit function corresponding to \(f\) and \(g\) leads to a solution of the generalized complementarity problem. Moreover, we propose a descent algorithm for \(\mathrm{GCP}(f,g)\) and show a result on the global convergence of a descent algorithm for solving generalized complementarity problem. Finally, we present some preliminary numerical results. Our results further give a unified/generalization treatment of such results for the nonlinear complementarity problem based on generalized Fischer-Burmeister function and its generalizations.
MSC:
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
90C56 Derivative-free methods and methods using generalized derivatives
Software:
MCPLIB
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aashtiani, H; Magnanti, T, Equilibrium on a congested transportation network, SIAM J Algebr Discrete Methods, 42, 213-226, (1981) · Zbl 0501.90033
[2] Agdeppa, RP; Yamashita, N; Fukushima, M, The traffic equilibrium problem with nonadditive costs and its monotone mixed complementarity problem formulation, Transp Res Part B, 41, 862874, (2007)
[3] Andreani, R; Friedlander, A; Santos, SA, On the resolution of the generalized nonlinear complementarity problem, SIAM J Optim, 12, 303-321, (2002) · Zbl 1006.65068
[4] Chen J-S, Huang Z-H, She C-Y (2011) A new class of penalized NCP-functions and its properties. Comput Optim Appl 50:49-73 · Zbl 1254.90253
[5] Chen, M; Bernstein, DH; Chien, SIJ; Mouskos, K, Simplified formulation of the toll design problem, Transp Res Rec, 1667, 8895, (1999)
[6] Chen, J-S, The semismooth-related properties of a merit function and a descent method for the nonlinear complementarity problem, J Glob Optim, 36, 565580, (2006) · Zbl 1144.90493
[7] Chen, Jein-shan, On some NCP-functions based on the generalized fischer-burmeister function, Asia Pac J Oper Res, 24, 401-420, (2007) · Zbl 1141.90557
[8] Chen, J-S; Gao, H-T; Pan, S-H, An R-linearly convergent derivative-free algorithm for nonlinear complementarity problems based on the generalized fischer-burmeister merit function, J Comput Appl Math, 232, 455-471, (2009) · Zbl 1175.65070
[9] Chen, J-S; Pan, S-H, A family of NCP functions and a descent method for the nonlinear complementarity problems, Comput Optim Appl, 40, 389-404, (2008) · Zbl 1153.90542
[10] Company R, Egorova VN, Jdar L (2014) Solving American option pricing models by the front fixing method: numerical analysis and computing. Abstr Appl Anal, Article ID 146745
[11] Cottle RW, Giannessi F, Lions J-L (eds) (1980) Variational inequalities and complementarity problems: theory and applications. Wiley, New York · Zbl 0484.90088
[12] Cottle RW, Pang J-S, Stone RE (1992) The linear complementarity problem. Academic Press, Boston · Zbl 0757.90078
[13] Dirkse, SP; Ferris, M, MCPLIB: a collection of nonlinear mixed complementarity problems, Optim Methods Softw, 5, 319-345, (1994)
[14] Di Pillo G, Giannessi F (eds) (1996) Nonlinear optimization and applications. Plenum Press, New York · Zbl 0941.00047
[15] Facchinei, F; Kanzow, C, On unconstrained and constrained stationary points of the implicit Lagrangian, J Optim Theory Appl, 92, 99-115, (1997) · Zbl 0914.90249
[16] Facchinei F, Pang J-S (2003) Finite dimensional variational inequalities and complementarity problems. Springer-Verlag, New York · Zbl 1062.90002
[17] Facchinei, F; Soares, J, A new merit function for nonlinear complementarity problems and related algorithm, SIAM J Optim, 7, 225-247, (1997) · Zbl 0873.90096
[18] Feng L, Linetsky V, Morales JL, Nocedal J (2011) On the solution of complementarity problems arising in American options pricing. Optim Methods Softw 26(4-5):813-825 · Zbl 1229.90230
[19] Ferris MC, Pang J-S (1997b) Engineering and economic applications of complementarity problems. SIAM Rev 39:669-713 · Zbl 0891.90158
[20] Ferris MC, Pang J-S (eds) (1997a) Complementarity and variational problems: state of the art. SIAM, Philadelphia · Zbl 0828.90127
[21] Ferris MC, Ralph D (1995) Projected gradient methods for nonlinear complementarity problems via normal maps. In: Du DZ, Qi L, Womersley RS (eds) Recent advances in nonsmooth optimization. World Scientific Publishers, Singapore, pp 57-87 · Zbl 0946.90090
[22] Fischer, A, Solution of monotone complementarity problems with locally Lipschitzian functions, Math Program, 76, 513-532, (1997) · Zbl 0871.90097
[23] Fischer, A, A new constrained optimization reformulation for complementarity problems, J Optim Theory Appl, 97, 105-117, (1998) · Zbl 0907.90260
[24] Gabriel, SA; Bernstein, D, The traffic equilibrium problem with nonadditive path costs, Transp Sci, 31, 337-348, (1997) · Zbl 0920.90058
[25] Galántai, A, Properties and construction of NCP functions, Comput Optim Appl, 52, 805-824, (2012) · Zbl 1282.90194
[26] Geiger, C; Kanzow, C, On the resolution of monotone complementarity problems, Comput Optim, 5, 155-173, (1996) · Zbl 0859.90113
[27] Gu W-Z, Tawhid MA (2014) Generalized complementarity problems based on generalized Fischer-Burmeister functions as unconstrained optimization. Adv Model Optim 16(2):269-284 · Zbl 1413.90285
[28] Harker, PT; Pang, J-S, Finite dimension variational inequality and nonlinear complementarity problems: a survey of theory, algorithms and applications, Math Program, 48, 161-220, (1990) · Zbl 0734.90098
[29] Hu S-L, Huang Z-H, Chen J-S (2009) Properties of a family of generalized NCP-functions and a derivative free algorithm for complementarity problems. J Comput Appl Math 230:68-82 · Zbl 1172.65029
[30] Huang J, Pang J-S (1998) Option pricing and linear complementarity. J Comput Finance 2:31-60 · Zbl 0813.90117
[31] Hyer DH, Isac G, Rassias TM (1997) Topics in nonlinear analysis and applications. World scientific Publishing Company, Singapore
[32] Isac G (1992) Complementarity problems, Lecture Notes in Mathematics, vol 1528. Springer Verlag, Berlin · Zbl 0795.90072
[33] Jiang, H, Unconstrained minimization approaches to nonlinear complementarity problems, J Glob Optim, 9, 169-181, (1996) · Zbl 0868.90122
[34] Jiang, H; Fukushima, M; Qi, L; Sun, D, A trust region method for solving generalized complementarity problems, SIAM J Optim, 8, 140-157, (1998) · Zbl 0911.90324
[35] Kanzow, C, Nonlinear complementarity as unconstrained optimization, J Optim Theory Appl, 88, 139-155, (1996) · Zbl 0845.90120
[36] Lo, HK; Chen, A, Traffic equilibrium problem with route-specific costs: formulation and algorithms, Transp Res Part B, 34, 493-513, (2000)
[37] Luca, TD; Facchinei, F; Kanzow, C, A semismooth equation approach to the solution of nonlinear complementarity problems, Math Program, 75, 407-439, (1996) · Zbl 0874.90185
[38] Mangasarian, OL; Solodov, MV, Nonlinear complementarity as unconstrained and constrained minimization, Math Program, 62, 277-297, (1993) · Zbl 0813.90117
[39] McKean, HP, Appendix: a free boundary problem for the heat equation arising from a problem in mathematical economics, Ind Manag Rev, 6, 3239, (1965)
[40] Noor MA (1993) General nonlinear complementarity problems. In: Srivastava HM, Rassias TM (eds) Analysis, geometry, and groups: a riemann legacy volume. Hadronic Press, Palm Harbor, pp 337-371
[41] Noor, MA, Quasi-complementarity problem, J Math Anal Appl, 130, 344-353, (1988) · Zbl 0645.90086
[42] Ortega JM, Rheinboldt WC (1970) Iterative solution of nonlinear equations in several variables. Academic Press, New York, San Francisco, London · Zbl 0241.65046
[43] Outrata, JV; Zowe, J, A Newton method for a class of quasi-variational inequalities, Comput Optim Appl, 4, 5-21, (1995) · Zbl 0827.49007
[44] Pang JS (1981) The implicit complementarity problem. In: Mangasarian OL, Meyer RR, Robinson SM (eds) Nonlinear programming. Academic Press, New York, pp 487-518 · Zbl 1006.65068
[45] Patriksson M (1994) The traffic assignment problem: models and methods. VSP, Utrecht · Zbl 0828.90127
[46] Patriksson, M, Algorithms for computing traffic equilibria, Netw Spatial Econ, 4, 2338, (2004) · Zbl 1079.90141
[47] Sheffi Y (1985) Urban transportation networks: equilibrium analysis with mathematical programming methods. Prentice Hall, New Jersey
[48] Tawhid, MA, An application of \(H\)-differentiability to nonnegative and unrestricted generalized complementarity, Comput Optim Appl, 39, 51-74, (2008) · Zbl 1147.90405
[49] Tseng, P, Growth behavior of a class of merit functions for the nonlinear complementarity problem, J Optim Theory Appl, 89, 17-37, (1996) · Zbl 0866.90127
[50] Moerbeke, P, On optimal stopping and free boundary problems, Arch Ration Mech Anal, 60, 101148, (1976) · Zbl 0336.35047
[51] Wilmott P, Howison S, Dewynne J (1995) The mathematics of financial derivatives. Cambridge University Press, Cambridge · Zbl 0842.90008
[52] Xu M, Gao ZY (2011) A complementary formulation for traffic equilibrium problem with a new nonadditive route cost. Sci China Technol Sci 54(9):2525-2530 · Zbl 1237.90059
[53] Yamada K, Yamashita N, Fukushima M (2000) A new derivative-free descent method for the nonlinear complementarity problems. In: Pillo GD, Giannessi F (eds) Nonlinear optimization and related topics. Kluwer Academic Publishers, Netherlands, pp 463-487 · Zbl 0996.90085
[54] Yamashita, N; Fukushima, M, On stationary points of the implicit Lagrangian for nonlinear complementarity problems, J Optim Theory Appl, 84, 653-663, (1995) · Zbl 0824.90131
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.