×

zbMATH — the first resource for mathematics

A smoothing-type algorithm for solving linear complementarity problems with strong convergence properties. (English) Zbl 1190.90236
Summary: We construct an augmented system of the standard monotone linear complementarity problem (LCP), and establish the relations between the augmented system and the LCP. We present a smoothing-type algorithm for solving the augmented system. The algorithm is shown to be globally convergent without assuming any prior knowledge of feasibility/infeasibility of the problem. In particular, if the LCP has a solution, then the algorithm either generates a maximal complementary solution of the LCP or detects correctly solvability of the LCP, and in the latter case, an existing smoothing-type algorithm can be directly applied to solve the LCP without any additional assumption and it generates a maximal complementary solution of the LCP; and that if the LCP is infeasible, then the algorithm detect correctly infeasibility of the LCP. To the best of our knowledge, such properties have not appeared in the existing literature for smoothing-type algorithms.

MSC:
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Adler, I., Gale, D.: On the solution of the positive semi-definite complementarity problem. Technique Report ORC 75-12, Operations Research Center, University of California, Berkely (1975)
[2] Burke, J., Xu, S.: The global linear convergence of a non-interior path-following algorithm for linear complementarity problems. Math. Oper. Res. 23, 719–734 (1998) · Zbl 0977.90056
[3] Burke, J., Xu, S.: A non-interior predictor-corrector path following algorithm for the monotone linear complementarity problem. Math. Program. 87, 113–130 (2000) · Zbl 1081.90603
[4] Chen, B., Chen, X.: A global and local superlinear continuation-smoothing method for P 0+R 0 and monotone NCP. SIAM J. Optim. 9, 624–645 (1999) · Zbl 0955.90132
[5] Chen, B., Harker, P.T.: A non-interior-point continuation method for linear complementarity problem. SIAM J. Matrix Anal. Appl. 14, 1168–1190 (1993) · Zbl 0788.65073
[6] Chen, C., Mangasarian, O.L.: Smoothing method for convex inequalities and linear complementarity problems. Math. Program. 71, 51–69 (1995) · Zbl 0855.90124
[7] Chen, B., Xiu, N.: Superlinear noninterior one-step continuation method for monotone LCP in the absence of strict complementarity. J. Optim. Theory Appl. 108, 317–332 (2001) · Zbl 1041.90056
[8] Chen, X., Ye, Y.: On homotopy-smoothing methods for variational inequalities. SIAM J. Control Optim. 37, 589–616 (1999) · Zbl 0973.65051
[9] Chen, X., Ye, Y.: On smoothing methods for the P 0 matrix linear complementarity problem. SIAM J. Optim. 11, 341–363 (2000) · Zbl 0994.65077
[10] Chen, X., Tseng, P.: Non-interior continuation methods for solving semidefinite complementarity problems. Math. Program. 95, 431–474 (2003) · Zbl 1023.90046
[11] Cottle, R.W., Pang, J.-S., Stone, R.E.: The Linear Complementarity Problem. Academic, Boston (1992)
[12] Engelke, S., Kanzow, C.: Predictor-corrector smoothing methods for the solution of linear programming. Preprint, Department of Mathematics, University of Hamburg (2000) · Zbl 1028.90026
[13] Engelke, S., Kanzow, C.: Improved smoothing-type methods for the solution of linear programs. Numer. Math. 90, 487–507 (2002) · Zbl 0994.65065
[14] Facchinei, F., Kanzow, C.: Beyond monotonicity in regularization methods for nonlinear complementarity problems. SIAM J. Control Optim. 37, 1150–1161 (1999) · Zbl 0997.90085
[15] Güler, O., Ye, Y.: Convergence behavior of interior-point algorithms. Math. Program. 60, 215–228 (1993) · Zbl 0803.90087
[16] Hayashi, S., Yamashita, N., Fukushima, M.: A combined smoothing and regularization method for monotone second-order cone complementarity problems. SIAM J. Optim. 15, 593–615 (2005) · Zbl 1114.90139
[17] Hotta, K., Yoshise, A.: Global convergence of a non-interior-point algorithms using Chen-Harker-Kanzow functions for nonlinear complementarity problems. Math. Program. 86, 105–133 (1999) · Zbl 0978.90095
[18] Huang, Z.H.: Sufficient conditions on nonemptiness and boundedness of the solution set of the P 0 function nonlinear complementarity problem. Oper. Res. Lett. 30, 202–210 (2002) · Zbl 1010.90081
[19] Huang, Z.H.: Locating a maximally complementary solution of the monotone NCP by using non-interior-point smoothing algorithms. Math. Methods Oper. Res. 61, 41–55 (2005) · Zbl 1066.90127
[20] Huang, Z.H.: The global linear and local quadratic convergence of a non-interior continuation algorithm for the LCP. IMA J. Numer. Anal. 25, 670–684 (2005) · Zbl 1084.65061
[21] Huang, Z.H., Sun, J.: A non-interior continuation algorithm for the P 0 or P * LCP with strong global and local convergence properties. Appl. Math. Optim. 26, 237–262 (2005) · Zbl 1112.90083
[22] Huang, Z.H., Wang, H.: Smoothing-type algorithm for solving linear programs by using an augmented complementarity problem. Appl. Math. Comput. 177, 330–345 (2006) · Zbl 1101.65060
[23] Huang, Z.H., Sun, D., Zhao, G.Y.: A smoothing Newton-type algorithm of stronger convergence for the quadratically constrained convex quadratic programming. Comput. Optim. Appl. 35, 199–237 (2006) · Zbl 1151.90509
[24] Kanzow, C.: Some noninterior continuation methods for linear complementarity problems. SIAM J. Matrix Anal. Appl. 17, 851–868 (1996) · Zbl 0868.90123
[25] Karamardian, S.: Complementarity problems over cones with monotone and pseudomonotone maps. J. Optim. Theory Appl. 18, 445–454 (1976) · Zbl 0304.49026
[26] Mclinden, L.: Stable monotone variational inequalities. Math. Program. 48, 303–338 (1990) · Zbl 0726.90093
[27] Qi, H.D.: A regularization smoothing Newton method for box constrained variational inequality problems with P 0-functions. SIAM J. Optim. 10, 315–330 (1999) · Zbl 0955.90136
[28] Qi, L., Sun, D.: Improving the convergence of non-interior point algorithm for nonlinear complementarity problems. Math. Comput. 69, 283–304 (2000) · Zbl 0947.90117
[29] Qi, L., Sun, D., Zhou, G.: A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequality problems. Math. Program. 87, 1–35 (2000) · Zbl 0989.90124
[30] Sun, J., Huang, Z.H.: A smoothing Newton algorithm for the LCP with a sufficient matrix that terminates finitely at a maximally complementary solution. Optim. Meth. Softw. 21(4), 597–615 (2006) · Zbl 1113.90158
[31] Tseng, P.: Analysis of a non-interior continuation method based on Chen-Mangasarian smoothing functions for complementarity problems. In: Fukushima, M., Qi, L. (eds.) Reformulation-Nonsmooth, Piecewise Smooth, Semismooth and Smoothing Methods, pp. 381–404. Kluwer Academic, Boston (1999) · Zbl 0928.65078
[32] Ye, Y.: On homogeneous and self-dual algorithms for LCP. Math. Program. 76, 211–221 (1996) · Zbl 0881.90116
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.