Mixed-integer convex quadratic programs with indicator variables (MIQP) encompass a wide range of applications, from statistical learning to energy, finance, and logistics. The outer approximation (OA) algorithm has been proven efficient in solving MIQP, and the key to the success of an OA algorithm is the strength of the cutting planes employed. In this paper, we propose a new technique for deriving cutting planes for MIQP from various convex relaxations, and, as a result, we develop new OA algorithms for solving MIQP at scale. The contributions of our work are two-fold: (1) we bridge the work on the convexification of MIQP and the algorithm design to solve large-scale problems, and (2) we demonstrate through a computational study on the sparse portfolio selection problem that our algorithms give rise to significant speedups compared with the state-of-the-art methods in the literature.

Applications in statistics and data sciences require modeling an inherit sparsity as well as structural relationships among variables and often lead to NP-Hard nonconvex problems. Sparsity and structural relations in such problems are usually modeled by introducing indicator (binary) variables associated with the original continuous variables and enforcing complementarity relations between them. We consider optimization problems with convex objective functions of the continuous variables and arbitrary constraints on their associated indicators, and study the resulting conic mixed-binary sets with complementarity restrictions. For such sets, by studying the recessive directions and also utilizing perspective functions, we provide a practical framework to derive compact, ideal, and conic-representable extended formulations. The size of our extended formulation depends on the "rank" of the function and the presence of sign restrictions. Moreover, our techniques highlight that the complexity of the convex hull characterizations of these conic mixed-binary sets with complementarity restrictions hinges solely on the complexity of the convex hull characterization of a set defined by only the indicator variables. This then enables us to take advantage of the extensive research on convex hull descriptions of binary sets and related sophisticated optimization software. In addition, our results unify and generalize previous results established for special cases, e.g., perspective reformulation for separable functions, non-separable rank-one functions, or low-rank quadratic functions optimized over domains with combinatorial constraints on indicator variables and possibly sign constraints on continuous variables. On the computational side, we illustrate the effectiveness of our approach on sparse structured logistic regression problems.

Decision diagrams have emerged as a new technique to solve mixed-integer problems, based on using dynamic programming. Moreover, decision diagrams can also be used to convexify the feasible regions of the problems under consideration, and thus the decision diagram techniques can be combined with standard branch-and-bound methods. However, most of results concerning decision diagrams pertain to pure integer sets, as the convexifications obtained, based on the path polytope, are inherently polyhedral. In this talk we discuss how to use decision diagrams to solve and convexify mixed-integer quadratic optimization problems, a class of problems with non-polyhedral ideal formulations.

We consider sensitivity analysis for Mixed Binary Quadratic Programs (MBQPs) with respect to changing right-hand-sides (rhs). We show that even if the optimal solution of a given MBQP is known, it is NP-hard to approximate the change in objective function value with respect to changes in rhs. Next, we study algorithmic approaches to obtaining dual bounds for MBQP with changing rhs. We leverage Burer’s completely-positive (CPP) reformulation of MBQPs. Its dual is an instance of co-positive programming (COP), and can be used to obtain sensitivity bounds. We prove that strong duality between the CPP and COP problems holds if the feasible region is bounded or if the objective function is convex, while the duality gap can be strictly positive if neither condition is met. We also show that the COP dual has multiple optimal solutions, and the choice of the dual solution affects the quality of the bounds with rhs changes. We finally provide a method for finding good nearly optimal dual solutions, and we present preliminary computational results on sensitivity analysis for MBQPs.