Ideal formulations for constrained convex optimization problems with
  indicator variables
  Motivated by modern regression applications, in this paper, we study the
convexification of a class of convex optimization problems with indicator
variables and combinatorial constraints on the indicators. Unlike most of the
previous work on convexification of sparse regression problems, we
simultaneously consider the nonlinear non-separable objective, indicator
variables, and combinatorial constraints. Specifically, we give the convex hull
description of the epigraph of the composition of a one-dimensional convex
function and an affine function under arbitrary combinatorial constraints. As
special cases of this result, we derive ideal convexifications for problems
with hierarchy, multi-collinearity, and sparsity constraints. Moreover, we also
give a short proof that for a separable objective function, the perspective
reformulation is ideal independent from the constraints of the problem. Our
computational experiments with regression problems under hierarchy constraints
on real datasets demonstrate the potential of the proposed approach in
improving the relaxation quality without significant computational overhead.
