Thread Subject: Updating QHull: Removing redundant constraints (Help with convhullnl on large data)

Hello,

I'm working on a quadratic programing problem where I have a constraint matrix

Ax <= b; where size(A) = [ 20,000 20 ] and size(b) = [20,000 1];

However, many of these constraints are redundant. I need to figure out which ones are not needed, and remove them.

I know of one way to do this:

- Find the convex hull of the constraint space and only keep those points on the hull:
http://www.mathworks.com/matlabcentral/fileexchange/7897-noredund-remove-redundant-linear-constraints-or-inequalities

b = b - A*c; % polytope A*x <= b now includes the origin
% obtain dual polytope vertices
D = A ./ repmat(b,[1 size(A,2)]);
k = convhulln(D);


----

However, here is the problem. When I run convhulln on the data, matlab crashes. Reading about QHull on their website, it seems a number of bugs with large data have been fixed recently, but I don't know how to upgrade QHull.

Does anybody know a better way to remove my constraints, or a way to upgrade QHull to a newer version that might not segfault on my data?

I just wonder whether the issue Chris mentioned has some solution.

"Does anybody know a better way to remove my constraints, or a way to upgrade QHull to a newer version that might not segfault on my data?"

The version of qhull used in matlab seems pretty old, "2000-2003"

Sandro

"Chris McIntosh" wrote in message <hnol66$p0k$1@fred.mathworks.com>...
> Hello,
>
> I'm working on a quadratic programing problem where I have a constraint matrix
>
> Ax <= b; where size(A) = [ 20,000 20 ] and size(b) = [20,000 1];
>
> However, many of these constraints are redundant. I need to figure out which ones are not needed, and remove them.
>
> I know of one way to do this:
>
> - Find the convex hull of the constraint space and only keep those points on the hull:
> http://www.mathworks.com/matlabcentral/fileexchange/7897-noredund-remove-redundant-linear-constraints-or-inequalities
>
> b = b - A*c; % polytope A*x <= b now includes the origin
> % obtain dual polytope vertices
> D = A ./ repmat(b,[1 size(A,2)]);
> k = convhulln(D);
>
>
> ----
>
> However, here is the problem. When I run convhulln on the data, matlab crashes. Reading about QHull on their website, it seems a number of bugs with large data have been fixed recently, but I don't know how to upgrade QHull.
>
> Does anybody know a better way to remove my constraints, or a way to upgrade QHull to a newer version that might not segfault on my data?

I am also interested in an updated version of QHull in MATLAB. I wonder if someone is working on it already?