Extended semismooth Newton method for functions with values in a cone. (English) Zbl 1396.49022
Summary: This paper deals with variational inclusions of the form \(0 \in K-f(x)\) where \(f : \mathbb R^n\rightarrow \mathbb R^m\) is a semismooth function and \(K\) is a nonempty closed convex cone in \(\mathbb R^m\). We show that the previous problem can be solved by a Newton-type method using the Clarke generalized Jacobian of \(f\).
The results obtained in this paper extend those obtained by Robinson in the famous paper [S. M. Robinson, Numer. Math. 19, 341–347 (1972; Zbl 0227.65040)]. We provide a semilocal method with a superlinear convergence that is new in the context of semismooth functions. Finally, numerical results are also given to illustrate the convergence.
The results obtained in this paper extend those obtained by Robinson in the famous paper [S. M. Robinson, Numer. Math. 19, 341–347 (1972; Zbl 0227.65040)]. We provide a semilocal method with a superlinear convergence that is new in the context of semismooth functions. Finally, numerical results are also given to illustrate the convergence.
MSC:
| 49M15 | Newton-type methods |
| 49J53 | Set-valued and variational analysis |
| 47H04 | Set-valued operators |
| 65K10 | Numerical optimization and variational techniques |
| 14P15 | Real-analytic and semi-analytic sets |
Keywords:
variational inclusion; semismooth function; closed convex cone; majorizing sequence; normed convex processCitations:
Zbl 0227.65040References:
| [1] | Adly, S.; Seeger, A., A nonsmooth algorithm for cone-constrained eigenvalue problems, Comput. Optim. Appl., 49, 299-318, (2011) · Zbl 1220.90128 · doi:10.1007/s10589-009-9297-7 |
| [2] | Aubin, J.-P., Lipschitz behaviour of solutions to convex minimization problems, Math. Oper. Res., 9, 87-111, (1984) · Zbl 0539.90085 · doi:10.1287/moor.9.1.87 |
| [3] | Aubin, J.-P., Frankowska, H.: Set Valued Analysis. Birkhäuser, Boston (1990) · Zbl 0713.49021 |
| [4] | Bolte, J.; Daniilidis, A.; Lewis, A., Tame functions are semismooth, Math. Program., Ser. B, 117, 5-19, (2009) · Zbl 1158.49030 · doi:10.1007/s10107-007-0166-9 |
| [5] | Burke, J.V.; Qi, L., Weak directional closedness and generalized subdifferentials, J. Math. Anal. Appl., 159, 485-499, (1981) · Zbl 0818.46041 · doi:10.1016/0022-247X(91)90209-I |
| [6] | Cabuzel, C.; Pietrus, A., Local convergence of newton’s method for subanalytic variational inclusions, Positivity, 12, 525-533, (2008) · Zbl 1191.49032 · doi:10.1007/s11117-007-2155-x |
| [7] | Chaney, R.W., Second-order necessary conditions in constrained semismooth optimization, SIAM J. Control Optim., 25, 1072-1081, (1987) · Zbl 0635.49013 · doi:10.1137/0325059 |
| [8] | Chaney, R.W., Second-order necessary conditions in semismooth optimization, Math. Program., 40, 95-109, (1988) · Zbl 0663.49004 · doi:10.1007/BF01580725 |
| [9] | Clarke, F.H.: Optimization and Nonsmooth Analysis. SIAM, Philadelphia (1990) · Zbl 0696.49002 · doi:10.1137/1.9781611971309 |
| [10] | Correa, R.; Joffre, A.; Comtesse, L. (ed.); Correa, R. (ed.); Weintraub, A. (ed.), Some properties of semismooth and regular functions in nonsmooth analysis, (1987), Berlin |
| [11] | Correa, R.; Joffre, A., Tangent continuous directional derivatives in nonsmooth analysis, J. Optim. Theory Appl., 6, 1-21, (1989) · Zbl 0644.49016 · doi:10.1007/BF00940840 |
| [12] | Dontchev, A.L., Local convergence of the Newton method for generalized equation, C. R. Acad. Sci., Ser. 1 Math., 322, 327-331, (1996) · Zbl 0844.47034 |
| [13] | Dontchev, A.L., Uniform convergence of the Newton method for Aubin continuous maps, Serdica Math. J., 22, 385-398, (1996) · Zbl 0865.90115 |
| [14] | Dontchev, A.L.; Quincampoix, M.; Zlateva, N., Aubin criterion for metric regularity, J. Convex Anal., 13, 281-297, (2006) · Zbl 1098.49018 |
| [15] | Dontchev, A.L., Rockafellar, R.T.: Implicit Functions and Solution Mappings. Springer Monographs in Mathematics. Springer, New York (2009) · Zbl 1178.26001 · doi:10.1007/978-0-387-87821-8 |
| [16] | Fischer, A., A special Newton-type optimization method, Optimization, 24, 269-284, (1992) · Zbl 0814.65063 · doi:10.1080/02331939208843795 |
| [17] | Jean-Alexis, C.; Pietrus, A., Newton-secant method for functions with values in a cone, Serdica Math. J., 39, 271-286, (2013) · Zbl 1324.49016 |
| [18] | Kantorovich, L.V., On newton’s method, Tr. Mat. Inst. Steklova, 28, 105-144, (1949) · Zbl 0038.07401 |
| [19] | Levitin, E.S.; Polyak, B.T., Constrained minimization methods, Ž. Vyčisl. Mat. Mat. Fiz., 6, 787-823, (1996) · Zbl 0184.38902 |
| [20] | Lewis, A.S., Ill-conditioned convex processes and conic linear systems, Math. Oper. Res., 24, 829-834, (1999) · Zbl 1074.90559 · doi:10.1287/moor.24.4.829 |
| [21] | Lewis, A.S., Ill-conditioned inclusions, Set-Valued Anal., 4, 375-381, (2001) · Zbl 0994.15006 · doi:10.1023/A:1012610112736 |
| [22] | Mifflin, R., Semismooth and semiconvex functions in constrained optimization, SIAM J. Control Optim., 15, 959-972, (1977) · Zbl 0376.90081 · doi:10.1137/0315061 |
| [23] | Mifflin, R., An algorithm for constrained optimization with semismooth functions, Math. Oper. Res., 2, 191-207, (1977) · Zbl 0395.90069 · doi:10.1287/moor.2.2.191 |
| [24] | Mordukhovich, B.S., Complete characterization of openess metric regularity and Lipschitzian properties of multifunctions, Trans. Am. Math. Soc., 340, 1-36, (1993) · Zbl 0791.49018 · doi:10.1090/S0002-9947-1993-1156300-4 |
| [25] | Mordukhovich, B.S.: Variational Analysis and Generalized Differentiation I: Basic Theory. A Series of Comprehensive Studies in Mathematics, vol. 330. Springer, New York (2006) |
| [26] | Piétrus, A., Non differentiable perturbed newton’s method for functions with values on a cone, Investig. Oper., 35, 58-67, (2014) · Zbl 1314.49017 |
| [27] | Qi, L., Semismoothness and decomposition of maximal normal operators, J. Math. Anal. Appl., 146, 271-279, (1990) · Zbl 0717.49013 · doi:10.1016/0022-247X(90)90347-I |
| [28] | Qi, L.; Sun, J., Semismooth version of newton’s method, Math. Program., 58, 353-367, (1993) · Zbl 0780.90090 · doi:10.1007/BF01581275 |
| [29] | Qi, L.; Yin, H., A strongly semismooth integral function and its application, Comput. Optim. Appl., 25, 223-246, (2003) · Zbl 1065.90076 · doi:10.1023/A:1022969507994 |
| [30] | Rheinboldt, W.C., A unified convergence theory for a class of iterative processes, SIAM J. Numer. Anal., 5, 42-63, (1968) · Zbl 0155.46701 · doi:10.1137/0705003 |
| [31] | Robinson, S.M., Normed convex processes, Trans. Am. Math. Soc., 174, 127-140, (1972) · Zbl 0264.47018 · doi:10.1090/S0002-9947-1972-0313769-9 |
| [32] | Robinson, S.M., Extension of newton’s method to non linear functions with values in a cone, Numer. Math., 19, 341-347, (1972) · Zbl 0227.65040 · doi:10.1007/BF01404880 |
| [33] | Robinson, S.M., Generalized equations and their solutions, part I: basic theory, Math. Program. Stud., 10, 128-141, (1979) · Zbl 0404.90093 · doi:10.1007/BFb0120850 |
| [34] | Robinson, S.M., Generalized equations and their solutions, part II: application to nonlinear programming, Math. Program. Stud., 19, 200-221, (1982) · Zbl 0495.90077 · doi:10.1007/BFb0120989 |
| [35] | Rockafellar, R.T.; Nurminski, E. (ed.), Favorable classes of Lipschitz-continuous functions in subgradient optimization, 125-143, (1982), New York · Zbl 0511.26009 |
| [36] | Rockafellar, R.T., Lipschitzian properties of multifonctions, Nonlinear Anal., 9, 867-885, (1984) · Zbl 0573.54011 · doi:10.1016/0362-546X(85)90024-0 |
| [37] | Rockafellar, R.T., Wets, R.J.B.: Variational Analysis. A Series of Comprehensives Studies in Mathematics, vol. 317. Springer, New York (1998) · Zbl 0888.49001 |
| [38] | Rockafellar, R.T.: Monotone Processes of Convex and Concave Type. Memoirs, vol. 77. Am. Math. Soc., Providence (1967) · Zbl 0189.19602 |
| [39] | Rockafellar, R.T.: Convex Analysis. Princeton Univ. Press, Princeton (1970) · Zbl 0193.18401 · doi:10.1515/9781400873173 |
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.
