Linear Equation

• Jul 17th 2010, 06:02 PM
zhu1984
Linear 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

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

• Jul 17th 2010, 06:13 PM
Ackbeet
Well, one thing you could do is write this in terms of unit step functions. Define

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

Then you have for your sum the following:

$\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 PM
zhu1984
I mean, use a linear expression to represent $\sum (f(xi, yi))$

Quote:

Originally Posted by Ackbeet
Well, one thing you could do is write this in terms of unit step functions. Define

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

Then you have for your sum the following:

$\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:30 PM
Ackbeet
Ok, what is a linear expression? Can you give an example?
• Jul 17th 2010, 06:40 PM
zhu1984
like, x1 + x2 + y1 + y2 - x3 or
2*x1 -3*y1 + 4*x2 - 5*y2 or something like this
• Jul 19th 2010, 03:09 AM
Ackbeet
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 $\sum_{i}f(x_{i},y_{i})$ is nonlinear:

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

$g(X_{1},Y_{1})=1$
$g(X_{2},Y_{1})=1$
$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 PM
zhu1984
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 PM
Ackbeet
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 PM
zhu1984
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 AM
Ackbeet
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 AM
Ackbeet