Minimization Over the Nonconvex Sparsity Constraint Using A Hybrid First-order method

Numerical mathematical programming methods (65K05) Analysis of algorithms and problem complexity (68Q25) Nonconvex programming, global optimization (90C26) Nonsmooth analysis (49J52)

Abstract: In this paper, we consider the nonconvex optimization problem in which the objective is continuously differentiable and the feasible set is a nonconvex

e l l_{p}

ball. Studying such optimization offers the possibility to bridge the gap between a range of intermediate values

p i n (0, 1)

and

p i n 0, 1

in the norm-constraint sparse optimization, both in theory and practice. We propose a novel hybrid method within a first-order algorithmic framework for solving such problems by combining the Frank-Wolfe method and the gradient projection method. During iterations, it solves a Frank-Wolfe subproblem if the current iterate is in the interior of the

e l l_{p}

ball, and it solves a gradient projection subproblem with a weighted

e l l_{1}

-ball constraint if the current iterate is on the boundary of the

e l l_{p}

ball. Global convergence is proved, and a worst-case iteration complexity

O (1 / e p s i l o n^{2})

of the optimality error is also established. We believe our proposed method is the first practical algorithm for solving

e l l_{p}

-ball constrained nonlinear problems with theoretical guarantees. Numerical experiments demonstrate the practicability and efficiency of the proposed algorithm.

This page was built for publication: Minimization Over the Nonconvex Sparsity Constraint Using A Hybrid First-order method

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6504445)