We consider the problem of solving a large-scale Quadratically Constrained Quadratic Program. Such problems occur naturally in many scientific and web applications. Although there are efficient methods which tackle this problem, they are mostly not scalable. In this paper, we develop a method that transforms the quadratic constraint into a linear form by sampling a set of low-discrepancy points. The transformed problem can then be solved by applying any state-of-the-art large-scale quadratic programming solvers. We show the convergence of our approximate solution to the true solution as well as some finite sample error bounds. Experimental results are also shown to prove scalability as well as improved quality of approximation in practice.
We consider the problem of solving a large-scale Quadratically Constrained Quadratic Program. Such problems occur naturally in many scientific and web applications. Although there are efficient methods which tackle this problem, they are mostly not scalable. In this paper, we develop a method that transforms the quadratic constraint into a linear form by sampling a set of low-discrepancy points. The transformed problem can then be solved by applying any state-of-the-art large-scale quadratic programming solvers. We show the convergence of our approximate solution to the true solution as well as some finite sample error bounds. Experimental results are also shown to prove scalability as well as improved quality of approximation in practice.
Quadratic programming (QP) is a well-studied fundamental NP-hard optimization problem which optimizes a quadratic objective over a set of linear constraints. In this paper, we reformulate QPs as a mixed-integer linear problem (MILP). This is done via the reformulation of QP as a linear complementary problem, and the use of binary variables and big-M constraints, to model the complementary constraints. To obtain such reformulation, we show how to impose bounds on the dual variables without eliminating all the (globally) optimal primal solutions; using some fundamental results on the solution of perturbed linear systems. Reformulating non-convex QPs as MILPs provides an advantageous way to obtain global solutions as it allows the use of current state-of-the-art MILP solvers. To illustrate this, we compare the performance of our solution approach, labeled quadprogIP, with the current benchmark global QP solver quadprogBB, as well as with BARON, one of the leading non-linear programming (NLP) solvers, and CPLEX's non-convex QP solver, on a large variety of QP test instances. In practice, quadprogIP is shown to typically outperform by orders of magnitude quadprogBB, BARON, and CPLEX on standard QPs. For general QPs, quadprogIP outperforms quadprogBB, outperforms BARON in most instances, while CPLEX performs the best on these instances. For box-constrained QPs, quadprogIP has a comparable performance to quadprogBB and BARON in small- to medium-scale instances, but is outperformed by these solvers on large-scale instances; while CPLEX performs the best on box-constrained QP instances. Also, unlike quadprogBB, the solution approach proposed here is able to solve QP instances whose dual feasible set is unbounded. The MATLAB code, called quadprogIP, and the instances used to perform these numerical experiments are publicly available at https://github.com/xiawei918/quadprogIP.
We present an iterative algorithm to compute feasible solutions in reasonable running time to quadratically constrained quadratic programs (QCQPs), which form a challenging class of nonconvex continuous optimization. This algorithm is based on a mixed-integer linear program (MILP) which is a restriction of the original QCQP obtained by discretizing all quadratic terms. In each iteration, this MILP restriction is solved to get a feasible QCQP solution. Since the quality of this solution heavily depends on the chosen discretization of the MILP, we iteratively adapt the discretization values based on the MILP solution of the previous iteration. To maintain a reasonable problem size in each iteration of the algorithm, the discretization sizes are fixed at predefined values. Although our algorithm did not always yield good feasible solutions on arbitrary QCQP instances, an extensive computational study on almost 1300 test instances of two different problem classes - box-constrained quadratic programs with complementarity constraints and disjoint bilinear programs, demonstrates the effectiveness of our approach. We compare the quality of our solutions against those from heuristics and local optimization algorithms in two state-of-the-art commercial solvers and observe that on one instance class we clearly outperform the other methods whereas on the other class we obtain competitive results.
Binary Quadratic Program with Variable Partitioning Constraints The binary quadratic program with variable partitioning constraints is a very general class of optimization problems that is very difficult to solve because of the nonconvexity and integrality of the variables and is ubiquitous, among others, in network design, computer vision, and transportation and logistics. In their article, “A convex reformulation and an outer approximation for a large class of binary quadratic programs,” Rostami et al. show how to transform such a nonconvex challenging problem into a convex bilinear program with decomposable structure. The authors develop a branch-and-cut algorithm based on outer approximation cuts, in which the cuts are generated on the fly by efficiently solving separation subproblems. The results of their computational experiments on different problems confirm the efficacy of the solution methods in solving large-scale problem instances.
We provide a generic toolkit for sparsifying the constraint set of linear programs (LPs). To this end, we reduce solving a linear program with n constraints and d variables (n≫ d), to solving a sequence of LPs defined over only a small subset of the constraints, obtained by adaptively sub-sampling the original set. We provide results for both the low and high precision regimes. To achieve the former result, we streamline and generalize the techniques from [Assadi '25] for approximately computing maximum matchings in the semi-streaming setting to the case of general LPs. For the latter, we robustify the methods of [Clarkson '95], which were originally designed for exact LP solvers. As a consequence we obtain fast approximate LP solvers which reduce the dependence on width and error from quadratic to linear, compared to vanilla multiplicative-weights based approaches. Additionally, we leverage our findings to obtain fast LP solvers in the quantum query access model, where the running time scales with √n. This completely decouples the component responsible for quantum speed-ups, solely represented by a generalization of Grover’s search, from its classical algorithmic counterpart.
The class of mixed-integer quadratically constrained quadratic programs (QCQP) consists of minimizing a quadratic function under quadratic constraints where the variables could be integer or continuous. On a previous paper we introduced a method called MIQCR for solving QCQPs with the following restriction: all quadratic sub-functions of purely continuous variables are already convex. In this paper, we propose an extension of MIQCR which applies to any QCQP. Let (P) be a QCQP. Our approach to solve (P) is first to build an equivalent mixed-integer quadratic problem (P∗). This equivalent problem (P∗) has a quadratic convex objective function, linear constraints, and additional variables y that are meant to satisfy the additional quadratic constraints y=xxT, where x are the initial variables of problem (P). We then propose to solve (P∗) by a branch-and-bound algorithm based on the relaxation of the additional quadratic constraints and of the integrality constraints. This type of branching is known as spatial branch-and-bound. Computational experiences are carried out on a total of 325 instances. The results show that the solution time of most of the considered instances is improved by our method in comparison with the recent implementation of QuadProgBB, and with the solvers Cplex, Couenne, Scip, BARON and GloMIQO.
We reformulate a (indefinite) quadratic program (QP) as a mixed-integer linear programming (MILP) problem by first reformulating a QP as a linear complementary problem, and then using binary variables and big-M constraints to model its complementary constraints. To obtain such reformulation, we use fundamental results on the solution of perturbed linear systems to impose bounds on the QP’s dual variables without eliminating any of its (globally) optimal primal solutions. Reformulating a nonconvex QP as a MILP problem allows the use of current state-of-the-art MILP solvers to find its global optimal solution. To illustrate this, we compare the performance of this MILP-based solution approach, labeled quadprogIP, with quadprogBB, BARON, and CPLEX. In practice, quadprogIP is shown to typically outperform by orders of magnitude quadprogBB, BARON, and CPLEX on standard QPs. Also, unlike quadprogBB, quadprogIP is able to solve QP instances in which the dual feasible set is unbounded. The MATLAB code quadprogIP and the instances used to perform the reported numerical experiments are publicly available at https://github.com/xiawei918/quadprogIP .