Article ID: | iaor1997714 |
Country: | Netherlands |
Volume: | 68 |
Issue: | 2 |
Start Page Number: | 169 |
End Page Number: | 186 |
Publication Date: | Feb 1995 |
Journal: | Mathematical Programming (Series A) |
Authors: | Caron Richard J., Obuchowska Wiesawa T. |
Keywords: | programming: convex |
In this paper the authors are concerned with characterizing minimal representations of feasible regions defined by both linear and convex quadratic constraints. They say that representation is minimal if every other representation has either more quadratic constraints, or has the same number of quadratic constraints and at least as many linear constraints. The authors will prove that a representation is minimal if and only if it contains no redundant constraints, no pseudo-quadratic constraints and no implicit equality constraints. They define a pseudo-quadratic constraint as a quadratic constraint that can be replaced by a finite number of linear constraints. In order to prove the minimal representation theorem, the authors also prove that if the surfaces of two quadratic constraints match on a ball, then they match everywhere. In this paper they also provide algorithms that can be used to detect implicit equalities and pseudo-quadratic constraints. The redundant constraints can be identified using the hypersphere directions method.