A Hierarchical Branch-and-Bound Algorithm to Compute the Worst-Case Norm of Uncertain Linear Systems under Inputs with Magnitude and Rate Bounds

摘要

In this paper, we consider the worst-case norm (WCN) of uncertain convolution systems when the inputs are modelled to have bounded magnitude and limited rate. The WCN computation is formulated via a discretization approach, which leads to an NP-hard convex maximization problem. To compute the global solution of the WCN, we develop Hierarchical Branch-and-Bound (HBB) algorithm, which employs a standard Branch-and-Bound (SBB) technique as a subroutine. We validate the HBB algorithm and compare numerical results with that obtained by the SBB algorithm. The HBB algorithm yields correct results with excellent computational speed and outperforms the SBB algorithm, and hence, is viable to attain the WCN computation of high dimensional problems.