Convex relaxations in combinatorial optimization and robust control
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.
Date:
9 May 2018, 14:00
Venue:
Venue to be announced
Speaker:
Prof George Halikias (City University, London)
Organising department:
Department of Engineering Science
Organiser:
Professor Kostas Margellos (University of Oxford)
Organiser contact email address:
kostas.margellos@eng.ox.ac.uk
Part of:
Control Seminar Series
Booking required?:
Not required
Audience:
Members of the University only
Editor:
Kostas Margellos
