April 2018, 14(2): 707-718. doi: 10.3934/jimo.2017070

An adaptive trust region algorithm for large-residual nonsmooth least squares problems

College of Mathematics and Information Science, Guangxi University, Nanning, Guangxi 530004, China

* Corresponding author

Received  July 2015 Revised  June 2016 Published  September 2017

In this paper, an adaptive trust region algorithm in which the trust region radius converges to zero is presented for solving large-residual nonsmooth least squares problems. This algorithm uses the smoothing technique of the approximation function, and it combines an adaptive trust region radius. Moreover, this algorithm differs from the existing methods for solving nonsmooth equations through use of the approximation function of second-order information, which improves the convergence rate for large-residual nonsmooth least squares problems. Under some suitable conditions, the global and local superlinear convergences of the proposed method are proven. The preliminary numerical results indicate that the proposed algorithm is effective and suitable for solving large-residual nonsmooth least squares problems.

Citation: Zhou Sheng, Gonglin Yuan, Zengru Cui, Xiabin Duan, Xiaoliang Wang. An adaptive trust region algorithm for large-residual nonsmooth least squares problems. Journal of Industrial & Management Optimization, 2018, 14 (2) : 707-718. doi: 10.3934/jimo.2017070
References:
[1]

M. Al-Baali and R. Fletcher, Variational methods for non-linear least-squares, J. Oper. Res. Soc., 36 (1985), 405-421.

[2]

X. Chen, On the convergence of Broyden-like methods for nonlinear equations with nondiffentiable terms, Ann. Institut. Statist. Math., 42 (1990), 387-401. doi: 10.1007/BF00050844.

[3]

X. Chen and L. Qi, A parameterized Newton method and a quasi-Newton method for nonsmooth equations, Comput. Optim. Appl., 3 (1994), 157-179. doi: 10.1007/BF01300972.

[4]

X. Chen and T. Yamamoto, On the convergence of some quasi-Newton methods for nonlinear equations with nondifferentiable operators, Computing, 49 (1992), 87-94. doi: 10.1007/BF02238652.

[5]

A. R. Conn, N. I. M. Gould and Ph. L. Toint, Trust-Region Methods Society for Industrial and Applied Mathematics SIAM, Philadelphia, PA, 2000. doi: 10.1137/1.9780898719857.

[6]

J. Fan and J. Pan, An improve trust region algorithm for nonlinear equations, Comput. Optim. Appl., 48 (2011), 59-70. doi: 10.1007/s10589-009-9236-7.

[7]

J. Fan and Y. Yuan, A new trust region algorithm with trust region radius converging to zero, in Proceedings of the 5th International Conference on Optimization: Techniques and Applications (December 2001, Hongkong) (ed. D. Li), 2001,786-794. doi: 10.4208/jcm.1601-m2015-0399.

[8]

L. Hei, A self-adaptive trust region algorithm, J. Comput. Math., 21 (2003), 229-236.

[9]

K. Levenberg, A method for the solution of certain nonlinear problem in least squares, Quarterly Journal of Mechanics and Applied Mathematics, 2 (1944), 164-168. doi: 10.1090/qam/10666.

[10]

S. LiuZ. Wang and C. Liu, On convergence analysis of dual proximal-gradient methods with approximate gradient for a class of nonsmooth convex minimization problems, J. Ind. Manag. Optim., 12 (2016), 389-402. doi: 10.3934/jimo.2016.12.389.

[11]

K. Madsen, An algorithm for minimax solution of overdetermined systems of nonlinear equations, Rep. TP 559, AERE Harwell, England, 1973.

[12]

B. Martinet, Régularisation d'inéquations variationelles par approxiamations succcessives, Rev. Fr. Inform. Rech. Oper., 4 (1970), 154-158.

[13]

J. Moré, Recent developments in algorithms and software for trust region methods, in Mathematical Programming: The State of Art (eds. A. Bachem, M. Grötachel and B. Korte), Springer, Berlin, (1983), 258-287.

[14]

M. J. D. Powell, Convergence properties of a class of minimization algorithms, in Nonlinear Programming (Q. L. Mangasarian, R. R. Meyer and S. M. Robinson), Vol. 2, Academic Press, New York, 1974, 1-27.

[15]

L. Qi, Trust region algorithms for solving nonsmooth equations, SIAM J. Optimization, 5 (1995), 219-230. doi: 10.1137/0805011.

[16]

L. QiZ. Wei and G. Yuan, An active-set projected trust region algorithm with limited memory BFGS technique for box constrained nonsmooth equations, Optimization, 62 (2013), 857-878. doi: 10.1080/02331934.2011.603321.

[17]

Z. Sheng, A. Ouyang and L. B. Liu, et al., A novel parameter estimation method for Muskingum model using new Newton-type trust region algorithm Math. Probl. Eng. (2014), Art. ID 634852, 7 pp. doi: 10.1155/2014/634852.

[18]

Z. Shi and J. Guo, A new trust region method for unconstrained optimization, J. Comput. and Appl. Math., 213 (2008), 509-520. doi: 10.1016/j.cam.2007.01.027.

[19]

T. Steihaug, The conjugate gradient method and trust regions in large scale optimization, SIAM J. Numer Anal, 20 (1983), 626-637. doi: 10.1137/0720042.

[20]

W. SunR. J. B. Sampaio and J. Yuan, Quasi-Newton trust region algorithm for non-smooth least squares problems, Appl. Math. Comput., 105 (1999), 183-194. doi: 10.1016/S0096-3003(98)10103-0.

[21]

G. YuanS. Lu and Z. Wei, A new trust-region method with line search for solving symmetric nonlinear equations, Intern. J. Compu. Math., 88 (2011), 2109-2123. doi: 10.1080/00207160.2010.526206.

[22]

G. YuanX. Lu and Z. Wei, BFGS trust-region method for symmetric nonlinear equations, J. Compu. and Appl. Math., 230 (2009), 44-58. doi: 10.1016/j.cam.2008.10.062.

[23]

G. YuanZ. Meng and Y. Li, A modified Hestenes and Stiefel conjugate gradient algorithm for large-scale nonsmooth minimizations and nonlinear equations, J. Optim. Theo. Appl., 168 (2016), 129-152. doi: 10.1007/s10957-015-0781-1.

[24]

G. YuanZ. Wei and G. Li, A modified Polak-Ribi're-Polyak conjugate gradient algorithm for nonsmooth convex programs, J. Compu. and Appl. Math., 255 (2014), 86-96. doi: 10.1016/j.cam.2013.04.032.

[25]

G. YuanZ. Wei and X. Lu, A BFGS trust-region method for nonlinear equations, Computing, 92 (2011), 317-333. doi: 10.1007/s00607-011-0146-z.

[26]

J. Zhang and Y. Wang, A new trust region method for nonlinear equations, Math. Methods Oper. Res., 58 (2003), 283-298. doi: 10.1007/s001860300302.

[27]

S. ZhouY. Li and L. Kong, A smoothing iterative method for quantile regression with nonconvex $l_p $ penalty, J. Ind. Manag. Optim., 12 (2016), 93-112. doi: 10.3934/jimo.2016006.

show all references

References:
[1]

M. Al-Baali and R. Fletcher, Variational methods for non-linear least-squares, J. Oper. Res. Soc., 36 (1985), 405-421.

[2]

X. Chen, On the convergence of Broyden-like methods for nonlinear equations with nondiffentiable terms, Ann. Institut. Statist. Math., 42 (1990), 387-401. doi: 10.1007/BF00050844.

[3]

X. Chen and L. Qi, A parameterized Newton method and a quasi-Newton method for nonsmooth equations, Comput. Optim. Appl., 3 (1994), 157-179. doi: 10.1007/BF01300972.

[4]

X. Chen and T. Yamamoto, On the convergence of some quasi-Newton methods for nonlinear equations with nondifferentiable operators, Computing, 49 (1992), 87-94. doi: 10.1007/BF02238652.

[5]

A. R. Conn, N. I. M. Gould and Ph. L. Toint, Trust-Region Methods Society for Industrial and Applied Mathematics SIAM, Philadelphia, PA, 2000. doi: 10.1137/1.9780898719857.

[6]

J. Fan and J. Pan, An improve trust region algorithm for nonlinear equations, Comput. Optim. Appl., 48 (2011), 59-70. doi: 10.1007/s10589-009-9236-7.

[7]

J. Fan and Y. Yuan, A new trust region algorithm with trust region radius converging to zero, in Proceedings of the 5th International Conference on Optimization: Techniques and Applications (December 2001, Hongkong) (ed. D. Li), 2001,786-794. doi: 10.4208/jcm.1601-m2015-0399.

[8]

L. Hei, A self-adaptive trust region algorithm, J. Comput. Math., 21 (2003), 229-236.

[9]

K. Levenberg, A method for the solution of certain nonlinear problem in least squares, Quarterly Journal of Mechanics and Applied Mathematics, 2 (1944), 164-168. doi: 10.1090/qam/10666.

[10]

S. LiuZ. Wang and C. Liu, On convergence analysis of dual proximal-gradient methods with approximate gradient for a class of nonsmooth convex minimization problems, J. Ind. Manag. Optim., 12 (2016), 389-402. doi: 10.3934/jimo.2016.12.389.

[11]

K. Madsen, An algorithm for minimax solution of overdetermined systems of nonlinear equations, Rep. TP 559, AERE Harwell, England, 1973.

[12]

B. Martinet, Régularisation d'inéquations variationelles par approxiamations succcessives, Rev. Fr. Inform. Rech. Oper., 4 (1970), 154-158.

[13]

J. Moré, Recent developments in algorithms and software for trust region methods, in Mathematical Programming: The State of Art (eds. A. Bachem, M. Grötachel and B. Korte), Springer, Berlin, (1983), 258-287.

[14]

M. J. D. Powell, Convergence properties of a class of minimization algorithms, in Nonlinear Programming (Q. L. Mangasarian, R. R. Meyer and S. M. Robinson), Vol. 2, Academic Press, New York, 1974, 1-27.

[15]

L. Qi, Trust region algorithms for solving nonsmooth equations, SIAM J. Optimization, 5 (1995), 219-230. doi: 10.1137/0805011.

[16]

L. QiZ. Wei and G. Yuan, An active-set projected trust region algorithm with limited memory BFGS technique for box constrained nonsmooth equations, Optimization, 62 (2013), 857-878. doi: 10.1080/02331934.2011.603321.

[17]

Z. Sheng, A. Ouyang and L. B. Liu, et al., A novel parameter estimation method for Muskingum model using new Newton-type trust region algorithm Math. Probl. Eng. (2014), Art. ID 634852, 7 pp. doi: 10.1155/2014/634852.

[18]

Z. Shi and J. Guo, A new trust region method for unconstrained optimization, J. Comput. and Appl. Math., 213 (2008), 509-520. doi: 10.1016/j.cam.2007.01.027.

[19]

T. Steihaug, The conjugate gradient method and trust regions in large scale optimization, SIAM J. Numer Anal, 20 (1983), 626-637. doi: 10.1137/0720042.

[20]

W. SunR. J. B. Sampaio and J. Yuan, Quasi-Newton trust region algorithm for non-smooth least squares problems, Appl. Math. Comput., 105 (1999), 183-194. doi: 10.1016/S0096-3003(98)10103-0.

[21]

G. YuanS. Lu and Z. Wei, A new trust-region method with line search for solving symmetric nonlinear equations, Intern. J. Compu. Math., 88 (2011), 2109-2123. doi: 10.1080/00207160.2010.526206.

[22]

G. YuanX. Lu and Z. Wei, BFGS trust-region method for symmetric nonlinear equations, J. Compu. and Appl. Math., 230 (2009), 44-58. doi: 10.1016/j.cam.2008.10.062.

[23]

G. YuanZ. Meng and Y. Li, A modified Hestenes and Stiefel conjugate gradient algorithm for large-scale nonsmooth minimizations and nonlinear equations, J. Optim. Theo. Appl., 168 (2016), 129-152. doi: 10.1007/s10957-015-0781-1.

[24]

G. YuanZ. Wei and G. Li, A modified Polak-Ribi're-Polyak conjugate gradient algorithm for nonsmooth convex programs, J. Compu. and Appl. Math., 255 (2014), 86-96. doi: 10.1016/j.cam.2013.04.032.

[25]

G. YuanZ. Wei and X. Lu, A BFGS trust-region method for nonlinear equations, Computing, 92 (2011), 317-333. doi: 10.1007/s00607-011-0146-z.

[26]

J. Zhang and Y. Wang, A new trust region method for nonlinear equations, Math. Methods Oper. Res., 58 (2003), 283-298. doi: 10.1007/s001860300302.

[27]

S. ZhouY. Li and L. Kong, A smoothing iterative method for quantile regression with nonconvex $l_p $ penalty, J. Ind. Manag. Optim., 12 (2016), 93-112. doi: 10.3934/jimo.2016006.

Figure 1.  The value of $\|F(x_k)\|$ with iteration $k$ for Example 5.1
Figure 2.  The value of $\|F(x_k)\|$ with iteration $k$ for Example 5.2
[1]

Nobuko Sagara, Masao Fukushima. trust region method for nonsmooth convex optimization. Journal of Industrial & Management Optimization, 2005, 1 (2) : 171-180. doi: 10.3934/jimo.2005.1.171

[2]

Yun Cai, Song Li. Convergence and stability of iteratively reweighted least squares for low-rank matrix recovery. Inverse Problems & Imaging, 2017, 11 (4) : 643-661. doi: 10.3934/ipi.2017030

[3]

H. D. Scolnik, N. E. Echebest, M. T. Guardarucci. Extensions of incomplete oblique projections method for solving rank-deficient least-squares problems. Journal of Industrial & Management Optimization, 2009, 5 (2) : 175-191. doi: 10.3934/jimo.2009.5.175

[4]

Stefan Kindermann. Convergence of the gradient method for ill-posed problems. Inverse Problems & Imaging, 2017, 11 (4) : 703-720. doi: 10.3934/ipi.2017033

[5]

Honglan Zhu, Qin Ni, Meilan Zeng. A quasi-Newton trust region method based on a new fractional model. Numerical Algebra, Control & Optimization, 2015, 5 (3) : 237-249. doi: 10.3934/naco.2015.5.237

[6]

Jun Chen, Wenyu Sun, Zhenghao Yang. A non-monotone retrospective trust-region method for unconstrained optimization. Journal of Industrial & Management Optimization, 2013, 9 (4) : 919-944. doi: 10.3934/jimo.2013.9.919

[7]

Lijuan Zhao, Wenyu Sun. Nonmonotone retrospective conic trust region method for unconstrained optimization. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 309-325. doi: 10.3934/naco.2013.3.309

[8]

Dan Xue, Wenyu Sun, Hongjin He. A structured trust region method for nonconvex programming with separable structure. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 283-293. doi: 10.3934/naco.2013.3.283

[9]

Hassan Mohammad, Mohammed Yusuf Waziri, Sandra Augusta Santos. A brief survey of methods for solving nonlinear least-squares problems. Numerical Algebra, Control & Optimization, 2019, 9 (1) : 1-13. doi: 10.3934/naco.2019001

[10]

Sanming Liu, Zhijie Wang, Chongyang Liu. On convergence analysis of dual proximal-gradient methods with approximate gradient for a class of nonsmooth convex minimization problems. Journal of Industrial & Management Optimization, 2016, 12 (1) : 389-402. doi: 10.3934/jimo.2016.12.389

[11]

Zhili Ge, Gang Qian, Deren Han. Global convergence of an inexact operator splitting method for monotone variational inequalities. Journal of Industrial & Management Optimization, 2011, 7 (4) : 1013-1026. doi: 10.3934/jimo.2011.7.1013

[12]

Liyan Qi, Xiantao Xiao, Liwei Zhang. On the global convergence of a parameter-adjusting Levenberg-Marquardt method. Numerical Algebra, Control & Optimization, 2015, 5 (1) : 25-36. doi: 10.3934/naco.2015.5.25

[13]

Yu-Ning Yang, Su Zhang. On linear convergence of projected gradient method for a class of affine rank minimization problems. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1507-1519. doi: 10.3934/jimo.2016.12.1507

[14]

Wei-Zhe Gu, Li-Yong Lu. The linear convergence of a derivative-free descent method for nonlinear complementarity problems. Journal of Industrial & Management Optimization, 2017, 13 (2) : 531-548. doi: 10.3934/jimo.2016030

[15]

Liang Zhang, Wenyu Sun, Raimundo J. B. de Sampaio, Jinyun Yuan. A wedge trust region method with self-correcting geometry for derivative-free optimization. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 169-184. doi: 10.3934/naco.2015.5.169

[16]

Chunlin Hao, Xinwei Liu. A trust-region filter-SQP method for mathematical programs with linear complementarity constraints. Journal of Industrial & Management Optimization, 2011, 7 (4) : 1041-1055. doi: 10.3934/jimo.2011.7.1041

[17]

Hongxiu Zhong, Guoliang Chen, Xueping Guo. Semi-local convergence of the Newton-HSS method under the center Lipschitz condition. Numerical Algebra, Control & Optimization, 2019, 9 (1) : 85-99. doi: 10.3934/naco.2019007

[18]

JaEun Ku. Maximum norm error estimates for Div least-squares method for Darcy flows. Discrete & Continuous Dynamical Systems - A, 2010, 26 (4) : 1305-1318. doi: 10.3934/dcds.2010.26.1305

[19]

Runchang Lin, Huiqing Zhu. A discontinuous Galerkin least-squares finite element method for solving Fisher's equation. Conference Publications, 2013, 2013 (special) : 489-497. doi: 10.3934/proc.2013.2013.489

[20]

Micol Amar, Andrea Braides. A characterization of variational convergence for segmentation problems. Discrete & Continuous Dynamical Systems - A, 1995, 1 (3) : 347-369. doi: 10.3934/dcds.1995.1.347

2017 Impact Factor: 0.994

Article outline

Figures and Tables

[Back to Top]