Improving the convergence of noninterior point algorithms for nonlinear complementarity problems
Authors:
Liqun Qi and Defeng Sun
Journal:
Math. Comp. 69 (2000), 283304
MSC (1991):
Primary 90C33; Secondary 90C30, 65H10
Published electronically:
February 19, 1999
MathSciNet review:
1642766
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: Recently, based upon the ChenHarkerKanzowSmale smoothing function and the trajectory and the neighbourhood techniques, Hotta and Yoshise proposed a noninterior point algorithm for solving the nonlinear complementarity problem. Their algorithm is globally convergent under a relatively mild condition. In this paper, we modify their algorithm and combine it with the superlinear convergence theory for nonlinear equations. We provide a globally linearly convergent result for a slightly updated version of the HottaYoshise algorithm and show that a further modified HottaYoshise algorithm is globally and superlinearly convergent, with a convergence order , under suitable conditions, where is an additional parameter.
 1.
J. Burke and S. Xu, ``The global linear convergence of a noninterior pathfollowing algorithm for linear complementarity problem", to appear in Mathematics of Operations Research.
 2.
J. Burke and S. Xu, ``A noninterior predictorcorrector path following algorithm for the monotone linear complementarity problem", Preprint, Department of Mathematics, University of Washington, Seattle, WA 98195, September, 1997.
 3.
J. Burke and S. Xu, ``A noninterior predictorcorrector path following method for LCP'', in: M. Fukushima and L. Qi, eds., Reformulation  Nonsmooth, Piecewise Smooth, Semismooth and Smoothing Methods, Kluwer Academic Publisher, Nowell, Maryland, pp. 4564, 1998.
 4.
B. Chen and X. Chen, ``A global linear and local quadratic continuation smoothing method for variational inequalities with box constraints'', Preprint, Department of Management and Systems, Washington State University, Pullman, March 1997.
 5.
B. Chen and X. Chen, ``A global and local superlinear continuationsmoothing method for and monotone NCP'', to appear in SIAM Journal on Optimization.
 6.
Bintong
Chen and Patrick
T. Harker, A noninteriorpoint continuation method for linear
complementarity problems, SIAM J. Matrix Anal. Appl.
14 (1993), no. 4, 1168–1190. MR 1238931
(94g:90139), http://dx.doi.org/10.1137/0614081
 7.
Bintong
Chen and Patrick
T. Harker, A continuation method for monotone variational
inequalities, Math. Programming 69 (1995),
no. 2, Ser. A, 237–253. MR 1348806
(96m:90101), http://dx.doi.org/10.1007/BF01585559
 8.
Bintong
Chen and Patrick
T. Harker, Smooth approximations to nonlinear complementarity
problems, SIAM J. Optim. 7 (1997), no. 2,
403–420. MR 1443626
(98e:90192), http://dx.doi.org/10.1137/S1052623495280615
 9.
B. Chen and N. Xiu, ``A global linear and local quadratic noninterior continuation method for nonlinear complementarity problems based on ChenMangasarian smoothing function'', to appear in SIAM Journal on Optimization.
 10.
Chun
Hui Chen and O.
L. Mangasarian, Smoothing methods for convex inequalities and
linear complementarity problems, Math. Programming 71
(1995), no. 1, Ser. A, 51–69. MR 1362957
(96j:90082), http://dx.doi.org/10.1007/BF01592244
 11.
Chunhui
Chen and O.
L. Mangasarian, A class of smoothing functions for nonlinear and
mixed complementarity problems, Comput. Optim. Appl.
5 (1996), no. 2, 97–138. MR 1373293
(96m:90102), http://dx.doi.org/10.1007/BF00249052
 12.
X.
Chen, L.
Qi, and D.
Sun, Global and superlinear convergence of
the smoothing Newton method and its application to general box constrained
variational inequalities, Math. Comp.
67 (1998), no. 222, 519–540. MR 1458218
(98g:90034), http://dx.doi.org/10.1090/S0025571898009326
 13.
X. Chen and Y. Ye, ``On homotopysmoothing methods for variational inequalities'', to appear in SIAM Journal on Control and Optimization.
 14.
Frank
H. Clarke, Optimization and nonsmooth analysis, Canadian
Mathematical Society Series of Monographs and Advanced Texts, John Wiley
& Sons Inc., New York, 1983. A WileyInterscience Publication. MR 709590
(85m:49002)
 15.
F. Facchinei, H. Jiang, and L. Qi, ``A smoothing method for mathematical programming with equilibrium constraints'', to appear in Mathematical Programming.
 16.
M.C. Ferris and J.S. Pang, ``Engineering and economic applications of complementarity problems'', SIAM Review, 39 (1997), 669713. CMP 98:06
 17.
M. Fukushima, Z.Q. Luo, and J.S. Pang, ``A globally convergent sequential quadratic programming algorithm for mathematical programming problems with linear complementarity constraints'', Computational Optimization and Applications, 10 (1998), 534. CMP 98:09
 18.
Patrick
T. Harker and JongShi
Pang, Finitedimensional variational inequality and nonlinear
complementarity problems: a survey of theory, algorithms and
applications, Math. Programming 48 (1990),
no. 2, (Ser. B), 161–220. MR 1073707
(91g:90166), http://dx.doi.org/10.1007/BF01582255
 19.
K. Hotta and A. Yoshise ``Global convergence of a class of noninteriorpoint algorithms using ChenHarkerKanzow functions for nonlinear complementarity problems'', Discussion Paper Series No. 708, Institute of Policy and Planning Sciences, University of Tsukuba, Tsukuba, Ibaraki 305, Japan, December 1996. CMP 98:13
 20.
Christian
Kanzow, Some noninterior continuation methods for linear
complementarity problems, SIAM J. Matrix Anal. Appl.
17 (1996), no. 4, 851–868. MR 1410705
(97g:90148), http://dx.doi.org/10.1137/S0895479894273134
 21.
C. Kanzow and H. Jiang, ``A continuation method for (strongly) monotone variational inequalities", Mathematical Programming 81 (1998), 103125. CMP 98:11
 22.
Masakazu
Kojima, Nimrod
Megiddo, and Toshihito
Noma, Homotopy continuation methods for nonlinear complementarity
problems, Math. Oper. Res. 16 (1991), no. 4,
754–774. MR 1135047
(93b:90097), http://dx.doi.org/10.1287/moor.16.4.754
 23.
M.
Kojima, N.
Megiddo, T.
Noma, and A.
Yoshise, A unified approach to interior point algorithms for linear
complementarity problems, Lecture Notes in Computer Science,
vol. 538, SpringerVerlag, Berlin, 1991. MR 1226025
(94e:90004)
 24.
J.
M. Ortega and W.
C. Rheinboldt, Iterative solution of nonlinear equations in several
variables, Academic Press, New York, 1970. MR 0273810
(42 #8686)
 25.
JongShi
Pang, Complementarity problems, Handbook of global
optimization, Nonconvex Optim. Appl., vol. 2, Kluwer Acad. Publ.,
Dordrecht, 1995, pp. 271–338. MR 1377087
(97a:90095)
 26.
Li
Qun Qi, Convergence analysis of some algorithms for solving
nonsmooth equations, Math. Oper. Res. 18 (1993),
no. 1, 227–244. MR 1250115
(95f:65109), http://dx.doi.org/10.1287/moor.18.1.227
 27.
Li
Qun Qi and Xiao
Jun Chen, A globally convergent successive approximation method for
severely nonsmooth equations, SIAM J. Control Optim.
33 (1995), no. 2, 402–418. MR 1318657
(96a:90035), http://dx.doi.org/10.1137/S036301299223619X
 28.
Li
Qun Qi and Jie
Sun, A nonsmooth version of Newton’s method, Math.
Programming 58 (1993), no. 3, Ser. A, 353–367.
MR
1216791 (94b:90077), http://dx.doi.org/10.1007/BF01581275
 29.
Stephen
M. Robinson, Generalized equations, Mathematical programming:
the state of the art (Bonn, 1982) Springer, Berlin, 1983,
pp. 346–367. MR 717407
(85d:90074)
 30.
Steve
Smale, Algorithms for solving equations, (Berkeley, Calif.,
1986) Amer. Math. Soc., Providence, RI, 1987, pp. 172–195. MR 934223
(89d:65060)
 31.
Paul
Tseng, An infeasible pathfollowing method for monotone
complementarity problems, SIAM J. Optim. 7 (1997),
no. 2, 386–402. MR 1443625
(98c:90169), http://dx.doi.org/10.1137/S105262349427409X
 32.
P. Tseng, ``Analysis of a noninterior continuation method based on ChenMangasarian functions for complementarity problems'', in: M. Fukushima and L. Qi, eds., Reformulation  Nonsmooth, Piecewise Smooth, Semismooth and Smoothing Methods, Kluwer Academic Publisher, Nowell, Maryland, pp. 381404, 1998.
 33.
Stephen
J. Wright, Primaldual interiorpoint methods, Society for
Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997. MR 1422257
(98a:90004)
 34.
Stephen
Wright and Daniel
Ralph, A superlinear infeasibleinteriorpoint algorithm for
monotone complementarity problems, Math. Oper. Res.
21 (1996), no. 4, 815–838. MR 1419904
(97j:90076), http://dx.doi.org/10.1287/moor.21.4.815
 35.
S. Xu, ``The global linear convergence of an infeasible noninterior pathfollowing algorithm for complementarity problems with uniform functions", Preprint, Department of Mathematics, University of Washington, Seattle, WA 98195, December 1996.
 36.
S. Xu, ``The global linear convergence and complexity of a noninterior pathfollowing algorithm for monotone LCP based on ChenHarkerKanzowSmale smooth functions", Preprint, Department of Mathematics, University of Washington, Seattle, WA 98195, February 1997.
 1.
 J. Burke and S. Xu, ``The global linear convergence of a noninterior pathfollowing algorithm for linear complementarity problem", to appear in Mathematics of Operations Research.
 2.
 J. Burke and S. Xu, ``A noninterior predictorcorrector path following algorithm for the monotone linear complementarity problem", Preprint, Department of Mathematics, University of Washington, Seattle, WA 98195, September, 1997.
 3.
 J. Burke and S. Xu, ``A noninterior predictorcorrector path following method for LCP'', in: M. Fukushima and L. Qi, eds., Reformulation  Nonsmooth, Piecewise Smooth, Semismooth and Smoothing Methods, Kluwer Academic Publisher, Nowell, Maryland, pp. 4564, 1998.
 4.
 B. Chen and X. Chen, ``A global linear and local quadratic continuation smoothing method for variational inequalities with box constraints'', Preprint, Department of Management and Systems, Washington State University, Pullman, March 1997.
 5.
 B. Chen and X. Chen, ``A global and local superlinear continuationsmoothing method for and monotone NCP'', to appear in SIAM Journal on Optimization.
 6.
 B. Chen and P.T. Harker, ``A noninteriorpoint continuation method for linear complementarity problems", SIAM Journal on Matrix Analysis and Applications, 14 (1993), 11681190. MR 94g:90139
 7.
 B. Chen and P.T. Harker, ``A continuation method for monotone variational inequalities", Mathematical Programming, 69 (1995), 237253. MR 96m:90101
 8.
 B. Chen and P.T. Harker, ``Smooth approximations to nonlinear complementarity problems", SIAM Journal on Optimization, 7 (1997), 403420. MR 98e:90192
 9.
 B. Chen and N. Xiu, ``A global linear and local quadratic noninterior continuation method for nonlinear complementarity problems based on ChenMangasarian smoothing function'', to appear in SIAM Journal on Optimization.
 10.
 C. Chen and O.L. Mangasarian, ``Smoothing methods for convex inequalities and linear complementarity problems", Mathematical Programming, 71 (1995), 5169. MR 96j:90082
 11.
 C. Chen and O.L. Mangasarian, ``A class of smoothing functions for nonlinear and mixed complementarity problems", Computational Optimization and Applications, 5 (1996), 97138. MR 96m:90102
 12.
 X. Chen, L. Qi, and D. Sun, ``Global and superlinear convergence of the smoothing Newton method and its application to general box constrained variational inequalities", Mathematics of Computation, 67 (1998), 519540. MR 98g:90034
 13.
 X. Chen and Y. Ye, ``On homotopysmoothing methods for variational inequalities'', to appear in SIAM Journal on Control and Optimization.
 14.
 F.H. Clarke, Optimization and Nonsmooth Analysis, Wiley, New York, 1983. MR 85m:49002
 15.
 F. Facchinei, H. Jiang, and L. Qi, ``A smoothing method for mathematical programming with equilibrium constraints'', to appear in Mathematical Programming.
 16.
 M.C. Ferris and J.S. Pang, ``Engineering and economic applications of complementarity problems'', SIAM Review, 39 (1997), 669713. CMP 98:06
 17.
 M. Fukushima, Z.Q. Luo, and J.S. Pang, ``A globally convergent sequential quadratic programming algorithm for mathematical programming problems with linear complementarity constraints'', Computational Optimization and Applications, 10 (1998), 534. CMP 98:09
 18.
 P.T. Harker and J.S. Pang, ``Finitedimensional variational inequality and nonlinear complementarity problem: A survey of theory, algorithms and applications'', Mathematical Programming, 48 (1990) 161220. MR 91g:90166
 19.
 K. Hotta and A. Yoshise ``Global convergence of a class of noninteriorpoint algorithms using ChenHarkerKanzow functions for nonlinear complementarity problems'', Discussion Paper Series No. 708, Institute of Policy and Planning Sciences, University of Tsukuba, Tsukuba, Ibaraki 305, Japan, December 1996. CMP 98:13
 20.
 C. Kanzow, ``Some noninterior continuation methods for linear complementarity problems", SIAM Journal on Matrix Analysis and Applications, 17 (1996), 851868. MR 97g:90148
 21.
 C. Kanzow and H. Jiang, ``A continuation method for (strongly) monotone variational inequalities", Mathematical Programming 81 (1998), 103125. CMP 98:11
 22.
 M. Kojima, N. Megiddo, and T. Noma, ``Homotopy continuation methods for nonlinear complementarity problems'', Mathematics of Operations Research, 16 (1991), 754774. MR 93b:90097
 23.
 M. Kojima, N. Megiddo, T. Noma, and A. Yoshise, ``A unified approach to interior point algorithms for linear complementarity problems'', Lecture Notes in Computer Science 538, SpringerVerlag, Berlin, Germany, 1991. MR 94e:90004
 24.
 J.M. Ortega and W.C. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables, Academic Press, Inc., San Diego, 1970. MR 42:8686
 25.
 J.S. Pang, ``Complementarity problems,'' in: R. Horst and P. Pardalos, eds., Handbook of Global Optimization, Kluwer Academic Publishers, Boston, pp. 271338, 1995. MR 97a:90095
 26.
 L. Qi, ``Convergence analysis of some algorithms for solving nonsmooth equations'', Mathematics of Operations Research, 18 (1993), 227244. MR 95f:65109
 27.
 L. Qi and X. Chen, ``A globally convergent successive approximation method for severely nonsmooth equations'', SIAM Journal on Control and Optimization, 33 (1995), 402418. MR 96a:90035
 28.
 L. Qi and J. Sun, ``A nonsmooth version of Newton's method'', Mathematical Programming, 58 (1993), 353367. MR 94b:90077
 29.
 S.M. Robinson, ``Generalized equations'', in: A. Bachem, M. Grötschel and B. Korte, eds., Mathematical Programming: The State of the Art, SpringerVerlag, Berlin, pp. 346347, 1983. MR 85d:90074
 30.
 S. Smale, ``Algorithms for solving equations", Proceedings of the International Congress of Mathematicians (1986), Berkeley, California, pp. 172195. MR 89d:65060
 31.
 P. Tseng, ``An infeasible pathfollowing method for monotone complementarity problem", SIAM Journal on Optimization, 7 (1997), 386402. MR 98c:90169
 32.
 P. Tseng, ``Analysis of a noninterior continuation method based on ChenMangasarian functions for complementarity problems'', in: M. Fukushima and L. Qi, eds., Reformulation  Nonsmooth, Piecewise Smooth, Semismooth and Smoothing Methods, Kluwer Academic Publisher, Nowell, Maryland, pp. 381404, 1998.
 33.
 S. Wright, PrimalDual Interior Point Methods, SIAM, Philadelphia, PA, 1997. MR 98a:90004
 34.
 S. Wright and D. Ralph, ``A superlinear infeasibleinteriorpoint algorithm for monotone complementarity problems'', Mathematics of Operations Research, 21 (1996), 815838. MR 97j:90076
 35.
 S. Xu, ``The global linear convergence of an infeasible noninterior pathfollowing algorithm for complementarity problems with uniform functions", Preprint, Department of Mathematics, University of Washington, Seattle, WA 98195, December 1996.
 36.
 S. Xu, ``The global linear convergence and complexity of a noninterior pathfollowing algorithm for monotone LCP based on ChenHarkerKanzowSmale smooth functions", Preprint, Department of Mathematics, University of Washington, Seattle, WA 98195, February 1997.
Similar Articles
Retrieve articles in Mathematics of Computation of the American Mathematical Society
with MSC (1991):
90C33,
90C30,
65H10
Retrieve articles in all journals
with MSC (1991):
90C33,
90C30,
65H10
Additional Information
Liqun Qi
Affiliation:
School of Mathematics, The University of New South Wales, Sydney 2052, Australia
Email:
L.Qi@unsw.edu.au
Defeng Sun
Affiliation:
School of Mathematics, The University of New South Wales, Sydney 2052, Australia
Email:
sun@maths.unsw.edu.au
DOI:
http://dx.doi.org/10.1090/S0025571899010820
PII:
S 00255718(99)010820
Keywords:
Nonlinear complementarity problem,
noninterior point,
approximation,
superlinear convergence
Received by editor(s):
June 9, 1997
Received by editor(s) in revised form:
March 9, 1998
Published electronically:
February 19, 1999
Additional Notes:
This work is supported by the Australian Research Council.
Article copyright:
© Copyright 1999 American Mathematical Society
