I know the real numbers $a,b,c$ and $d$ and I am trying to find three more numbers - $x, y, z$ - such that their average is equal to $d$ and the sum $|a-x| + |b-y| + |c-z|$ is minimal.
How would I do that? I can use a computer to compute the numbers, but I have no idea how to approach the problem. Any help is appreaciated.
On
Formulate
$\min \ |a-x| + |b-y | + |c-z|$
$s.t. \ x+y+z = 3d$
Replace $x = 3d - y - z$, you have $\min |a-3d + y+ z| + |b-y| + |c-z|$.
Linearize it by replacing:
$\min t_1 + t_2 + t_3 \\ s.t. \ -t_1 \leq a-3d+y+z \leq t_1 \\ \qquad -t_2 \leq b-y \leq t_2 \\ \qquad -t_3 \leq c-z \leq t_3 \\ \qquad \quad t_1,t_2,t_3 \geq 0$
You now have a linear problem. You can even solve this in Excel Solver.
I created an excel template for you available here. Just change the parameters in the orange part as you wish. Then, go to excel solver and just click the solve button. It will be updated after you do so.
If you can not find excel solver in your excel spreadsheet, just follow this: https://support.office.com/en-us/article/load-the-solver-add-in-in-excel-612926fc-d53b-46b4-872c-e24772f078ca
On
We'll do it by reducing to the case where $a=b=c=0$ by changing variables, where it's much easier to see what's going on.
Let $\delta_x = x-a$, $\delta_y = y-b$, and $\delta_z = z-c$. We must have $0=3d-(x+y+z) = 3d-(a+b+c)-(\delta_x+\delta_y+\delta_z)$. Let's write $\Delta = 3d-(a+b+c)$. So $\delta_x+\delta_y+\delta_z = \Delta$. And we want to minimize $|\delta_x|+|\delta_y|+|\delta_z|$. I claim the minimum is achieved with $\delta_x=\delta_y=\delta_z=\Delta/3$, so $|\delta_x|+|\delta_y|+|\delta_z| = |\Delta| = |3d-(a+b+c)|$. Here's why:
It's quite easy but there's some casework (as mjqxxxx states in their answer, we are proving the triangle inequality in one dimension). First suppose $\Delta \ge 0$. If $\delta_x<0$, then $\delta_y+\delta_z > \Delta$. If $\delta_y < 0$, then $\delta_z>\Delta$, so $|\delta_x|+|\delta_y|+|\delta_z|>\Delta = |\Delta|$. Similarly, if any two of the deltas are negative, we exceed $|\Delta|$. If $\delta_x<0$ and $\delta_y, \delta_z\ge 0$, then again $|\delta_y|+|\delta_z|=\delta_y+\delta_z > \Delta = |\Delta|$. Similarly, if any of the deltas is negative, we exceed $|\Delta|$. So all deltas are nonnegative, and so $|\delta_x|+|\delta_y|+|\delta_z| = \delta_x+\delta_y+\delta_z=\Delta=|\Delta|$.
If $\Delta<0$, then let $\Delta' = -\Delta$, $\delta_x'=-\delta_x$, $\delta_y'=-\delta_y$, and $\delta_z'=-\delta_z$. We have $|\delta_x'|+|\delta_y'|+|\delta_z'| = |\delta_x|+|\delta_y|+|\delta_z|$, and $\delta_x'+\delta_y'+\delta_z' = \Delta'$. The above paragraph shows that the minimum is again $|\Delta'|=|\Delta|$.
On
Let $$s=3d-a-b-c.\tag1$$ If $\underline{s=0}$ then vector $\{x,y,z\}=\{a,b,c\}$ provides the global minimum $|a-x|+|b-y|+|c-z| = 0.$
Otherwize, denote \begin{cases}u=\min\left(\dfrac{x-a}s,\dfrac{y-b}s,\dfrac{z-c}s\right)\\ v=\mathrm{med}\left(\dfrac{x-a}s,\dfrac{y-b}s,\dfrac{z-c}s\right)\\ w=\max\left(\dfrac{x-a}s,\dfrac{y-b}s,\dfrac{z-c}s\right),\tag2 \end{cases} then $$u+v+w = 1,\quad u\le v\le w.\tag3$$
Let us minimize the function $$f(u,v)=|u|+|v|+1-u-v\tag4$$ under the conditions $(3),$ using the intervals method.
$\underline{\text{Case }\mathrm{u \le v \le 0 \le 1-u-v}}.$
$$f(u,v) = 1-2u-2v,\quad u\le v\le 0\le 1-u-v,$$
$$\min f(u,v)= 1\quad\text{at}\quad \{u,v\}=\{0,0\}$$
$\underline{\text{Case }\mathrm{u \le 0\le v\le 1-u-v}}.$
$$f(u,v) = 1-2u,\quad u\le 0\le 2v\le 1-u,$$
$$\min f(u,v)= 1\quad\text{at}\quad u=0,\quad v\in\left[0,\frac12\right].$$
$\underline{\text{Case }\mathrm{0\le u \le v\le 1-u-v}}.$
$$\min f(u,v) = 1 \quad\text{at}\quad 0 \le u \le \dfrac13,\quad v \le \dfrac{1-u}2.\tag5$$
Formulas $(5)$ present the common solution. In the terms of $x,y,z,$ this gives
$$\color{brown}{\mathbf{\min|a-x|+|b-y|+|c-z| = |3d-a-b-c|\quad\text{at}\\ {\small \left[\begin{align} &\left(\dfrac{x-a}s\in\left[0,\dfrac13\right]\right)\wedge\left(\dfrac{y-b}s\in\left[0,\dfrac12\left(1-\dfrac{x-a}s\right)\right]\right)\wedge\left(\dfrac{z-c}s\in\left[0,1-\dfrac{x-a}s-\dfrac{y-b}s\right]\right)\\ &\left(\dfrac{x-a}s\in\left[0,\dfrac13\right]\right)\wedge\left(\dfrac{z-c}s\in\left[0,\dfrac12\left(1-\dfrac{x-a}s\right)\right]\right)\wedge\left(\dfrac{y-b}s\in\left[0,1-\dfrac{x-a}s-\dfrac{z-c}s\right]\right)\\ &\left(\dfrac{y-b}s\in\left[0,\dfrac13\right]\right)\wedge\left(\dfrac{x-a}s\in\left[0,\dfrac12\left(1-\dfrac{y-b}s\right)\right]\right)\wedge\left(\dfrac{z-c}s\in\left[0,1-\dfrac{x-a}s-\dfrac{y-b}s\right]\right)\\ &\left(\dfrac{y-b}s\in\left[0,\dfrac13\right]\right)\wedge\left(\dfrac{z-c}s\in\left[0,\dfrac12\left(1-\dfrac{y-b}s\right)\right]\right)\wedge\left(\dfrac{x-a}s\in\left[0,1-\dfrac{z-c}s-\dfrac{y-b}s\right]\right)\\ &\left(\dfrac{z-c}s\in\left[0,\dfrac13\right]\right)\wedge\left(\dfrac{y-b}s\in\left[0,\dfrac12\left(1-\dfrac{z-c}s\right)\right]\right)\wedge\left(\dfrac{x-a}s\in\left[0,1-\dfrac{z-c}s-\dfrac{y-b}s\right]\right)\\ &\left(\dfrac{z-c}s\in\left[0,\dfrac13\right]\right)\wedge\left(\dfrac{x-a}s\in\left[0,\dfrac12\left(1-\dfrac{z-c}s\right)\right]\right)\wedge\left(\dfrac{y-b}s\in\left[0,1-\dfrac{z-c}s-\dfrac{x-a}s\right]\right)\\ \end{align}\right.}}}$$
On
Considering the problem
$$ \min_{x_k}\sum_{k=1}^n |a_k-x_k|\ \ \mbox{s. t.}\ \ \sum_{k=1}^n x_k = n d $$
This problem can be handled by the Dynamic Programming multi-stage process algorithm with $f_k(x_k) = |a_k-x_k|$
$$ M_1(x) = f_1(x)\\ M_k(x) = \min_{-nd \le x_k \le nd}\left[f_k(x_k)+M_{k-1}(x-x_k)\right] $$
and finally $\min M_n(\cdot)$ is the sought value.
Let $x=a+d_a$, $y=b+d_b$, and $z=c+d_c$; then you want to minimize $|d_a|+|d_b|+|d_c|$ while satisfying $d_a+d_b+d_c=3d-a-b-c\equiv D$. By the triangle inequality, $$ |d_a|+|d_b|+|d_c|\ge|d_a+d_b+d_c|=|D|; $$ so the minimized quantity can't possibly be smaller than $|D|$. Clearly this optimal value can be achieved by setting $d_a=d_b=d_c=D/3$, and this is one pleasantly symmetric solution. (For instance, it also minimizes $(x-a)^2+(y-b)^2+(z-c)^2$.) In terms of the original variables, you would want $$ x=d+\frac{2}{3}a-\frac{1}{3}b-\frac{1}{3}c, \\ y=d-\frac{1}{3}a+\frac{2}{3}b-\frac{1}{3}c, \\ z=d-\frac{1}{3}a-\frac{1}{3}b+\frac{2}{3}c. $$ But in fact the optimal value is achieved whenever $d_a$, $d_b$, and $d_c$ have the same sign as $D$ and sum to $D$. As OP describes, this solution space is geometrically an equilateral triangle, with vertices where $(d_a,d_b,d_c)$ is equal to $(D,0,0)$, $(0,D,0)$, and $(0,0,D)$. In terms of the original values, those vertices are at $$(x,y,z)_1=(3d-b-c,b,c), \\(x,y,z)_2=(a,3d-a-c,c),\\(x,y,z)_3=(a,b,3d-a-b).$$