An inexact bundle method for solving large structured linear matrix inequalities

The linear matrix inequality (LMI) is a powerful formalism for expressing convex mathematical constraints that arise in many engineering disciplines. Some practical applications of LMIs are so large that the usual interior point methods for solving them cannot be applied because of their memory requirements. Alternatively, an approach based on the idea of minimizing the maximum eigenvalue of a matrix-valued function can use less memory and exploit the structure of the problem for efficiency. However, special techniques for minimizing the maximum eigenvalue are required because it is not differentiable.; The dissertation reviews bundle methods and the related proximal point methods for minimizing nonsmooth convex functions. The convergence theory of the proximal point method is then extended to handle inexact function evaluations so the maximum eigenvalue can be approximated, sometimes quite loosely, depending on the precision required by the optimization algorithm. The algorithm is specialized to solve LMIs, producing the inexact spectral bundle method. In addition, an iterative Lanczos method is used for estimating of the maximum eigenvalue, and a new, efficient convergence test for the iterations is derived and its stability is proven.; For numerical testing an application involving the validation of an anesthesia model is considered. A technique for exploiting the displacement structure in this problem is developed, which includes a stable algorithm for solving positive definite displacement-structured linear systems. The full validation problem is too large to solve at once, so it is reduced to a series of subproblems of increasing size, and the inexact spectral bundle method is tested on these subproblems.; The algorithm successfully solves medium-size problems, with matrices of order 1500, much larger than what interior point methods can currently handle. However, the numerical results indicate two general performance issues that should be addressed before the algorithm can be considered truly practical for large problems. These issues involve the widely varying rates of convergence for feasible LMIs, and the slow convergence detection mechanism of the bundle method for infeasible LMIs. The proximal point framework seems flexible enough to allow for the innovations required to overcome these performance limitations.