Minimal representation of quadratically constrained convex feasible regions

Minimal representation of quadratically constrained convex feasible regions

0.00 Avg rating0 Votes
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: ,
Keywords: programming: convex
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.