One-dimensional search methods
$begingroup$
Among the one-dimensional search methods there are some, such as the one of the golden-section search, that only use the function, and others such as the one of the bisection, that use the derivative of the function.
Do you think that something similar to the bisection method could be done, but using only the value of the function, without derivatives? That is, take the average value of the interval and evaluate it to reduce the interval in each iteration in half
optimization convex-optimization
asked Jan 6 at 16:21
J. GarcíaJ. García
618
$endgroup$
add a comment |
$begingroup$
Among the one-dimensional search methods there are some, such as the one of the golden-section search, that only use the function, and others such as the one of the bisection, that use the derivative of the function.
Do you think that something similar to the bisection method could be done, but using only the value of the function, without derivatives? That is, take the average value of the interval and evaluate it to reduce the interval in each iteration in half
optimization convex-optimization
asked Jan 6 at 16:21
J. GarcíaJ. García
618
$endgroup$
add a comment |
$begingroup$
Among the one-dimensional search methods there are some, such as the one of the golden-section search, that only use the function, and others such as the one of the bisection, that use the derivative of the function.
Do you think that something similar to the bisection method could be done, but using only the value of the function, without derivatives? That is, take the average value of the interval and evaluate it to reduce the interval in each iteration in half
optimization convex-optimization
asked Jan 6 at 16:21
J. GarcíaJ. García
618
$endgroup$
Among the one-dimensional search methods there are some, such as the one of the golden-section search, that only use the function, and others such as the one of the bisection, that use the derivative of the function.
Do you think that something similar to the bisection method could be done, but using only the value of the function, without derivatives? That is, take the average value of the interval and evaluate it to reduce the interval in each iteration in half
optimization convex-optimization
optimization convex-optimization
asked Jan 6 at 16:21
J. GarcíaJ. García
618
asked Jan 6 at 16:21
J. GarcíaJ. García
618
asked Jan 6 at 16:21
J. GarcíaJ. García
618
asked Jan 6 at 16:21
J. GarcíaJ. García
618
asked Jan 6 at 16:21
J. GarcíaJ. García
618
618
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Knowing the value of $f$ at the midpoint and the left and right ends of an interval is not sufficient by itself to determine whether the minimum is in the left half or right half of the interval. It's easy to construct examples to see this.
For example, if $f(0)=2$, $f(1)=1$, and $f(2)=2$, you can't tell whether the minimum is in the interval from 0 to 1 or the interval from 1 to 2.
answered Jan 7 at 5:10
Brian BorchersBrian Borchers
6,18611320
$endgroup$
$begingroup$
Can you share an example?
$endgroup$
– J. García
Jan 7 at 9:27
$begingroup$
I've added one into the the answer.
$endgroup$
– Brian Borchers
Jan 7 at 15:52
add a comment |
$begingroup$
There is ternary search. It is a generalization of binary search for finding the maximum (or minimum) of a unimodal function. The idea is, you split the search space $[a, b)$ into three (approximately) equal parts, $[a, m)$, $[m, n)$, and $[n, b)$, and can discard one of the side ones. If $f(m) < f(n)$, then your maximum is in $[m, b)$. If $f(m) geq f(n)$, then the maximum is in $[a, n)$.
answered Jan 6 at 16:33
Todor MarkovTodor Markov
2,420412
$endgroup$
$begingroup$
But, using only the average point of the interval? Like Bisection Method, but not using $f'$, only $f$
$endgroup$
– J. García
Jan 6 at 20:09
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%2f3064061%2fone-dimensional-search-methods%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Knowing the value of $f$ at the midpoint and the left and right ends of an interval is not sufficient by itself to determine whether the minimum is in the left half or right half of the interval. It's easy to construct examples to see this.
For example, if $f(0)=2$, $f(1)=1$, and $f(2)=2$, you can't tell whether the minimum is in the interval from 0 to 1 or the interval from 1 to 2.
answered Jan 7 at 5:10
Brian BorchersBrian Borchers
6,18611320
$endgroup$
$begingroup$
Can you share an example?
$endgroup$
– J. García
Jan 7 at 9:27
$begingroup$
I've added one into the the answer.
$endgroup$
– Brian Borchers
Jan 7 at 15:52
add a comment |
$begingroup$
Knowing the value of $f$ at the midpoint and the left and right ends of an interval is not sufficient by itself to determine whether the minimum is in the left half or right half of the interval. It's easy to construct examples to see this.
For example, if $f(0)=2$, $f(1)=1$, and $f(2)=2$, you can't tell whether the minimum is in the interval from 0 to 1 or the interval from 1 to 2.
answered Jan 7 at 5:10
Brian BorchersBrian Borchers
6,18611320
$endgroup$
$begingroup$
Can you share an example?
$endgroup$
– J. García
Jan 7 at 9:27
$begingroup$
I've added one into the the answer.
$endgroup$
– Brian Borchers
Jan 7 at 15:52
add a comment |
$begingroup$
Knowing the value of $f$ at the midpoint and the left and right ends of an interval is not sufficient by itself to determine whether the minimum is in the left half or right half of the interval. It's easy to construct examples to see this.
For example, if $f(0)=2$, $f(1)=1$, and $f(2)=2$, you can't tell whether the minimum is in the interval from 0 to 1 or the interval from 1 to 2.
answered Jan 7 at 5:10
Brian BorchersBrian Borchers
6,18611320
$endgroup$
Knowing the value of $f$ at the midpoint and the left and right ends of an interval is not sufficient by itself to determine whether the minimum is in the left half or right half of the interval. It's easy to construct examples to see this.
For example, if $f(0)=2$, $f(1)=1$, and $f(2)=2$, you can't tell whether the minimum is in the interval from 0 to 1 or the interval from 1 to 2.
answered Jan 7 at 5:10
Brian BorchersBrian Borchers
6,18611320
edited Jan 7 at 15:52
answered Jan 7 at 5:10
Brian BorchersBrian Borchers
6,18611320
answered Jan 7 at 5:10
Brian BorchersBrian Borchers
6,18611320
answered Jan 7 at 5:10
Brian BorchersBrian Borchers
6,18611320
6,18611320
$begingroup$
Can you share an example?
$endgroup$
– J. García
Jan 7 at 9:27
$begingroup$
I've added one into the the answer.
$endgroup$
– Brian Borchers
Jan 7 at 15:52
add a comment |
$begingroup$
Can you share an example?
$endgroup$
– J. García
Jan 7 at 9:27
$begingroup$
I've added one into the the answer.
$endgroup$
– Brian Borchers
Jan 7 at 15:52
$begingroup$
Can you share an example?
$endgroup$
– J. García
Jan 7 at 9:27
$begingroup$
Can you share an example?
$endgroup$
– J. García
Jan 7 at 9:27
$begingroup$
I've added one into the the answer.
$endgroup$
– Brian Borchers
Jan 7 at 15:52
$begingroup$
I've added one into the the answer.
$endgroup$
– Brian Borchers
Jan 7 at 15:52
add a comment |
$begingroup$
There is ternary search. It is a generalization of binary search for finding the maximum (or minimum) of a unimodal function. The idea is, you split the search space $[a, b)$ into three (approximately) equal parts, $[a, m)$, $[m, n)$, and $[n, b)$, and can discard one of the side ones. If $f(m) < f(n)$, then your maximum is in $[m, b)$. If $f(m) geq f(n)$, then the maximum is in $[a, n)$.
answered Jan 6 at 16:33
Todor MarkovTodor Markov
2,420412
$endgroup$
$begingroup$
But, using only the average point of the interval? Like Bisection Method, but not using $f'$, only $f$
$endgroup$
– J. García
Jan 6 at 20:09
add a comment |
$begingroup$
There is ternary search. It is a generalization of binary search for finding the maximum (or minimum) of a unimodal function. The idea is, you split the search space $[a, b)$ into three (approximately) equal parts, $[a, m)$, $[m, n)$, and $[n, b)$, and can discard one of the side ones. If $f(m) < f(n)$, then your maximum is in $[m, b)$. If $f(m) geq f(n)$, then the maximum is in $[a, n)$.
answered Jan 6 at 16:33
Todor MarkovTodor Markov
2,420412
$endgroup$
$begingroup$
But, using only the average point of the interval? Like Bisection Method, but not using $f'$, only $f$
$endgroup$
– J. García
Jan 6 at 20:09
add a comment |
$begingroup$
There is ternary search. It is a generalization of binary search for finding the maximum (or minimum) of a unimodal function. The idea is, you split the search space $[a, b)$ into three (approximately) equal parts, $[a, m)$, $[m, n)$, and $[n, b)$, and can discard one of the side ones. If $f(m) < f(n)$, then your maximum is in $[m, b)$. If $f(m) geq f(n)$, then the maximum is in $[a, n)$.
answered Jan 6 at 16:33
Todor MarkovTodor Markov
2,420412
$endgroup$
There is ternary search. It is a generalization of binary search for finding the maximum (or minimum) of a unimodal function. The idea is, you split the search space $[a, b)$ into three (approximately) equal parts, $[a, m)$, $[m, n)$, and $[n, b)$, and can discard one of the side ones. If $f(m) < f(n)$, then your maximum is in $[m, b)$. If $f(m) geq f(n)$, then the maximum is in $[a, n)$.
answered Jan 6 at 16:33
Todor MarkovTodor Markov
2,420412
answered Jan 6 at 16:33
Todor MarkovTodor Markov
2,420412
answered Jan 6 at 16:33
Todor MarkovTodor Markov
2,420412
answered Jan 6 at 16:33
Todor MarkovTodor Markov
2,420412
2,420412
$begingroup$
But, using only the average point of the interval? Like Bisection Method, but not using $f'$, only $f$
$endgroup$
– J. García
Jan 6 at 20:09
add a comment |
$begingroup$
But, using only the average point of the interval? Like Bisection Method, but not using $f'$, only $f$
$endgroup$
– J. García
Jan 6 at 20:09
$begingroup$
But, using only the average point of the interval? Like Bisection Method, but not using $f'$, only $f$
$endgroup$
– J. García
Jan 6 at 20:09
$begingroup$
But, using only the average point of the interval? Like Bisection Method, but not using $f'$, only $f$
$endgroup$
– J. García
Jan 6 at 20:09
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%2f3064061%2fone-dimensional-search-methods%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
