Optimization Online


Identifying Redundant Linear Constraints in Systems of Linear Matrix Inequality Constraints

Shafiu Jibrin (shafiu.jibrin***at***nau.edu)
Daniel Stover (stoverd***at***onid.orst.edu)

Abstract: Semidefinite programming has been an interesting and active area of research for several years. In semidefinite programming one optimizes a convex (often linear) objective function subject to a system of linear matrix inequality constraints. Despite its numerous applications, algorithms for solving semidefinite programming problems are restricted to problems of moderate size because the computation time grows faster than linear as the size increases. There are also storage requirements. So, it is of interest to consider how to identify redundant constraints from a semidefinite programming problem. However, it is known that the problem of determining whether or not a linear matrix inequality constraint is redundant or not is NP complete, in general. In this paper, we develop deterministic methods for identifying all redundant {\em linear} constraints in semidefinite programming. We use a characterization of the normal cone at a boundary point and semidefinite programming duality. Our methods extend certain redundancy techniques from linear programming to semidefinite programming.

Keywords: Semidefinite programming, Linear matrix inequalities, Redundancy, Normal cone

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Citation: To appear in the Journal of Interdisciplinary Mathematics


Entry Submitted: 06/05/2006
Entry Accepted: 06/05/2006
Entry Last Modified: 06/30/2006

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society