I have a large linear inequality system of the form $Ax ≤ 0$.
Is there a way to solve this system using linear algebra tools like SVD?
Is it possible to solve a linear inequality system using SVD?
2
$\begingroup$
linear-algebra
inequality
1 Answers
1
No; loosely speaking this problem is more related to linear programming, which is not equal to linear algebra.
(Plugging in an SVD of $A$ will be too helpful as you probably have seen.)
The set $Ax\leq 0$ is a convex polytope and the representation $Ax\leq 0$ is called its H-representation because it is a description as intersection of half-spaces. Another representation is its V-representation which consists of a list of the vertices. The Wikipedia entry on convex polytopes has more pointers.
-
0Yes, that's what I thought. I know it can be solve using linear-$p$rogramming, and indeed, my desired solution is the list of vertices. Thanks. – 2012-07-24