2
$\begingroup$

Is there a divide and conquer algorithm for optimizing weakly unimodal continuous functions?

Adding more details:

My function has a flat line on the left and right and then there is a global minima in between but this global minima repeats for a while on what would seem like a straight line. To the left of the minima and right of the flat line on left, the behavior is monotonic decreasing. To the right of the minima and left of the flat line on right, the behavior is monotonic increasing. Also, the function is a positive function that is it's range is always >0. In addition, the function is defined only above zero. i.e, it's domain is always >0.

I see the main issue being that the initial bracket of three points may not be ideal. If the initial bracket was ideal, then does golden section search converge to optimal solution? Or is the issue bigger-even if the initial bracket was ideal?

Improve this question
$\endgroup$
2
  • $\begingroup$ Could you add a few more details to your question (the exact definition of a weakly unimodal continuous function, problem size, any constraints -- explicit or implicit -- that are important to you)? $\endgroup$
    – Christian Clason
    Commented Apr 25, 2016 at 7:37
  • $\begingroup$ @ChristianClason I have added the information about the function! $\endgroup$
    – user251385
    Commented Apr 26, 2016 at 5:34

1 Answer 1

Reset to default
4
$\begingroup$

No, there is not.

The problem is that your weakly unimodal function might be constant except for a very small "bump". No algorithm that evaluates the function a finite number of times can distinguish such a function from the constant function unless it gets lucky.

Suppose you had such an algorithm and ran it on a constant test function $f(x)=c$ for which it stopped after $k$ function evaluations (all of which had the same value.) Next run it on a function $g$ that has the same constant value at each of those $k$ points but also has a hidden bump that doesn't hit any of those points. Your algorithm would stop after the same $k$ iterations with an incorrect result.

Divide and conquer algorithms for global minimization of non-convex functions require additional properties of the function (for example Lipschitz continuity) in order to deal with this issue.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Can you recommend or give references to such divide and conquer algorithms for global minimization of non-convex functions that require additional properties of the function (for example Lipschitz continuity) in order to deal with this issue ? $\endgroup$
    – user251385
    Commented Apr 25, 2016 at 2:54
  • $\begingroup$ Sure, see Introduction to Global Optimization, 2nd ed. by Horst and Pardalos, chapter 5, for a discussion of branch and bound algorithms for global optimization of Lipschitz continuous functions. $\endgroup$
    – Brian Borchers
    Commented Apr 25, 2016 at 3:28
  • $\begingroup$ I have added some more detail about the graph of my function and it's domain and range being positive based on ChristianClason's comment. From your description, I see the main issue being that the initial bracket of three points may not be ideal. If the initial bracket was ideal, then does golden section search converge to optimal solution? Or is the issue bigger-even if the initial bracket was ideal? $\endgroup$
    – user251385
    Commented Apr 26, 2016 at 16:49
  • $\begingroup$ I don't believe that there's anything in your expanded statement of the problem that eliminates the coutnerexample given in my answer. $\endgroup$
    – Brian Borchers
    Commented Apr 26, 2016 at 17:33

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.