Projection onto a Capped Rotated Second-Order Cone with Applications to Sparse Regression Relaxations

 This paper establishes a closed-form expression for projecting onto a capped rotated second-order cone. This special object is a convex set that arises as a part of the feasible region of the perspective relaxation of mixed-integer nonlinear programs (MINLP) with binary indicator variables. The rapid computation of the projection onto this convex set enables the development of effective methods for solving the continuous relaxation of MINLPs whose feasible region may involve a Cartesian product of a large number of such sets. As a proof of concept for the applicability of our projection method, we develop
a projected gradient method and specialize a general form of FISTA to use our projection technique in order to effectively solve the continuous perspective relaxation of a sparse regression problem with L0 and L2 penalties. We also generalize the basic sparse regression formulation and solution method to support group sparsity. In experiments we first demonstrate that the projection problem is solved faster and more accurately with our closed-form than with an interior-point solver, and also when solving sparse regression problems our methods that applies our projection formula can outperform a state-of-the-art interior point solver while nearly matching its solution accuracy.