Hi guys,

Given:

X = {x1, x2, ... xn}

Y = {y1, y2, ... yn}

and function f where

f(x, y) = 1 if (x >= y)

f(x, y) = 0 otherwise

Is there a linear representative of

$\displaystyle \sum (f(xi + yi))$

Thanks in advance!

Printable View

- Jul 17th 2010, 06:02 PMzhu1984Linear Equation
Hi guys,

Given:

X = {x1, x2, ... xn}

Y = {y1, y2, ... yn}

and function f where

f(x, y) = 1 if (x >= y)

f(x, y) = 0 otherwise

Is there a linear representative of

$\displaystyle \sum (f(xi + yi))$

Thanks in advance! - Jul 17th 2010, 06:13 PMAckbeet
Well, one thing you could do is write this in terms of unit step functions. Define

$\displaystyle u(t)=\begin{cases}0\quad t<0\\ 1\quad t\ge 0\end{cases}.$

Then you have for your sum the following:

$\displaystyle \displaystyle{\sum_{n=1}^{N}f(x_{i},y_{i})=\sum_{n =1}^{N}u(x_{i}-y_{i})}.$

But this may be trading one unusable thing for another. What exactly do you mean by "linear representative"? - Jul 17th 2010, 06:18 PMzhu1984
- Jul 17th 2010, 06:30 PMAckbeet
Ok, what is a linear expression? Can you give an example?

- Jul 17th 2010, 06:40 PMzhu1984
like, x1 + x2 + y1 + y2 - x3 or

2*x1 -3*y1 + 4*x2 - 5*y2 or something like this - Jul 19th 2010, 03:09 AMAckbeet
In your last edit of the OP, I think you meant to have a comma in-between the xi and the yi inside the argument of the function f. f is defined to be a function of two arguments.

I do not think your function can be represented by a linear expression. The problem is that f is itself nonlinear. Proof that $\displaystyle \sum_{i}f(x_{i},y_{i})$ is nonlinear:

Let $\displaystyle X_{1}=\{0,0,2\}, X_{2}=\{0,0,5\},$, and let $\displaystyle Y_{1}=\{0,0,-3\}, Y_{2}=\{0,0,-7\}.$ (Prime numbers are great for counter-examples!) For your function $\displaystyle g(X,Y)=\sum_{i} f(x_{i},y_{i})$ to be linear in $\displaystyle X$ means you'd have to have $\displaystyle g(aX_{1}+bX_{2},Y)=ag(X_{1},Y)+bg(X_{2},Y)$ for all scalars $\displaystyle a,b$ and for all vectors $\displaystyle X_{1},X_{2},Y.$ So, check it out:

$\displaystyle g(X_{1},Y_{1})=1$

$\displaystyle g(X_{2},Y_{1})=1$

$\displaystyle g(X_{1}+X_{2},Y_{1})=g(\{0,0,7\},\{0,0,-3\})=1\not=g(X_{1},Y_{1})+g(X_{2},Y_{1}).$

For this reason, I think you're barking up the wrong tree. You said in a PM that this question is a crucial part of your current work. If you could perhaps give me more context, I might be able to help you find a different way around this problem. - Jul 21st 2010, 12:48 PMzhu1984
The detailed context is like this:

Given two vectors of variables A and B, and linear constraints on them

(such as a3 + b4 > 0, a1 + a2 =1, the number of constraints can be many), what are solutions of A and B

such that the *number* of pairwise subtractions that are positive (a_i -

b_i > 0) is maximized? or, in other word, what are solutions that maximize the number of "ai - bi > 0" being true?

Thank you ! - Jul 21st 2010, 01:04 PMAckbeet
How many elements are in A and B?

Have you listed all the constraints?

What do you mean by "solutions of A and B"?

I'd probably hand this question off to Excel's Solver routine. - Jul 21st 2010, 01:29 PMzhu1984
the number of elements in A and B can be more than 100 and the number of constraints can be 200 or more. The solustion of A and B is the solution for each of elements in A and B that makes "ai - bi > 0" maximum.

For example, there are a1, a2, a3 in vector A and b1, b2, b3 in vector B.

The constraints are:

a1 - b1> a2 - b2;

a2 = 1;

a2 -b2 > a3 - b3;

b3 + a2 > 0;

one of the the solution for our problem can be: a1 = 5 b1 = 3, a2 = 1, b2 = 0, a3 = 0, b3 = 0;

because this makes: a1 - b1 > 0, a2 - b2 > 0 and a3 - b3 > 0. If we cannot fine a solution that makes all of the "ai - bi" greater than zero, the solution should be the one that makes as much as "ai - bi" greater than zero. Is there any existed theory discuss with this? - Jul 22nd 2010, 05:54 AMAckbeet
This problem simply isn't in the realm of linear programming. You're trying to maximize a nonlinear function with certain constraints. I'd recommend the book

*How to Solve It: Modern Heuristics*, by Michalewicz and Fogel. You might be best off with an evolutionary algorithm or an annealing algorithm. I can imagine that with a hill-climbing algorithm, you're going to run into local maximums and get stuck. So you're going to need ways of escaping local maximums. - Jul 22nd 2010, 06:46 AMAckbeet
You could also hand your optimization problem off to gnumeric. Here's a thread talking about that.

- Jul 23rd 2010, 10:16 AMzhu1984
Thank you sooo much! I will go to see that.

- Jul 23rd 2010, 10:17 AMAckbeet
You're very welcome. Have a good one!