Linear Programming - Separation of points

[lockedup]

This semester while taking Linear Programming (Linear Optimization Models), we talked about using a linear program to separate two sets of points A and B. The general program is:

Max d
s.t.
y_A ≥ ax_A+b+d
y_B ≤ ax_B+b-d

It can be expanded into finding a polynomial that passes between the two sets.

I'm wondering if anyone has tried other functions. My book says you can as long you leave the function alone and just work with the coefficients. I'm trying to work with trig functions (cos(πx) mostly because the period is 1) and exponential functions but I'm not getting very far. Has anyone seen or tried anything like this?

 

[Stephen Tashi]

As I understand your first example, it is:

A is a finite set of points \{x_A,y_A\}
B is a finite set of points \{x_B,y_B\}

Considering a,b,d to be variables, find the values of a,b,d that maximize d subject to the contraints:

y_A \ge a (x_A) + b + d for each (x_A,y_A) \in A
y_B \le a (x_B) + b + d for each (x_B,y_B) \in B

So you are interested in variants of the problem, perhaps with more variables, say a,b,c,d and contraints like:

y_A \ge a(cos(b\pi (x_A)) + c + d ?

As far as I can see, this would not be a linear programming problem since the constraints involve terms like cos(b\pi(x_A)) that do not become linear functions of the unknowns even after a numerical value is substituted for x_A.

By contrast, a term like b (x_A)^3 in a polynomial function does become a linear function of b after we substittue a specific number for x_A.

You can handle constraints like y_A \ge a (cos(x_A)) + b with linear programming.

There may be other ways of solving the variant of the problem that you propose. Are you interested solving the variant problem or are you just trying to understand the limitations of linear programming?

 

[lockedup]

I'm more or less trying to understand the limits of linear programming. Here's what I was thinking. A = {(-2,0), (0,0), (2,0)} and B = {(-1,0), (1,0)}. How would you separate those with a curve? The obvious answer to me is a cosine curve. Particularly, f(x) = cos (πx) (because the period is 1).

Now, I was hoping I could run a program like this:

Max d:
s.t.
y ≥ a(sin(πx)) + b(cos(πx)) + c + d
y ≤ a(sin(πx)) + b(cos(πx)) + c - d

and get a = c = 0, and b = d = 1.

 

[Stephen Tashi]

For that example, cos(\pi x) is a feasible solution. But 100 cos(\pi x) would be a better solution because it makes d greater. You are in a situation where there is no max for d. You can make d as large as you want. To force the answer to be cos(\pi x) you need to use different constraints - or perhaps even a different objective function.

 

[lockedup]

What about a function like f(x) = Ae^x + B? Or f(x) = (A/x) + B

 

[Stephen Tashi]

What about a function like f(x) = Ae^x + B? Or f(x) = (A/x) + B

What do you mean by "what about "? Those functions produce linear constraints in variables A and B after you substitute particular values of X. As to whether the linear program associated with them has a unique solution, I refuse to think about it yet! You'll have to convince me that separating points with the graph of a function can be an interesting problem.

 

[Office_Shredder]

This could be a clustering problem. I have a bunch of data points corresponding to the conditions under which some experiment is committed. Sometimes the experiment is a success, sometimes it isn't. I perform the experiment again and, after measuring the conditions but before committing the experiment, I want to predict whether the experiment is a success or not. One method would be to find a non-linear equation (if necessary, depending on what the data looks like) that separates the points, and then finding which side my new set of conditions lies on.

For example I fire a projectile with an angle of theta, and measure the windspeed when I do so. I want to know if the projectile goes at least 10 yards. If I didn't know how to do the math (use the data to figure out the coefficient of drag of the cannonball etc) I could just make a bunch of measurements, and try to separate the successes and the failures by a function f(theta,windspeed)=0. A better function is one in which f(theta,windspeed)>d for all the successes so far, and f(theta,windspeed)<d for all the failures for a large value of d

 

[Stephen Tashi]

The example you give is a plausible application. It's more restricted than the general problem of separating two sets of points with a curve. A function y = f(x) can only have one y value for each x value, it can't be used to separate sets of data where the data has different y values (and different success vs fail results) for the same x value. For example data triplets like (persons height, persons weight, whether they can jump a 3 foot fence) could not necessarily be separated.

Using the data in your example, y = A/x + B isn't defined at x = 0, so we can't define how the graph affects the data point (0,0). (i.e. you can't write the constraint implied by the data point (0,0) )

I see no reason to give up on using y = A e^x + B. Have you tried it?