3
$\begingroup$

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.

$\endgroup$

5 Answers 5

4
$\begingroup$

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|$.

$\endgroup$
0
3
+150
$\begingroup$

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).$$

$\endgroup$
6
  • $\begingroup$ I accepted your answer as the "pleasantly symmetric" solution is good enough for what I need, but the three points of the triangle you have given are not the points that form the triangle with minimum values. Please fix that or remove it from your answer. $\endgroup$
    – jan
    Jan 27, 2019 at 12:36
  • $\begingroup$ Can you give a specific example where it's not right, and say where you see the vertices? $\endgroup$
    – mjqxxxx
    Jan 27, 2019 at 19:20
  • $\begingroup$ I've plotted the function and your triangle in geogebra and they are completely off. If you need numbers I can find some tomorrow. $\endgroup$
    – jan
    Jan 28, 2019 at 20:32
  • $\begingroup$ Sure, sounds good. When I set $a=1$ and $b=2$ and $c=3$, for instance, and fix $z=3-x-y$ (that is, $d=1$), I expect the corners to be at $(x,y)_1=(-2,2)$ and $(x,y)_2=(1,-1)$ and $(x,y)_3=(1,2)$. And in WolframAlpha, "minimize $|1-x|+|2-y|+|3-(3-x-y)|$" shows the corners exactly there. So I'd be interested to see a counterexample. $\endgroup$
    – mjqxxxx
    Jan 29, 2019 at 6:12
  • $\begingroup$ Okay. So I checked your example and two of the points are correct, but (1,2) is not (and the two points being correct is a coincidence, they usually aren't) . Your formula gives the z-axis for that point 3d-a-b = 3-2-1 = 0, but the correct z-coordinate is of course the just the function output, so that would be |1-1| + |2-2|+ |3-(3-1-2)| = 3. imgur.com/wtpUPLe That's the graph given some random values and it's completely off. Try setting d to something like 5, you'll see it just gets worse and worse. $\endgroup$
    – jan
    Jan 29, 2019 at 10:14
2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Could you please elaborate on how to solve the linear problem? $\endgroup$
    – jan
    Jan 20, 2019 at 17:10
  • $\begingroup$ Check the updated answer $\endgroup$ Jan 24, 2019 at 0:14
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.}}}$$

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .