Suppose I have a set of points denoted by $a_i$
I want to minimize this model:
$$\sum_i (w |(x-a_i)|1(x-a_i)+v|x-a_i|1(a_i-x))$$
where 1(x) denotes an indicator function which takes value $1$ if $x>0$ and $0$, otherwise.
I believe this optimization model should have a close form solution. In fact, the solution represents a line that minimizes the weighted distance between this line (i.e., y=x) and a set of points.
Best Answer
You can rewrite the sum like this: $$ f(x)=\sum_i (w |(x-a_i)|1(x-a_i)+v|x-a_i|1(a_i-x)) = \sum_i b(x-a_i)+c |x-a_i| $$ with $b=\frac{w-v}{2}$ and $c=\frac{v+w}{2}$. Differentiate with respect to $x$: $$ f'(x)=\sum_i b + c~\text{sign}(x-a_i) $$
$f(x)$ is a piecewise-linear function that changes slope at points $a_k$. Thus, its minimum is given by one of them. We need to find a point $x=a_k$ such that the slope of $f'(x)$ is not positive to the left of it and is not negative to the right of it. This condition can be written as $$ -2c\le Nb+(k-1)c-(N-k)c \le 0 $$ or $$ 0 \le \frac{Nb}{2c} + \frac{2k+1-N}{2} \le 1 $$
Then the answer is $k = \lceil\frac{N-1}{2}+\frac{NB}{2c}\rceil$ and the optimal $x$ is given by $a_k$.