The Subgradient-Simplex Based Cutting Plane Method to Solve Linear Matrix Inequalities

摘要

Many problems in system and control areas are in the form of Linear matrix inequalities (LMIs). Methods such as interior point methods have been applied to solve these problems. However, for problems with large numbers of LMIs, these algorithms involving high dimensional matrixes can be inefficient. In this paper, the subgradient-simplex based cutting plane method is used to solve the LMI feasibility problem. The method obtains a feasible solution by iteratively cutting off the non-feasible part of a given polyhedron. At the query points, deep cuts are constructed by sequentially checking the LMIs, rather than handle all the LMIs simultaneously, until the infeasibility for an LMI is detected. The calculation of query points is a key step for cutting plane methods. The subgradientsimplex based cutting plane method efficiently finds query points in a three-level process. A point on the half way along the subgradient is easily obtained as the query point. A sphere inscribed in a corner or the Chebyshev center is calculated based on simplex tableaus to ensure the query points are deep inside. Redundant constraints can also be pruned based on simplex tableaus.