Convex relaxation methods are presented for solving two distinct (and apparently unconnected) computationally intractable (NP-hard) problems.

The first is the classical combinatorial Quadratic Integer Programming (QIP) problem, which has numerous applications in Control, OR, Statistics and graph theory. The proposed technique explores the properties of the optimal solution of the dual problem in order to reduce the duality gap. This is achieved by solving a problem of the same form as the primal but of reduced rank, involving the enumeration of the vertices of a zonotope in a low-dimensional space which can be performed via a polynomial-time algorithm.

The second problem is the calculation of the “structured singular value” (mu) of a matrix, which is still the main computational bottleneck in robust control. Our approach proceeds by formulating and solving a sequence of “relaxed” structured distance-to-singularity problems. Bounds on the structured singular value are obtained by specializing the results to uncertainty structures involving simultaneous spectral-radius and norm constraints. Provided the solution (or a “good” bound) of a reduced-rank mu-problem can be obtained, our method produces an upper bound bound for the original problem which breaches the convex relaxation (“D-iteration”) bound, via the solution of an eigenvalue problem.

The similarities between the techniques corresponding to each problem (QIP and mu) are highlighted, which suggests that the could be instances of a single general methodology in the area of convex relaxations.