arrow
Volume 41, Issue 4
A Trust-Region Method for Nonsmooth Nonconvex Optimization

Ziang Chen, Andre Milzarek & Zaiwen Wen

J. Comp. Math., 41 (2023), pp. 683-716.

Published online: 2023-02

Export citation
  • Abstract

We propose a trust-region type method for a class of nonsmooth nonconvex optimization problems where the objective function is a summation of a (probably nonconvex) smooth function and a (probably nonsmooth) convex function. The model function of our trust-region subproblem is always quadratic and the linear term of the model is generated using abstract descent directions. Therefore, the trust-region subproblems can be easily constructed as well as efficiently solved by cheap and standard methods. When the accuracy of the model function at the solution of the subproblem is not sufficient, we add a safeguard on the stepsizes for improving the accuracy. For a class of functions that can be "truncated'', an additional truncation step is defined and a stepsize modification strategy is designed. The overall scheme converges globally and we establish fast local convergence under suitable assumptions. In particular, using a connection with a smooth Riemannian trust-region method, we prove local quadratic convergence for partly smooth functions under a strict complementary condition. Preliminary numerical results on a family of $\ell_1$-optimization problems are reported and demonstrate the efficiency of our approach.

  • AMS Subject Headings

90C30, 65K05, 90C06

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address

ziang@math.duke.edu (Ziang Chen)

andremilzarek@cuhk.edu.cn (Andre Milzarek)

wenzw@pku.edu.cn (Zaiwen Wen)

  • BibTex
  • RIS
  • TXT
@Article{JCM-41-683, author = {Chen , ZiangMilzarek , Andre and Wen , Zaiwen}, title = {A Trust-Region Method for Nonsmooth Nonconvex Optimization}, journal = {Journal of Computational Mathematics}, year = {2023}, volume = {41}, number = {4}, pages = {683--716}, abstract = {

We propose a trust-region type method for a class of nonsmooth nonconvex optimization problems where the objective function is a summation of a (probably nonconvex) smooth function and a (probably nonsmooth) convex function. The model function of our trust-region subproblem is always quadratic and the linear term of the model is generated using abstract descent directions. Therefore, the trust-region subproblems can be easily constructed as well as efficiently solved by cheap and standard methods. When the accuracy of the model function at the solution of the subproblem is not sufficient, we add a safeguard on the stepsizes for improving the accuracy. For a class of functions that can be "truncated'', an additional truncation step is defined and a stepsize modification strategy is designed. The overall scheme converges globally and we establish fast local convergence under suitable assumptions. In particular, using a connection with a smooth Riemannian trust-region method, we prove local quadratic convergence for partly smooth functions under a strict complementary condition. Preliminary numerical results on a family of $\ell_1$-optimization problems are reported and demonstrate the efficiency of our approach.

}, issn = {1991-7139}, doi = {https://doi.org/10.4208/jcm.2110-m2020-0317}, url = {http://global-sci.org/intro/article_detail/jcm/21411.html} }
TY - JOUR T1 - A Trust-Region Method for Nonsmooth Nonconvex Optimization AU - Chen , Ziang AU - Milzarek , Andre AU - Wen , Zaiwen JO - Journal of Computational Mathematics VL - 4 SP - 683 EP - 716 PY - 2023 DA - 2023/02 SN - 41 DO - http://doi.org/10.4208/jcm.2110-m2020-0317 UR - https://global-sci.org/intro/article_detail/jcm/21411.html KW - Trust-region method, Nonsmooth composite programs, Quadratic model function, Global and local convergence. AB -

We propose a trust-region type method for a class of nonsmooth nonconvex optimization problems where the objective function is a summation of a (probably nonconvex) smooth function and a (probably nonsmooth) convex function. The model function of our trust-region subproblem is always quadratic and the linear term of the model is generated using abstract descent directions. Therefore, the trust-region subproblems can be easily constructed as well as efficiently solved by cheap and standard methods. When the accuracy of the model function at the solution of the subproblem is not sufficient, we add a safeguard on the stepsizes for improving the accuracy. For a class of functions that can be "truncated'', an additional truncation step is defined and a stepsize modification strategy is designed. The overall scheme converges globally and we establish fast local convergence under suitable assumptions. In particular, using a connection with a smooth Riemannian trust-region method, we prove local quadratic convergence for partly smooth functions under a strict complementary condition. Preliminary numerical results on a family of $\ell_1$-optimization problems are reported and demonstrate the efficiency of our approach.

Ziang Chen, Andre Milzarek & Zaiwen Wen. (2023). A Trust-Region Method for Nonsmooth Nonconvex Optimization. Journal of Computational Mathematics. 41 (4). 683-716. doi:10.4208/jcm.2110-m2020-0317
Copy to clipboard
The citation has been copied to your clipboard