-2

Say if you want to find the minimum value of $A$ where: $$A=|x-2|+|x+3|+|x-6|$$

How would you solve it and what is the logic?

I read that I should set each absolute value to $0$. And substitute each $x$ value. The smallest value of $A$ based on that is the answer.

I don't really get why I should set each absolute value to $0$. Why would that help me get the smallest value of $A$?

Dave
  • 13,568
user456677
  • 1
  • We have that $|x-k|\ge 0$.

    The minimum of $|x-k| = 0$ at $x=k$.

    Therefore, the minimum should lie at one of our $k$'s $(-3,2,6)$.

     – Saketh Malyala Jun 21 '17 at 01:11
  • I understand that. Thak you. – user456677 Jun 21 '17 at 01:15
  • Aside: one usually uses the pipe character (shift-backslash on american keyboards) to denote absolute values, rather than using the letter ell. In some fonts, such as the one I read your post in, the letter ell does not display solely as a vertical line. –  Jun 21 '17 at 01:16

2 Answers2

1

The main idea here is to narrow the solution to problem down to a small, finite set of cases, and then just check each case in turn.

The graph of this function consists of a finite number of straight lines; if this function does* have a minimum, then the minimum has to happen at one of the corners joining the straight lines. The corners of the graph are precisely the points where the individual absolute value terms change direction: i.e. where they are zero.

*: an example of a similar function that doesn't have a minimum is $f(x) = |x| - 2|x-1|$

1

If you plot out the curve, we can see that the curve is a convex piecewise linear function with kinks at those values. That is the subgradient changes at those points.

Remark:

An alternative way to do this quicker is to note that this is just measuring the sum of distance of $x$ from the points $2$, $-3$ and $6$. It can be proven that the optimal solution is at the median. In this case, the median is $2$ and $2$ would minimize $A$.

subgradient of $|x|$ would be $sign(x)$.

Let's consider what happens when $x \notin \{2, -3, 6 \}.$

When $x < -3$, the subgradient would be $(-1)+(-1)+(-1)=-3<0$, hence it is decreasing.

When $ x \in (-3,2)$, the subgradient would be $1 + (-1)+(-1) = -1<0$, hence it is still decreasing.

when $x \in (2,6)$, the subgradient would be $1+1+(-1)=1 > 0$, hence it is increasing.

when $x > 6$, the subgradient is $1+1+1=3 >0$ and it is increasing.

We can see that the slope changes from negative to positive at the median where there are equal number of kinks of the left and equal number of kinks on the right.

Siong Thye Goh
  • 149,520
  • 20
  • 88
  • 149