## Linear Programming - Separation of points

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.
yA ≥ axA+b+d
yB ≤ axB+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?

 PhysOrg.com science news on PhysOrg.com >> Heat-related deaths in Manhattan projected to rise>> Dire outlook despite global warming 'pause': study>> Sea level influenced tropical climate during the last ice age
 Recognitions: Science Advisor 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?
 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.

Recognitions:

## Linear Programming - Separation of points

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.

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

Recognitions: