8
$\begingroup$

Suppose that I want to optimize a unimodal function defined on some real interval. I can use the well-known algorithm as described in Wikipedia under the name of ternary search.

In case of the algorithm that repeatedly halving intervals, it is common to reserve the term binary search for discrete problems and to use the term bisection method otherwise. Extrapolating this convention, I suspect that the term trisection method might apply to the algorithm that solves my problem.

My question is whether it is common among academics, and is safe to use in, e.g., senior theses, to apply the term ternary search even if the algorithm is applied to a continuous problem. I need a reputable source for this. I'm also interested whether the term trisection method actually exists.

Improve this question
$\endgroup$
11
  • 1
    $\begingroup$ I don't know about the terminology, but why would you do that? There is not much time to be won by trisecting. $\endgroup$
    – Raphael
    Jan 15, 2014 at 8:35
  • 4
    $\begingroup$ I wouldn't worry about it. If Wikipedia calls it "ternary search", that's probably the most common name so use that. The worst that can happen is that your examiner recommends you change it to "trisection" throughout, as a minor correction. $\endgroup$
    – David Richerby
    Jan 15, 2014 at 10:01
  • $\begingroup$ @DavidRicherby I actually want to use "trisection" because it is consistent with the binary case. To do this I need to know the term is really used. $\endgroup$
    – Pteromys
    Jan 16, 2014 at 1:14
  • $\begingroup$ @Raphael The problem I'm concerned with is optimizing, not finding zeros, of functions. $\endgroup$
    – Pteromys
    Jan 16, 2014 at 1:15
  • 2
    $\begingroup$ @Pteromys It's more important to be consistent with standard usage than with some other case. Unless somebody confirms that "trisection" is used, stick with "ternary search" as that's the only term you have evidence for. (And, yeah, Google doesn't help because you get a million hits for people trying to subdivide angles.) "Trisection" may be a name with better justification but you're not in a position to invent new names for existing concepts. You could add a parenthetical remark but I wouldn't go farther than that without evidence of use. $\endgroup$
    – David Richerby
    Jan 16, 2014 at 1:26

2 Answers 2

Reset to default
1
$\begingroup$

Check out Fibonacci search and golden section search (the article about Fibonacci search talks about an array, but the technique is really applicable just like golden section search to continuous functions). Fibonacci search is a tiny bit faster. The trick is that you can reuse the points from one iteration to the next. For Fibonacci, you'll have to determine the number of iterations beforehand. No big deal, you know the precision sought anyway.

It can be shown that if you just compare the function values for relative order, Fibonacci search is fastest possible. If you consider the actual values, some form of quasi-Newton is faster.

Improve this answer
$\endgroup$
0
$\begingroup$

The word "bitonic search" can probably refer to this concept. See this book and these lecture notes for instance.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I didn't know the word, but from the sources you've given I can only know that the term is used problems of a discrete domain. $\endgroup$
    – Pteromys
    Jan 20, 2014 at 10:55
  • 2
    $\begingroup$ You are right I had not noticed the emphasis on the continuity. Then how about Golden Section Search? $\endgroup$
    – Hoda
    Jan 20, 2014 at 16:31
  • $\begingroup$ thanks. The term "golden section search" seems to explicitly stand for the continuous case. However, it is reserved for a particular way of division of intervals. I'd like to divide intervals in another way. $\endgroup$
    – Pteromys
    Jan 21, 2014 at 0:39
  • 2
    $\begingroup$ @Pteromys, it can be shown (see Avriel and Wilde, "Optimality proof for the symmetric Fibonacci search technique", Fibonacci Quarterly 4:4, 265-269 (oct 1966)) that the Fibonacci search (closely related to the golden section search) is optimal if you only compare values for greater/smaller. $\endgroup$
    – vonbrand
    Jan 29, 2014 at 21:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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