×

zbMATH — the first resource for mathematics

On the natural merit function for solving complementarity problems. (English) Zbl 1236.90127
The authors consider a general class of complementarity problems (CP’s) of the form \[ H(x,y,w)=0, x^{T}w=0, x,w \geq 0, \] containing the usual CP’s and investigate the problem of minimization of the natural merit function, which is the sum of squares of the gap components. They give conditions which provide for the stationary points of this problem to be solutions of the initial one. These conditions utilize non-singularity of the Jacobian or monotonicity type properties.

MSC:
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
90C46 Optimality conditions and duality in mathematical programming
90C30 Nonlinear programming
Software:
SPG
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Andreani, R., Birgin, E.G., Martínez, J.M., Schuverdt, M.L.: Augmented lagrangian methods under the constant positive linear dependence constraint qualification. Math. Program. 111, 5–32 (2008) · Zbl 1163.90041
[2] Andreani R., Friedlander A., Martínez J.M.: On the solution of finite-dimensional variational inequalities using smooth optimization with simple bounds. J. Optim. Theory Appl. 94, 635–657 (1997) · Zbl 0892.90169
[3] Andreani R., Friedlander A., Santos S.A.: On the resolution of the generalized nonlinear complementarity problem. SIAM J. Optim. 12, 303–321 (2001) · Zbl 1006.65068
[4] Andreani R., Martínez J.M.: Reformulation of variational inequalities on a simplex and compactification of complementarity problems. SIAM J. Optim. 10, 878–895 (2000) · Zbl 0955.90135
[5] Bellavia S., Morini B.: An interior global method for nonlinear systems with simple bounds. Optim. Methods Softw. 20, 1–22 (2005) · Zbl 1073.01515
[6] Birgin E.G., Martínez J.M., Raydan M.: Nonmonotone spectral projected gradient methods on convex sets. SIAM J. Optim. 10, 1196–1211 (2000) · Zbl 1047.90077
[7] Birgin E.G., Martínez J.M., Raydan M.: Algorithm 813 SPG: Software for convex-constrained optimization. ACM Trans. Math. Softw. 27, 340–349 (2001) · Zbl 1070.65547
[8] Birgin E.G., Martínez J.M., Raydan M.: Inexact spectral projected gradient methods on convex sets. IMA J. Numer. Anal. 23, 340–349 (2003) · Zbl 1047.65042
[9] Cottle R., Pang J.S., Stone H.: The Linear Complementarity Problem. Academic Press, New York (1992) · Zbl 0757.90078
[10] Dan H., Yamashita N., Fukushima M.: A superlinearly convergent algorithm for the monotone nonlinear complementarity problem without uniqueness and nondegeneracy conditions. Math. Oper. Res. 27, 743–753 (2002) · Zbl 1082.90568
[11] Facchinei, F., Fischer, A., Kanzow, C.: A semismooth Newton method for variational inequalities: the case of box constraints. In: Ferris, M.C., Pang, J.-S. (eds.) Complementarity and Variational Problems–State of the Art, pp. 76–90. SIAM, Philadelphia (1997) · Zbl 0886.90152
[12] Facchinei F., Fischer A., Kanzow C.: Regularity properties of a semismooth reformulation of variational inequalities. SIAM J. Optim. 8, 850–869 (1998) · Zbl 0913.90249
[13] Facchinei F., Fischer A., Kanzow C., Peng J.-M.: A simply constrained optimization reformulation of KKT systems arising from variational inequalities. Appl. Math. Optim. 40, 19–37 (1999) · Zbl 0966.90076
[14] Facchinei F., Pang J.S.: Finite-Dimensional Inequalities and Complementarity Problems. Springer, New York (2003) · Zbl 1062.90002
[15] Facchinei F., Soares J.: A new merit function for complementarity problems and a related algorithm. SIAM J. Optim. 7, 225–247 (1997) · Zbl 0873.90096
[16] Fernandes L., Friedlander A., Guedes M.C., Júdice J.: Solution of a general linear complementarity problem using smooth optimization and its applications to bilinear programming and LCP. Appl. Math. Optim. 43, 1–19 (2001) · Zbl 1033.90132
[17] Fernandes L., Júdice J., Figueiredo I.: On the solution of a finite element approximation of a linear obstacle plate problem. Int. J. Appl. Math. Comput. Sci. 12, 27–40 (2002) · Zbl 1041.74068
[18] Ferris M.C., Kanzow C., Munson T.S.: Feasible Descent Algorithms for Mixed Complementarity Problems. Math. Program. 86, 475–497 (1999) · Zbl 0946.90094
[19] Fischer A.: New constrained optimization reformulation of complementarity problems. J. Optim. Theory Appl. 12, 303–321 (2001)
[20] Friedlander A., Martínez J.M., Santos S.A.: Solution of linear complementarity problems using minimization with simple bounds. J. Glob. Optim. 6, 1–15 (1995) · Zbl 0827.90129
[21] Friedlander A., Martínez J.M., Santos S.A.: A new strategy for solving variational inequalities on bounded polytopes. Numer. Funct. Anal. Optim. 16, 653–668 (1995) · Zbl 0824.49026
[22] Haslinger, J., Hlavacek, I., Necas, J.: Numerical methods for unilateral problems in solid mechanics. In: Ciarlet, P., Lions, J.L. (eds.) Handbook of Numerical Analysis vol. 4, North-Holland, Amsterdam (1999)
[23] Kikuchi N., Oden J.T.: Contact Problems in Elasticity: a Study of Variational Inequalities and Finite Elements. SIAM, Philadelphia (1988) · Zbl 0685.73002
[24] Kojima M., Megiddo N., Noma T., Yoshise A.: A Unified Approach to Interior-Point Algorithms for Linear Complementarity Problems. Lecture Notes in Computer Science 538. Springer, Berlin (1991) · Zbl 0745.90069
[25] Mangasarian O.L., Solodov M.: Nonlinear complementarity as unconstrained and constrained minimization. Math. Program. 62, 277–297 (1993) · Zbl 0813.90117
[26] Monteiro R.D.C., Wright S.J.: Local convergence of interior-point algorithms for degenerate monotone LCP problems. Comput. Optim. Appl. 3, 131–155 (1994) · Zbl 0801.90110
[27] Monteiro R.D.C., Wright S.J.: Superlinear primal-dual affine scaling algorithms for LCP. Math. Program. 69, 311–333 (1995) · Zbl 0844.90098
[28] Moré J.J.: Global methods for nonlinear complementarity problems. Math. Oper. Res. 21, 598–614 (1996) · Zbl 0868.90127
[29] Murty K.: Linear Complementarity, Linear and Nonlinear Programming. Heldermann, Berlin (1988) · Zbl 0634.90037
[30] Patrício, J.: Algoritmos de Pontos Interiores para Problemas Complementares Monótonos e suas Aplicações. PhD Thesis, University of Coimbra, Portugal (2007) (in Portuguese)
[31] Potra F.: Primal-Dual affine scaling interior point methods for linear complementarity problems. SIAM J. Optim. 19, 114–143 (2008) · Zbl 1171.90017
[32] Ralph, D., Wright, S. : Superlinear convergence of an interior-point method for monotone variational inequalities. In: Ferris, M.C., Pang, J.-S. (eds.) Complementarity and Variational Problems. State of Art, SIAM Publications, Philadelphia (1998)
[33] Shapiro A.: Sensitivity analysis of parameterized variational inequalities. Math. Oper. Res. 30, 109– 126 (2005) · Zbl 1082.49015
[34] Simantiraki E., Shanno D.: An infeasible interior point method for linear complementarity problem. SIAM J. Optim. 7, 620–640 (1997) · Zbl 0913.65056
[35] Solodov M.V.: Stationary points of bound constrained minimization reformulations. J. Optim. Theory Appl. 94, 449–467 (1997) · Zbl 0893.90161
[36] Wright S.J., Ralph D.: A superlinear infeasible interior-point algorithms for monotone complementarity problems. Math. Oper. Res. 21, 815–838 (1996) · Zbl 0867.90112
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.