A global linear programming solution to some open robustness problems including matrix polytope stability

We consider a matrix having entries which depend affinely on uncertain parameters; these parameters are restricted to a box. Subsequently, we provide a solution to the robust stability problem. This solution involves only a finite number of linear programs. More specifically, using the problem data, we define a finitely terminating sequential procedure for linear program (LP) generation with each new set of LPs dependent on the solution of the preceding set. Given any prescribed accuracy level ε for the global optimum, we guarantee its attainment via solution of N_ε problems where N_ε is the dimension of the matrix under consideration. In turn, each of these problems can be solved in a finite number of stages N_ε each involving no more than 4n-2 linear programs. This, however, does not imply polynomial complexity because the dependence of N_ε on n is unknown