×

zbMATH — the first resource for mathematics

A projected-gradient interior-point algorithm for complementarity problems. (English) Zbl 1229.65097
The authors consider the following problem: Find \(x\in\mathbb{R}^n\), \(y\in\mathbb{R}^n\), \(w\in\mathbb{R}^n\) such that \[ H(x,y,w)= 0,\;x_iw_i= 0,\;i= 1,2,\dots, n,\;x\geq 0,\;w\geq 0,\tag{1} \] where \(H: \mathbb{R}^{n+m+n}\to \mathbb{R}^{n+m}\) is continuously differentiable. Many problems can be formutated in this form, e.g. linear and nonlinear complementarity problems, variational inequalities, KKT conditions of nonlinear programming. The authors propose the projected-gradient interior-point algorithm for solving problem (1). Convergence of the proposed algorithm is analyzed, special attention is devoted to linear problems. Computational experience with the algorithm for solving linear complementarity problems, as well as linear, quadratic and nonlinear programming problems are reported. Conclusions about the efficiency of the proposed methodology are included in the last section of the paper.

MSC:
65K05 Numerical mathematical programming methods
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
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., Santos, S.A.: On the resolution of the generalized nonlinear complementarity problem. SIAM J. Optim. 12, 303–321 (2001) · Zbl 1006.65068
[3] Andreani, R., Júdice, J., Martinez, J.M., Patrício, J.: On the natural merit function for solving complementarity problems. Math. Program. (to appear) · Zbl 1236.90127
[4] Birgin, E.G., Martinez, J.M., Raydan, M.: Nonmonotone spectral projected gradient methods on convex sets. SIAM J. Optim. 10, 1196–1211 (2000) · Zbl 1047.90077
[5] Birgin, E.G., Martinez, J.M., Raydan, M.: Algorithm 813 SPG: software for convex–constrained optimization. ACM Trans. Math. Softw. 27, 340–349 (2001) · Zbl 1070.65547
[6] Birgin, E.G., Martinez, J.M., Raydan, M.: Inexact spectral projected gradient methods on convex sets. IMA J. Numer. Anal. 23, 539–559 (2003) · Zbl 1047.65042
[7] Brooke, A., Kendrick, D., Meeraus, A., Raman, R.: GAMS–A User’s Guide. GAMS Development Corporation (1998)
[8] Cottle, R., Pang, J., Stone, R.: The Linear Complementarity Problem. Academic, New York (1992)
[9] Dennis, J.E., Schnabel, R.B.: Numerical Methods for Unconstrained Optimization and Nonlinear Equations. Prentice Hall Series in Computational Mathematics, Englewood Cliffs, New Jersey (1983) · Zbl 0579.65058
[10] Facchinei, F., Pang, J.S.: Finite-Dimensional Inequalities and Complementarity Problems. Springer, New York (2003) · Zbl 1062.90002
[11] 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
[12] 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
[13] Ferris, M.C., Kanzow, C., Munson, T.S.: Feasible descent algorithms for mixed complementarity problems. Math. Program. 86, 475–497 (1999) · Zbl 0946.90094
[14] Ferris, M.C., Munson, T.S.: Interfaces to PATH 3.0: design, implementation and usage. Comput. Optim. Appl. 12, 207–227 (1999) · Zbl 1040.90549
[15] Fischer, A.: New constrained optimization reformulation of complementarity problems. J. Optim. Theory Appl. 12, 303–321 (2001)
[16] Floudas, C.A., Pardalos, P.M.: A Collection of Test Problems for Constrained Global Optimization Algorithms, vol. 455. Springer, New York (1990) · Zbl 0718.90054
[17] Gay, D.M.: Electronic Mail Distribution of Linear Programming Test Problems. Technical report, Mathematical Programming Society COAL Newsletter (1985)
[18] Golub, G., Van Loan, C.: Matrix Computations. Johns Hopkins University Press, Baltimore (1983) · Zbl 0559.65011
[19] Gould, N.I., Orban, D., Toint, P.: General CUTEr Documentation. Technical Report TR/PA/02/13, CERFACS (2003) · Zbl 1068.90526
[20] Haslinger, J., Hlavacek, I., Necas, J.: Numerical methods for unilateral problems in solid mechanics. In: Ciarlet, P.G., Lions, J.L. (eds.) Handbook of Numerical Analysis, vol. IV. North–Holland, Amsterdam (1996)
[21] Intel Corporation: Intel Fortran Compiler User’s Guide (2002)
[22] Júdice, J., Raydan, M., Rosa, S., Santos, S.: On the solution of the symmetric eigenvalue complementarity problem by the spectral projected gradient algorithm. Numer. Algorithms 45, 391–407 (2008) · Zbl 1144.65042
[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. IN: Lecture Notes in Computer Science, vol. 538. Springer, Berlin (1991) · Zbl 0745.90069
[25] Li, D.-H., Fukushima, M.: Derivative–free line search and global convergence of Broyden–like method for nonlinear equations. Optim. Methods Softw. 13, 181–201 (2000) · Zbl 0960.65076
[26] Murtagh, B.A., Saunders, M.A.: MINOS 5.1 User Guide. Technical Report, Department of Operations Research, Stanford University (1987)
[27] Murty, K.: Linear Complementarity, Linear and Nonlinear Programming. Heldermann, Berlin (1988) · Zbl 0634.90037
[28] Nocedal, J., Wright, S.: Numerical Optimization. Springer, New York (2000) · Zbl 0930.65067
[29] Ortega, J.M., Rheinboldt, W.C.: Iterative Solution of Nonlinear Equations in Several Variables. SIAM, Philadelphia (2000) · Zbl 0949.65053
[30] Ostrowski, A.M.: Solution of Equations and Systems of Equations. Academic, New York (1967) · Zbl 0153.45903
[31] Patrício, J.: Algoritmos de Pontos Interiores para Problemas Complementares Monótonos e Suas Aplicações. PhD thesis, Universidade de Coimbra, Portugal (2007). In Portuguese
[32] Portugal, L.F., Resende, M.G.C., Veiga, G., Júdice, J.J.: A truncated primal-infeasible dual-feasible network interior point method. Networks 35, 91–108 (2000) · Zbl 0957.90022
[33] Schwetlick, H.: Numerische Lösung Nichtlinearer Gleichungen. Deutscher Verlag der Wissenschaften, Berlin (1979) · Zbl 0402.65028
[34] Solodov, M.V.: Stationary points of bound constrained minimization reformulations. J. Optim. Theory Appl. 94, 449–467 (1997) · Zbl 0893.90161
[35] Vanderbei, R.J.: LOQO: an interior point code for quadratic programming. Optim. Methods Softw. 12, 451–484 (1999) · Zbl 0973.90518
[36] Vanderbei, R.J.: LOQO’s User Manual, Version 4.05. School of Engineering and Applied Science, Princeton University (2000)
[37] Wright, S.: Primal–Dual Interior–Point Methods. SIAM, Philadelphia (1997) · Zbl 0863.65031
[38] Wright, S.J., Ralph, D.: A superlinear infeasible interior-point algorithm 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.