Mixing
How to optimize three numbers such that their sum is always equal?
$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.
optimization convex-optimization
asked Jan 20 at 15:02
JanekmuricJanekmuric
92211
$endgroup$
add a comment |
$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.
optimization convex-optimization
asked Jan 20 at 15:02
JanekmuricJanekmuric
92211
$endgroup$
add a comment |
$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.
optimization convex-optimization
asked Jan 20 at 15:02
JanekmuricJanekmuric
92211
$endgroup$
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.
optimization convex-optimization
optimization convex-optimization
asked Jan 20 at 15:02
JanekmuricJanekmuric
92211
asked Jan 20 at 15:02
JanekmuricJanekmuric
92211
asked Jan 20 at 15:02
JanekmuricJanekmuric
92211
asked Jan 20 at 15:02
JanekmuricJanekmuric
92211
asked Jan 20 at 15:02
JanekmuricJanekmuric
92211
92211
add a comment |
add a comment |
5 Answers
5
active
oldest
votes
$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-cequiv 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).$$
answered Jan 24 at 13:59
mjqxxxxmjqxxxx
31.6k24086
$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$
– Janekmuric
Jan 27 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 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$
– Janekmuric
Jan 28 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 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$
– Janekmuric
Jan 29 at 10:14
|
show 1 more comment
$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_zge 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|$.
answered Jan 24 at 1:00
cspruncsprun
1,93329
$endgroup$
add a comment |
$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
answered Jan 20 at 16:29
independentvariableindependentvariable
16011
$endgroup$
$begingroup$
Could you please elaborate on how to solve the linear problem?
$endgroup$
– Janekmuric
Jan 20 at 17:10
$begingroup$
Check the updated answer
$endgroup$
– independentvariable
Jan 24 at 0:14
add a comment |
$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.
answered Jan 25 at 14:43
CesareoCesareo
9,2013517
$endgroup$
add a comment |
$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=minleft(dfrac{x-a}s,dfrac{y-b}s,dfrac{z-c}sright)\
v=mathrm{med}left(dfrac{x-a}s,dfrac{y-b}s,dfrac{z-c}sright)\
w=maxleft(dfrac{x-a}s,dfrac{y-b}s,dfrac{z-c}sright),tag2
end{cases}
then
$$u+v+w = 1,quad ule vle w.tag3$$
Let us minimize the function
$$f(u,v)=|u|+|v|+1-u-vtag4$$
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 ule vle 0le 1-u-v,$$
$$min f(u,v)= 1quadtext{at}quad {u,v}={0,0}$$
$underline{text{Case }mathrm{u le 0le vle 1-u-v}}.$
$$f(u,v) = 1-2u,quad ule 0le 2vle 1-u,$$
$$min f(u,v)= 1quadtext{at}quad u=0,quad vinleft[0,frac12right].$$
$underline{text{Case }mathrm{0le u le vle 1-u-v}}.$
$$min f(u,v) = 1 quadtext{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|quadtext{at}\
{small left[begin{align}
&left(dfrac{x-a}sinleft[0,dfrac13right]right)wedgeleft(dfrac{y-b}sinleft[0,dfrac12left(1-dfrac{x-a}sright)right]right)wedgeleft(dfrac{z-c}sinleft[0,1-dfrac{x-a}s-dfrac{y-b}sright]right)\
&left(dfrac{x-a}sinleft[0,dfrac13right]right)wedgeleft(dfrac{z-c}sinleft[0,dfrac12left(1-dfrac{x-a}sright)right]right)wedgeleft(dfrac{y-b}sinleft[0,1-dfrac{x-a}s-dfrac{z-c}sright]right)\
&left(dfrac{y-b}sinleft[0,dfrac13right]right)wedgeleft(dfrac{x-a}sinleft[0,dfrac12left(1-dfrac{y-b}sright)right]right)wedgeleft(dfrac{z-c}sinleft[0,1-dfrac{x-a}s-dfrac{y-b}sright]right)\
&left(dfrac{y-b}sinleft[0,dfrac13right]right)wedgeleft(dfrac{z-c}sinleft[0,dfrac12left(1-dfrac{y-b}sright)right]right)wedgeleft(dfrac{x-a}sinleft[0,1-dfrac{z-c}s-dfrac{y-b}sright]right)\
&left(dfrac{z-c}sinleft[0,dfrac13right]right)wedgeleft(dfrac{y-b}sinleft[0,dfrac12left(1-dfrac{z-c}sright)right]right)wedgeleft(dfrac{x-a}sinleft[0,1-dfrac{z-c}s-dfrac{y-b}sright]right)\
&left(dfrac{z-c}sinleft[0,dfrac13right]right)wedgeleft(dfrac{x-a}sinleft[0,dfrac12left(1-dfrac{z-c}sright)right]right)wedgeleft(dfrac{y-b}sinleft[0,1-dfrac{z-c}s-dfrac{x-a}sright]right)\
end{align}right.}}}$$
answered Jan 24 at 20:45
Yuri NegometyanovYuri Negometyanov
11.8k1729
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3080686%2fhow-to-optimize-three-numbers-such-that-their-sum-is-always-equal%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
5 Answers
5
active
oldest
votes
5 Answers
5
active
oldest
votes
active
oldest
votes
active
oldest
votes
$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-cequiv 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).$$
answered Jan 24 at 13:59
mjqxxxxmjqxxxx
31.6k24086
$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$
– Janekmuric
Jan 27 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 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$
– Janekmuric
Jan 28 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 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$
– Janekmuric
Jan 29 at 10:14
|
show 1 more comment
$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-cequiv 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).$$
answered Jan 24 at 13:59
mjqxxxxmjqxxxx
31.6k24086
$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$
– Janekmuric
Jan 27 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 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$
– Janekmuric
Jan 28 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 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$
– Janekmuric
Jan 29 at 10:14
|
show 1 more comment
$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-cequiv 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).$$
answered Jan 24 at 13:59
mjqxxxxmjqxxxx
31.6k24086
$endgroup$
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-cequiv 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).$$
answered Jan 24 at 13:59
mjqxxxxmjqxxxx
31.6k24086
answered Jan 24 at 13:59
mjqxxxxmjqxxxx
31.6k24086
answered Jan 24 at 13:59
mjqxxxxmjqxxxx
31.6k24086
answered Jan 24 at 13:59
mjqxxxxmjqxxxx
31.6k24086
31.6k24086
$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$
– Janekmuric
Jan 27 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 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$
– Janekmuric
Jan 28 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 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$
– Janekmuric
Jan 29 at 10:14
|
show 1 more comment
$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$
– Janekmuric
Jan 27 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 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$
– Janekmuric
Jan 28 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 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$
– Janekmuric
Jan 29 at 10:14
$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$
– Janekmuric
Jan 27 at 12:36
$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$
– Janekmuric
Jan 27 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 at 19:20
$begingroup$
Can you give a specific example where it's not right, and say where you see the vertices?
$endgroup$
– mjqxxxx
Jan 27 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$
– Janekmuric
Jan 28 at 20:32
$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$
– Janekmuric
Jan 28 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 at 6:12
$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 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$
– Janekmuric
Jan 29 at 10:14
$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$
– Janekmuric
Jan 29 at 10:14
|
show 1 more comment
$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_zge 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|$.
answered Jan 24 at 1:00
cspruncsprun
1,93329
$endgroup$
add a comment |
$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_zge 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|$.
answered Jan 24 at 1:00
cspruncsprun
1,93329
$endgroup$
add a comment |
$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_zge 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|$.
answered Jan 24 at 1:00
cspruncsprun
1,93329
$endgroup$
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_zge 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|$.
answered Jan 24 at 1:00
cspruncsprun
1,93329
edited Jan 25 at 14:24
answered Jan 24 at 1:00
cspruncsprun
1,93329
answered Jan 24 at 1:00
cspruncsprun
1,93329
answered Jan 24 at 1:00
cspruncsprun
1,93329
1,93329
add a comment |
add a comment |
$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
answered Jan 20 at 16:29
independentvariableindependentvariable
16011
$endgroup$
$begingroup$
Could you please elaborate on how to solve the linear problem?
$endgroup$
– Janekmuric
Jan 20 at 17:10
$begingroup$
Check the updated answer
$endgroup$
– independentvariable
Jan 24 at 0:14
add a comment |
$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
answered Jan 20 at 16:29
independentvariableindependentvariable
16011
$endgroup$
$begingroup$
Could you please elaborate on how to solve the linear problem?
$endgroup$
– Janekmuric
Jan 20 at 17:10
$begingroup$
Check the updated answer
$endgroup$
– independentvariable
Jan 24 at 0:14
add a comment |
$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
answered Jan 20 at 16:29
independentvariableindependentvariable
16011
$endgroup$
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
answered Jan 20 at 16:29
independentvariableindependentvariable
16011
edited Jan 24 at 0:13
answered Jan 20 at 16:29
independentvariableindependentvariable
16011
answered Jan 20 at 16:29
independentvariableindependentvariable
16011
answered Jan 20 at 16:29
independentvariableindependentvariable
16011
16011
$begingroup$
Could you please elaborate on how to solve the linear problem?
$endgroup$
– Janekmuric
Jan 20 at 17:10
$begingroup$
Check the updated answer
$endgroup$
– independentvariable
Jan 24 at 0:14
add a comment |
$begingroup$
Could you please elaborate on how to solve the linear problem?
$endgroup$
– Janekmuric
Jan 20 at 17:10
$begingroup$
Check the updated answer
$endgroup$
– independentvariable
Jan 24 at 0:14
$begingroup$
Could you please elaborate on how to solve the linear problem?
$endgroup$
– Janekmuric
Jan 20 at 17:10
$begingroup$
Could you please elaborate on how to solve the linear problem?
$endgroup$
– Janekmuric
Jan 20 at 17:10
$begingroup$
Check the updated answer
$endgroup$
– independentvariable
Jan 24 at 0:14
$begingroup$
Check the updated answer
$endgroup$
– independentvariable
Jan 24 at 0:14
add a comment |
$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.
answered Jan 25 at 14:43
CesareoCesareo
9,2013517
$endgroup$
add a comment |
$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.
answered Jan 25 at 14:43
CesareoCesareo
9,2013517
$endgroup$
add a comment |
$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.
answered Jan 25 at 14:43
CesareoCesareo
9,2013517
$endgroup$
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.
answered Jan 25 at 14:43
CesareoCesareo
9,2013517
edited Jan 27 at 14:45
answered Jan 25 at 14:43
CesareoCesareo
9,2013517
answered Jan 25 at 14:43
CesareoCesareo
9,2013517
answered Jan 25 at 14:43
CesareoCesareo
9,2013517
9,2013517
add a comment |
add a comment |
$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=minleft(dfrac{x-a}s,dfrac{y-b}s,dfrac{z-c}sright)\
v=mathrm{med}left(dfrac{x-a}s,dfrac{y-b}s,dfrac{z-c}sright)\
w=maxleft(dfrac{x-a}s,dfrac{y-b}s,dfrac{z-c}sright),tag2
end{cases}
then
$$u+v+w = 1,quad ule vle w.tag3$$
Let us minimize the function
$$f(u,v)=|u|+|v|+1-u-vtag4$$
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 ule vle 0le 1-u-v,$$
$$min f(u,v)= 1quadtext{at}quad {u,v}={0,0}$$
$underline{text{Case }mathrm{u le 0le vle 1-u-v}}.$
$$f(u,v) = 1-2u,quad ule 0le 2vle 1-u,$$
$$min f(u,v)= 1quadtext{at}quad u=0,quad vinleft[0,frac12right].$$
$underline{text{Case }mathrm{0le u le vle 1-u-v}}.$
$$min f(u,v) = 1 quadtext{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|quadtext{at}\
{small left[begin{align}
&left(dfrac{x-a}sinleft[0,dfrac13right]right)wedgeleft(dfrac{y-b}sinleft[0,dfrac12left(1-dfrac{x-a}sright)right]right)wedgeleft(dfrac{z-c}sinleft[0,1-dfrac{x-a}s-dfrac{y-b}sright]right)\
&left(dfrac{x-a}sinleft[0,dfrac13right]right)wedgeleft(dfrac{z-c}sinleft[0,dfrac12left(1-dfrac{x-a}sright)right]right)wedgeleft(dfrac{y-b}sinleft[0,1-dfrac{x-a}s-dfrac{z-c}sright]right)\
&left(dfrac{y-b}sinleft[0,dfrac13right]right)wedgeleft(dfrac{x-a}sinleft[0,dfrac12left(1-dfrac{y-b}sright)right]right)wedgeleft(dfrac{z-c}sinleft[0,1-dfrac{x-a}s-dfrac{y-b}sright]right)\
&left(dfrac{y-b}sinleft[0,dfrac13right]right)wedgeleft(dfrac{z-c}sinleft[0,dfrac12left(1-dfrac{y-b}sright)right]right)wedgeleft(dfrac{x-a}sinleft[0,1-dfrac{z-c}s-dfrac{y-b}sright]right)\
&left(dfrac{z-c}sinleft[0,dfrac13right]right)wedgeleft(dfrac{y-b}sinleft[0,dfrac12left(1-dfrac{z-c}sright)right]right)wedgeleft(dfrac{x-a}sinleft[0,1-dfrac{z-c}s-dfrac{y-b}sright]right)\
&left(dfrac{z-c}sinleft[0,dfrac13right]right)wedgeleft(dfrac{x-a}sinleft[0,dfrac12left(1-dfrac{z-c}sright)right]right)wedgeleft(dfrac{y-b}sinleft[0,1-dfrac{z-c}s-dfrac{x-a}sright]right)\
end{align}right.}}}$$
answered Jan 24 at 20:45
Yuri NegometyanovYuri Negometyanov
11.8k1729
$endgroup$
add a comment |
$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=minleft(dfrac{x-a}s,dfrac{y-b}s,dfrac{z-c}sright)\
v=mathrm{med}left(dfrac{x-a}s,dfrac{y-b}s,dfrac{z-c}sright)\
w=maxleft(dfrac{x-a}s,dfrac{y-b}s,dfrac{z-c}sright),tag2
end{cases}
then
$$u+v+w = 1,quad ule vle w.tag3$$
Let us minimize the function
$$f(u,v)=|u|+|v|+1-u-vtag4$$
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 ule vle 0le 1-u-v,$$
$$min f(u,v)= 1quadtext{at}quad {u,v}={0,0}$$
$underline{text{Case }mathrm{u le 0le vle 1-u-v}}.$
$$f(u,v) = 1-2u,quad ule 0le 2vle 1-u,$$
$$min f(u,v)= 1quadtext{at}quad u=0,quad vinleft[0,frac12right].$$
$underline{text{Case }mathrm{0le u le vle 1-u-v}}.$
$$min f(u,v) = 1 quadtext{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|quadtext{at}\
{small left[begin{align}
&left(dfrac{x-a}sinleft[0,dfrac13right]right)wedgeleft(dfrac{y-b}sinleft[0,dfrac12left(1-dfrac{x-a}sright)right]right)wedgeleft(dfrac{z-c}sinleft[0,1-dfrac{x-a}s-dfrac{y-b}sright]right)\
&left(dfrac{x-a}sinleft[0,dfrac13right]right)wedgeleft(dfrac{z-c}sinleft[0,dfrac12left(1-dfrac{x-a}sright)right]right)wedgeleft(dfrac{y-b}sinleft[0,1-dfrac{x-a}s-dfrac{z-c}sright]right)\
&left(dfrac{y-b}sinleft[0,dfrac13right]right)wedgeleft(dfrac{x-a}sinleft[0,dfrac12left(1-dfrac{y-b}sright)right]right)wedgeleft(dfrac{z-c}sinleft[0,1-dfrac{x-a}s-dfrac{y-b}sright]right)\
&left(dfrac{y-b}sinleft[0,dfrac13right]right)wedgeleft(dfrac{z-c}sinleft[0,dfrac12left(1-dfrac{y-b}sright)right]right)wedgeleft(dfrac{x-a}sinleft[0,1-dfrac{z-c}s-dfrac{y-b}sright]right)\
&left(dfrac{z-c}sinleft[0,dfrac13right]right)wedgeleft(dfrac{y-b}sinleft[0,dfrac12left(1-dfrac{z-c}sright)right]right)wedgeleft(dfrac{x-a}sinleft[0,1-dfrac{z-c}s-dfrac{y-b}sright]right)\
&left(dfrac{z-c}sinleft[0,dfrac13right]right)wedgeleft(dfrac{x-a}sinleft[0,dfrac12left(1-dfrac{z-c}sright)right]right)wedgeleft(dfrac{y-b}sinleft[0,1-dfrac{z-c}s-dfrac{x-a}sright]right)\
end{align}right.}}}$$
answered Jan 24 at 20:45
Yuri NegometyanovYuri Negometyanov
11.8k1729
$endgroup$
add a comment |
$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=minleft(dfrac{x-a}s,dfrac{y-b}s,dfrac{z-c}sright)\
v=mathrm{med}left(dfrac{x-a}s,dfrac{y-b}s,dfrac{z-c}sright)\
w=maxleft(dfrac{x-a}s,dfrac{y-b}s,dfrac{z-c}sright),tag2
end{cases}
then
$$u+v+w = 1,quad ule vle w.tag3$$
Let us minimize the function
$$f(u,v)=|u|+|v|+1-u-vtag4$$
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 ule vle 0le 1-u-v,$$
$$min f(u,v)= 1quadtext{at}quad {u,v}={0,0}$$
$underline{text{Case }mathrm{u le 0le vle 1-u-v}}.$
$$f(u,v) = 1-2u,quad ule 0le 2vle 1-u,$$
$$min f(u,v)= 1quadtext{at}quad u=0,quad vinleft[0,frac12right].$$
$underline{text{Case }mathrm{0le u le vle 1-u-v}}.$
$$min f(u,v) = 1 quadtext{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|quadtext{at}\
{small left[begin{align}
&left(dfrac{x-a}sinleft[0,dfrac13right]right)wedgeleft(dfrac{y-b}sinleft[0,dfrac12left(1-dfrac{x-a}sright)right]right)wedgeleft(dfrac{z-c}sinleft[0,1-dfrac{x-a}s-dfrac{y-b}sright]right)\
&left(dfrac{x-a}sinleft[0,dfrac13right]right)wedgeleft(dfrac{z-c}sinleft[0,dfrac12left(1-dfrac{x-a}sright)right]right)wedgeleft(dfrac{y-b}sinleft[0,1-dfrac{x-a}s-dfrac{z-c}sright]right)\
&left(dfrac{y-b}sinleft[0,dfrac13right]right)wedgeleft(dfrac{x-a}sinleft[0,dfrac12left(1-dfrac{y-b}sright)right]right)wedgeleft(dfrac{z-c}sinleft[0,1-dfrac{x-a}s-dfrac{y-b}sright]right)\
&left(dfrac{y-b}sinleft[0,dfrac13right]right)wedgeleft(dfrac{z-c}sinleft[0,dfrac12left(1-dfrac{y-b}sright)right]right)wedgeleft(dfrac{x-a}sinleft[0,1-dfrac{z-c}s-dfrac{y-b}sright]right)\
&left(dfrac{z-c}sinleft[0,dfrac13right]right)wedgeleft(dfrac{y-b}sinleft[0,dfrac12left(1-dfrac{z-c}sright)right]right)wedgeleft(dfrac{x-a}sinleft[0,1-dfrac{z-c}s-dfrac{y-b}sright]right)\
&left(dfrac{z-c}sinleft[0,dfrac13right]right)wedgeleft(dfrac{x-a}sinleft[0,dfrac12left(1-dfrac{z-c}sright)right]right)wedgeleft(dfrac{y-b}sinleft[0,1-dfrac{z-c}s-dfrac{x-a}sright]right)\
end{align}right.}}}$$
answered Jan 24 at 20:45
Yuri NegometyanovYuri Negometyanov
11.8k1729
$endgroup$
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=minleft(dfrac{x-a}s,dfrac{y-b}s,dfrac{z-c}sright)\
v=mathrm{med}left(dfrac{x-a}s,dfrac{y-b}s,dfrac{z-c}sright)\
w=maxleft(dfrac{x-a}s,dfrac{y-b}s,dfrac{z-c}sright),tag2
end{cases}
then
$$u+v+w = 1,quad ule vle w.tag3$$
Let us minimize the function
$$f(u,v)=|u|+|v|+1-u-vtag4$$
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 ule vle 0le 1-u-v,$$
$$min f(u,v)= 1quadtext{at}quad {u,v}={0,0}$$
$underline{text{Case }mathrm{u le 0le vle 1-u-v}}.$
$$f(u,v) = 1-2u,quad ule 0le 2vle 1-u,$$
$$min f(u,v)= 1quadtext{at}quad u=0,quad vinleft[0,frac12right].$$
$underline{text{Case }mathrm{0le u le vle 1-u-v}}.$
$$min f(u,v) = 1 quadtext{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|quadtext{at}\
{small left[begin{align}
&left(dfrac{x-a}sinleft[0,dfrac13right]right)wedgeleft(dfrac{y-b}sinleft[0,dfrac12left(1-dfrac{x-a}sright)right]right)wedgeleft(dfrac{z-c}sinleft[0,1-dfrac{x-a}s-dfrac{y-b}sright]right)\
&left(dfrac{x-a}sinleft[0,dfrac13right]right)wedgeleft(dfrac{z-c}sinleft[0,dfrac12left(1-dfrac{x-a}sright)right]right)wedgeleft(dfrac{y-b}sinleft[0,1-dfrac{x-a}s-dfrac{z-c}sright]right)\
&left(dfrac{y-b}sinleft[0,dfrac13right]right)wedgeleft(dfrac{x-a}sinleft[0,dfrac12left(1-dfrac{y-b}sright)right]right)wedgeleft(dfrac{z-c}sinleft[0,1-dfrac{x-a}s-dfrac{y-b}sright]right)\
&left(dfrac{y-b}sinleft[0,dfrac13right]right)wedgeleft(dfrac{z-c}sinleft[0,dfrac12left(1-dfrac{y-b}sright)right]right)wedgeleft(dfrac{x-a}sinleft[0,1-dfrac{z-c}s-dfrac{y-b}sright]right)\
&left(dfrac{z-c}sinleft[0,dfrac13right]right)wedgeleft(dfrac{y-b}sinleft[0,dfrac12left(1-dfrac{z-c}sright)right]right)wedgeleft(dfrac{x-a}sinleft[0,1-dfrac{z-c}s-dfrac{y-b}sright]right)\
&left(dfrac{z-c}sinleft[0,dfrac13right]right)wedgeleft(dfrac{x-a}sinleft[0,dfrac12left(1-dfrac{z-c}sright)right]right)wedgeleft(dfrac{y-b}sinleft[0,1-dfrac{z-c}s-dfrac{x-a}sright]right)\
end{align}right.}}}$$
answered Jan 24 at 20:45
Yuri NegometyanovYuri Negometyanov
11.8k1729
edited Jan 24 at 20:54
answered Jan 24 at 20:45
Yuri NegometyanovYuri Negometyanov
11.8k1729
answered Jan 24 at 20:45
Yuri NegometyanovYuri Negometyanov
11.8k1729
answered Jan 24 at 20:45
Yuri NegometyanovYuri Negometyanov
11.8k1729
11.8k1729
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3080686%2fhow-to-optimize-three-numbers-such-that-their-sum-is-always-equal%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
