Abstract
We investigate a global complexity bound of the Levenberg–Marquardt Method (LMM) for nonsmooth equations. The global complexity bound is an upper bound to the number of iterations required to get an approximate solution that satisfies a certain condition. We give sufficient conditions under which the bound of the LMM for nonsmooth equations is the same as smooth cases. We also show that it can be reduced under some regularity assumption. Furthermore, by applying these results to nonsmooth equations equivalent to the nonlinear complementarity problem (NCP), we get global complexity bounds for the NCP. In particular, we give a reasonable bound when the mapping involved in the NCP is a uniformly P-function.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Facchinei, F., Pang, J.-S.: Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer, New York (2003)
Facchinei, F., Kanzow, C.: A nonsmooth inexact Newton method for the solution of large-scale nonlinear complementarity problems. Math. Program., Ser. A 76, 493–512 (1997)
Jiang, H., Ralph, D.: Global and local superlinear convergence analysis of Newton-type methods for semismooth equations with smooth least squares. In: Fukushima, M., Qi, L. (eds.) Reformulation: Nonsmooth, Piecewise Smooth, Semismooth and Smoothing Methods, pp. 181–209. Kluwer Academic, Dordrecht (1999)
Kanzow, C., Yamashita, N., Fukushima, M.: Levenberg-Marquardt methods with strong local convergence properties for solving nonlinear equations with convex constraints. J. Comput. Appl. Math. 173, 321–343 (2005)
Ma, C., Tang, J.: The quadratic convergence of a smoothing Levenberg-Marquardt method for nonlinear complementarity problem. Appl. Math. Comput. 197, 566–581 (2008)
Ma, C., Tang, J., Chen, X.: A globally convergent Levenberg-Marquardt method for solving nonlinear complementarity problem. Appl. Math. Comput. 192, 370–381 (2007)
Sabramanian, P.K.: Gauss-Newton methods for the complementarity problem. J. Optim. Theory Appl. 77, 467–482 (1993)
Zhang, J., Zhang, X.: A smoothing Levenberg-Marquardt method for NCP. Appl. Math. Comput. 178, 212–228 (2006)
Cartis, C., Gould, N.I.M., Toint, P.L.: On the complexity of steepest descent, Newton’s and regularized Newton’s methods for nonconvex unconstrained optimization problems. Technical Report 09/14, Department of Mathematics, FUNDP—University of Namur (2009)
Cartis, C., Gould, N.I.M., Toint, P.L.: Adaptive cubic regularization methods for unconstrained optimization. PartII: worst-case function- and derivative-evaluation complexity. Math. Program. doi:10.1007/s10107-009-0337-y
Gratton, S., Sartenaer, A., Toint, P.L.: Recursive trust-region methods for multiscale nonlinear optimization. SIAM J. Optim. 19, 414–444 (2008)
Nesterov, Yu.: Introductory Lectures on Convex Optimization. Kluwer Academic, Dordrecht (2004)
Nesterov, Yu.: Accelerating the cubic regularization of Newton’s method on convex problems. Math. Program., Ser. B 112, 159–181 (2008)
Nesterov, Yu., Polyak, B.T.: Cubic regularization of Newton method and its global performance. Math. Program., Ser. A 108, 177–205 (2006)
Polyak, R.A.: Regularized Newton method for unconstrained convex optimization. Math. Program., Ser. B 120, 125–145 (2009)
Ueda, K., Yamashita, N.: Convergence properties of the regularized Newton method for the unconstrained nonconvex optimization. Appl. Math. Optim. 62, 27–46 (2010)
Ueda, K., Yamashita, N.: On a global complexity bound of the Levenberg-Marquardt method. J. Optim. Theory Appl. 147, 443–453 (2010)
Clarke, F.H.: Optimization and Nonsmooth Analysis. SIAM, Philadelphia (1983)
Qi, L.: Convergence analysis of some algorithms for solving nonsmooth equations. Math. Oper. Res. 18, 227–244 (1993)
Qi, L., Sun, J.: A nonsmooth version of Newton’s method. Math. Program., Ser. A 58, 353–367 (1993)
Hogan, W.W.: Point-to-set maps in mathematical programming. SIAM Rev. 15, 591–603 (1973)
Moré, J.J.: The Levenberg-Marquardt algorithm: implementation and theory. In: Numerical Analysis. Lecture Notes in Mathematics, vol. 630, pp. 105–116 (1978)
Osborne, M.R.: Nonlinear least squares—the Levenberg algorithm revisited. J. Aust. Math. Soc. 19, 343–357 (1976)
Fischer, A.: A special Newton-type optimization method. Optimization 24, 269–284 (1992)
Facchinei, F., Soares, J.: A new merit function for nonlinear complementarity problems and a related algorithm. SIAM J. Optim. 7, 225–247 (1997)
Chen, J.-S.: The semismooth-related properties of a merit function and a descent method for the nonlinear complementarity problem. J. Glob. Optim. 36, 565–580 (2006)
Chen, B., Chen, X., Kanzow, C.: A penalized Fischer-Burmeister NCP-function. Math. Program., Ser. A 88, 211–216 (2000)
Jiang, H., Qi, L.: A new nonsmooth equations approach to nonlinear complementarity problems. SIAM J. Control Optim. 35, 178–193 (1997)
Kanzow, C., Fukushima, M.: Equivalence of the generalized complementarity problem to differentiable unconstrained minimization. J. Optim. Theory Appl. 90, 581–603 (1996)
Moré, J.J.: Classes of functions and feasibility conditions in nonlinear complementarity problems. Math. Program., Ser. A 6, 327–338 (1974)
Luca, T.D., Facchinei, F., Kanzow, C.: A semismooth equation approach to the solution of nonlinear complementarity problems. Math. Program., Ser. A 75, 407–439 (1996)
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Ilio Galligani.
Rights and permissions
About this article
Cite this article
Ueda, K., Yamashita, N. Global Complexity Bound Analysis of the Levenberg–Marquardt Method for Nonsmooth Equations and Its Application to the Nonlinear Complementarity Problem. J Optim Theory Appl 152, 450–467 (2012). https://doi.org/10.1007/s10957-011-9907-2
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10957-011-9907-2