An Active-Set Algorithmic Framework for Non-Convex Optimization Problems over the Simplex

Abstract

In this paper, we describe a new active-set algorithmic framework for minimizing a non-convex function over the unit simplex. At each iteration, the method makes use of a rule for identifying active variables (i.e., variables that are zero at a stationary point) and specific directions (that we name active-set gradient related directions) satisfying a new "nonorthogonality" type of condition. We prove global convergence to stationary points when using an Armijo line search in the given framework. We further describe three different examples of active-set gradient related directions that guarantee linear convergence rate (under suitable assumptions). Finally, we report numerical experiments showing the effectiveness of the approach.

29 pages, 3 figures

References in corpus (4)

• A Fast Active Set Block Coordinate Descent Algorithm for ${\ell }_1$-regularized least squares
• An Active Set Algorithm for Nonlinear Optimization with Polyhedral Constraints
• A two-phase gradient method for quadratic programming problems with a single linear constraint and bounds on the variables
• A Two-Stage Active-Set Algorithm for Bound-Constrained Optimization