A duality-bounds algorithm for non-convex quadratic programs with additional multiplicative constraints (Q2425955)

The paper presents a duality-bounds algorithm that uses a branch-and-bound scheme for solving a globally non-convex quadratic programming problem \((P)\) with several additional linear multiplicative constraints. The algorithm works by solving non-convex programming problem \((P2)\) which is equivalent to the problem \((P)\). The well known weak duality theorem of Lagrange duality is used to obtain the lower bounds of the optimal value of \((P2)\) during the algorithm search. It is shown that, in this case, the Lagrangian dual problem is equivalent to an ordinary linear programming problem. So the subproblems that must be solved for obtaining these lower bounds are all linear programming problems, which can be solved efficiently by the simplex method. Convergence of the algorithm is proved and a solved sample example is given. All the standard convergence properties of a branch-and-bound algorithm for non-convex problems are obtained.