A primal-dual active set method for quadratic problems with bound constraints is presented which extends the infeasible active set approach of [K. Kunisch and F. Rendl. An infeasible active set method for convex problems with simple bounds. SIAM Journal on Optimization, 14(1):35-52, 2003]. Based on a guess of the active set, a primal-dual pair (x,α) … Read more
A new method for solving sequences of quadratic programs (QPs) is presented. For each new QP in the sequence, the method utilizes hot-starts that employ information computed by an active-set QP solver during the solution of the first QP. This avoids the computation and factorization of the full matrices for all but the first problem … Read more
We propose an efficient computational method for linearly constrained quadratic optimization problems (QOPs) with complementarity constraints based on their Lagrangian and doubly nonnegative (DNN) relaxation and first-order algorithms. The simplified Lagrangian-CPP relaxation of such QOPs proposed by Arima, Kim, and Kojima in 2012 takes one of the simplest forms, an unconstrained conic linear optimization problem … Read more
The trust-region problem, which minimizes a nonconvex quadratic function over a ball, is a key subproblem in trust-region methods for solving nonlinear optimization problems. It enjoys many attractive properties such as an exact semi-definite linear programming relaxation (SDP-relaxation) and strong duality. Unfortunately, such properties do not, in general, hold for an extended trust-region problem having … Read more
The problem of minimizing a quadratic form over the unit simplex, referred to as a standard quadratic optimization problem, admits an exact reformulation as a linear optimization problem over the convex cone of completely positive matrices. This computationally intractable cone can be approximated from the inside and from the outside by two sequences of nested … Read more
We investigate the computational potential of split inequalities for non-convex quadratic integer programming, first introduced by Letchford and further examined by Burer and Letchford. These inequalities can be separated by solving convex quadratic integer minimization problems. For small instances with box-constraints, we show that the resulting dual bounds are very tight; they can close a … Read more
The trust region subproblem concerns the minimization of a general quadratic over the unit ball in R^n. Extensions to this problem are of interest because of applications to, for example, combinatorial optimization. However the extension obtained by adding an arbitrary family of linear side constraints is NP-hard. In this paper we consider variants of the … Read more
In this work we propose and test a new linearisation technique for Binary Quadratic Problems (BQP). We computationally prove that the new formulation, called Extended Linear Formulation, performs much better than the standard one in practice, despite not being stronger in terms of Linear Programming relaxation (LP). We empirically prove that this behaviour is due … Read more
The alternating direction method of multipliers (ADMM) has emerged as a powerful technique for large-scale structured optimization. Despite many recent results on the convergence properties of ADMM, a quantitative characterization of the impact of the algorithm parameters on the convergence times of the method is still lacking. In this paper we find the optimal algorithm … Read more
We introduce a new relaxation framework for nonconvex quadratically constrained quadratic programs (QCQPs). In contrast to existing relaxations based on semidefinite programming (SDP), our relaxations incorporate features of both SDP and second order cone programming (SOCP) and, as a result, solve more quickly than SDP. A downside is that the calculated bounds are weaker than … Read more