On 3/7/00 at 9:03 AM, preston.pierce@cplc.com (Pierce, Preston) wrote:

> In the homework on location problems, I'm having trouble getting started. I
> think I understand how to formulate best approximation problems given
> several functions, but in this assignment we are starting with just a group
> of coordinates. I really don't have a specific question. I just need
> someone to point me in the right direction.

On 3/7/00 at 5:48 AM, GENE_RYE@udlp.com wrote:

> On parts b through e of HW 23, the actually stated problem seems to be to answer
> yes or no to the posed question of whether or not the given situation can be
> written as an LP. I would like to think I can get away with a yes/no to those 4
> problem sections, but I believe the intent is that we are to at least set up
> said problem?
>
> In this later case, I think that the approach for most of them (3 of 4) is to
> assume the (infininity,norm) format and the (1.norm) format for the last. The
> equations (I think) can be derived using point slope methodology.
>
> Right track or wrong race course?



To Gene & Preston:

First you have to decide
What does "distance" mean?
and next you must decide
What does "best" mean?
For most of these problems, "distance" refers to the L1 or Linfinity distance. The L1 distance between (x,y) and (5,8) is |x-5|+|y-8|. The Linfinity distance between (x,y) and (5,8) is max{|x-5|,|x-8|}.

Whatever notion of distance you choose, you must decide after you have written down the "distances" from (x,y) to the points (5,8), (-1,-13), (7,2), (3, 15), and (-8,4), what to do with them. One approach would be to try to choose (x,y) to minimize the sum of those distances. Another approach would be to try to choose (x,y) to minimize the largest of those distances.

So those are the two choices you must make. Altogether there would be four possibilities since you have two choices for your notion of "distance" and two choices how to use those distances. Problems c,d, and e use three of these four possibilities.

Now, once you have written down the objective function, you still need to turn it into a linear programming problem. Primarily, this means getting rid of all of the absolute value signs and maxima. The tricks that we learned in our study of approximation problems should be helpful here. One useful fact is that |a| is always the same as max{a,-a}. Another useful trick is that minimizing max{a,b} is the same as minimizing z subject to z>=a and z>=b. Still another useful trick is that minimizing |a|+|b| is the same as either
minimizing max{a+b,a-b,-a+b,-a-b}
or of
minimizing z1+z2 subject to z1>=a, z1>=-a, z2>=b, z2>=-b.

In problems c-e, I want you to express it as an LP. Your opinion "yes" or "no" is not enough. However, for b I will accept just your opinion.

I hope this helps.

- Prof. Jonathan Spingarn


On 3/9/00 at 11:47 AM, Julie_K_Pickett@armstrong.com wrote:

> I was wondering if you could answer a couple of questions about the homework.
>
> Homework #23
> I think I understand how to set up parts b through e of the problem. Are we
> supposed to just set up this parts or are we also supposed to solve them?
>
> Part a -- I don't remember enough from calculus to be sure that I know how to do
> this. What I did was set up the distance equations to some point x and y and
> then separated the x and y components. I ultimately came up with something
> like:
> 5x^2 + 12x + 148 and 5b^2 - 32b + 478. Since the object is to minimize the
> distance, I took the first derivatives of these two equations with respect to x
> and y and came up with x= -1.2 and y = 3.2. When I graph the points, however,
> this doesn't seem very reasonable. Am I off course with this?

You are not off track, you just made a mistake somewhere. Your answer for the y-coordinate is correct. There is no reason to expand the squares; use the chain rule to differentiate. For example, the derivative with respect to x of (x-5)^2+(y-8)^2 is 2(x-5).

For your other questions about #23, please see the letters I have written to other students. Click on "letters" at the class website.

>
> Homework #24
> My question with respect to this problem is how I'm supposed to come up with the
> points on the cube which satisfy the constraints. I didn't follow how you came
> up with the points you used in the example in class. It seemed that you simply
> picked points at random which satisfied the constraints. Following that idea,
> I've come up with the following six points:
>
> (0, 1, 2)
> (0, 2, 0.5)
> (6, 0.33, 0)
> (1, 1.33, 0)
> (6, 0, 0.5)
> (.5, 0, 2)
>
> Again, am I on the right track with this approach?
>
>
>

You've got the wrong points -- none of your points are on the cube because they do not satisfy 0 =< xi =< 1 (i=1,2,3). The points you want are the vertices of the polygon where the plane 6x1+3x2+2x3=7 intersects the cube. Here's one easy way to find all of them:
first, evaluate 6x1+3x2+2x3 at each of the eight vertices of the cube. Then, check each edge of the cube to see if 7 lies between the values of 6x1+3x2+2x3 at the endpoints of the edge. For example,
at the vertex (1,0,0), the value of 6x1+3x2+2x3 is 6
at the vertex (1,0,1), the value of 6x1+3x2+2x3 is 8
Now, 7 does lie between 6 and 8. In fact 7 is 1/2 of the way from 6 to 8, so this tells you that 6x1+3x2+2x3 has the value 7 at the point 1/2 of the way from (1,0,0) to (1,0,1) and that point is (1,0,1/2). This would be the basic feasible solution where x3 is basic, x1 is nonbasic with value 1, and x2 is nonbasic with value 0.
Some edges do not contain a point where 6x1+3x2+2x3=7. For example,
at the vertex (1,0,0), the value of 6x1+3x2+2x3 is 6
at the vertex (0,0,0), the value of 6x1+3x2+2x3 is 0
Since 7 does not lie between 0 and 6, the polygon does not intersect the edge that joins (1,0,0) and (0,0,0).