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
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!
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"?
I mean, use a linear expression to represent $\displaystyle \sum (f(xi, yi))$
Quote:
Originally Posted by Ackbeet
Ok, what is a linear expression? Can you give an example?
like, x1 + x2 + y1 + y2 - x3 or
2*x1 -3*y1 + 4*x2 - 5*y2 or something like this
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.
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 !
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.
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?
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.
You could also hand your optimization problem off to gnumeric. Here's a thread talking about that.
Thank you sooo much! I will go to see that.
You're very welcome. Have a good one!
