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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[8]

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

[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. Google Scholar

[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. Google Scholar

[11]

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

[12]

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

[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. Google Scholar

[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. Google Scholar

[15]

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

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[8]

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

[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. Google Scholar

[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. Google Scholar

[11]

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

[12]

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

[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. Google Scholar

[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. Google Scholar

[15]

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

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

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

2018 Impact Factor: 1.025

Metrics

  • PDF downloads (52)
  • HTML views (535)
  • Cited by (0)

[Back to Top]