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]

Jing Zhou, Cheng Lu, Ye Tian, Xiaoying Tang. A socp relaxation based branch-and-bound method for generalized trust-region subproblem. Journal of Industrial & Management Optimization, 2021, 17 (1) : 151-168. doi: 10.3934/jimo.2019104

[2]

Zuliang Lu, Fei Huang, Xiankui Wu, Lin Li, Shang Liu. Convergence and quasi-optimality of $ L^2- $norms based an adaptive finite element method for nonlinear optimal control problems. Electronic Research Archive, 2020, 28 (4) : 1459-1486. doi: 10.3934/era.2020077

[3]

Gang Luo, Qingzhi Yang. The point-wise convergence of shifted symmetric higher order power method. Journal of Industrial & Management Optimization, 2021, 17 (1) : 357-368. doi: 10.3934/jimo.2019115

[4]

George W. Patrick. The geometry of convergence in numerical analysis. Journal of Computational Dynamics, 2021, 8 (1) : 33-58. doi: 10.3934/jcd.2021003

[5]

Thierry Horsin, Mohamed Ali Jendoubi. On the convergence to equilibria of a sequence defined by an implicit scheme. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020465

[6]

Parikshit Upadhyaya, Elias Jarlebring, Emanuel H. Rubensson. A density matrix approach to the convergence of the self-consistent field iteration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 99-115. doi: 10.3934/naco.2020018

[7]

Leilei Wei, Yinnian He. A fully discrete local discontinuous Galerkin method with the generalized numerical flux to solve the tempered fractional reaction-diffusion equation. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020319

[8]

Yi-Long Luo, Yangjun Ma. Low Mach number limit for the compressible inertial Qian-Sheng model of liquid crystals: Convergence for classical solutions. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 921-966. doi: 10.3934/dcds.2020304

[9]

Thomas Frenzel, Matthias Liero. Effective diffusion in thin structures via generalized gradient systems and EDP-convergence. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 395-425. doi: 10.3934/dcdss.2020345

[10]

Wei Ouyang, Li Li. Hölder strong metric subregularity and its applications to convergence analysis of inexact Newton methods. Journal of Industrial & Management Optimization, 2021, 17 (1) : 169-184. doi: 10.3934/jimo.2019105

[11]

Qiao Liu. Local rigidity of certain solvable group actions on tori. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 553-567. doi: 10.3934/dcds.2020269

[12]

Sihem Guerarra. Maximum and minimum ranks and inertias of the Hermitian parts of the least rank solution of the matrix equation AXB = C. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 75-86. doi: 10.3934/naco.2020016

[13]

Thierry Cazenave, Ivan Naumkin. Local smooth solutions of the nonlinear Klein-gordon equation. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020448

[14]

Haiyu Liu, Rongmin Zhu, Yuxian Geng. Gorenstein global dimensions relative to balanced pairs. Electronic Research Archive, 2020, 28 (4) : 1563-1571. doi: 10.3934/era.2020082

[15]

Jianhua Huang, Yanbin Tang, Ming Wang. Singular support of the global attractor for a damped BBM equation. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020345

[16]

Bernold Fiedler. Global Hopf bifurcation in networks with fast feedback cycles. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 177-203. doi: 10.3934/dcdss.2020344

[17]

Mehdi Bastani, Davod Khojasteh Salkuyeh. On the GSOR iteration method for image restoration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 27-43. doi: 10.3934/naco.2020013

[18]

Xavier Carvajal, Liliana Esquivel, Raphael Santos. On local well-posedness and ill-posedness results for a coupled system of mkdv type equations. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020382

[19]

Gunther Uhlmann, Jian Zhai. Inverse problems for nonlinear hyperbolic equations. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 455-469. doi: 10.3934/dcds.2020380

[20]

Monia Capanna, Jean C. Nakasato, Marcone C. Pereira, Julio D. Rossi. Homogenization for nonlocal problems with smooth kernels. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020385

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (144)
  • HTML views (725)
  • Cited by (0)

[Back to Top]