About OpenKnowledge@NAU | For NAU Authors

Monte Carlo algorithms for the detection of necessary linear matrix inequality constraints

Jibrin, Shafiu and Pressman, Irwin S. (2001) Monte Carlo algorithms for the detection of necessary linear matrix inequality constraints. International Journal of Nonlinear Sciences and Numerical Simulation, 2 (2). pp. 139-154. ISSN 2191-0294


Download (2MB) | Preview
Publisher’s or external URL: http://dx.doi.org/10.1515/IJNSNS.2001.2.2.139


We reduce the size of large semidefinite programming problems by identifying necessary linear matrix inequalities (LMI's) using Monte Carlo techniques. We describe three algorithms for detecting necessary LMI constraints that extend algorithms used in linear programming to semidefinite programming. We demonstrate that they are beneficial and could serve as tools for a semidefinite programming preprocessor. A necessary LMI is one whose removal changes the feasible region defined by all the LMI constraints. The general problem of checking whether or not a particular LMI is necessary is NP-complete. However, the methods we describe are polynomial in each iteration, and the number of iterations can be limited by stopping rules. This provides a practical method for reducing the size of some large Semidefinite Programming problems before one attempts to solve them. We demonstrate the applicability of this approach to solving instances of the Lowner ellipsoid problem. We also consider the problem of classification of all the constraints of a semidefinite programming problem as redundant or necessary.

Item Type: Article
Publisher’s Statement: The final publication is available at www.degruyter.com
ID number or DOI: 10.1515/IJNSNS.2001.2.2.139
Keywords: Combinatorial optimization; hit; semidefinite
Subjects: Q Science > QA Mathematics
NAU Depositing Author Academic Status: Faculty/Staff
Department/Unit: College of Engineering, Forestry, and Natural Science > Mathematics and Statistics
Date Deposited: 16 Feb 2016 23:30
URI: http://openknowledge.nau.edu/id/eprint/261

Actions (login required)

IR Staff Record View IR Staff Record View


Downloads per month over past year