Results 1 to 13 of 13

Thread: Linear Equation

  1. #1
    Newbie
    Joined
    Jul 2010
    Posts
    9

    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

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

    Thanks in advance!
    Attached Thumbnails Attached Thumbnails Linear Equation-linear.png   Linear Equation-linear.png   Linear Equation-linear.png  
    Last edited by zhu1984; Jul 17th 2010 at 06:14 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    7
    Awards
    2
    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"?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jul 2010
    Posts
    9
    I mean, use a linear expression to represent $\displaystyle \sum (f(xi, yi))$

    Quote Originally Posted by Ackbeet View Post
    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"?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    7
    Awards
    2
    Ok, what is a linear expression? Can you give an example?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Jul 2010
    Posts
    9
    like, x1 + x2 + y1 + y2 - x3 or
    2*x1 -3*y1 + 4*x2 - 5*y2 or something like this
    Follow Math Help Forum on Facebook and Google+

  6. #6
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    7
    Awards
    2
    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Jul 2010
    Posts
    9
    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 !
    Follow Math Help Forum on Facebook and Google+

  8. #8
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    7
    Awards
    2
    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.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Jul 2010
    Posts
    9
    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?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    7
    Awards
    2
    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.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    7
    Awards
    2
    You could also hand your optimization problem off to gnumeric. Here's a thread talking about that.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Newbie
    Joined
    Jul 2010
    Posts
    9
    Thank you sooo much! I will go to see that.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    7
    Awards
    2
    You're very welcome. Have a good one!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. linear equation
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: Oct 22nd 2009, 10:26 AM
  2. Linear Equation
    Posted in the Algebra Forum
    Replies: 2
    Last Post: Mar 5th 2009, 01:40 AM
  3. Replies: 1
    Last Post: Nov 17th 2008, 06:17 PM
  4. Linear Equation
    Posted in the Algebra Forum
    Replies: 3
    Last Post: Oct 10th 2008, 08:28 AM
  5. Linear Equation Help
    Posted in the Algebra Forum
    Replies: 3
    Last Post: Dec 12th 2006, 05:37 PM

Search Tags


/mathhelpforum @mathhelpforum