Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2211.08911 · Mathematical Programming Computation

Fix and bound: an efficient approach for solving large-scale quadratic programming problems with box constraints

Marco Locatelli, Veronica Piccialli, Antonio M. Sudoso

Published Nov 5, 2024• 1 citation
arXivHTMLPDF
DOI
10.1007/s12532-024-00270-y

Related papers

Globally solving nonconvex quadratic programming problems with box constraints via integer programming methods

Pierre Bonami, Oktay Günlük, Jeff Linderoth

Mathematical Programming Computation•Feb 24, 2018•38 citations

A Polyhedral Approach for Nonconvex Quadratic Programming Problems with Box Constraints

Yasutoshi Yajima, Tetsuya Fujie

Journal of Global Optimization•Sep 1, 1998•47 citations

Approximating quadratic programming with bound and quadratic constraints

Yinyu Ye Y

Mathematical Programming•Feb 1, 1999•167 citations

Large-Scale Quadratically Constrained Quadratic Program via Low-Discrepancy Sequences

Kinjal Basu, Ankan Saha, Shaunak Chatterjee

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.

arXiv:1710.01163•neural information processing systems•Oct 2, 2017•5 citations

Globally solving Non-Convex Quadratic Programs via Linear Integer Programming techniques

Wei Xia, Juan C. Vera, Luis F. Zuluaga

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.

arXiv:1511.02423•Nov 8, 2015•9 citations

Approximation Algorithms for Quadratic Programming

Minyue Fu, Zhi-Quan Tom Luo, Yinyu Ye Y

Journal of Combinatorial Optimization•Mar 1, 1998•79 citations
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.