I have added comments throughout your message and my original reply. My comments are not preceeded by any characters while I have placed *** before all the other lines. *** ***From guy@trofis.tfrc.csiro.au Tue Mar 24 21:42:42 1992 ***Received: from [192.94.62.1] by orion.waterloo.edu with SMTP *** id <AA09368>; Tue, 24 Mar 92 21:42:01 -0500 ***Received: by trofis.tfrc.csiro.au id AA24625 *** (5.65c/IDA-1.4.4 for hwolkowi@orion.uwaterloo.ca); Wed, 25 Mar 1992 12:40:47 +1000 ***Date: Wed, 25 Mar 1992 12:40:47 +1000 ***From: Guy Carpenter <guy@trofis.tfrc.csiro.au> ***Message-Id: <199203250240.AA24625@trofis.tfrc.csiro.au> ***To: hwolkowi@orion ***Subject: Re: Convex Envelope in n-dimensions? ***Status: RO *** *** ***Late last year I posted a Q to the net asking about determining ***if a point was contained in the convex hull defined by a number ***of points. *** ***You were kind enough to formulate a comprehensive reply which ***directed me to Farkas lemma. *** ***At the time I was under pressure to get the code working, so I ***implemented a brute force solution. It works. It's very slow. ***But as the method shows promise, I am now trying to use your ***suggestions to write an efficient solution. *** ***I'm having a problem understanding the final step, and wonder if ***I could impose upon you for a little further direction. *** ***As a reminder, the problem as originally stated: *** ***>I have a set of points defined by coordinates in n-dimensional ***>space, where n varies, (no more than ~10). I would like to be able ***>to define the smallest convex envelope which encloses those ***>points, so that I may check for inclusion/exclusion of points ***>from another set. *** ***Your solution, condensed here by me: *** ***> Let A denote the matrix with columns a_i. ***> Let the matrix B be A with the vector of ones e^T ***> adjoined as the last row. ***> Now suppose a point y is given. ***> Let b be the vector y with 1 adjoined as the last row. ***> ***> Then y is in the convex envelope if and only if ***> b=Bx, x>=0 ***> is a consistent system. You can use the simplex method right here to find the vector x and so see if y is in the convex envelope, i.e. solve the linear programming problem: min 0x s.t. Bx=b, x>=0 To solve this problem you have to use the two phase approach and phase I is essentially equivalent to the Farkas lemma arguement I mentioned. So if you need to actually find the vector x that gives the coordinates of the convex combinations, then you should use the simplex method here, i.e. phase I of the simplex method. The phase I approach identifies infeasibility while if the problem is feasible, then the optimal value of the phase I program is 0 and the optimal solution yields the vector x and the basis tells you which columns of the matrix A are used in the convex combination. The matrix B has n+1 rows and so there will be at most n+1 columns that are needed in the basis. Less may be possible if there is a degenerate basic feasible solution. NOte that the fact you need at most n+1 is also a consequence of Caratheodory's theorem. ***> ***> Now Farkas Lemma states that this system is consistent if and only if ***> B^Tz >= 0 implies b^Tz >=0 ***> ***> But this system can be checked using the simplex method, i.e. check ***> whether 0 is the solution of the linear program ***> min b^Tz subject to B^Tz >= 0 ***> So, if 0 is the solution then the given point y is in the convex ***> envelope, otherwise it is not. *** ***I am using the simplex algorithm as presented in Sedgewick, Alogorithms ***in C. Unfortunately Sedgewick doesn't persue the simplex alg very far, ***so I'm trying to work from his arm waving at the end of chapter. *** ***My fundamental problem is this: *** *** Is the z vector constrained to z>=0 ? This appears No!!! You should not have z>=0. The standard trick is to do a substitution, i.e. let z=z'-z'', where both z' and z'' are >=0. After this substitution you have a LP with nonnegative variables. *** to be implicit in the method I am attempting to use, *** and perhaps that is the start of my problem. If it is not *** so constrained, does the simplex code need to be changed? *** *** Can I assume z=0 is a (possibly non-optimal) solution at *** which to start the simplex driven pivoting? *** It would appear to be the case, but I think this leads to *** an inconsistant conclusion later on. *** ***To illustrate the approach, I will work a very simple problem and ***show how it fails: *** ***take 3 points in two dimensions : [1,2] [2,3] [0,4] ***and test for inclusion the point [20, 20], clearly outside. *** ***A = 1 2 0 B = 1 2 0 y = 20 b = 20 *** 2 3 4 2 3 4 20 20 *** 1 1 1 1 *** ***B^T = 1 2 1 b^T = 20 20 1 *** 2 3 1 *** 0 4 1 *** ***minimize b^Tz subject to B^Tz >=0 This is the correct LP here. *** ***Yields an objective function maximize (20 z1 + 20 z2 + z3) Why maximize????? You mean minimze here???? ***This is adjusted to fit the alg to minimize (-20 z1 - 20 z2 - z3). *** ***The set of constraints is: Adding slack variables yields: *** ***1 z1 + 2 z2 + 1 z3 >=0 1 z1 + 2 z2 + 1 z3 + k1 = 0 ***2 z1 + 3 z2 + 1 z3 >=0 2 z1 + 3 z2 + 1 z3 + k2 = 0 ***0 z1 + 4 z2 + 1 z3 >=0 0 z1 + 4 z2 + 1 z3 + k3 = 0 You have added NEGATIVE slacks??? You need to add surplus variables since the constraints were >= 0. 1 z1 + 2 z2 + 1 z3 >=0 1 z1 + 2 z2 + 1 z3 - k1 = 0 2 z1 + 3 z2 + 1 z3 >=0 2 z1 + 3 z2 + 1 z3 - k2 = 0 0 z1 + 4 z2 + 1 z3 >=0 0 z1 + 4 z2 + 1 z3 - k3 = 0 I will not continue with example as I can see that it will not work due to your assumptions that zi>=0 and since ki <= 0 in your formulation. Please try solving the LP I mentioned above. I think that approach will be easier and there is no need to worry about the nonnegativity of the variables only adding artificial variables for phase I. *** ***Which produces the following matrix ala Sedgewick: *** ***20 20 -1 0 0 0 0 <- objective function coeff's negated *** 1 2 1 1 0 0 0 *** 2 3 1 0 1 0 0 *** 0 4 1 0 0 1 0 *** ***The simplex code will cause pivoting at (2,3) (assuming top left is (1,1).) ***and consider the game over, since there will be no more negative ***coeffients in the objective function. This yields the following: *** ***23 22 0 1 0 0 0 <- value of objective fn is still 0, implying *** 3 2 1 1 0 0 0 that the point y is in the convex hull, ***-1 1 0 -1 1 0 0 which we know to be wrong. ***-5 2 0 -1 0 1 0 *** ***I can clearly see that this last stage is meaningless. Since all of the ***last column values are 0, the value of the objective function will always ***be zero. *** ***I though perhaps I needed to use the two phase method described briefly ***at the end of the chapter: *** *** "Specifically, we add another set of artificial variables *** s1.s2...sn and add variable si to the ith equation. This is *** done simply by adding to the matrix N columns filled with the *** identity matrix. This immediately gives a feasible basis for *** this new linear probram. The trick is to run the above program *** algorithm with the objective function -s1-s2-...-sn. If there *** is a solution to the original linear program, then this *** objective function can be maximized at zero." *** ***Oh my - that sounds very much like the lemma which is the basis of ***the method you described?! Worse, if the objective function to ***be minimised has all negative coefficients, Sedgewicks own code ***will refuse to do anything at all, as his code terminates as soon ***as row 0 contains no negative values. (this row is initialized with ***the negative of the coefficients.) *** ***I am immensely grateful for the help you have already provided, and ***apologise for asking for more of your time. Any help will be much ***appreciated. *** ***Many thanks, ***Guy. ***---------------------------------------------------------------------- ***CSIRO Tropical P.O. Box 780 Work : (070) 91 1755 *** Forest Atherton Q 4883 Fax : (070) 91 3245 *** Research Australia Home : (070) 95 3309 *** Centre guy@tfrc.csiro.au ***---------------------------------------------------------------------- *** *** ***