Nonmonotone enhanced proximal DC algorithms for a class of structured nonsmooth DC programming

Zhaosong Lu, Zirui Zhou

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

In this paper we consider a class of structured nonsmooth difference-of-convex (DC) minimization in which the first convex component is the sum of a smooth and a nonsmooth function while the second convex component is the supremum of finitely many convex smooth functions. The existing methods for this problem usually have weak convergence guarantees or exhibit slow convergence. Due to this, we propose two nonmonotone enhanced proximal DC algorithms for solving this problem. For possible acceleration, one uses a nonmonotone line-search scheme in which the associated Lipschitz constant is adaptively approximated by some local curvature information of the smooth function in the first convex component, and the other employs an extrapolation scheme. It is shown that every accumulation point of the solution sequence generated by them is a D-stationary point of the problem. These methods may, however, become inefficient when the number of convex smooth functions in defining the second convex component is large. To remedy this issue, we propose randomized counterparts for them and show that every accumulation point of the generated solution sequence is a D-stationary point of the problem almost surely. Some preliminary numerical experiments are conducted to demonstrate the efficiency of the proposed algorithms.

Original languageEnglish (US)
Pages (from-to)2725-2752
Number of pages28
JournalSIAM Journal on Optimization
Volume29
Issue number4
DOIs
StatePublished - 2019

Bibliographical note

Funding Information:
∗Received by the editors September 27, 2018; accepted for publication (in revised form) June 13, 2019; published electronically October 31, 2019. https://doi.org/10.1137/18M1214342 Funding: The work of the authors was supported by an NSERC Discovery grant. The work of the second author was also supported by an SFU Alan Mekler postdoctoral fellowship. †Department of Industrial and Systems Engineering, University of Minnesota, 111 Church St. S.E. Minneapolis, MN 55455 and Department of Mathematics, Simon Fraser University, Burnaby, British Columbia, V5A 1S6 Canada (zhaosong@umn.edu). ‡Department of Mathematics, Hong Kong Baptist University, Kowloon Tong, Kowloon, Hong Kong (zirui-zhou@hkbu.edu.hk). 1The proximal operator associated with fn is defined as proxfn(x) = argminy{21‖y−x‖2+fn(y)}.

Funding Information:
The work of the authors was supported by an NSERC Discovery grant. The work of the second author was also supported by an SFU Alan Mekler postdoctoral fellowship.

Publisher Copyright:
© 2019 Society for Industrial and Applied Mathematics

Keywords

  • D-stationary point
  • Extrapolation
  • Nonmonotone line search
  • Nonsmooth DC programming
  • Proximal DCA

Fingerprint

Dive into the research topics of 'Nonmonotone enhanced proximal DC algorithms for a class of structured nonsmooth DC programming'. Together they form a unique fingerprint.

Cite this