Convergence of quasi-Newton methods for solving constrained generalized equations
ESAIM: Control, Optimisation and Calculus of Variations, Tome 28 (2022), article no. 32

In this paper, we focus on quasi-Newton methods to solve constrained generalized equations. As is well-known, this problem was firstly studied by Robinson and Josephy in the 70’s. Since then, it has been extensively studied by many other researchers, specially Dontchev and Rockafellar. Here, we propose two Broyden-type quasi-Newton approaches to dealing with constrained generalized equations, one that requires the exact resolution of the subproblems, and other that allows inexactness, which is closer to numerical reality. In both cases, projections onto the feasible set are also inexact. The local convergence of general quasi-Newton approaches is established under a bounded deterioration of the update matrix and Lipschitz continuity hypotheses. In particular, we prove that a general scheme converges linearly to the solution under suitable assumptions. Furthermore, when a Broyden-type update rule is used, the convergence is superlinearly. Some numerical examples illustrate the applicability of the proposed methods.

DOI : 10.1051/cocv/2022026
Classification : 90C53, 65K15
Keywords: Inexact quasi-Newton, Constrained generalized equations, Inexact projection, Broyden update 
@article{COCV_2022__28_1_A32_0,
     author = {Andreani, Roberto and Carvalho, Rui M. and Secchin, Leonardo D. and Silva, Gilson N.},
     title = {Convergence of {quasi-Newton} methods for solving constrained generalized equations},
     journal = {ESAIM: Control, Optimisation and Calculus of Variations},
     year = {2022},
     publisher = {EDP-Sciences},
     volume = {28},
     doi = {10.1051/cocv/2022026},
     mrnumber = {4428679},
     zbl = {1493.90232},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/cocv/2022026/}
}
TY  - JOUR
AU  - Andreani, Roberto
AU  - Carvalho, Rui M.
AU  - Secchin, Leonardo D.
AU  - Silva, Gilson N.
TI  - Convergence of quasi-Newton methods for solving constrained generalized equations
JO  - ESAIM: Control, Optimisation and Calculus of Variations
PY  - 2022
VL  - 28
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/cocv/2022026/
DO  - 10.1051/cocv/2022026
LA  - en
ID  - COCV_2022__28_1_A32_0
ER  - 
%0 Journal Article
%A Andreani, Roberto
%A Carvalho, Rui M.
%A Secchin, Leonardo D.
%A Silva, Gilson N.
%T Convergence of quasi-Newton methods for solving constrained generalized equations
%J ESAIM: Control, Optimisation and Calculus of Variations
%D 2022
%V 28
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/cocv/2022026/
%R 10.1051/cocv/2022026
%G en
%F COCV_2022__28_1_A32_0
Andreani, Roberto; Carvalho, Rui M.; Secchin, Leonardo D.; Silva, Gilson N. Convergence of quasi-Newton methods for solving constrained generalized equations. ESAIM: Control, Optimisation and Calculus of Variations, Tome 28 (2022), article no. 32. doi: 10.1051/cocv/2022026

[1] M. Abbas, M. Alshahrani, Q. H. Ansari, O. S. Iyiola and Y. Shehu, Iterative methods for solving proximal split minimization problems. Numer. Algor. 78 (2018) 193–215. | MR | Zbl | DOI

[2] S. Adly, R. Cibulka and H. V. Ngai, Newton’s method for solving inclusions using set-valued approximations. SIAM J. Optim. 25 (2015) 159–184. | MR | Zbl | DOI

[3] S. Adly and V. N. Huynh, Quasi-Newton methods for solving nonsmooth equations: generalized Dennis-Moré theorem and Broyden’s update. J. Convex Anal. 25 (2018) 1075–1104. | MR | Zbl

[4] S. Adly, H. Van Ngai and V. V. Nguyen, Newton’s method for solving generalized equations: Kantorovich’s and Smale’s approaches. J. Math. Anal. Appl. 439 (2016) 396–418. | MR | Zbl | DOI

[5] A. A. Aguiar, O. P. Ferreira and L. F. Prudente, Subgradient method with feasible inexact projections for constrained convex optimization problems. Optimization (2021) 1–23. | MR | Zbl

[6] F. J. Aragón Artacho, A. Belyakov, A. L. Dontchev and M. López, Local convergence of quasi-Newton methods under metric regularity. Comput. Optim. Appl. 58 (2014) 225–247. | MR | Zbl | DOI

[7] F. J. Aragón Artacho, A. L. Dontchev, M. Gaydu, M. H. Geoffroy and V. M. Veliov, Metric Regularity of Newton’s Iteration. SIAM J. Control Optim. 49 (2011) 339–362. | MR | Zbl | DOI

[8] D. Azé and C. C. Chou, On a Newton type iterative method for solving inclusions. Math. Oper. Res. 20 (1995) 790–800. | MR | Zbl | DOI

[9] D. Bertsekas, Nonlinear Programming, Optimization and Computation Series, 2nd edn., Athena Scientific, Belmont, MA (1999). | MR | Zbl

[10] J. F. Bonnans, Local analysis of Newton-type methods for variational inequalities and nonlinear programming. Appl. Math. Optim. 29 (1994) 161–186. | MR | Zbl | DOI

[11] Y. Censor, A. Gibali and S. Reich, Algorithms for the split variational inequality problem. Numer. Algor. 59 (2012) 301–323. | MR | Zbl | DOI

[12] Y. Censor, A. Gibali, S. Reich and S. Sabach, Common solutions to variational inequalities. Set-Valued Variat. Anal. 20 (2012) 229–247. | MR | Zbl | DOI

[13] R. Cibulka, A. Dontchev and A. Kruger, Strong metric subregularity of mappings in variational analysis and optimization. J. Math. Anal. Appl. 457 (2018) 1247–1282. | MR | Zbl | DOI

[14] F. R. De Oliveira, O. P. Ferreira and G. N. Silva, Newton’s method with feasible inexact projections for solving constrained generalized equations. Comput. Optim. Appl. 72 (2019) 159–177. | MR | Zbl | DOI

[15] R. S. Dembo, S. C. Eisenstat and T. Steihaug, Inexact Newton methods. SIAM J. Numer. Anal. 19 (1982) 400–408. | MR | Zbl | DOI

[16] S. Dempe, Foundations of Bilevel Programming. Nonconvex Optimization and Its Applications, vol. 61, 1st edn., Springer US, Dordrecht (2002). | MR | Zbl

[17] J. E. Dennis and J. J. Moré, Quasi-Newton methods, motivation and theory. SIAM Rev. 19 (1977) 46–89. | MR | Zbl | DOI

[18] J. E. Dennis and J. J. Moré, A characterization of superlinear convergence and its application to quasi-Newton methods. Math. Comput. 28 (1974) 549–560. | MR | Zbl | DOI

[19] A. Dontchev, Local analysis of a Newton-type method based on partial linearization, in The mathematics of numerical analysis (Park City, UT, 1995), vol. 32. Amer. Math. Soc., Providence, RI (1996), pp. 295–306. | MR | Zbl

[20] A. L. Dontchev, Generalizations of the Dennis-Moré theorem. SIAM J. Optim. 22 (2012) 821–830. | MR | Zbl | DOI

[21] A. L. Dontchev and W. W. Hager, An inverse mapping theorem for set-valued maps. Proc. Am. Math. Soc. 121 (1994) 481–489. | MR | Zbl | DOI

[22] A. L. Dontchev, M. Huang, I. V. Kolmanovsky and M. M. Nicotra, Inexact Newton-Kantorovich methods for constrained nonlinear model predictive control. IEEE Trans. Autom. Control 64 (2019) 3602–3615. | MR | Zbl | DOI

[23] A. L. Dontchev and R. T. Rockafellar, Implicit Functions and Solution Mappings: A View from Variational Analysis, Springer Monographs in Mathematics, 1st edn., Springer, New York, NY (2009). | MR | Zbl

[24] A. L. Dontchev and R. T. Rockafellar, Convergence of inexact Newton methods for generalized equations. Math. Progr. 139 (2013) 115–137. | MR | Zbl | DOI

[25] O. Ferreira and G. Silva, Local convergence analysis of Newton’s method for solving strongly regular generalized equations. J. Math. Anal. Appl. 458 (2018) 481–496. | MR | Zbl | DOI

[26] O. P. Ferreira, A robust semi-local convergence analysis of Newton’s method for cone inclusion problems in Banach spaces under affine invariant majorant condition. J. Comput. Appl. Math. 279 (2015) 318–335. | MR | Zbl | DOI

[27] O. P. Ferreira and G. N. Silva, Kantorovich’s Theorem on Newton’s method for solving strongly regular generalized equation. SIAM J. Optim. 27 (2017) 910–926. | MR | Zbl | DOI

[28] M. L. Gonçalves and J. G. Melo, A Newton conditional gradient method for constrained nonlinear systems. J. Comput. Appl. Math. 311 (2017) 473–483. | MR | Zbl | DOI

[29] H. He, C. Ling and H.-K. Xu, A relaxed projection method for split variational inequalities. J. Optim. Theory Appl. 166 (2015) 213–233. | MR | Zbl | DOI

[30] N. Josephy, Newton’s method for generalized equations and the pies energy model, Ph.D. thesis, University of Wisconsin-Madison (1979).

[31] C. T. Kelley, Iterative methods for linear and nonlinear equations, SIAM (1995). | MR | Zbl | DOI

[32] C. T. Kelley and E. W. Sachs, A new proof of superlinear convergence for Broyden’s method in Hilbert space. SIAM J. Optim. 1 (1991) 146–150. | MR | Zbl | DOI

[33] D. Klatte and B. Kummer, Approximations and generalized Newton methods. Math. Progr. 168 (2018) 673–716. | MR | Zbl | DOI

[34] A. Moudafi, Split monotone variational inclusions. J. Optim. Theory Appl. 150 (2011) 275–283. | MR | Zbl | DOI

[35] S. M. Robinson, Extension of Newton’s method to nonlinear functions with values in a cone. Numer. Math. 19 (1972) 341–347. | MR | Zbl | DOI

[36] S. M. Robinson, Generalized equations and their solutions, Part I: Basic theory. Springer Berlin Heidelberg, Berlin, Heidelberg (1979), pp. 128–141. | Zbl

[37] S. M. Robinson, Strongly regular generalized equations. Math. Oper. Res. 5 (1980) 43–62. | MR | Zbl | DOI

[38] S. M. Robinson, Generalized Equations. Springer Berlin Heidelberg, Berlin, Heidelberg (1983), pp. 346–367. | Zbl

[39] E. W. Sachs, Broyden’s method in Hilbert space. Math. Progr. 35 (1986) 71–82. | MR | Zbl | DOI

[40] L. L. Wei Ouyang, Hölder strong metric subregularity and its applications to convergence analysis of inexact Newton methods. J. Ind. Manag. Optim. 17 (2021) 169–184. | MR | Zbl | DOI

Cité par Sources :

This work has been partially supported by CEPID-CeMEAI (FAPESP 2013/07375-0), FAPESP (grants 2018/24293- 0 and 2017/18308-2), CNPq (grants 306988/2021-6, 309136/2021-0 and 434796/2018-2), PRONEX - CNPq/FAPERJ (grant E-26/010.001247/2016).