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

| cite | improve this answer | |
$\endgroup$
  • $\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$ – Ciprum Jan 27 '19 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 '19 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$ – Ciprum Jan 28 '19 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 '19 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$ – Ciprum Jan 29 '19 at 10:14
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|$.

| cite | improve this answer | |
$\endgroup$
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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Could you please elaborate on how to solve the linear problem? $\endgroup$ – Ciprum Jan 20 '19 at 17:10
  • $\begingroup$ Check the updated answer $\endgroup$ – independentvariable Jan 24 '19 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.

| cite | improve this answer | |
$\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.}}}$$

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.