A class of diagonal quasi-Newton penalty decomposition algorithms for sparse bound-constrained nonconvex optimization

This paper discusses an improved quasi-Newton penalty decomposition algorithm for the cardinality bound-constrained optimization problems whose simple bounds on the variables are assumed to be finite. Until an approximate stationary point is found, this algorithm approximates the solutions of a sequence of penalty subproblems by a two-block decomposition scheme. This scheme finds an approximate solution of the first penalty subproblem in a closed form without simple bounds on variables and explicitly an approximate solution of the second penalty subproblem in the presence of both bound and cardinality constraints. Under a new assumption on the gradient of the objective function, which is weaker than the Lipschitz continuity from the origin, convergence to a stationary point is investigated for the new algorithm. To be efficient and robust in finite precision arithmetic, an improved version of our algorithm uses several practical enhancements, such as an improved line search using either a backtracking or an extrapolation framework (with one objective function evaluation only at the accepted point) and four cheap diagonal approximations of the Hessian matrix (based on the differences of previous points and gradients or the distribution of the eigenvalues). Extensive numerical experiments on a set of 846 cardinality bound-constrained test problems are provided with dimensions ranging from 2 to 9000, showing that the new algorithm is competitive with several state-of-the-art algorithms not only in finding high-accuracy approximate global minimum points but also in finding high-accuracy approximate basic feasible points.

Article

Download

View PDF