×

On the finite convergence of Newton-type methods for \(P_{0}\) affine variational inequalities. (English) Zbl 1129.90055

Summary: Based on the techniques used in non-smooth Newton methods and regularized smoothing Newton methods, a Newton-type algorithm is proposed for solving the \(P _{0}\) affine variational inequality problem. Under mild conditions, the algorithm can find an exact solution of the \(P _{0}\) affine variational inequality problem in finite steps. Preliminary numerical results indicate that the algorithm is promising.

MSC:

90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
49J40 Variational inequalities
90C30 Nonlinear programming
49J52 Nonsmooth analysis
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Chen, B., Chen, X.: A global linear and local quadratic continuation smoothing method for variational inequalities with box constraints. Computational Optimization and Applications, 13(1), 131–158 (2000) · Zbl 0987.90079 · doi:10.1023/A:1026546230851
[2] Chen, X., Ye, Y.: On homotopy-smoothing methods for variational inequalities. SIAM Journal on Control and Optimization, 37(4), 589–616 (1999) · Zbl 0973.65051 · doi:10.1137/S0363012997315907
[3] Marcotte, P., Wu, J. H.: On the convergence of projection methods: application to the decomposition of affine variational inequalities. Journal of Optimization Theory and Applications, 85, 347–362 (1995) · Zbl 0831.90104 · doi:10.1007/BF02192231
[4] Solodov, M. V., Svaiter, B. F.: A new projection method for variational inequality problems. SIAM Journal on Control and Optimization, 37, 765–776 (1999) · Zbl 0959.49007 · doi:10.1137/S0363012997317475
[5] Mehrotra, S., Ye, Y.: On finding the optimal facet of linear programs. Mathematical Programming, 62, 497–515 (1993) · Zbl 0803.90089 · doi:10.1007/BF01585180
[6] Ye, Y.: On the finite convergence of interior-point algorithms for linear programming. Mathematical Programming 57, 325–335 (1992) · Zbl 0794.90036 · doi:10.1007/BF01581087
[7] Fischer, A., Kanzow, C.: On the finite termination of an iterative method for linear complementarity problems. Mathematical Programming, 74, 279–292 (1996) · Zbl 0855.90125
[8] Sun, D., Han, J., Zhao, Y. B.: On the finite termination of the damped-Newton algorithm for the linear complementarity problem. Acta Mathematica Applicatae Sinica, 21, 148–154 (1998) · Zbl 0958.90081
[9] Huang, Z. H., Zhang, L., Han, J.: A hybrid smoothing-nonsmooth Newton-type algorithm yielding an exact solution of the P 0-LCP. Journal of Computational Mathematics, 6, 797–806 (2004) · Zbl 1068.65075
[10] Huang, Z. H., Han, J., Xu, D., Zhang, L. P.: The non-interior continuation methods for solving the P 0- function nonlinear complementarity problem. Science in China, Series A, 44(2), 1107–1114 (2001) · Zbl 1002.90072 · doi:10.1007/BF02877427
[11] Zhang, L. P., Han, J. Y., Huang, Z. H.: Superlinear/Quadratic one-step smoothing Newton method for P 0-NCP. Acta Mathematica Sinica, English Series, 21, 117–128 (2005) · Zbl 1124.90037 · doi:10.1007/s10114-004-0412-5
[12] Huang, Z. H., Qi, L., Sun, D.: Sub-quadratic convergence of a smoothing Newton algorithm for the P 0– and monotone LCP. Mathematical Programming, 99, 423–441 (2004) · Zbl 1168.90646 · doi:10.1007/s10107-003-0457-8
[13] Huang, Z. H., Han, J. Y., Chen, Z.: Predictor-corrector smoothing Newton method, based on anew smoothing function, for solving the nonlinear complementarity problem with a P 0 function. Journal of Optimization Theory and Applications, 117(1), 39–68 (2003) · Zbl 1044.90081 · doi:10.1023/A:1023648305969
[14] Qi, H.: A regularized smoothing Newton method for box constrained variational inequality problems with P 0-functions. SIAM Journal on Optimization, 10(1), 315–330 (2000) · Zbl 0955.90136 · doi:10.1137/S1052623497324047
[15] Sun, D.: A regularization Newton method for solving nonlinear complementarity problems. Applied Mathematics and Optimization, 35, 315–339 (1999) · Zbl 0937.90110 · doi:10.1007/s002459900128
[16] Zhang, L. P., Gao, Z.: Quadratic one-step smoothing Newton method for P 0-LCP without strict complementarity. Applied Mathematics and Computation, 140, 367–379 (2003) · Zbl 1049.65054 · doi:10.1016/S0096-3003(02)00234-5
[17] Fischer, A.: A special Newton-type optimization method. Optimization, 24(1), 269–284 (1992) · Zbl 0814.65063 · doi:10.1080/02331939208843795
[18] Clarke, F. H.: Optimization and Nonsmooth Analysis, Wiley, New York, 1983 · Zbl 0582.49001
[19] Chen, B., Harker, P. T. : A non-interior-point continuation method for linear complementarity problems. SIAM Journal on Matrix Analysis and Applications, 14(2), 1168–1190 (1993) · Zbl 0788.65073 · doi:10.1137/0614081
[20] Qi, L., Sun, D., Zhou, G. : A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequality problems. Mathematical Programming, 87(1), 1–35 (2000) · Zbl 0989.90124
[21] Qi, L., Sun, J.: A nonsmooth version of Newton’s method. Mathematical Programming, 58, 353–367 (1993) · Zbl 0780.90090 · doi:10.1007/BF01581275
[22] Murty, K. G.: Linear complementarity, linear and nonlinear programming, Sigma Ser. Appl. Math. 3, Heldermann-Verlag, Berlin, 1988 · Zbl 0634.90037
[23] Fathi, Y.: Computational complexity of LCPs associated with possitive definite matrices. Mathematical Programming, 17, 335–344 (1979) · Zbl 0421.90072 · doi:10.1007/BF01588254
[24] Ahn, B. H.: Iterative methods for linear complementarity problem with upperbounds and lowerbounds. Mathematical Programming, 26, 265–315 (1983) · Zbl 0506.90081
[25] Kanzow, C.: Global convergence properties of some iterative methods for linear complementarity problems. SIAM Journal on Optimization, 6, 326–341 (1996) · Zbl 0847.90132 · doi:10.1137/0806019
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.