A nonsmooth version of Newton’s method. (English) Zbl 0780.90090

Summary: Newton’s method for solving a nonlinear equation of several variables is extended to a nonsmooth case by using the generalized Jacobian instead of the derivative. This extension includes the B-derivative version of Newton’s method as a special case. Convergence theorems are proved under the condition of semismoothness. It is shown that the gradient function of the augmented Lagrangian for \(C^ 2\)-nonlinear programming is semismooth. Thus, the extended Newton’s method can be used in the augmented Lagrangian method for solving nonlinear programs.


90C30 Nonlinear programming
49J52 Nonsmooth analysis
49M15 Newton-type methods
90-08 Computational methods for problems pertaining to operations research and mathematical programming
Full Text: DOI


[1] J.V. Burke and L. Qi, ”Weak directional closedness and generalized subdifferentials,”Journal of Mathematical Analysis and Applications 159 (1991) 485–499. · Zbl 0818.46041 · doi:10.1016/0022-247X(91)90209-I
[2] R.W. Chaney, ”Second-order necessary conditions in constrained semismooth optimization,”SIAM Journal on Control and Optimization 25 (1987) 1072–1081. · Zbl 0635.49013 · doi:10.1137/0325059
[3] R. W. Chaney, ”Second-order necessary conditions in semismooth optimization,”Mathematical Programming 40 (1988) 95–109. · Zbl 0663.49004 · doi:10.1007/BF01580725
[4] F.H. Clarke,Optimization and Nonsmooth Analysis (Wiley, New York, 1983). · Zbl 0582.49001
[5] R. Correa and A. Jofre, ”Some properties of semismooth and regular functions in nonsmooth analysis,” in: L. Contesse, R. Correa and A. Weintraub, eds.,Proceedings of the IFIP Working Conference (Springer, Berlin, 1987).
[6] R. Correa and A. Jofre, ”Tangent continuous directional derivatives in nonsmooth analysis,”Journal of Optimization Theory and Applications 6 (1989) 1–21. · Zbl 0644.49016 · doi:10.1007/BF00940840
[7] P.T. Harker and B. Xiao, ”Newton’s method for the nonlinear complementarity problem: A B-differentiable equation approach,”Mathematical Programming 48 (1990) 339–357. · Zbl 0724.90071 · doi:10.1007/BF01582262
[8] M. Kojima and S. Shindo, ”Extensions of Newton and quasi-Newton methods to systems ofPC 1 Equations,”Journal of Operations Research Society of Japan 29 (1986) 352–374. · Zbl 0611.65032
[9] B. Kummer, ”Newton’s method for non-differentiable functions,” in: J. Guddat, B. Bank, H. Hollatz, P. Kall, D. Karte, B. Kummer, K. Lommatzsch, L. Tammer, M. Vlach and K. Zimmermann, eds.,Advances in Mathematical Optimization (Akademi-Verlag, Berlin, 1988) pp. 114–125. · Zbl 0662.65050
[10] R. Mifflin, ”Semismooth and semiconvex functions in constrained optimization,”SIAM J. Control and Optimization 15 (1977) 957–972. · Zbl 0376.90081 · doi:10.1137/0315061
[11] R. Mifflin, ”An algorithm for constrained optimization with semismooth functions,”Mathematics of Operations Research 2 (1977) 191–207. · Zbl 0395.90069 · doi:10.1287/moor.2.2.191
[12] J.M. Ortega and W.C. Rheinboldt,Iterative Solution of Nonlinear Equations in Several Variables (Academic Press, New York, 1970). · Zbl 0241.65046
[13] J.S. Pang, ”Newton’s method for B-differentiable equations,”Mathematics of Operations Research 15 (1990) 311–341. · Zbl 0716.90090 · doi:10.1287/moor.15.2.311
[14] J.S. Pang, ”A B-differentiable equation-based, globally, and locally quadratically convergent algorithm for nonlinear programs, complementarity and variational inequality problems,”Mathematical Programming 51 (1991) 101–131. · Zbl 0733.90063 · doi:10.1007/BF01586928
[15] L. Qi, ”Semismoothness and decomposition of maximal normal operators,”Journal of Mathematical Analysis and Applications 146 (1990) 271–279. · Zbl 0717.49013 · doi:10.1016/0022-247X(90)90347-I
[16] L. Qi and J. Sun, ”A nonsmooth version of Newton’s method and an interior point algorithm for convex programming,” Applied Mathematics Preprint 89/33, School of Mathematics, The University of New South Wales (Kensington, NSW, 1989).
[17] S.M. Robinson, ”Local structure of feasible sets in nonlinear programming, part III: stability and sensitivity,”Mathematical Programming Study 30 (1987) 45–66. · Zbl 0629.90079
[18] S.M. Robinson, ”An implicit function theorem for B-differentiable functions,”Industrial Engineering Working Paper, University of Wisconsin (Madison, WI, 1988).
[19] S.M. Robinson, ”Newton’s method for a class of nonsmooth functions,”Industrial Engineering Working Paper, University of Wisconsin (Madison, WI, 1988).
[20] R.T. Rockafellar, ”Proximal subgradients, marginal values, and augmented Lagrangians in nonconvex optimization,”Mathematics of Operations Research 6 (1981) 427–437. · Zbl 0492.90073 · doi:10.1287/moor.6.3.424
[21] R.T. Rockafellar, ”Favorable classes of Lipschitz-continuous functions in subgradient optimization,” in: E. Nurminski, ed.,Nondifferentiable Optimization (Pergamon Press, New York, 1982) pp. 125–143. · Zbl 0511.26009
[22] R.T. Rockafellar, ”Linear-quadratic programming and optimal control,”SIAM Journal on Control and Optimization 25 (1987) 781–814. · Zbl 0617.49010 · doi:10.1137/0325045
[23] R.T. Rockafellar, ”Computational schemes for solving large-scale problems in extended linearquadratic programming,”Mathematical Programming 48 (1990) 447–474. · Zbl 0735.90050 · doi:10.1007/BF01582268
[24] R.T. Rockafellar and R.J-B. Wets, ”Generalized linear-quadratic problems of deterministic and stochastic optimal control in discrete time,”SIAM Journal on Control and Optimization 28 (1990) 810–822. · Zbl 0714.49036 · doi:10.1137/0328046
[25] A. Shapiro, ”On concepts of directional differentiability,”Journal of Optimization Theory and Applications 66 (1990) 477–487. · Zbl 0682.49015 · doi:10.1007/BF00940933
[26] J.E. Spingarn, ”Submonotone subdifferentials of Lipschitz functions,”Transactions of the American Mathematical Society 264 (1981) 77–89. · Zbl 0465.26008 · doi:10.1090/S0002-9947-1981-0597868-8
[27] J. Sun, ”An affine-scaling method for linearly constrained convex programs,” Preprint, Department of IEMS, Northwestern University (Evanston, IL, 1990).
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.