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

Qi, Liqun; Sun, Jie

Math. Program. 58, No. 3 (A), 353-367 (1993).

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.

MSC:

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

Keywords:

nonlinear equation of several variables; generalized Jacobian; B- derivative; semismoothness; gradient function; augmented Lagrangian

References:

[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
[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
[3]	R. W. Chaney, ”Second-order necessary conditions in semismooth optimization,”Mathematical Programming 40 (1988) 95–109. · Zbl 0663.49004
[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
[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
[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
[11]	R. Mifflin, ”An algorithm for constrained optimization with semismooth functions,”Mathematics of Operations Research 2 (1977) 191–207. · Zbl 0395.90069
[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
[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
[15]	L. Qi, ”Semismoothness and decomposition of maximal normal operators,”Journal of Mathematical Analysis and Applications 146 (1990) 271–279. · Zbl 0717.49013
[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
[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
[23]	R.T. Rockafellar, ”Computational schemes for solving large-scale problems in extended linearquadratic programming,”Mathematical Programming 48 (1990) 447–474. · Zbl 0735.90050
[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
[25]	A. Shapiro, ”On concepts of directional differentiability,”Journal of Optimization Theory and Applications 66 (1990) 477–487. · Zbl 0682.49015
[26]	J.E. Spingarn, ”Submonotone subdifferentials of Lipschitz functions,”Transactions of the American Mathematical Society 264 (1981) 77–89. · Zbl 0465.26008
[27]	J. Sun, ”An affine-scaling method for linearly constrained convex programs,” Preprint, Department of IEMS, Northwestern University (Evanston, IL, 1990).