Abstract We consider the problem of minimizing a (possibly nonconvex) quadratic function over a (possibly unbounded) polyhedron, referred to as a quadratic program. By incorporating the first-order optimality conditions, a quadratic program can be formulated as an optimization problem with complementarity constraints. We investigate the effect of incorporating optimality conditions on the strength of linear and semidefinite programming (SDP) relaxations based on the reformulation-linearization technique (RLT relaxation), and the Shor relaxation combined with the RLT relaxation (SDP-RLT relaxation). We establish that the RLT and SDP-RLT bounds arising from the complementarity formulation do not strengthen finite RLT and SDP-RLT bounds arising from the original formulation. On the other hand, the complementarity formulation may yield strictly tighter lower bounds for quadratic programs with a finite optimal value, but unbounded RLT and SDP-RLT relaxations. We present several classes of instances of quadratic programs to illustrate the behavior of the relaxations arising from the complementarity formulation. In particular, our examples reveal that the complementarity formulation should be used with some caution as it may even fail to yield a valid lower bound for unbounded quadratic programs.

Abstract Quadratic programs with box constraints involve minimizing a possibly nonconvex quadratic function subject to lower and upper bounds on each variable. This is a well-known NP-hard problem that frequently arises in various applications. We focus on two convex relaxations, namely the reformulation–linearization technique (RLT) relaxation and the SDP-RLT relaxation obtained by combining the Shor relaxation with the RLT relaxation. Both relaxations yield lower bounds on the optimal value of a quadratic program with box constraints. We show that each component of each vertex of the RLT relaxation lies in the set $$\{0,\frac{1}{2},1\}$$ { 0 , 1 2 , 1 } . We present complete algebraic descriptions of the set of instances that admit exact RLT relaxations as well as those that admit exact SDP-RLT relaxations. We show that our descriptions can be converted into algorithms for efficiently constructing instances with (1) exact RLT relaxations, (2) inexact RLT relaxations, (3) exact SDP-RLT relaxations, and (4) exact SDP-RLT but inexact RLT relaxations. Our preliminary computational experiments illustrate that our algorithms are capable of generating computationally challenging instances for state-of-the-art solvers.

Abstract We study convex relaxations of nonconvex quadratic programs. We identify a family of so-called feasibility preserving convex relaxations, which includes the well-known copositive and doubly nonnegative relaxations, with the property that the convex relaxation is feasible if and only if the nonconvex quadratic program is feasible. We observe that each convex relaxation in this family implicitly induces a convex underestimator of the objective function on the feasible region of the quadratic program. This alternative perspective on convex relaxations enables us to establish several useful properties of the corresponding convex underestimators. In particular, if the recession cone of the feasible region of the quadratic program does not contain any directions of negative curvature, we show that the convex underestimator arising from the copositive relaxation is precisely the convex envelope of the objective function of the quadratic program, strengthening Burer’s well-known result on the exactness of the copositive relaxation in the case of nonconvex quadratic programs. We also present an algorithmic recipe for constructing instances of quadratic programs with a finite optimal value but an unbounded relaxation for a rather large family of convex relaxations including the doubly nonnegative relaxation.

Abstract A standard quadratic program is an optimization problem that consists of minimizing a (nonconvex) quadratic form over the unit simplex. We focus on reformulating a standard quadratic program as a mixed integer linear programming problem. We propose two alternative formulations. Our first formulation is based on casting a standard quadratic program as a linear program with complementarity constraints. We then employ binary variables to linearize the complementarity constraints. For the second formulation, we first derive an overestimating function of the objective function and establish its tightness at any global minimizer. We then linearize the overestimating function using binary variables and obtain our second formulation. For both formulations, we propose a set of valid inequalities. Our extensive computational results illustrate that the proposed mixed integer linear programming reformulations significantly outperform other global solution approaches. On larger instances, we usually observe improvements of several orders of magnitude.

We present a simple first-order approximation algorithm for the support vector classification problem. Given a pair of linearly separable data sets and ϵ ∈ (0,1), the proposed algorithm computes a separating hyperplane whose margin is within a factor of (1−ϵ) of that of the maximum-margin separating hyperplane. We discuss how our algorithm can be extended to nonlinearly separable and inseparable data sets. The running time of our algorithm is linear in the number of data points and in 1/ϵ. In particular, the number of support vectors computed by the algorithm is bounded above by O(ζ/ϵ) for all sufficiently small ϵ > 0, where ζ is the square of the ratio of the distances between the farthest and closest pairs of points in the two data sets. Furthermore, we establish that our algorithm exhibits linear convergence. Our computational experiments, presented in the online supplement, reveal that the proposed algorithm performs quite well on standard data sets in comparison with other first-order algorithms. We adopt the real number model of computation in our analysis.

Given a set 𝒜 of m points in n-dimensional space with corresponding positive weights, the weighted Euclidean one-center problem, which is a generalization of the minimum enclosing ball problem, involves the computation of a point c 𝒜 ∈ ℝ n that minimizes the maximum weighted Euclidean distance from c 𝒜 to each point in 𝒜. In this paper, given ϵ > 0, we propose and analyze an algorithm that computes a (1 + ϵ)-approximate solution to the weighted Euclidean one-center problem. Our algorithm explicitly constructs a small subset 𝒳 ⫅ 𝒜, called an ϵ-core set of 𝒜, for which the optimal solution of the corresponding weighted Euclidean one-center problem is a close approximation to that of 𝒜. In addition, we establish that ∣ 𝒳∣ depends only on ϵ and on the ratio of the smallest and largest weights, but is independent of the number of points m and the dimension n. This result subsumes and generalizes the previously known core set results for the minimum enclosing ball problem. Our algorithm computes a (1 + ϵ)-approximate solution to the weighted Euclidean one-center problem for 𝒜 in 𝒪(mn∣𝒳∣) arithmetic operations. Our computational results indicate that the size of the ϵ-core set computed by the algorithm is, in general, significantly smaller than the theoretical worst-case estimate, which contributes to the efficiency of the algorithm, especially for large-scale instances. We shed some light on the possible reasons for this discrepancy between the theoretical estimate and the practical performance.