Optimization Online


Optimization over Sparse Symmetric Sets via a Nonmonotone Projected Gradient Method

Zhaosong Lu (zhaosong***at***sfu.ca)

Abstract: We consider the problem of minimizing a Lipschitz differentiable function over a class of sparse symmetric sets that has wide applications in engineering and science. For this problem, it is known that any accumulation point of the classical projected gradient (PG) method with a constant stepsize $1/L$ satisfies the $L$-stationarity optimality condition that was introduced in [3]. In this paper we introduce a new optimality condition that is stronger than the $L$-stationarity optimality condition. We also propose a nonmonotone projected gradient (NPG) method for this problem by incorporating some support-changing and coordintate-swapping strategies into a projected gradient method with variable stepsizes. It is shown that any accumulation point of NPG satisfies the new optimality condition and moreover it is a coordinatewise stationary point. Under some suitable assumptions, we further show that it is a {\it global} or a {\it local} minimizer of the problem. Numerical experiments are conducted to compare the performance of PG and NPG. The computational results demonstrate that NPG has substantially better solution quality than PG, and moreover, it is at least comparable to, but sometimes can be much faster than PG in terms of speed.

Keywords: cardinality constraint, sparse optimization, sparse projection, nonmonotone projected gradient method

Category 1: Nonlinear Optimization

Category 2: Global Optimization

Category 3: Combinatorial Optimization

Citation: Manuscript, Department of Mathematics, Simon Fraser University, Canada.

Download: [PDF]

Entry Submitted: 09/28/2015
Entry Accepted: 09/29/2015
Entry Last Modified: 11/29/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society