1
$\begingroup$

Let us say that I have an 1D optimization problem. For example, I want to find the minimum of the flowing function:

y = f(x) = x^3 - 6x^2 + 4x + 12    x in [-2.1, 6.1]

Plotting here

The global minimum of this function is at x = -2.1. There is a local minimum at x =~ 3.5

If I run some local optimization algorithm starting from the point x = 3 for example. The Algorithm will trapped in the local minimum x= 3.5 which is expected and OK.

My question:

Is it possible after running the local optimization algorithm to extract the boundary of the x variable that belongs to this local minimum without brute-forcing? in other words, I would like to know, analytically, what is the range of x that if I re-run the same algorithm starting from it (this range), I will got the same result. So, I can avoid running Algorithm again from this range.

P.S. the mentioned function was just an example. The real case is 6D function optimization.

$\endgroup$
1
  • 2
    $\begingroup$ In general, I don't think this is possible. It will depend heavily on the exact algorithm and algorithm parameters used. In some special cases, and with some simple algorithms, perhaps it can be done. But these are unlikely to be the cases (problems) for which you want to know this - if you know that much about the problem you wish to solve, you probably don''t need to run an optimizer. Anyhow, you can look up "basis of attraction" or "region of attraction" or perhaps "radius" of attraction. it only gets much more complicated in higher dimensions. $\endgroup$ Commented Jun 18, 2018 at 10:35

1 Answer 1

2
$\begingroup$

Partially answered in comments:

In general, I don't think this is possible. It will depend heavily on the exact algorithm and algorithm parameters used. In some special cases, and with some simple algorithms, perhaps it can be done. But these are unlikely to be the cases (problems) for which you want to know this - if you know that much about the problem you wish to solve, you probably don''t need to run an optimizer. Anyhow, you can look up "basis of attraction" or "region of attraction" or perhaps "radius" of attraction. it only gets much more complicated in higher dimensions. – Mark L. Stone

As an example of how complicated it can become, look at this paper about finding zeros of some complex polynomials with Newton's method, where the basin of attraction can be a fractal. One figure (6, page 32) from that paper:

Fractal domain of attraction for Newton's method


M. Drexler, I. J. Sobey, C. Bracher "Fractal Characteristics of Newton's Method on Polynomials" Numerical Analysis Group Report no. 96/14 (Nov. 1996).

$\endgroup$
1
  • 1
    $\begingroup$ I love this vivid, easy to understand example! Great find! I've edited to include a more complete citation so that the source isn't lost. $\endgroup$
    – Sycorax
    Commented Nov 27, 2018 at 17:35

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.