A smoothing Newton algorithm for weighted linear complementarity problem. (English) Zbl 1346.90778
Summary: In this paper, we present a new smoothing Newton method for solving monotone weighted linear complementarity problem (WCP). Our algorithm needs only to solve one linear system of equation and performs one line search per iteration. Any accumulation point of the iteration sequence generated by our algorithm is a solution of WCP. Under suitable conditions, our algorithm has local quadratic convergence rate. Numerical experiments show the feasibility and efficiency of the algorithm.
MSC:
| 90C33 | Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) |
| 90C53 | Methods of quasi-Newton type |
Keywords:
weighted linear complementarity problem; smoothing Newton method; locally quadratic convergenceReferences:
| [1] | Anstreicher, K.: Interior-point algorithms for a generalization of linear programming and weighted centering. Optim. Methods Softw. 27(4-5), 605-612 (2012) · Zbl 1254.90106 · doi:10.1080/10556788.2011.644791 |
| [2] | Hu, S., Huang, Z.: A nonmonotone smoothing Newton algorithm for solving nonlinear complementarity problems. Optim. Methods Softw. 24(3), 447-460 (2009) · Zbl 1173.90552 · doi:10.1080/10556780902769862 |
| [3] | Huang, Z.: Locating a maximally complementarity solution of the monotone NCP by using non-interior-point smoothing algorithms. Math. Methods Oper. Res. 61, 41-55 (2005) · Zbl 1066.90127 · doi:10.1007/s001860400384 |
| [4] | Huang, Z., Han, J., Chen, Z.: Predictor-corrector smoothing Newton method, based on a new smoothing function, for solving the nonlinear complementarity problem with a \[P_0\] P0 function. J. Optim. Theory Appl. 117(1), 39-68 (2003) · Zbl 1044.90081 · doi:10.1023/A:1023648305969 |
| [5] | Huang, Z., Qi, L., Sun, D.: Sub-quadratic convergence of a smoothing Newton algorithm for the \[P_0\] P0- and monotone LCP. Math. Program Ser. A 99, 423-441 (2004) · Zbl 1168.90646 · doi:10.1007/s10107-003-0457-8 |
| [6] | Huang, Z., Xu, S.: Convergence properties of a non-interior-point smoothing algorithm for the \[P_*P\]∗ NCP. J. Ind. Manag. Optim. 3(3), 569-584 (2007) · Zbl 1166.90370 · doi:10.3934/jimo.2007.3.569 |
| [7] | Ma, C.: A new smoothing and regularization Newton method for \[P_0\] P0-NCP. J. Global Optim. 48(2), 241-261 (2010) · Zbl 1228.90127 · doi:10.1007/s10898-009-9489-9 |
| [8] | Ma, C., Chen, X.: The convergence of a one-step smoothing Newton method for \[P_0\] P0-NCP based on a new smoothing NCP-function. J. Comput. Appl. Math. 216(1), 1-13 (2008) · Zbl 1140.65046 · doi:10.1016/j.cam.2007.03.031 |
| [9] | Mifflin, R.: Semismooth and semiconvex functions in constrained optimization. SIAM J. Control Optim 15, 957-972 (1977) · Zbl 0376.90081 · doi:10.1137/0315061 |
| [10] | Potra, F.: Weighted complementarity problems-a new paradigm for computing equilibria. SIAM J. Optim 22(4), 1634-1654 (2012) · Zbl 1273.90217 · doi:10.1137/110837310 |
| [11] | Qi, L.: Convergence analysis of some algorithms for solving nonsmooth equations. Math. Oper. Res. 18, 227-244 (1993) · Zbl 0776.65037 · doi:10.1287/moor.18.1.227 |
| [12] | Qi, L., Sun, D., Zhou, G.: A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequalities. Math. Program Ser. A 87, 1-35 (2000) · Zbl 0989.90124 |
| [13] | Qi, L., Sun, J.: A nonsmooth version of Newton’s method. Math. Program 58(2), 353-367 (1993) · Zbl 0780.90090 · doi:10.1007/BF01581275 |
| [14] | Sun, J., Huang, Z.: A smoothing Newton algorithm for the LCP with a sufficient matrix that terminates finitely at a maximally complementarity solution. Optim. Methods Softw. 21(4), 597-615 (2006) · Zbl 1113.90158 · doi:10.1080/10556780600627727 |
| [15] | Zhang, L., Zhang, X.: Global linear and quadratic one-step smoothing Newton method for \[P_0\] P0-LCP. J. Global Optim. 25, 363-376 (2003) · Zbl 1046.90092 · doi:10.1023/A:1022528320719 |
| [16] | Zhou, G., Caccetta, L., Teo, K.: A superlinearly convergent method for a class of complementarity problems with non-Lipschitzian functions. SIAM J. Optim 22(4), 1811-1827 (2010) · Zbl 1206.90197 · doi:10.1137/080726690 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
