Explicit convex hull description of bivariate quadratic sets with indicator variables

\(\) We consider the nonconvex set \(S_n = \{(x,X,z): X = x x^T, \; x (1-z) =0,\; x \geq 0,\; z \in \{0,1\}^n\}\), which is closely related to the feasible region of several difficult nonconvex optimization problems such as the best subset selection and constrained portfolio optimization. Utilizing ideas from convex analysis and disjunctive programming, … Read more

Recursive McCormick Linearization of Multilinear Programs

Linear programming (LP) relaxations are widely employed in exact solution methods for multilinear programs (MLP). One example is the family of Recursive McCormick Linearization (RML) strategies, where bilinear products are substituted for artificial variables, which deliver a relaxation of the original problem when introduced together with concave and convex envelopes. In this article, we introduce … Read more

Generalization of Doubly Nonnegative Cone: Focusing on Inner-Approximation for Generalized Copositive Cone

We aim to provide better relaxation for generalized completely positive (copositive) programming. We first develop an inner-approximation hierarchy for the generalized copositive cone over a symmetric cone. Exploiting this hierarchy as well as the existing hierarchy proposed by Zuluaga et al. (SIAM J Optim 16(4):1076–1091, 2006), we then propose two (NN and ZVP) generalized doubly … Read more

An SDP Relaxation for the Sparse Integer Least Square Problem

In this paper, we study the sparse integer least square problem (SILS), which is the NP-hard variant of the least square problem, where we only consider sparse {0, ±1}-vectors. We propose an l1-based SDP relaxation to SILS, and provide sufficient conditions for our SDP relaxation to solve SILS. The class of data input which guarantee … Read more

Solving Two-Trust-Region Subproblems using Semidefinite Optimization with Eigenvector Branching

Semidefinite programming (SDP) problems typically utilize the constraint that X-xx’ is PSD to obtain a convex relaxation of the condition X=xx’, where x is an n-vector. In this paper we consider a new hyperplane branching method for SDP based on using an eigenvector of X-xx’. This branching technique is related to previous work of Saxeena, … Read more

Strong duality of a conic optimization problem with a single hyperplane and two cone constraints

Strong (Lagrangian) duality of general conic optimization problems (COPs) has long been studied and its profound and complicated results appear in different forms in a wide range of literatures. As a result, characterizing the known and unknown results can sometimes be difficult. The aim of this article is to provide a unified and geometric view … Read more

On Piecewise Linear Approximations of Bilinear Terms: Structural Comparison of Univariate and Bivariate Mixed-Integer Programming Formulations

Bilinear terms naturally appear in many optimization problems. Their inherent nonconvexity typically makes them challenging to solve. One approach to tackle this difficulty is to use bivariate piecewise linear approximations for each variable product, which can be represented via mixed-integer linear programming (MIP) formulations. Alternatively, one can reformulate the variable products as a sum of … Read more

A Reformulation Technique to Solve Polynomial Optimization Problems with Separable Objective Functions of Bounded Integer Variables

Real-world problems are often nonconvex and involve integer variables, representing vexing challenges to be tackled using state-of-the-art solvers. We introduce a mathematical identity-based reformulation of a class of polynomial integer nonlinear optimization (PINLO) problems using a technique that linearizes polynomial functions of separable and bounded integer variables of any degree. We also introduce an alternative … Read more

Exactness in SDP relaxations of QCQPs: Theory and applications

Quadratically constrained quadratic programs (QCQPs) are a fundamental class of optimization problems. In a QCQP, we are asked to minimize a (possibly nonconvex) quadratic function subject to a number of (possibly nonconvex) quadratic constraints. Such problems arise naturally in many areas of operations research, computer science, and engineering. Although QCQPs are NP-hard to solve in … Read more

On obtaining the convex hull of quadratic inequalities via aggregations

A classical approach for obtaining valid inequalities for a set involves weighted aggregations of the inequalities that describe such set. When the set is described by linear inequalities, thanks to the Farkas lemma, we know that every valid inequality can be obtained using aggregations. When the inequalities describing the set are two quadratics, Yildiran showed … Read more