×

zbMATH — the first resource for mathematics

An inexact projected LM type algorithm for solving convex constrained nonlinear equations. (English) Zbl 1461.90097
Summary: In this paper, we propose two complementary variants of the projected Levenberg-Marquardt (LM) algorithm for solving convex constrained nonlinear equations. Since the orthogonal projection onto the feasible set may be computationally expensive, we first propose a local LM algorithm in which inexact projections are allowed. The feasible inexact projections used in our algorithm can be easily obtained by means of iterative methods, such as conditional gradient. Local convergence of the proposed algorithm is established by using an error bound condition which is weaker than the standard full-rank assumption. We further present and analyze a global version of this algorithm by means of a nonmonotone line search technique. Numerical experiments are reported to showcase the effectiveness of the proposed algorithms, especially when the projection onto the feasible set is difficult to compute.
MSC:
90C25 Convex programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Behling, R.; Fischer, A.; Haeser, G.; Ramos, A.; Schönefeld, K., On the constrained error bound condition and the projected levenberg-marquardt method, Optimization, 66, 8, 1397-1411 (2017) · Zbl 1407.90306
[2] Behling, R.; Fischer, A.; Herrich, M.; Iusem, A.; Ye, Y., A Levenberg-Marquardt method with approximate projections, Comput. Optim. Appl., 59, 1, 5-26 (2014) · Zbl 1298.90103
[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.; Morini, B., Subspace trust-region methods for large bound-constrained nonlinear equations, SIAM J. Numer. Anal., 44, 4, 1535-1555 (2006) · Zbl 1128.65033
[5] 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
[6] Fan, J., On the Levenberg-Marquardt methods for convex constrained nonlinear equations, J. Ind. Manag. Optim., 9, 1, 227-241 (2013) · Zbl 1294.90061
[7] 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
[8] Gonçalves, M. L.N.; Oliveira, F. R., An inexact Newton-like conditional gradient method for constrained nonlinear systems, Appl. Numer. Math., 132, 22-34 (2018) · Zbl 06902340
[9] Kanzow, C.; Yamashita, N.; Fukushima, M., Levenberg-marquardt methods with strong local convergence properties for solving nonlinear equations with convex constraints, J. Comput. Appl. Math., 172, 2, 375-397 (2004) · Zbl 1064.65037
[10] Kozakevich, D. N.; Martinez, J. M.; Santos, S. A., Solving nonlinear systems of equations with simple constraints, J. Comput. Appl. Math., 16, 215-235 (1997) · Zbl 0896.65041
[11] 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
[12] 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
[13] Marini, L.; Morini, B.; Porcelli, M., Quasi-Newton methods for constrained nonlinear systems: complexity analysis and applications, Comput. Optim. Appl., 71, 147-170 (2018) · Zbl 1405.90143
[14] Martinez, J. M., Quasi-inexact-Newton methods with global convergence for solving constrained nonlinear systems, Nonlinear Anal.-Theor., 30, 1, 1-7 (1997) · Zbl 0898.65024
[15] Morini, B.; Porcelli, M.; Toint, P. L., Approximate norm descent methods for constrained nonlinear systems, Math. Comp., 87, 311, 1327-1351 (2018) · Zbl 1383.65051
[16] Porcelli, M., On the convergence of an inexact Gauss-Newton trust-region method for nonlinear least-squares problems with simple bounds, Optim. Letters, 7, 3, 447-465 (2013) · Zbl 1268.90091
[17] 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
[18] 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
[19] 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
[20] Levenberg, K., A method for the solution of certain nonlinear problem in least squares, Quart. Appl. Math., 2, 164-166 (1944)
[21] Marquardt, D. W., An algorithm for least-squares estimation of nonlinear inequalities, SIAM J. Appl. Math., 11, 431-441 (1963) · Zbl 0112.10505
[22] Zhang, J.-L., On the convergence properties of the levenberg-marquardt method, Optimization, 52, 6, 739-756 (2003) · Zbl 1059.90132
[23] Fan, J.-y.; Yuan, Y.-x., On the quadratic convergence of the levenberg-marquardt method without nonsingularity assumption, Computing, 74, 1, 23-39 (2005) · Zbl 1076.65047
[24] Yamashita, N.; Fukushima, M., On the rate of convergence of the levenberg-marquardt method, (Topics in Numerical Analysis (2001), Springer Vienna), 239-249 · Zbl 1001.65047
[25] M. Jaggi, Revisiting Frank-Wolfe: Projection-free sparse convex optimization, in: Proceedings of the 30th International Conference on Machine Learning (ICML-13), Vol. 28, 2013, pp. 427-435.
[26] Grippo, L.; Lampariello, F.; Lucidi, S., A nonmonotone line search technique for Newton’s method, SIAM J. Numer. Anal., 23, 4, 707-716 (1986) · Zbl 0616.65067
[27] Frank, M.; Wolfe, P., An algorithm for quadratic programming, Naval Res. Logist., 3, 1-2, 95-110 (1956)
[28] Gould, N. I.M.; Orban, D.; Toint, P. L., CUTEr, a constrained and unconstrained testing environment, revisited, ACM Trans. Math. Software, 29, 373-394 (2003) · Zbl 1068.90526
[29] Hock, W.; Schittkowski, K., Test examples for nonlinear programming codes, J. Optim. Theory Appl., 30, 1, 127-129 (1980) · Zbl 0393.90072
[30] Morini, B.; Porcelli, M., TRESNEI, a matlab trust-region solver for systems of nonlinear equalities and inequalities, Comput. Optim. Appl., 51, 27-49 (2012) · Zbl 1244.90224
[31] Gonçalves, D. S.; Gomes-Ruggiero, M. A.; Lavor, C., A projected gradient method for optimization over density matrices, Optim. Methods Softw., 31, 328-341 (2016) · Zbl 1342.65143
[32] Allen-Zhu, Z.; Hazan, E.; Hu, W.; Li, Y., Linear convergence of a frank-wolfe type algorithm over trace-norm balls, (Guyon, I.; Luxburg, U. V.; Bengio, S.; Wallach, H.; Fergus, R.; Vishwanathan, S.; Garnett, R., Adv. Neural Inf. Process. Syst., Vol. 30 (2017), Curran Associates, Inc.), 6191-6200
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.