Convex relaxation methods in optimisation and robust control

This thesis deals with the analysis of the real µ problem as a powerful tool for measuring the stability margins of a system subject to parametric uncertainty. Several algorithms of varying complexity are proposed for calculating upper bounds of the structured singular value of a matrix M subject to real parametric uncertainty. Our approach is based on the projection of the uncertainty set in the most critical direction. This is implicit in the set of optimal (minimum-norm) unstructured singularising perturbations and is defined by the pair of singular vectors corresponding to the largest singular value of M. Two relaxations are considered to simplify the problem. A randomised algorithm is proposed which relies on the partial enumeration of the Zonotope’s vertices for high dimensional problems when the complete enumeration may not be practical. Applying this bound to our problem produces a probabilistic lower bound on the structured distance to singularity. The main results of the thesis are extended to the distance to singularity problems with "correlated" or nonlinear descriptions of uncertainty. A similar randomised algorithm is proposed for breaching the gap between the Quadratic Integer Programming (QIP) and its convex relaxation which is closely related to the structured singular value problem. It is shown that the duality gap can be reduced, provided a Reduced Rank Quadratic Integer Problem (RRQIP) can be solved. Alternatively, a sequence of increasingly tighter bounds can be obtained by solving a sequence of QIP’s of progressively increasing complexity (and rank). Here, we present a randomisation algorithm for breaching the duality gap when the full enumeration is not computationally feasible. The Greatest Common Divisor(GCD) problem to calculate the nearest common root of a polynomial set under perturbations in their coefficients is also considered in this thesis. We propose a relaxation technique directly to the Sylvester structure before converting to the diagonal matrix which is the standard setting for the structured singular value estimation. This could give an upper bound tighter than the largest singular value without solving the equivalent µ problem which is potentially large-scale. Several numerical examples illustrate the main results of this work