Approximate Newton methods for nonsmooth equations. (English) Zbl 0899.90150
Summary: We develop general approximate Newton methods for solving Lipschitz continuous equations by replacing the iteration matrix with a consistently approximated Jacobian, thereby reducing the computation in the generalized Newton method. Locally superlinear convergence results are presented under moderate assumptions. To construct a consistently approximated Jacobian, we introduce two main methods: the classic difference approximation method and the \(\varepsilon\)-generalized Jacobian method. The former can be applied to problems with specific structures, while the latter is expected to work well for general problems. Numerical tests show that the two methods are efficient. Finally, a norm reducing technique for the global convergence of the generalized Newton method is briefly discussed.
MSC:
| 90C30 | Nonlinear programming |
| 65K05 | Numerical mathematical programming methods |
| 49J52 | Nonsmooth analysis |
| 65H10 | Numerical computation of solutions to systems of equations |
Keywords:
semismooth equations; approximate Newton methods; Lipschitz continuous equations; consistently approximated Jacobian; superlinear convergenceReferences:
| [1] | Robinson, S. M., Local Structure of Feasible Sets in Nonlinear Programming Part 3: Stability and Sensitivity, Mathematical Programming Study, Vol. 30, pp. 45–66, 1987. · Zbl 0629.90079 · doi:10.1007/BFb0121154 |
| [2] | Robinson, S. M., Newton’s Method for a Class of Nonsmooth Functions, Working Paper, Industrial Engineering Department, University of Wisconsin, Madison, Wisconsin, 1988. |
| [3] | Robinson, S. M., An Implicit Function Theorem for B-Differentiable Functions, Working Paper, Industrial Engineering Department, University of Wisconsin, Madison, Wisconsin, 1988. |
| [4] | Harker, P. T., and Xiao, B., Newton’s Method for Nonlinear Complementarity Problem: A B-Differentiable Equation Approach, Mathematical Programming, Vol. 48, pp. 339–357, 1990. · Zbl 0724.90071 · doi:10.1007/BF01582262 |
| [5] | Pang, J. S., Newton’s Method for B-Differentiable Equations, Mathematics of Operation Research, Vol. 15, pp. 311–341, 1990. · Zbl 0716.90090 · doi:10.1287/moor.15.2.311 |
| [6] | Pang, J. S., A B-Differentiable Equation-Based, Globally and Locally Quadratically Convergent Algorithm for Nonlinear Programs, Complementarity, and Variational Inequality Problems, Mathematical Programming, Vol. 51, pp. 101–131, 1991. · Zbl 0733.90063 · doi:10.1007/BF01586928 |
| [7] | Qi, L., Superlinearly Convergent Approximate Newton Methods for LC1-Optimization Problems, Mathematical Programming, Vol. 64, pp. 277–294, 1994. · Zbl 0820.90102 · doi:10.1007/BF01582577 |
| [8] | Sun, J., and Qi, L., An Interior Point Algorithm of O( \(\sqrt m \) |log {\(\epsilon\)}|) Iterations for C 1-Convex Programming, Mathematical Programming, Vol. 57, pp. 239–257, 1992. · Zbl 0787.90068 · doi:10.1007/BF01581083 |
| [9] | Xiao, B., and Harker, P. T., A Nonsmooth Newton Method for Variational Inequalities, Part 1: Theory, Mathematical Programming, Vol. 65, pp. 151–194, 1994. · Zbl 0812.65048 · doi:10.1007/BF01581695 |
| [10] | Xiao, B., and Harker, P. T., A Nonsmooth Newton Method for Variational Inequalities, Part 2: Numerical Results, Mathematical Programming, Vol. 65, pp. 195–216, 1994. · Zbl 0812.65049 · doi:10.1007/BF01581696 |
| [11] | Kojima, M., and Shindo, S., Extensions of Newton and Quasi-Newton Methods to Systems of PC1-Equations, Journal of the Operation Research Society of Japan, Vol. 29, pp. 352–374, 1986. · Zbl 0611.65032 |
| [12] | Ip, C. M., and Kyparisis, J., Local Convergence of Quasi-Newton Methods for B-Differentiable Equations, Mathematical Programming, Vol. 58, pp. 71–89, 1992. · Zbl 0761.90088 · doi:10.1007/BF01580895 |
| [13] | Qi, L., and Sun, J., A Nonsmooth Version of Newton’s Method, Mathematical Programming, Vol. 58, pp. 353–367, 1993. · Zbl 0780.90090 · doi:10.1007/BF01581275 |
| [14] | Clarke, F. K., Optimization and Nonsmooth Analysis, John Wiley and Sons, New York, New York, 1983. · Zbl 0582.49001 |
| [15] | Pang, J. S., and Qi, L., Nonsmooth Equations: Motivation and Algorithms, SIAM Journal on Optimization, Vol. 3, pp. 443–465, 1993. · Zbl 0784.90082 · doi:10.1137/0803021 |
| [16] | Qi, L., Convergence Analysis of Some Algorithms for Solving Nonsmooth Equations, Mathematics of Operation Research, Vol. 18, pp. 227–244, 1993. · Zbl 0776.65037 · doi:10.1287/moor.18.1.227 |
| [17] | Chen, X., and Qi, L., A Parameterized Newton Method and a Quasi-Newton Method for Solving Nonsmooth Equations, Computational Optimization and Applications, Vol. 3, pp. 157–179, 1994. · Zbl 0821.65029 · doi:10.1007/BF01300972 |
| [18] | Xu, H., A New Version of Newton’s Method for Nonsmooth Equations, Numerical Report 158, Dundee University, Dundee, Scotland, 1995. |
| [19] | Ortega, J. M., and Rheinboldt, W. C., Iterative Solution of Nonlinear Equations in Several Variables, Academic Press, New York, New York, 1970. · Zbl 0241.65046 |
| [20] | Mayne, D. Q., and Polak, E., Nondifferentiable Optimization Adaptive Smoothing, Journal of Optimization Theory and Applications, Vol. 43, pp. 601–613, 1984. · Zbl 0518.49024 · doi:10.1007/BF00935008 |
| [21] | Martinez, J. M., and Qi, L., Inexact Newton Methods for Solving Nonsmooth Equations, Journal of Computational and Applied Mathematics Vol. 60, pp. 127–145, 1995. · Zbl 0833.65045 · doi:10.1016/0377-0427(94)00088-I |
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.
