| Description |
NOREDUND - Remove redundant linear inequalities from a set of inequalities; i.e., remove redundant linear constraints defining a feasible region. Note that the feasible region satisfies A*x <= b, where A is a fixed matrix, b is a fixed vector, and x is the vector of coordinates in your space; i.e., all values of x (or equivalently, all ordered n-tuples of coordinate numbers) which satisfy the inequality A*x <= b are inside the feasible region (or on its boundary). Removing redundant constraints means removing rows of A and the corresponding entries in b which are not necessary, which then leaves a new inequality An*x <= bn. Since the number of columns in A and An is the same (equal to the number of rows in x, or equivalently to the dimensionality of your space), the dimensionality of the problem is unchanged. Rather, the redundant constraints are simply removed.
[An,bn] = noredund(A,b)
For n variables:
A = m x n matrix, where m >= n (m constraints)
b = m x 1 vector (m constraints)
An = mm x n matrix, where mm >= n (mm nonredundant constraints)
bn = mm x 1 vector (mm nonredundant constraints)
NOTES:
(1) Unbounded feasible regions are permitted.
(2) This program requires that the feasible region have some finite extent in all dimensions. For example, the feasible region cannot be a line segment in 2-D space, or a plane in 3-D space.
(3) At least two dimensions are required.
(4) See function CON2VERT which is limited to bounded feasible regions but also outputs vertices for the region.
(5) Written by Michael Kleder, June 2005. Minor update, Feb 2006. |
