×

zbMATH — the first resource for mathematics

An inexact Newton-like conditional gradient method for constrained nonlinear systems. (English) Zbl 06902340
Summary: In this paper, we propose an inexact Newton-like conditional gradient method for solving constrained systems of nonlinear equations. The local convergence of the new method as well as results on its rate are established by using a general majorant condition. Two applications of such condition are provided: one is for functions whose derivatives satisfy a Hölder-like condition and the other is for functions that satisfy a Smale condition, which includes a substantial class of analytic functions. Some preliminary numerical experiments illustrating the applicability of the proposed method are also presented.

MSC:
65-XX Numerical analysis
Software:
STRSCNE; minpack; CoDoSol
PDF BibTeX Cite
Full Text: DOI
References:
[1] Behling, R.; Fischer, A., A unified local convergence analysis of inexact constrained Levenberg-Marquardt methods, Optim. Lett., 6, 5, 927-940, (2012) · Zbl 1279.90159
[2] Bellavia, S.; Morini, B., Subspace trust-region methods for large bound-constrained nonlinear equations, SIAM J. Numer. Anal., 44, 4, 1535-1555, (2006) · Zbl 1128.65033
[3] Bellavia, S.; Macconi, M.; Morini, B., An affine scaling trust-region approach to bound-constrained nonlinear systems, Appl. Numer. Math., 44, 3, 257-280, (2003) · Zbl 1018.65067
[4] Bellavia, S.; Macconi, M.; Pieraccini, S., Constrained dogleg methods for nonlinear systems with simple bounds, Comput. Optim. Appl., 53, 3, 771-794, (2012) · Zbl 1262.90163
[5] Bogle, I. D.L.; Perkins, J. D., A new sparsity preserving quasi-Newton update for solving nonlinear equations, SIAM J. Sci. Stat. Comput., 11, 4, 621-630, (1990) · Zbl 0749.65033
[6] Broyden, C. G., The convergence of an algorithm for solving sparse nonlinear systems, Math. Comput., 25, 285-294, (1971) · Zbl 0227.65038
[7] Chen, J.; Li, W., Convergence behaviour of inexact Newton methods under weak Lipschitz condition, J. Comput. Appl. Math., 191, 1, 143-164, (2006) · Zbl 1092.65043
[8] Cruz, W. L.; Raydan, M., Nonmonotone spectral methods for large-scale nonlinear systems, Optim. Methods Softw., 18, 5, 583-599, (2003) · Zbl 1069.65056
[9] Dunn, J. C., Convergence rates for conditional gradient sequences generated by implicit step length rules, SIAM J. Control Optim., 18, 5, 473-487, (1980) · Zbl 0457.65048
[10] Echebest, N.; Schuverdt, M. L.; Vignau, R. P., A derivative-free method for solving box-constrained underdetermined nonlinear systems of equations, Appl. Math. Comput., 219, 6, 3198-3208, (2012) · Zbl 1309.65055
[11] Facchinei, F.; Fischer, A.; Herrich, M., An LP-Newton method: nonsmooth equations, KKT systems, and nonisolated solutions, Math. Program., Ser. A, 146, 1-2, 1-36, (2014) · Zbl 1317.90276
[12] Ferreira, O. P.; Gonçalves, M. L.N., Local convergence analysis of inexact Newton-like methods under majorant condition, Comput. Optim. Appl., 48, 1, 1-21, (2011) · Zbl 1279.90195
[13] Floudas, C. A., Handbook of test problems in local and global optimization, Nonconvex Optimization and Its Applications, vol. 33, (1999), Kluwer Academic Dordrecht
[14] Frank, M.; Wolfe, P., An algorithm for quadratic programming, Nav. Res. Logist., 3, 1-2, 95-110, (1956)
[15] Freund, R.; Grigas, P., New analysis and results for the Frank-Wolfe method, Math. Program., 1-32, (2014)
[16] Gonçalves, M. L.N., Local convergence of the Gauss-Newton method for injective-overdetermined systems of equations under a majorant condition, Comput. Math. Appl., 66, 4, 490-499, (2013) · Zbl 1360.65160
[17] Gonçalves, M. L.N., Inexact Gauss-Newton like methods for injective-overdetermined systems of equations under a majorant condition, Numer. Algorithms, 72, 2, 377-392, (2016) · Zbl 1343.65059
[18] Gonçalves, M. L.N.; Melo, J. G., A Newton conditional gradient method for constrained nonlinear systems, J. Comput. Appl. Math., 311, 473-483, (2017) · Zbl 1382.65141
[19] Harchaoui, Z.; Juditsky, A.; Nemirovski, A., Conditional gradient algorithms for norm-regularized smooth convex optimization, Math. Program., 1-38, (2014)
[20] Huang, Z., The convergence ball of Newton’s method and the uniqueness ball of equations under Hölder-type continuous derivatives, Comput. Math. Appl., 47, 2-3, 247-251, (2004) · Zbl 1052.65054
[21] Jaggi, M., Revisiting Frank-Wolfe: projection-free sparse convex optimization, (Proceedings of the 30th International Conference on Machine Learning, vol. 28, ICML-13, (2013)), 427-435
[22] Kanzow, C., An active set-type Newton method for constrained nonlinear systems, (Ferris, M.; Mangasarian, O.; Pang, J.-S., Complementarity: Applications, Algorithms and Extensions, Appl. Optim., vol. 50, (2001), Springer US), 179-200 · Zbl 0983.90060
[23] Kanzow, C., Strictly feasible equation-based methods for mixed complementarity problems, Numer. Math., 89, 1, 135-160, (2001) · Zbl 0992.65070
[24] Kelley, C., Iterative methods for linear and nonlinear equations, (1995), Society for Industrial and Applied Mathematics · Zbl 0832.65046
[25] Kozakevich, D. N.; Mario, J.; Santos, S. A., Solving nonlinear systems of equations with simple constraints, Comput. Appl. Math., 16, 215-235, (1997) · Zbl 0896.65041
[26] La Cruz, W., A projected derivative-free algorithm for nonlinear equations with convex constraints, Optim. Methods Softw., 29, 1, 24-41, (2014) · Zbl 1285.65028
[27] La Cruz, W.; Martínez, J. M.; Raydan, M., Spectral residual method without gradient information for solving large-scale nonlinear systems of equations, Math. Comput., 75, 255, 1429-1448, (2006) · Zbl 1122.65049
[28] Lan, G.; Zhou, Y., Conditional gradient sliding for convex optimization, SIAM J. Optim., 26, 2, 1379-1409, (2016) · Zbl 1342.90132
[29] Lukšan, L.; Vlček, J., Computational experience with globally convergent descent methods for large sparse systems of nonlinear equations, Optim. Methods Softw., 8, 201-223, (1998) · Zbl 0927.65068
[30] Lukšan, L.; Vlček, J., Sparse and partially separable test problems for unconstrained and equality constrained optimization, (1999), Institute of Computer Science, Academy of Sciences of the Czech Republic, Technical Report No. 767 · Zbl 0955.90102
[31] Lukšan, L.; Vlček, J., Test problems for unconstrained optimization, (2003), Institute of Computer Science, Academy of Sciences of the Czech Republic, Technical Report No. 897 · Zbl 1029.90060
[32] Luo, Z.-Q.; Tseng, P., Error bounds and convergence analysis of feasible descent methods: a general approach, Ann. Oper. Res., 46/47, 1-4, 157-178, (1993) · Zbl 0793.90076
[33] Luss, R.; Teboulle, M., Conditional gradient algorithms for rank-one matrix approximations with a sparsity constraint, SIAM Rev., 55, 1, 65-98, (2013) · Zbl 1263.90094
[34] Macconi, M.; Morini, B.; Porcelli, M., Trust-region quadratic methods for nonlinear systems of mixed equalities and inequalities, Appl. Numer. Math., 59, 5, 859-876, (2009) · Zbl 1165.65030
[35] Marini, L.; Morini, B.; Porcelli, M., Quasi-Newton methods for constrained nonlinear systems: complexity analysis and applications, Comput. Optim. Appl., (2018) · Zbl 1405.90143
[36] Martinez, M. J., Quasi-inexact-Newton methods with global convergence for solving constrained nonlinear systems, Nonlinear Anal., 30, 1, 1-7, (1997) · Zbl 0898.65024
[37] Moré, J. J.; Garbow, B. S.; Hillstrom, K. E., Testing unconstrained optimization software, ACM Trans. Math. Softw., 7, 1, 17-41, (1981) · Zbl 0454.65049
[38] Morini, B., Convergence behaviour of inexact Newton methods, Math. Comput., 68, 228, 1605-1613, (1999) · Zbl 0933.65050
[39] Morini, B.; Porcelli, M.; Toint, P. L., Approximate norm descent methods for constrained nonlinear systems, Math. Comput., 87, 311, 1327-1351, (2018) · Zbl 1383.65051
[40] Porcelli, M., On the convergence of an inexact Gauss-Newton trust-region method for nonlinear least-squares problems with simple bounds, Optim. Lett., 7, 3, 447-465, (2013) · Zbl 1268.90091
[41] Schubert, L. K., Modification of a quasi-Newton method for nonlinear equations with a sparse Jacobian, Math. Comput., 24, 27-30, (1970) · Zbl 0198.49402
[42] Shen, W.; Li, C., Smale’s α-theory for inexact Newton methods under the γ-condition, J. Math. Anal. Appl., 369, 1, 29-42, (2010) · Zbl 1193.65090
[43] Smale, S., Newton’s method estimates from data at one point, (The Merging of Disciplines: New Directions in Pure, Applied, and Computational Mathematics, Laramie, Wyo., 1985, (1986), Springer New York), 185-196
[44] Wang, P.; Zhu, D., An inexact derivative-free Levenberg-Marquardt method for linear inequality constrained nonlinear systems under local error bound conditions, Appl. Math. Comput., 282, 32-52, (2016) · Zbl 1410.49037
[45] Zhang, Y.; Zhu, D.-t., Inexact Newton method via Lanczos decomposed technique for solving box-constrained nonlinear systems, Appl. Math. Mech., 31, 12, 1593-1602, (2010) · Zbl 1275.65030
[46] Zhu, D., An affine scaling trust-region algorithm with interior backtracking technique for solving bound-constrained nonlinear systems, J. Comput. Appl. Math., 184, 2, 343-361, (2005) · Zbl 1087.65047
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.