Least absolute deviation minimization by derivative. $Q=\sum_{i=1}^{N} |y_i-\rho|$
I know that $dQ/d\rho=0$ implies to $\rho=median\{y_1,...y_N\}$ but I dont even know why this minimizes $Q$ since $d^2Q/d\rho^2=0$ and isn't >0.
Look at:
$\displaystyle\frac{dQ}{d\rho}=-\sum_{i=1}^{N}sign(y_i-\rho) $
remember $sign(x)=\displaystyle\frac{x}{|x|}=\frac{|x|}{x}$
$\displaystyle\frac{dQ}{d\rho}=-\sum_{i=1}^{N}\frac{(y_i-\rho)}{|y_i-\rho|} $
$\displaystyle\frac{d^2Q}{d\rho^2}=-\sum_{i=1}^{N}\frac{-|y_i-\rho|+sign(y_i-\rho)(y_i-\rho)}{(y_i-\rho)^2}$
$\displaystyle\frac{d^2Q}{d\rho^2}=-\sum_{i=1}^{N}\frac{-|y_i-\rho|+\displaystyle\frac{|y_i-\rho|}{(y_i-\rho)}(y_i-\rho)}{(y_i-\rho)^2}$
$\displaystyle\frac{d^2Q}{d\rho^2}=-\sum_{i=1}^{N}\frac{-|y_i-\rho|+\displaystyle{|y_i-\rho|}}{(y_i-\rho)^2}=0$
 A: The function $\rho \mapsto \sum_i |y_i - \rho|$ is not differentiable at $y_1, \ldots, y_N$, so there will be some caveats to using derivatives to reason about minimizers.
I haven't checked your calculations, but it is not surprising that your computation leads to a zero second derivative. The original function $\sum_i |y_i - \rho|$ is a piecewise linear function in $\rho$ with "knots" at $y_1, \ldots, y_N$. Your derivative computations should be valid for values of $\rho$ that aren't at the knots; because the function is linear at each segment, you'll get a zero second derivative there. However, this does not tell you immediately about the function globally because of the non-differentiability at the knots. [There are things called subderivatives that generalize the idea of derivatives to handle these situations, but it's not necessary to go into that here.]
If you want to argue that the critical point is a minimizer, try showing that the first derivative is nonnegative to the right of the critical point, and nonpositive to the left of the critical point.

Let $f(\rho) = \sum_i |y_i - \rho|$.
Claim: if $\rho^*$ is a median of $y_1, \ldots, y_N$, then $f(\rho^*) \le f(\rho)$ for any $\rho$.
For simplicity I assume $y_1 < \cdots < y_N$. For cases where some of the $y_i$ are the same, the argument below can be modified to handle it.
It suffices to show that $f(\rho) \le f(\rho')$ for $\rho^* \le \rho \le \rho'$, and that $f(\rho') \ge f(\rho)$ for $\rho' \le \rho \le \rho^*$.
Show that $f$ is a piecewise linear function with knots at $y_1 \le \cdots \le y_N$ and slopes $-N, -(N-2), -(N-4), \ldots, N-4, N-2, N$. (You've basically already done this in your computation of $dQ/d\rho$.) Once you've done this, you've shown that $f$ has a "jagged U" shape, so there are global minimizers.

*

*When $N$ is even, there is a segment of slope $0$ in the middle, between $y_{N/2}$ and $y_{N/2 + 1}$. Any point on this segment serves as a median, and you can see from the shape of $f$ that these are all minimizers.

*When $N$ is odd, the two segments between $y_{(N-1)/2}, y_{(N+1)/2}, y_{(N+3)/2}$ have slopes $-1$ and $1$. This middle point $y_{(N+1)/2}$ is the median and can be seen to be the minimizer due to the shape of $f$.

Again, I've assumed the $y_1, \ldots, y_N$ are unique; you can modify this argument to handle the more general case when some values are repeated.
