Results 1 to 13 of 13

Math Help - 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

    \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; July 17th 2010 at 07: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
    5
    Awards
    2
    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"?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jul 2010
    Posts
    9
    I mean, use a linear expression to represent \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

    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"?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    5
    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
    5
    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 \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.
    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
    5
    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
    5
    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
    5
    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
    5
    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: October 22nd 2009, 11:26 AM
  2. Linear Equation
    Posted in the Algebra Forum
    Replies: 2
    Last Post: March 5th 2009, 02:40 AM
  3. Replies: 1
    Last Post: November 17th 2008, 07:17 PM
  4. Linear Equation
    Posted in the Algebra Forum
    Replies: 3
    Last Post: October 10th 2008, 09:28 AM
  5. Linear Equation Help
    Posted in the Algebra Forum
    Replies: 3
    Last Post: December 12th 2006, 06:37 PM

Search Tags


/mathhelpforum @mathhelpforum