Abstract
We discuss local convergence of Newton’s method to a singular solution x * of the nonlinear equations F(x) = 0, for \(F:{\mathbb{R}}^n \rightarrow {\mathbb{R}}^n\) . It is shown that an existing proof of Griewank, concerning linear convergence to a singular solution x * from a starlike domain around x * for F twice Lipschitz continuously differentiable and x * satisfying a particular regularity condition, can be adapted to the case in which F′ is only strongly semismooth at the solution. Further, Newton’s method can be accelerated to produce fast linear convergence to a singular solution by overrelaxing every second Newton step. These results are applied to a nonlinear-equations reformulation of the nonlinear complementarity problem (NCP) whose derivative is strongly semismooth when the function f arising in the NCP is sufficiently smooth. Conditions on f are derived that ensure that the appropriate regularity conditions are satisfied for the nonlinear-equations reformulation of the NCP at x *.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Daryina A.N., Izmailov A.F. and Solodov M.V. (2004). A class of active-set Newton methods for mixed complementarity problems. SIAM J. Optim. 15(2): 409–429
Decker D.W., Keller H.B. and Kelley C.T. (1983). Convergence rates for Newton’s method at singular points. SIAM J. Numer. Anal. 20: 296–314
Decker D.W. and Kelley C.T. (1980). Newton’s method at singular points. I.. SIAM J. Numer. Anal. 17(1): 66–70
Decker D.W. and Kelley C.T. (1981). Convergence acceleration for Newton’s method at singular points. SIAM J. Numer. Anal. 19: 219–229
Evtushenko Y.G. and Purtov V.A. (1984). Sufficient conditions for a minimum for nonlinear programming problems. Soviet Math. Dokl. 30: 313–316
Facchinei F. and Pang J. (2003). Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer, Heidelberg
Golub G.H. and Van Loan C.F. (1996). Matrix Computations, third edn. The Johns Hopkins University Press, Baltimore
Griewank A. (1980). Starlike domains of convergence for Newton’s method at singularities. Numer. Math. 35(1): 95–111
Griewank A. (1985). On solving nonlinear equations with simple singularities or nearly singular solutions. SIAM Rev. 27: 537–563
Griewank A. and Osborne M.R. (1981). Newton’s method for singular problems when the dimension of the null space is > 1. SIAM J. Numer. Anal. 18(1): 145–149
Izmailov A.F. and Solodov M.V. (2001). Error bounds for 2-regular mappings with Lipschitzian derivatives and their applications. Math. Program. Ser. A 89: 413–435
Izmailov A.F. and Solodov M.V. (2002). Superlinearly convergent algorithms for solving singular equations and smooth reformulations of complementarity problems. SIAM J. Optim. 13(2): 386–405
Izmailov A.F. and Solodov M.V. (2002). The theory of 2-regularity for mappings with Lipschitzian derivatives and its applications to optimality conditions. Math. Oper. Res. 27: 614–635
Josephy, N.H.: Newton’s method for generalized equations. Technical Summary Report 1965, Mathematics Research Center, University of Wisconsin-Madison (1979)
Kanzow C. (1994). Some equation-based methods for the nonlinear complementarity problem. Optim. Methods Softw. 3(1): 327–340
Kelley C.T. and Suresh R. (1983). A new acceleration method for Newton’s method at singular points. SIAM J. Numer. Anal. 20(5): 1001–1009
ftp://ftp.cs.wisc.edu/math-prog/mcplib
Oberlin, C., Wright, S.J.: An accelerated Newton method for equations with equations with semismooth Jacobians and nonlinear complementarity problems: Extended version. Optimization technical report, Computer Sciences Department, University of Wisconsin-Madison (2006, Revised January 2007)
Qi L. and Sun J. (1993). A nonsmooth version of Newton’s method. Math. Program. 58: 353–367
Reddien G.W. (1978). On Newton’s method for singular problems. SIAM J. Numer. Anal. 15(5): 993–996
Reddien G.W. (1979). Newton’s method and high order singularities. Comput. Math. Appl. 5: 79–86
Author information
Authors and Affiliations
Corresponding author
Additional information
We dedicate this paper to Steve Robinson on the occasion of his 65th birthday, in recognition of his remarkable scholarly accomplishments and in appreciation for his guidance and his collegiality, grace, and kindness.
Research supported by NSF Grants SCI-0330538, DMS-0427689, CCF-0430504, CTS-0456694, CNS-0540147, DOE grant DE-FG02-04ER25627, and an NSF Graduate Research Fellowship.
Rights and permissions
About this article
Cite this article
Oberlin, C., Wright, S.J. An accelerated Newton method for equations with semismooth Jacobians and nonlinear complementarity problems. Math. Program. 117, 355–386 (2009). https://doi.org/10.1007/s10107-007-0173-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-007-0173-x