Search for: All records

Abstract We consider the convex quadratic optimization problem in$$\mathbb {R}^{n}$$ $R^n$with indicator variables and arbitrary constraints on the indicators. We show that a convex hull description of the associated mixed-integer set in an extended space with a quadratic number of additional variables consists of an$$(n+1) \times (n+1)$$ $(n+1)\times (n+1)$positive semidefinite constraint (explicitly stated) and linear constraints. In particular, convexification of this class of problems reduces to describing a polyhedral set in an extended formulation. While the vertex representation of this polyhedral set is exponential and an explicit linear inequality description may not be readily available in general, we derive a compact mixed-integer linear formulation whose solutions coincide with the vertices of the polyhedral set. We also give descriptions in the original space of variables: we provide a description based on an infinite number of conic-quadratic inequalities, which are “finitely generated.” In particular, it is possible to characterize whether a given inequality is necessary to describe the convex hull. The new theory presented here unifies several previously established results, and paves the way toward utilizing polyhedral methods to analyze the convex hull of mixed-integer nonlinear sets. 

Abstract This paper studies several solution paths of sparse quadratic minimization problems as a function of the weighing parameter of the bi-objective of estimation loss versus solution sparsity. Three such paths are considered: the “$$\ell _0$$ ${\ell }_0$-path” where the discontinuous$$\ell _0$$ ${\ell }_0$-function provides the exact sparsity count; the “$$\ell _1$$ ${\ell }_1$-path” where the$$\ell _1$$ ${\ell }_1$-function provides a convex surrogate of sparsity count; and the “capped$$\ell _1$$ ${\ell }_1$-path” where the nonconvex nondifferentiable capped$$\ell _1$$ ${\ell }_1$-function aims to enhance the$$\ell _1$$ ${\ell }_1$-approximation. Serving different purposes, each of these three formulations is different from each other, both analytically and computationally. Our results deepen the understanding of (old and new) properties of the associated paths, highlight the pros, cons, and tradeoffs of these sparse optimization models, and provide numerical evidence to support the practical superiority of the capped$$\ell _1$$ ${\ell }_1$-path. Our study of the capped$$\ell _1$$ ${\ell }_1$-path is interesting in its own right as the path pertains to computable directionally stationary (= strongly locally minimizing in this context, as opposed to globally optimal) solutions of a parametric nonconvex nondifferentiable optimization problem. Motivated by classical parametric quadratic programming theory and reinforced by modern statistical learning studies, both casting an exponential perspective in fully describing such solution paths, we also aim to address the question of whether some of them can be fully traced in strongly polynomial time in the problem dimensions. A major conclusion of this paper is that a path of directional stationary solutions of the capped$$\ell _1$$ ${\ell }_1$-regularized problem offers interesting theoretical properties and practical compromise between the$$\ell _0$$ ${\ell }_0$-path and the$$\ell _1$$ ${\ell }_1$-path. Indeed, while the$$\ell _0$$ ${\ell }_0$-path is computationally prohibitive and greatly handicapped by the repeated solution of mixed-integer nonlinear programs, the quality of$$\ell _1$$ ${\ell }_1$-path, in terms of the two criteria—loss and sparsity—in the estimation objective, is inferior to the capped$$\ell _1$$ ${\ell }_1$-path; the latter can be obtained efficiently by a combination of a parametric pivoting-like scheme supplemented by an algorithm that takes advantage of the Z-matrix structure of the loss function.