solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看125次
Globally solving Non-Convex Quadratic Programs via Linear Integer Programming techniques. (arXiv:1511.02423v3 [math.OC] UPDATED)
来源于:arXiv
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 (N 查看全文>>