_jarvis_'s blog

general mathematical doubt

By _jarvis_, history, 8 years ago, In English

I was solving a problem on spoj, the solution of that problem requires the assumtion that,

if we add the absolute value of 2 or more linear equation in x ( eg. f(x)=|5x-8| + |7x-1| + |12x-13| ) then it necessary that f(x) (note:here f(x) denotes the sum of those terms) would be montonically increasing as we go way from the optimal value of x (note: optimal value of x is the value at which f(x) is minimum) .

Just wanted to confirm if that statement is true or not?

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +16 Vote: I do not like it

This is a convex piecewise-linear function, which is weaker than what you state but perhaps still enough to prove the solution.

Let the terms turn to zero at points x1 ≤ x2 ≤ ... ≤ xn. Look at the derivative of this function. It can be trivially shown that for the term k of the form |akx + bk| we have xk =  - bk / ak. For x < xk, the term contributes  - ak to the derivative, and for x > xk, it contributes  + ak. So, the derivative increases by 2ak at each xk.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    I believe you meant that it is stronger than what author stated. Bitonicity (monotonic increase as we go away from the optimum point) follows from convexity, but not vice versa.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Yeah, it's stronger. Sorry, I've messed up the terms when reading.

      → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    thank you.

    → Reply