How to find out the global minimum of the following expression











up vote
12
down vote

favorite
2













$|x-1|+ |x-2|+|x-5|+|x-6|+|x-8|+|x-9|+|x- 10|+ |x-11|+|x-12|+|x-17|+|x-24|+|x-31|+ |x-32|$




i've solved questions of this sort before but there were only 3 terms i solved that by opening all the terms in the modulus and drawing a graph.This question came in a paper which requires the student to solve it within 5 minutes. What's a better method?










share|cite|improve this question









New contributor




CaptainQuestion is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.




















  • No, i checked again
    – CaptainQuestion
    Nov 25 at 16:07






  • 4




    Is the last minus sign a typo or not?
    – Alex Vong
    Nov 25 at 22:16






  • 1




    If these are all additions, then the minimising $x$ will be the median of the numbers, which is $10$. If the final part of the calculation really is a subtraction, then the minimising $x$ will be the median of all but the final two numbers, which would be $9$
    – Henry
    Nov 25 at 23:11












  • Yes the last minus is a typo sorry
    – CaptainQuestion
    2 days ago















up vote
12
down vote

favorite
2













$|x-1|+ |x-2|+|x-5|+|x-6|+|x-8|+|x-9|+|x- 10|+ |x-11|+|x-12|+|x-17|+|x-24|+|x-31|+ |x-32|$




i've solved questions of this sort before but there were only 3 terms i solved that by opening all the terms in the modulus and drawing a graph.This question came in a paper which requires the student to solve it within 5 minutes. What's a better method?










share|cite|improve this question









New contributor




CaptainQuestion is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.




















  • No, i checked again
    – CaptainQuestion
    Nov 25 at 16:07






  • 4




    Is the last minus sign a typo or not?
    – Alex Vong
    Nov 25 at 22:16






  • 1




    If these are all additions, then the minimising $x$ will be the median of the numbers, which is $10$. If the final part of the calculation really is a subtraction, then the minimising $x$ will be the median of all but the final two numbers, which would be $9$
    – Henry
    Nov 25 at 23:11












  • Yes the last minus is a typo sorry
    – CaptainQuestion
    2 days ago













up vote
12
down vote

favorite
2









up vote
12
down vote

favorite
2






2






$|x-1|+ |x-2|+|x-5|+|x-6|+|x-8|+|x-9|+|x- 10|+ |x-11|+|x-12|+|x-17|+|x-24|+|x-31|+ |x-32|$




i've solved questions of this sort before but there were only 3 terms i solved that by opening all the terms in the modulus and drawing a graph.This question came in a paper which requires the student to solve it within 5 minutes. What's a better method?










share|cite|improve this question









New contributor




CaptainQuestion is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.












$|x-1|+ |x-2|+|x-5|+|x-6|+|x-8|+|x-9|+|x- 10|+ |x-11|+|x-12|+|x-17|+|x-24|+|x-31|+ |x-32|$




i've solved questions of this sort before but there were only 3 terms i solved that by opening all the terms in the modulus and drawing a graph.This question came in a paper which requires the student to solve it within 5 minutes. What's a better method?







calculus






share|cite|improve this question









New contributor




CaptainQuestion is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.











share|cite|improve this question









New contributor




CaptainQuestion is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.









share|cite|improve this question




share|cite|improve this question








edited 2 days ago





















New contributor




CaptainQuestion is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.









asked Nov 25 at 15:57









CaptainQuestion

905




905




New contributor




CaptainQuestion is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.





New contributor





CaptainQuestion is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.






CaptainQuestion is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.












  • No, i checked again
    – CaptainQuestion
    Nov 25 at 16:07






  • 4




    Is the last minus sign a typo or not?
    – Alex Vong
    Nov 25 at 22:16






  • 1




    If these are all additions, then the minimising $x$ will be the median of the numbers, which is $10$. If the final part of the calculation really is a subtraction, then the minimising $x$ will be the median of all but the final two numbers, which would be $9$
    – Henry
    Nov 25 at 23:11












  • Yes the last minus is a typo sorry
    – CaptainQuestion
    2 days ago


















  • No, i checked again
    – CaptainQuestion
    Nov 25 at 16:07






  • 4




    Is the last minus sign a typo or not?
    – Alex Vong
    Nov 25 at 22:16






  • 1




    If these are all additions, then the minimising $x$ will be the median of the numbers, which is $10$. If the final part of the calculation really is a subtraction, then the minimising $x$ will be the median of all but the final two numbers, which would be $9$
    – Henry
    Nov 25 at 23:11












  • Yes the last minus is a typo sorry
    – CaptainQuestion
    2 days ago
















No, i checked again
– CaptainQuestion
Nov 25 at 16:07




No, i checked again
– CaptainQuestion
Nov 25 at 16:07




4




4




Is the last minus sign a typo or not?
– Alex Vong
Nov 25 at 22:16




Is the last minus sign a typo or not?
– Alex Vong
Nov 25 at 22:16




1




1




If these are all additions, then the minimising $x$ will be the median of the numbers, which is $10$. If the final part of the calculation really is a subtraction, then the minimising $x$ will be the median of all but the final two numbers, which would be $9$
– Henry
Nov 25 at 23:11






If these are all additions, then the minimising $x$ will be the median of the numbers, which is $10$. If the final part of the calculation really is a subtraction, then the minimising $x$ will be the median of all but the final two numbers, which would be $9$
– Henry
Nov 25 at 23:11














Yes the last minus is a typo sorry
– CaptainQuestion
2 days ago




Yes the last minus is a typo sorry
– CaptainQuestion
2 days ago










4 Answers
4






active

oldest

votes

















up vote
9
down vote



accepted










Unfortunately I needed some minutes to think about the problem before finding a solution that can be calculated very quickly:



Imagine the graph of the function $f_a(x)=|x-a|$. Having the graph in mind you see that the derivation $f'(x)=-1$ for $x<a$ and $f'(x)=1$ for $x>a$.



For the intervals: $(-infty,1)$, $(1,2)$, $(2,5)$, ..., $(32,infty)$ we can now easily calculate the derivative $f'(x)=f'_1(x)+f'_2(x)+f'_5(x)+...-f'_{32}(x)$:



In the range $(-infty,1)$ it is $f'(x)=-1-1-1-...-1+1=-11$.

In the range $(1,2)$ it is $f'(x)=+1-1-1-...-1+1=-9$.

In the range $(2,5)$ it is $f'(x)=+1+1+1-...-1+1=-7$.

...



In every step we simply have to invert one sign so "-1" becomes "+1". This means the derivative is changing by 2 at the points x=1,2,5,...



We start by calculating the derivative for $x<1$; it is -11.



Now we simply go through the ranges:



<1: -11

1..2: -9

2..5: -7

5..6: -5

6..8: -3

8..9: -1

9..10: +1

10..11: +3

11..12: +5

12..17: +7

17..24: +9

24..31: +11

31..32: +13

>32: +11



At $x=32$ the derivation decreases by 2 because of the minus sign before $|x-32|$; you could of course adapt this method for sums of elements of the form $b|x-a|$.



We see that for $x<9$ the derivation is negative and for $x>9$ the derivation is positive. We also know that the function is continuous. (This is important because the derivation is not defined at x=1,2,5,...) This means that the function is strictly decreasing respectively increasing for $x<9$ and for $x>9$.



So we know that the global minimum must be at $x=9$.






share|cite|improve this answer

















  • 1




    The right answer. Congratulations! Although I don't know if your method works when the number of terms is even, say $f(x) = |x-1|+ |x-2|$ or $f(x) = |x-11|+|x-12|+|x-17|+|x-24|$ (the minimum or maximum is an interval).
    – David
    Nov 25 at 22:20










  • @David Why should it be a problem if a whole interval represents the minimum or maximum? In the example of $|x-1|+|x-2|$ we would have $f'(x)=0$ in the whole interval 1...2.
    – Martin Rosenau
    Nov 26 at 6:28










  • This answers the previous version of my typo question but the method is absolutely wonderful. Thanks!
    – CaptainQuestion
    2 days ago


















up vote
13
down vote













You can in principle write out the function in a lot of intervals. But it would probably take too long. However, I will use this fact, without doing it explicitly. We know that if we do write this function, it is going to be linear on each interval (sum of linear functions is a linear function), and it's going to be continuous (sum of continuous functions is a continuous function). We also know that on a line you get minimum at one end, the other, or both (constant line). So all you need to do is to calculate your function at $1,2,5,6,...$ and find the minimum.






share|cite|improve this answer



















  • 1




    I like how this answer asks us to imagine the graph of the function. I find this "imagine" technique useful, while still being intuitive. Similar examples includes "imagine the multiplication table of this finite group" (the group could be huge) or "imagine the truth table for this proposition" (the formula could be long).
    – Alex Vong
    Nov 25 at 22:02








  • 1




    Perhaps the justification "when each absolute value changes, each of them is continuous" could be changed to "the sum of continuous functions is continuous".
    – Alex Vong
    Nov 25 at 22:23












  • @AlexVong That's probably better
    – Andrei
    Nov 25 at 22:29


















up vote
5
down vote













The answer (minimizer) in this case is $10$, the median of the sequence $$(1,2,5,6,8,9,10,11,12,17,24,31,32).$$



You can plug in $x=10$ in the function and you would find that the minimum value is $96$. In general, the solution to the following minimization problem



$$min{|x-a_1| + |x-a_2| + cdots + |x-a_n|}$$
is the median of $(a_1,ldots,a_n)$. To see why, consider first when $n=2$, and without loss of generality assume $a_1<a_2$. Then $|x-a_1|+|x-a_2|$ is the distance between $x$ and $a_1$ plus the distance between $x$ and $a_2$. It is easy to see that only when $x$ is in the middle of $a_1$ and $a_2$ should the sum of distances be minimal, which equals $|a_2-a_1|$ in this case. In this case the minimizer is not unique. Any points in $[a_1,a_2]$ is a minimizer.



When $n=3$, the function is $|x-a_1|+|x-a_2|+|x-a_3|$, and we order the parameters again so that $a_1<a_2<a_3$. When $x$ coincides with $a_2$, i.e. $x=a_2$, the value becomes $|a_2-a_1|+|a_2-a_3|=|a_3-a_1|$, the distance between $a_3$ and $a_1$. But when $xin[a_1,a_3], xneq a_2$, the value of the function is
$$|x-a_2|+|x-a_1|+|x-a_3| = |a_3-a_1| + |x-a_2|,$$
which is largar than $|a_3-a_1|$, the distance between $a_3$ and $a_1$. Similarly the value would become larger when $x$ is outside $[a_1,a_3]$. So in this case, the minimizer is unique and is equal to $a_2$, the median of $(a_1,a_2,a_3)$.



In general, when $n$ is odd, there exists a unique minimizer, which is equal to the (unique) median of the parameters $(a_1,ldots,a_n)$. When $n$ is even, the function is minimal and constant over the range $[a_i,a_j]$, where $a_i$ and $a_j$ are the two middle values.






share|cite|improve this answer

















  • 1




    That doesn't seem to be correct. Wolfram says the minimum is 51 at x=9. See here
    – I like Serena
    Nov 25 at 20:50








  • 3




    I see now that the confusion comes from the $−|x−32|$ in the problem statement @MartinRosenau. Note the minus sign. Fei Li solved it for a + sign.
    – I like Serena
    Nov 25 at 21:18






  • 1




    I plot the graph using wxmaxima and get the same result as @IlikeSerena. Note the minus sign at the end.
    – Alex Vong
    Nov 25 at 21:48








  • 1




    Maybe the OP @CaptainQuestion made a typo. We need his or her classification, but I think the purpose of this question is exactly what I have demonstrated.
    – Fei Li
    Nov 25 at 22:00






  • 1




    @AlexVong So I hoped, but the next sentence "which equals $|a_2-a_1|$ in this case." excludes this interpretation.
    – Servaes
    Nov 25 at 22:39


















up vote
1
down vote













TL;DR: Put the absolute values in ascending order, and look at the sum of the leading coefficients. One by one, change the signs in the sum from right to left. When the sum changes signs, you have passed a local extremum. When the sum equals zero, there is an extremum on an entire interval.





As an alternative to Andrei's excellent answer, or perhaps an extension, you could also look at the derivative. Clearly the function is continuous everywhere, and it is differentiable in all but finitely many points, call them $a_1,ldots,a_n$ in ascending order. Then we want to minimize
$$f(x)=sum_{k=1}^nc_k|x-a_k|=sum_{k=1}^n(-1)^{delta_{xleq a_k}}c_k(x-a_k),$$
where $delta$ denotes the Kronecker delta, in this case defined as
$$delta_{xleq a_k}:=left{begin{array}{ll}1&text{ if } xleq a_k\0&text{ otherwise}end{array}right..$$
This has derivative (for all $x$ apart from the $a_k$)
$$f'(x)=sum_{k=1}^n(-1)^{delta_{xleq a_k}}c_k.$$
The expression has a local minimum at $x$ if either $f'(x)=0$, or if $x=a_k$ for some $k$ and $f'(y)<0$ for $a_{k-1}<y<a_k$ and $f'(y)>0$ for $a_k<y<a_{k+1}$.



This is all rather formal; in practice this means you put the $c_k$ in ascending order, so here $n=13$ and $c_1=cdots=c_{12}=1$ and $c_{13}=-1$, and find all $m$ such that flipping the last $m$ signs in the sum
$$c_1+c_2+c_3+c_4+c_5+c_6+c_7+c_8+c_9+c_{10}+c_{11}+c_{12}+c_{13}$$
makes the sum change signs compared to changing the last $m-1$ signs. Here a quick look gives
$$c_1+c_2+c_3+c_4+c_5+c_6-c_7-c_8-c_9-c_{10}-c_{11}-c_{12}-c_{13}=1,$$
$$c_1+c_2+c_3+c_4+c_5-c_6-c_7-c_8-c_9-c_{10}-c_{11}-c_{12}-c_{13}=-1,$$
so $f$ has a local minimum at $a_6=9$, and it is not difficult to see that there is no other minimum.






share|cite|improve this answer























  • Anyone care to explain the downvote?
    – Servaes
    Nov 26 at 8:12











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',
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
});


}
});






CaptainQuestion is a new contributor. Be nice, and check out our Code of Conduct.










draft saved

draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3013010%2fhow-to-find-out-the-global-minimum-of-the-following-expression%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown

























4 Answers
4






active

oldest

votes








4 Answers
4






active

oldest

votes









active

oldest

votes






active

oldest

votes








up vote
9
down vote



accepted










Unfortunately I needed some minutes to think about the problem before finding a solution that can be calculated very quickly:



Imagine the graph of the function $f_a(x)=|x-a|$. Having the graph in mind you see that the derivation $f'(x)=-1$ for $x<a$ and $f'(x)=1$ for $x>a$.



For the intervals: $(-infty,1)$, $(1,2)$, $(2,5)$, ..., $(32,infty)$ we can now easily calculate the derivative $f'(x)=f'_1(x)+f'_2(x)+f'_5(x)+...-f'_{32}(x)$:



In the range $(-infty,1)$ it is $f'(x)=-1-1-1-...-1+1=-11$.

In the range $(1,2)$ it is $f'(x)=+1-1-1-...-1+1=-9$.

In the range $(2,5)$ it is $f'(x)=+1+1+1-...-1+1=-7$.

...



In every step we simply have to invert one sign so "-1" becomes "+1". This means the derivative is changing by 2 at the points x=1,2,5,...



We start by calculating the derivative for $x<1$; it is -11.



Now we simply go through the ranges:



<1: -11

1..2: -9

2..5: -7

5..6: -5

6..8: -3

8..9: -1

9..10: +1

10..11: +3

11..12: +5

12..17: +7

17..24: +9

24..31: +11

31..32: +13

>32: +11



At $x=32$ the derivation decreases by 2 because of the minus sign before $|x-32|$; you could of course adapt this method for sums of elements of the form $b|x-a|$.



We see that for $x<9$ the derivation is negative and for $x>9$ the derivation is positive. We also know that the function is continuous. (This is important because the derivation is not defined at x=1,2,5,...) This means that the function is strictly decreasing respectively increasing for $x<9$ and for $x>9$.



So we know that the global minimum must be at $x=9$.






share|cite|improve this answer

















  • 1




    The right answer. Congratulations! Although I don't know if your method works when the number of terms is even, say $f(x) = |x-1|+ |x-2|$ or $f(x) = |x-11|+|x-12|+|x-17|+|x-24|$ (the minimum or maximum is an interval).
    – David
    Nov 25 at 22:20










  • @David Why should it be a problem if a whole interval represents the minimum or maximum? In the example of $|x-1|+|x-2|$ we would have $f'(x)=0$ in the whole interval 1...2.
    – Martin Rosenau
    Nov 26 at 6:28










  • This answers the previous version of my typo question but the method is absolutely wonderful. Thanks!
    – CaptainQuestion
    2 days ago















up vote
9
down vote



accepted










Unfortunately I needed some minutes to think about the problem before finding a solution that can be calculated very quickly:



Imagine the graph of the function $f_a(x)=|x-a|$. Having the graph in mind you see that the derivation $f'(x)=-1$ for $x<a$ and $f'(x)=1$ for $x>a$.



For the intervals: $(-infty,1)$, $(1,2)$, $(2,5)$, ..., $(32,infty)$ we can now easily calculate the derivative $f'(x)=f'_1(x)+f'_2(x)+f'_5(x)+...-f'_{32}(x)$:



In the range $(-infty,1)$ it is $f'(x)=-1-1-1-...-1+1=-11$.

In the range $(1,2)$ it is $f'(x)=+1-1-1-...-1+1=-9$.

In the range $(2,5)$ it is $f'(x)=+1+1+1-...-1+1=-7$.

...



In every step we simply have to invert one sign so "-1" becomes "+1". This means the derivative is changing by 2 at the points x=1,2,5,...



We start by calculating the derivative for $x<1$; it is -11.



Now we simply go through the ranges:



<1: -11

1..2: -9

2..5: -7

5..6: -5

6..8: -3

8..9: -1

9..10: +1

10..11: +3

11..12: +5

12..17: +7

17..24: +9

24..31: +11

31..32: +13

>32: +11



At $x=32$ the derivation decreases by 2 because of the minus sign before $|x-32|$; you could of course adapt this method for sums of elements of the form $b|x-a|$.



We see that for $x<9$ the derivation is negative and for $x>9$ the derivation is positive. We also know that the function is continuous. (This is important because the derivation is not defined at x=1,2,5,...) This means that the function is strictly decreasing respectively increasing for $x<9$ and for $x>9$.



So we know that the global minimum must be at $x=9$.






share|cite|improve this answer

















  • 1




    The right answer. Congratulations! Although I don't know if your method works when the number of terms is even, say $f(x) = |x-1|+ |x-2|$ or $f(x) = |x-11|+|x-12|+|x-17|+|x-24|$ (the minimum or maximum is an interval).
    – David
    Nov 25 at 22:20










  • @David Why should it be a problem if a whole interval represents the minimum or maximum? In the example of $|x-1|+|x-2|$ we would have $f'(x)=0$ in the whole interval 1...2.
    – Martin Rosenau
    Nov 26 at 6:28










  • This answers the previous version of my typo question but the method is absolutely wonderful. Thanks!
    – CaptainQuestion
    2 days ago













up vote
9
down vote



accepted







up vote
9
down vote



accepted






Unfortunately I needed some minutes to think about the problem before finding a solution that can be calculated very quickly:



Imagine the graph of the function $f_a(x)=|x-a|$. Having the graph in mind you see that the derivation $f'(x)=-1$ for $x<a$ and $f'(x)=1$ for $x>a$.



For the intervals: $(-infty,1)$, $(1,2)$, $(2,5)$, ..., $(32,infty)$ we can now easily calculate the derivative $f'(x)=f'_1(x)+f'_2(x)+f'_5(x)+...-f'_{32}(x)$:



In the range $(-infty,1)$ it is $f'(x)=-1-1-1-...-1+1=-11$.

In the range $(1,2)$ it is $f'(x)=+1-1-1-...-1+1=-9$.

In the range $(2,5)$ it is $f'(x)=+1+1+1-...-1+1=-7$.

...



In every step we simply have to invert one sign so "-1" becomes "+1". This means the derivative is changing by 2 at the points x=1,2,5,...



We start by calculating the derivative for $x<1$; it is -11.



Now we simply go through the ranges:



<1: -11

1..2: -9

2..5: -7

5..6: -5

6..8: -3

8..9: -1

9..10: +1

10..11: +3

11..12: +5

12..17: +7

17..24: +9

24..31: +11

31..32: +13

>32: +11



At $x=32$ the derivation decreases by 2 because of the minus sign before $|x-32|$; you could of course adapt this method for sums of elements of the form $b|x-a|$.



We see that for $x<9$ the derivation is negative and for $x>9$ the derivation is positive. We also know that the function is continuous. (This is important because the derivation is not defined at x=1,2,5,...) This means that the function is strictly decreasing respectively increasing for $x<9$ and for $x>9$.



So we know that the global minimum must be at $x=9$.






share|cite|improve this answer












Unfortunately I needed some minutes to think about the problem before finding a solution that can be calculated very quickly:



Imagine the graph of the function $f_a(x)=|x-a|$. Having the graph in mind you see that the derivation $f'(x)=-1$ for $x<a$ and $f'(x)=1$ for $x>a$.



For the intervals: $(-infty,1)$, $(1,2)$, $(2,5)$, ..., $(32,infty)$ we can now easily calculate the derivative $f'(x)=f'_1(x)+f'_2(x)+f'_5(x)+...-f'_{32}(x)$:



In the range $(-infty,1)$ it is $f'(x)=-1-1-1-...-1+1=-11$.

In the range $(1,2)$ it is $f'(x)=+1-1-1-...-1+1=-9$.

In the range $(2,5)$ it is $f'(x)=+1+1+1-...-1+1=-7$.

...



In every step we simply have to invert one sign so "-1" becomes "+1". This means the derivative is changing by 2 at the points x=1,2,5,...



We start by calculating the derivative for $x<1$; it is -11.



Now we simply go through the ranges:



<1: -11

1..2: -9

2..5: -7

5..6: -5

6..8: -3

8..9: -1

9..10: +1

10..11: +3

11..12: +5

12..17: +7

17..24: +9

24..31: +11

31..32: +13

>32: +11



At $x=32$ the derivation decreases by 2 because of the minus sign before $|x-32|$; you could of course adapt this method for sums of elements of the form $b|x-a|$.



We see that for $x<9$ the derivation is negative and for $x>9$ the derivation is positive. We also know that the function is continuous. (This is important because the derivation is not defined at x=1,2,5,...) This means that the function is strictly decreasing respectively increasing for $x<9$ and for $x>9$.



So we know that the global minimum must be at $x=9$.







share|cite|improve this answer












share|cite|improve this answer



share|cite|improve this answer










answered Nov 25 at 21:50









Martin Rosenau

1,047128




1,047128








  • 1




    The right answer. Congratulations! Although I don't know if your method works when the number of terms is even, say $f(x) = |x-1|+ |x-2|$ or $f(x) = |x-11|+|x-12|+|x-17|+|x-24|$ (the minimum or maximum is an interval).
    – David
    Nov 25 at 22:20










  • @David Why should it be a problem if a whole interval represents the minimum or maximum? In the example of $|x-1|+|x-2|$ we would have $f'(x)=0$ in the whole interval 1...2.
    – Martin Rosenau
    Nov 26 at 6:28










  • This answers the previous version of my typo question but the method is absolutely wonderful. Thanks!
    – CaptainQuestion
    2 days ago














  • 1




    The right answer. Congratulations! Although I don't know if your method works when the number of terms is even, say $f(x) = |x-1|+ |x-2|$ or $f(x) = |x-11|+|x-12|+|x-17|+|x-24|$ (the minimum or maximum is an interval).
    – David
    Nov 25 at 22:20










  • @David Why should it be a problem if a whole interval represents the minimum or maximum? In the example of $|x-1|+|x-2|$ we would have $f'(x)=0$ in the whole interval 1...2.
    – Martin Rosenau
    Nov 26 at 6:28










  • This answers the previous version of my typo question but the method is absolutely wonderful. Thanks!
    – CaptainQuestion
    2 days ago








1




1




The right answer. Congratulations! Although I don't know if your method works when the number of terms is even, say $f(x) = |x-1|+ |x-2|$ or $f(x) = |x-11|+|x-12|+|x-17|+|x-24|$ (the minimum or maximum is an interval).
– David
Nov 25 at 22:20




The right answer. Congratulations! Although I don't know if your method works when the number of terms is even, say $f(x) = |x-1|+ |x-2|$ or $f(x) = |x-11|+|x-12|+|x-17|+|x-24|$ (the minimum or maximum is an interval).
– David
Nov 25 at 22:20












@David Why should it be a problem if a whole interval represents the minimum or maximum? In the example of $|x-1|+|x-2|$ we would have $f'(x)=0$ in the whole interval 1...2.
– Martin Rosenau
Nov 26 at 6:28




@David Why should it be a problem if a whole interval represents the minimum or maximum? In the example of $|x-1|+|x-2|$ we would have $f'(x)=0$ in the whole interval 1...2.
– Martin Rosenau
Nov 26 at 6:28












This answers the previous version of my typo question but the method is absolutely wonderful. Thanks!
– CaptainQuestion
2 days ago




This answers the previous version of my typo question but the method is absolutely wonderful. Thanks!
– CaptainQuestion
2 days ago










up vote
13
down vote













You can in principle write out the function in a lot of intervals. But it would probably take too long. However, I will use this fact, without doing it explicitly. We know that if we do write this function, it is going to be linear on each interval (sum of linear functions is a linear function), and it's going to be continuous (sum of continuous functions is a continuous function). We also know that on a line you get minimum at one end, the other, or both (constant line). So all you need to do is to calculate your function at $1,2,5,6,...$ and find the minimum.






share|cite|improve this answer



















  • 1




    I like how this answer asks us to imagine the graph of the function. I find this "imagine" technique useful, while still being intuitive. Similar examples includes "imagine the multiplication table of this finite group" (the group could be huge) or "imagine the truth table for this proposition" (the formula could be long).
    – Alex Vong
    Nov 25 at 22:02








  • 1




    Perhaps the justification "when each absolute value changes, each of them is continuous" could be changed to "the sum of continuous functions is continuous".
    – Alex Vong
    Nov 25 at 22:23












  • @AlexVong That's probably better
    – Andrei
    Nov 25 at 22:29















up vote
13
down vote













You can in principle write out the function in a lot of intervals. But it would probably take too long. However, I will use this fact, without doing it explicitly. We know that if we do write this function, it is going to be linear on each interval (sum of linear functions is a linear function), and it's going to be continuous (sum of continuous functions is a continuous function). We also know that on a line you get minimum at one end, the other, or both (constant line). So all you need to do is to calculate your function at $1,2,5,6,...$ and find the minimum.






share|cite|improve this answer



















  • 1




    I like how this answer asks us to imagine the graph of the function. I find this "imagine" technique useful, while still being intuitive. Similar examples includes "imagine the multiplication table of this finite group" (the group could be huge) or "imagine the truth table for this proposition" (the formula could be long).
    – Alex Vong
    Nov 25 at 22:02








  • 1




    Perhaps the justification "when each absolute value changes, each of them is continuous" could be changed to "the sum of continuous functions is continuous".
    – Alex Vong
    Nov 25 at 22:23












  • @AlexVong That's probably better
    – Andrei
    Nov 25 at 22:29













up vote
13
down vote










up vote
13
down vote









You can in principle write out the function in a lot of intervals. But it would probably take too long. However, I will use this fact, without doing it explicitly. We know that if we do write this function, it is going to be linear on each interval (sum of linear functions is a linear function), and it's going to be continuous (sum of continuous functions is a continuous function). We also know that on a line you get minimum at one end, the other, or both (constant line). So all you need to do is to calculate your function at $1,2,5,6,...$ and find the minimum.






share|cite|improve this answer














You can in principle write out the function in a lot of intervals. But it would probably take too long. However, I will use this fact, without doing it explicitly. We know that if we do write this function, it is going to be linear on each interval (sum of linear functions is a linear function), and it's going to be continuous (sum of continuous functions is a continuous function). We also know that on a line you get minimum at one end, the other, or both (constant line). So all you need to do is to calculate your function at $1,2,5,6,...$ and find the minimum.







share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








edited Nov 26 at 4:10









Alex Vong

1,137819




1,137819










answered Nov 25 at 16:40









Andrei

10.2k21025




10.2k21025








  • 1




    I like how this answer asks us to imagine the graph of the function. I find this "imagine" technique useful, while still being intuitive. Similar examples includes "imagine the multiplication table of this finite group" (the group could be huge) or "imagine the truth table for this proposition" (the formula could be long).
    – Alex Vong
    Nov 25 at 22:02








  • 1




    Perhaps the justification "when each absolute value changes, each of them is continuous" could be changed to "the sum of continuous functions is continuous".
    – Alex Vong
    Nov 25 at 22:23












  • @AlexVong That's probably better
    – Andrei
    Nov 25 at 22:29














  • 1




    I like how this answer asks us to imagine the graph of the function. I find this "imagine" technique useful, while still being intuitive. Similar examples includes "imagine the multiplication table of this finite group" (the group could be huge) or "imagine the truth table for this proposition" (the formula could be long).
    – Alex Vong
    Nov 25 at 22:02








  • 1




    Perhaps the justification "when each absolute value changes, each of them is continuous" could be changed to "the sum of continuous functions is continuous".
    – Alex Vong
    Nov 25 at 22:23












  • @AlexVong That's probably better
    – Andrei
    Nov 25 at 22:29








1




1




I like how this answer asks us to imagine the graph of the function. I find this "imagine" technique useful, while still being intuitive. Similar examples includes "imagine the multiplication table of this finite group" (the group could be huge) or "imagine the truth table for this proposition" (the formula could be long).
– Alex Vong
Nov 25 at 22:02






I like how this answer asks us to imagine the graph of the function. I find this "imagine" technique useful, while still being intuitive. Similar examples includes "imagine the multiplication table of this finite group" (the group could be huge) or "imagine the truth table for this proposition" (the formula could be long).
– Alex Vong
Nov 25 at 22:02






1




1




Perhaps the justification "when each absolute value changes, each of them is continuous" could be changed to "the sum of continuous functions is continuous".
– Alex Vong
Nov 25 at 22:23






Perhaps the justification "when each absolute value changes, each of them is continuous" could be changed to "the sum of continuous functions is continuous".
– Alex Vong
Nov 25 at 22:23














@AlexVong That's probably better
– Andrei
Nov 25 at 22:29




@AlexVong That's probably better
– Andrei
Nov 25 at 22:29










up vote
5
down vote













The answer (minimizer) in this case is $10$, the median of the sequence $$(1,2,5,6,8,9,10,11,12,17,24,31,32).$$



You can plug in $x=10$ in the function and you would find that the minimum value is $96$. In general, the solution to the following minimization problem



$$min{|x-a_1| + |x-a_2| + cdots + |x-a_n|}$$
is the median of $(a_1,ldots,a_n)$. To see why, consider first when $n=2$, and without loss of generality assume $a_1<a_2$. Then $|x-a_1|+|x-a_2|$ is the distance between $x$ and $a_1$ plus the distance between $x$ and $a_2$. It is easy to see that only when $x$ is in the middle of $a_1$ and $a_2$ should the sum of distances be minimal, which equals $|a_2-a_1|$ in this case. In this case the minimizer is not unique. Any points in $[a_1,a_2]$ is a minimizer.



When $n=3$, the function is $|x-a_1|+|x-a_2|+|x-a_3|$, and we order the parameters again so that $a_1<a_2<a_3$. When $x$ coincides with $a_2$, i.e. $x=a_2$, the value becomes $|a_2-a_1|+|a_2-a_3|=|a_3-a_1|$, the distance between $a_3$ and $a_1$. But when $xin[a_1,a_3], xneq a_2$, the value of the function is
$$|x-a_2|+|x-a_1|+|x-a_3| = |a_3-a_1| + |x-a_2|,$$
which is largar than $|a_3-a_1|$, the distance between $a_3$ and $a_1$. Similarly the value would become larger when $x$ is outside $[a_1,a_3]$. So in this case, the minimizer is unique and is equal to $a_2$, the median of $(a_1,a_2,a_3)$.



In general, when $n$ is odd, there exists a unique minimizer, which is equal to the (unique) median of the parameters $(a_1,ldots,a_n)$. When $n$ is even, the function is minimal and constant over the range $[a_i,a_j]$, where $a_i$ and $a_j$ are the two middle values.






share|cite|improve this answer

















  • 1




    That doesn't seem to be correct. Wolfram says the minimum is 51 at x=9. See here
    – I like Serena
    Nov 25 at 20:50








  • 3




    I see now that the confusion comes from the $−|x−32|$ in the problem statement @MartinRosenau. Note the minus sign. Fei Li solved it for a + sign.
    – I like Serena
    Nov 25 at 21:18






  • 1




    I plot the graph using wxmaxima and get the same result as @IlikeSerena. Note the minus sign at the end.
    – Alex Vong
    Nov 25 at 21:48








  • 1




    Maybe the OP @CaptainQuestion made a typo. We need his or her classification, but I think the purpose of this question is exactly what I have demonstrated.
    – Fei Li
    Nov 25 at 22:00






  • 1




    @AlexVong So I hoped, but the next sentence "which equals $|a_2-a_1|$ in this case." excludes this interpretation.
    – Servaes
    Nov 25 at 22:39















up vote
5
down vote













The answer (minimizer) in this case is $10$, the median of the sequence $$(1,2,5,6,8,9,10,11,12,17,24,31,32).$$



You can plug in $x=10$ in the function and you would find that the minimum value is $96$. In general, the solution to the following minimization problem



$$min{|x-a_1| + |x-a_2| + cdots + |x-a_n|}$$
is the median of $(a_1,ldots,a_n)$. To see why, consider first when $n=2$, and without loss of generality assume $a_1<a_2$. Then $|x-a_1|+|x-a_2|$ is the distance between $x$ and $a_1$ plus the distance between $x$ and $a_2$. It is easy to see that only when $x$ is in the middle of $a_1$ and $a_2$ should the sum of distances be minimal, which equals $|a_2-a_1|$ in this case. In this case the minimizer is not unique. Any points in $[a_1,a_2]$ is a minimizer.



When $n=3$, the function is $|x-a_1|+|x-a_2|+|x-a_3|$, and we order the parameters again so that $a_1<a_2<a_3$. When $x$ coincides with $a_2$, i.e. $x=a_2$, the value becomes $|a_2-a_1|+|a_2-a_3|=|a_3-a_1|$, the distance between $a_3$ and $a_1$. But when $xin[a_1,a_3], xneq a_2$, the value of the function is
$$|x-a_2|+|x-a_1|+|x-a_3| = |a_3-a_1| + |x-a_2|,$$
which is largar than $|a_3-a_1|$, the distance between $a_3$ and $a_1$. Similarly the value would become larger when $x$ is outside $[a_1,a_3]$. So in this case, the minimizer is unique and is equal to $a_2$, the median of $(a_1,a_2,a_3)$.



In general, when $n$ is odd, there exists a unique minimizer, which is equal to the (unique) median of the parameters $(a_1,ldots,a_n)$. When $n$ is even, the function is minimal and constant over the range $[a_i,a_j]$, where $a_i$ and $a_j$ are the two middle values.






share|cite|improve this answer

















  • 1




    That doesn't seem to be correct. Wolfram says the minimum is 51 at x=9. See here
    – I like Serena
    Nov 25 at 20:50








  • 3




    I see now that the confusion comes from the $−|x−32|$ in the problem statement @MartinRosenau. Note the minus sign. Fei Li solved it for a + sign.
    – I like Serena
    Nov 25 at 21:18






  • 1




    I plot the graph using wxmaxima and get the same result as @IlikeSerena. Note the minus sign at the end.
    – Alex Vong
    Nov 25 at 21:48








  • 1




    Maybe the OP @CaptainQuestion made a typo. We need his or her classification, but I think the purpose of this question is exactly what I have demonstrated.
    – Fei Li
    Nov 25 at 22:00






  • 1




    @AlexVong So I hoped, but the next sentence "which equals $|a_2-a_1|$ in this case." excludes this interpretation.
    – Servaes
    Nov 25 at 22:39













up vote
5
down vote










up vote
5
down vote









The answer (minimizer) in this case is $10$, the median of the sequence $$(1,2,5,6,8,9,10,11,12,17,24,31,32).$$



You can plug in $x=10$ in the function and you would find that the minimum value is $96$. In general, the solution to the following minimization problem



$$min{|x-a_1| + |x-a_2| + cdots + |x-a_n|}$$
is the median of $(a_1,ldots,a_n)$. To see why, consider first when $n=2$, and without loss of generality assume $a_1<a_2$. Then $|x-a_1|+|x-a_2|$ is the distance between $x$ and $a_1$ plus the distance between $x$ and $a_2$. It is easy to see that only when $x$ is in the middle of $a_1$ and $a_2$ should the sum of distances be minimal, which equals $|a_2-a_1|$ in this case. In this case the minimizer is not unique. Any points in $[a_1,a_2]$ is a minimizer.



When $n=3$, the function is $|x-a_1|+|x-a_2|+|x-a_3|$, and we order the parameters again so that $a_1<a_2<a_3$. When $x$ coincides with $a_2$, i.e. $x=a_2$, the value becomes $|a_2-a_1|+|a_2-a_3|=|a_3-a_1|$, the distance between $a_3$ and $a_1$. But when $xin[a_1,a_3], xneq a_2$, the value of the function is
$$|x-a_2|+|x-a_1|+|x-a_3| = |a_3-a_1| + |x-a_2|,$$
which is largar than $|a_3-a_1|$, the distance between $a_3$ and $a_1$. Similarly the value would become larger when $x$ is outside $[a_1,a_3]$. So in this case, the minimizer is unique and is equal to $a_2$, the median of $(a_1,a_2,a_3)$.



In general, when $n$ is odd, there exists a unique minimizer, which is equal to the (unique) median of the parameters $(a_1,ldots,a_n)$. When $n$ is even, the function is minimal and constant over the range $[a_i,a_j]$, where $a_i$ and $a_j$ are the two middle values.






share|cite|improve this answer












The answer (minimizer) in this case is $10$, the median of the sequence $$(1,2,5,6,8,9,10,11,12,17,24,31,32).$$



You can plug in $x=10$ in the function and you would find that the minimum value is $96$. In general, the solution to the following minimization problem



$$min{|x-a_1| + |x-a_2| + cdots + |x-a_n|}$$
is the median of $(a_1,ldots,a_n)$. To see why, consider first when $n=2$, and without loss of generality assume $a_1<a_2$. Then $|x-a_1|+|x-a_2|$ is the distance between $x$ and $a_1$ plus the distance between $x$ and $a_2$. It is easy to see that only when $x$ is in the middle of $a_1$ and $a_2$ should the sum of distances be minimal, which equals $|a_2-a_1|$ in this case. In this case the minimizer is not unique. Any points in $[a_1,a_2]$ is a minimizer.



When $n=3$, the function is $|x-a_1|+|x-a_2|+|x-a_3|$, and we order the parameters again so that $a_1<a_2<a_3$. When $x$ coincides with $a_2$, i.e. $x=a_2$, the value becomes $|a_2-a_1|+|a_2-a_3|=|a_3-a_1|$, the distance between $a_3$ and $a_1$. But when $xin[a_1,a_3], xneq a_2$, the value of the function is
$$|x-a_2|+|x-a_1|+|x-a_3| = |a_3-a_1| + |x-a_2|,$$
which is largar than $|a_3-a_1|$, the distance between $a_3$ and $a_1$. Similarly the value would become larger when $x$ is outside $[a_1,a_3]$. So in this case, the minimizer is unique and is equal to $a_2$, the median of $(a_1,a_2,a_3)$.



In general, when $n$ is odd, there exists a unique minimizer, which is equal to the (unique) median of the parameters $(a_1,ldots,a_n)$. When $n$ is even, the function is minimal and constant over the range $[a_i,a_j]$, where $a_i$ and $a_j$ are the two middle values.







share|cite|improve this answer












share|cite|improve this answer



share|cite|improve this answer










answered Nov 25 at 18:13









Fei Li

8761617




8761617








  • 1




    That doesn't seem to be correct. Wolfram says the minimum is 51 at x=9. See here
    – I like Serena
    Nov 25 at 20:50








  • 3




    I see now that the confusion comes from the $−|x−32|$ in the problem statement @MartinRosenau. Note the minus sign. Fei Li solved it for a + sign.
    – I like Serena
    Nov 25 at 21:18






  • 1




    I plot the graph using wxmaxima and get the same result as @IlikeSerena. Note the minus sign at the end.
    – Alex Vong
    Nov 25 at 21:48








  • 1




    Maybe the OP @CaptainQuestion made a typo. We need his or her classification, but I think the purpose of this question is exactly what I have demonstrated.
    – Fei Li
    Nov 25 at 22:00






  • 1




    @AlexVong So I hoped, but the next sentence "which equals $|a_2-a_1|$ in this case." excludes this interpretation.
    – Servaes
    Nov 25 at 22:39














  • 1




    That doesn't seem to be correct. Wolfram says the minimum is 51 at x=9. See here
    – I like Serena
    Nov 25 at 20:50








  • 3




    I see now that the confusion comes from the $−|x−32|$ in the problem statement @MartinRosenau. Note the minus sign. Fei Li solved it for a + sign.
    – I like Serena
    Nov 25 at 21:18






  • 1




    I plot the graph using wxmaxima and get the same result as @IlikeSerena. Note the minus sign at the end.
    – Alex Vong
    Nov 25 at 21:48








  • 1




    Maybe the OP @CaptainQuestion made a typo. We need his or her classification, but I think the purpose of this question is exactly what I have demonstrated.
    – Fei Li
    Nov 25 at 22:00






  • 1




    @AlexVong So I hoped, but the next sentence "which equals $|a_2-a_1|$ in this case." excludes this interpretation.
    – Servaes
    Nov 25 at 22:39








1




1




That doesn't seem to be correct. Wolfram says the minimum is 51 at x=9. See here
– I like Serena
Nov 25 at 20:50






That doesn't seem to be correct. Wolfram says the minimum is 51 at x=9. See here
– I like Serena
Nov 25 at 20:50






3




3




I see now that the confusion comes from the $−|x−32|$ in the problem statement @MartinRosenau. Note the minus sign. Fei Li solved it for a + sign.
– I like Serena
Nov 25 at 21:18




I see now that the confusion comes from the $−|x−32|$ in the problem statement @MartinRosenau. Note the minus sign. Fei Li solved it for a + sign.
– I like Serena
Nov 25 at 21:18




1




1




I plot the graph using wxmaxima and get the same result as @IlikeSerena. Note the minus sign at the end.
– Alex Vong
Nov 25 at 21:48






I plot the graph using wxmaxima and get the same result as @IlikeSerena. Note the minus sign at the end.
– Alex Vong
Nov 25 at 21:48






1




1




Maybe the OP @CaptainQuestion made a typo. We need his or her classification, but I think the purpose of this question is exactly what I have demonstrated.
– Fei Li
Nov 25 at 22:00




Maybe the OP @CaptainQuestion made a typo. We need his or her classification, but I think the purpose of this question is exactly what I have demonstrated.
– Fei Li
Nov 25 at 22:00




1




1




@AlexVong So I hoped, but the next sentence "which equals $|a_2-a_1|$ in this case." excludes this interpretation.
– Servaes
Nov 25 at 22:39




@AlexVong So I hoped, but the next sentence "which equals $|a_2-a_1|$ in this case." excludes this interpretation.
– Servaes
Nov 25 at 22:39










up vote
1
down vote













TL;DR: Put the absolute values in ascending order, and look at the sum of the leading coefficients. One by one, change the signs in the sum from right to left. When the sum changes signs, you have passed a local extremum. When the sum equals zero, there is an extremum on an entire interval.





As an alternative to Andrei's excellent answer, or perhaps an extension, you could also look at the derivative. Clearly the function is continuous everywhere, and it is differentiable in all but finitely many points, call them $a_1,ldots,a_n$ in ascending order. Then we want to minimize
$$f(x)=sum_{k=1}^nc_k|x-a_k|=sum_{k=1}^n(-1)^{delta_{xleq a_k}}c_k(x-a_k),$$
where $delta$ denotes the Kronecker delta, in this case defined as
$$delta_{xleq a_k}:=left{begin{array}{ll}1&text{ if } xleq a_k\0&text{ otherwise}end{array}right..$$
This has derivative (for all $x$ apart from the $a_k$)
$$f'(x)=sum_{k=1}^n(-1)^{delta_{xleq a_k}}c_k.$$
The expression has a local minimum at $x$ if either $f'(x)=0$, or if $x=a_k$ for some $k$ and $f'(y)<0$ for $a_{k-1}<y<a_k$ and $f'(y)>0$ for $a_k<y<a_{k+1}$.



This is all rather formal; in practice this means you put the $c_k$ in ascending order, so here $n=13$ and $c_1=cdots=c_{12}=1$ and $c_{13}=-1$, and find all $m$ such that flipping the last $m$ signs in the sum
$$c_1+c_2+c_3+c_4+c_5+c_6+c_7+c_8+c_9+c_{10}+c_{11}+c_{12}+c_{13}$$
makes the sum change signs compared to changing the last $m-1$ signs. Here a quick look gives
$$c_1+c_2+c_3+c_4+c_5+c_6-c_7-c_8-c_9-c_{10}-c_{11}-c_{12}-c_{13}=1,$$
$$c_1+c_2+c_3+c_4+c_5-c_6-c_7-c_8-c_9-c_{10}-c_{11}-c_{12}-c_{13}=-1,$$
so $f$ has a local minimum at $a_6=9$, and it is not difficult to see that there is no other minimum.






share|cite|improve this answer























  • Anyone care to explain the downvote?
    – Servaes
    Nov 26 at 8:12















up vote
1
down vote













TL;DR: Put the absolute values in ascending order, and look at the sum of the leading coefficients. One by one, change the signs in the sum from right to left. When the sum changes signs, you have passed a local extremum. When the sum equals zero, there is an extremum on an entire interval.





As an alternative to Andrei's excellent answer, or perhaps an extension, you could also look at the derivative. Clearly the function is continuous everywhere, and it is differentiable in all but finitely many points, call them $a_1,ldots,a_n$ in ascending order. Then we want to minimize
$$f(x)=sum_{k=1}^nc_k|x-a_k|=sum_{k=1}^n(-1)^{delta_{xleq a_k}}c_k(x-a_k),$$
where $delta$ denotes the Kronecker delta, in this case defined as
$$delta_{xleq a_k}:=left{begin{array}{ll}1&text{ if } xleq a_k\0&text{ otherwise}end{array}right..$$
This has derivative (for all $x$ apart from the $a_k$)
$$f'(x)=sum_{k=1}^n(-1)^{delta_{xleq a_k}}c_k.$$
The expression has a local minimum at $x$ if either $f'(x)=0$, or if $x=a_k$ for some $k$ and $f'(y)<0$ for $a_{k-1}<y<a_k$ and $f'(y)>0$ for $a_k<y<a_{k+1}$.



This is all rather formal; in practice this means you put the $c_k$ in ascending order, so here $n=13$ and $c_1=cdots=c_{12}=1$ and $c_{13}=-1$, and find all $m$ such that flipping the last $m$ signs in the sum
$$c_1+c_2+c_3+c_4+c_5+c_6+c_7+c_8+c_9+c_{10}+c_{11}+c_{12}+c_{13}$$
makes the sum change signs compared to changing the last $m-1$ signs. Here a quick look gives
$$c_1+c_2+c_3+c_4+c_5+c_6-c_7-c_8-c_9-c_{10}-c_{11}-c_{12}-c_{13}=1,$$
$$c_1+c_2+c_3+c_4+c_5-c_6-c_7-c_8-c_9-c_{10}-c_{11}-c_{12}-c_{13}=-1,$$
so $f$ has a local minimum at $a_6=9$, and it is not difficult to see that there is no other minimum.






share|cite|improve this answer























  • Anyone care to explain the downvote?
    – Servaes
    Nov 26 at 8:12













up vote
1
down vote










up vote
1
down vote









TL;DR: Put the absolute values in ascending order, and look at the sum of the leading coefficients. One by one, change the signs in the sum from right to left. When the sum changes signs, you have passed a local extremum. When the sum equals zero, there is an extremum on an entire interval.





As an alternative to Andrei's excellent answer, or perhaps an extension, you could also look at the derivative. Clearly the function is continuous everywhere, and it is differentiable in all but finitely many points, call them $a_1,ldots,a_n$ in ascending order. Then we want to minimize
$$f(x)=sum_{k=1}^nc_k|x-a_k|=sum_{k=1}^n(-1)^{delta_{xleq a_k}}c_k(x-a_k),$$
where $delta$ denotes the Kronecker delta, in this case defined as
$$delta_{xleq a_k}:=left{begin{array}{ll}1&text{ if } xleq a_k\0&text{ otherwise}end{array}right..$$
This has derivative (for all $x$ apart from the $a_k$)
$$f'(x)=sum_{k=1}^n(-1)^{delta_{xleq a_k}}c_k.$$
The expression has a local minimum at $x$ if either $f'(x)=0$, or if $x=a_k$ for some $k$ and $f'(y)<0$ for $a_{k-1}<y<a_k$ and $f'(y)>0$ for $a_k<y<a_{k+1}$.



This is all rather formal; in practice this means you put the $c_k$ in ascending order, so here $n=13$ and $c_1=cdots=c_{12}=1$ and $c_{13}=-1$, and find all $m$ such that flipping the last $m$ signs in the sum
$$c_1+c_2+c_3+c_4+c_5+c_6+c_7+c_8+c_9+c_{10}+c_{11}+c_{12}+c_{13}$$
makes the sum change signs compared to changing the last $m-1$ signs. Here a quick look gives
$$c_1+c_2+c_3+c_4+c_5+c_6-c_7-c_8-c_9-c_{10}-c_{11}-c_{12}-c_{13}=1,$$
$$c_1+c_2+c_3+c_4+c_5-c_6-c_7-c_8-c_9-c_{10}-c_{11}-c_{12}-c_{13}=-1,$$
so $f$ has a local minimum at $a_6=9$, and it is not difficult to see that there is no other minimum.






share|cite|improve this answer














TL;DR: Put the absolute values in ascending order, and look at the sum of the leading coefficients. One by one, change the signs in the sum from right to left. When the sum changes signs, you have passed a local extremum. When the sum equals zero, there is an extremum on an entire interval.





As an alternative to Andrei's excellent answer, or perhaps an extension, you could also look at the derivative. Clearly the function is continuous everywhere, and it is differentiable in all but finitely many points, call them $a_1,ldots,a_n$ in ascending order. Then we want to minimize
$$f(x)=sum_{k=1}^nc_k|x-a_k|=sum_{k=1}^n(-1)^{delta_{xleq a_k}}c_k(x-a_k),$$
where $delta$ denotes the Kronecker delta, in this case defined as
$$delta_{xleq a_k}:=left{begin{array}{ll}1&text{ if } xleq a_k\0&text{ otherwise}end{array}right..$$
This has derivative (for all $x$ apart from the $a_k$)
$$f'(x)=sum_{k=1}^n(-1)^{delta_{xleq a_k}}c_k.$$
The expression has a local minimum at $x$ if either $f'(x)=0$, or if $x=a_k$ for some $k$ and $f'(y)<0$ for $a_{k-1}<y<a_k$ and $f'(y)>0$ for $a_k<y<a_{k+1}$.



This is all rather formal; in practice this means you put the $c_k$ in ascending order, so here $n=13$ and $c_1=cdots=c_{12}=1$ and $c_{13}=-1$, and find all $m$ such that flipping the last $m$ signs in the sum
$$c_1+c_2+c_3+c_4+c_5+c_6+c_7+c_8+c_9+c_{10}+c_{11}+c_{12}+c_{13}$$
makes the sum change signs compared to changing the last $m-1$ signs. Here a quick look gives
$$c_1+c_2+c_3+c_4+c_5+c_6-c_7-c_8-c_9-c_{10}-c_{11}-c_{12}-c_{13}=1,$$
$$c_1+c_2+c_3+c_4+c_5-c_6-c_7-c_8-c_9-c_{10}-c_{11}-c_{12}-c_{13}=-1,$$
so $f$ has a local minimum at $a_6=9$, and it is not difficult to see that there is no other minimum.







share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








edited Nov 25 at 22:50

























answered Nov 25 at 22:35









Servaes

21k33792




21k33792












  • Anyone care to explain the downvote?
    – Servaes
    Nov 26 at 8:12


















  • Anyone care to explain the downvote?
    – Servaes
    Nov 26 at 8:12
















Anyone care to explain the downvote?
– Servaes
Nov 26 at 8:12




Anyone care to explain the downvote?
– Servaes
Nov 26 at 8:12










CaptainQuestion is a new contributor. Be nice, and check out our Code of Conduct.










draft saved

draft discarded


















CaptainQuestion is a new contributor. Be nice, and check out our Code of Conduct.













CaptainQuestion is a new contributor. Be nice, and check out our Code of Conduct.












CaptainQuestion is a new contributor. Be nice, and check out our Code of Conduct.
















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.





Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


Please pay close attention to the following guidance:


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


To learn more, see our tips on writing great answers.




draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3013010%2fhow-to-find-out-the-global-minimum-of-the-following-expression%23new-answer', 'question_page');
}
);

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







Popular posts from this blog

AnyDesk - Fatal Program Failure

How to calibrate 16:9 built-in touch-screen to a 4:3 resolution?

QoS: MAC-Priority for clients behind a repeater