Basin-hopping for global minima in SciPy - Step-by-Step Execution

Concept Flow - Basin-hopping for global minima

Start with initial guess x0

↓

Apply random step to x0 -> x1

↓

Local minimization at x1 -> x1_min

↓

Compare f(x1_min) with current best

↓

Accept x1_min

↓

Update current best

↓

Repeat steps for set iterations

↓

Return best found minimum

Basin-hopping starts from a guess, jumps randomly, finds local minima, and decides to accept new points to find the global minimum.

Execution Sample

SciPy

import numpy as np
from scipy.optimize import basinhopping

def func(x):
    return x**4 - 3*x**3 + 2

result = basinhopping(func, x0=0)
print(result.x, result.fun)

This code finds the global minimum of a function using basin-hopping starting from 0.

Execution Table

Step	Current x	Random Step x	Local Min x	Local Min f(x)	Accept?	Best x	Best f(x)
0	0.0	0.5	0.75	-0.796875	Yes	0.75	-0.796875
1	0.75	1.2	1.125	-0.669922	No	0.75	-0.796875
2	0.75	0.3	0.3	1.024	No	0.75	-0.796875
3	0.75	1.0	1.0	-0.75	No	0.75	-0.796875
4	0.75	0.8	0.8	-0.768	No	0.75	-0.796875
5	0.75	0.7	0.7	-0.784	No	0.75	-0.796875
6	0.75	0.76	0.76	-0.797	Yes	0.76	-0.797
7	0.76	0.77	0.77	-0.798	Yes	0.77	-0.798
8	0.77	0.78	0.78	-0.799	Yes	0.78	-0.799
9	0.78	0.79	0.79	-0.7995	Yes	0.79	-0.7995
10	0.79	0.8	0.8	-0.8	Yes	0.8	-0.8
Exit	-	-	-	-	-	0.8	-0.8

💡 Reached 10 iterations, stopping basin-hopping.

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	After 8	After 9	After 10
Current x	0.0	0.75	0.75	0.75	0.75	0.75	0.76	0.77	0.78	0.79	0.8
Best x	0.0	0.75	0.75	0.75	0.75	0.75	0.76	0.77	0.78	0.79	0.8
Best f(x)	2.0	-0.796875	-0.796875	-0.796875	-0.796875	-0.796875	-0.797	-0.798	-0.799	-0.7995	-0.8

Key Moments - 2 Insights

Why do some worse local minima get accepted sometimes?

Basin-hopping accepts worse minima with some probability to escape local traps, as seen in rows where 'Accept?' is 'No' but the algorithm continues searching.

Why does the best x sometimes not update even when a new local minimum is found?

The best x only updates if the new local minimum has a better (lower) function value, shown in rows where 'Accept?' is 'No' and 'Best x' stays the same.

Visual Quiz - 3 Questions

Look at the execution table, what is the best function value after step 5?

A -0.796875

B -0.784

C -0.75

D -0.669922

💡 Hint

Check the 'Best f(x)' column at step 5 in the execution table.

At which step does the algorithm first accept a better minimum than at step 0?

A Step 1

B Step 3

C Step 6

D Step 10

💡 Hint

Look for the first step where 'Best f(x)' improves after step 0.

If the random step size was larger, how would the 'Random Step x' values change?

A They would be closer to current x

B They would be more spread out from current x

C They would always be smaller than current x

D They would not change

💡 Hint

Random step size controls how far the new x jumps from current x.

Concept Snapshot

Basin-hopping:
- Starts from initial guess
- Makes random jumps
- Runs local minimization
- Accepts new points if better or probabilistically
- Repeats to find global minimum
- Useful for complex landscapes

Full Transcript

Basin-hopping is a method to find the lowest point of a function by jumping around randomly and then finding local low points. It starts with a guess, jumps randomly, finds a local minimum, and decides if it should keep that point. This repeats many times to find the best minimum overall. The execution table shows each step's current position, random jump, local minimum found, and if it was accepted. Variables like current position and best found minimum update as the algorithm runs. Sometimes worse points are accepted to avoid getting stuck. This helps find the global minimum even if the function has many ups and downs.

Practice

1. What is the main purpose of the basin-hopping algorithm in optimization?

easy

A. To calculate the derivative of a function

B. To perform a simple linear regression

C. To sort a list of numbers efficiently

D. To find the global minimum of a function with many local minima

Solution

1. Step 1: Understand the goal of basin-hopping

   Basin-hopping is designed to find the lowest point (global minimum) in complex functions that have many dips (local minima).

2. Step 2: Compare with other options

   Options A, B, and C describe unrelated tasks: differentiation, regression, and sorting, which are not the purpose of basin-hopping.

3. Final Answer:

   To find the global minimum of a function with many local minima -> Option D

4. Quick Check:

   Basin-hopping = global minimum search [OK]

Hint: Basin-hopping = global minimum finder in tricky functions [OK]

Common Mistakes:

• Confusing basin-hopping with simple optimization methods
• Thinking it sorts or differentiates functions
• Assuming it only finds local minima

2. Which of the following is the correct way to import the basin-hopping function from scipy?

easy

A. from scipy import basinhopping

B. import scipy.basinhopping

C. from scipy.optimize import basinhopping

D. import basinhopping from scipy.optimize

Solution

1. Step 1: Recall correct import syntax in Python

   To import a specific function from a module, use 'from module import function'.

2. Step 2: Match with scipy.optimize and basinhopping

   The basin-hopping function is inside scipy.optimize, so the correct import is 'from scipy.optimize import basinhopping'.

3. Final Answer:

   from scipy.optimize import basinhopping -> Option C

4. Quick Check:

   Correct import syntax = from scipy.optimize import basinhopping [OK]

Hint: Use 'from scipy.optimize import basinhopping' to import [OK]

Common Mistakes:

• Using incorrect import order or syntax
• Trying to import basin-hopping directly from scipy
• Using 'import basinhopping from ...' which is invalid

3. What will be the output of the following code snippet?

import numpy as np
from scipy.optimize import basinhopping

def func(x):
    return (x - 3)**2 + 5

result = basinhopping(func, x0=0, niter=5)
print(round(result.fun, 2))

medium

A. 5.00

B. 0.00

C. 9.00

D. 3.00

Solution

1. Step 1: Understand the function and its minimum

   The function is (x - 3)^2 + 5, which has its minimum value at x=3, and the minimum value is 5.

2. Step 2: Analyze basin-hopping output

   Basin-hopping tries to find the global minimum. Starting at x0=0, after 5 iterations, it should find near x=3, so the function value is near 5.

3. Final Answer:

   5.00 -> Option A

4. Quick Check:

   Minimum value of (x-3)^2+5 = 5 [OK]

Hint: Minimum of (x-3)^2+5 is 5 at x=3 [OK]

Common Mistakes:

• Confusing minimum value with x-coordinate
• Assuming starting point is the minimum
• Ignoring the constant +5 in the function

4. Identify the error in the following code using basin-hopping:

from scipy.optimize import basinhopping

def f(x):
    return x**2

result = basinhopping(f, x0=[1, 2], niter=10)
print(result.x)

medium

A. No error; code runs correctly

B. Function f must return a scalar, but it returns a list

C. x0 should be a numpy array, not a list

D. x0 should be a scalar, not a list

Solution

1. Step 1: Check input types for basin-hopping

   basinhopping accepts x0 as a scalar or array-like. A list like [1, 2] is valid and converted to numpy array internally.

2. Step 2: Verify function output

   Function f(x) = x**2. For vector x = np.array([1,2]), it returns np.array([1,4]), not a scalar. Optimization requires scalar objective function value.

3. Step 3: Test code behavior

   The code raises an error because the objective function returns an array instead of scalar.

4. Final Answer:

   Function f must return a scalar, but it returns a list -> Option B

5. Quick Check:

   Objective func must return scalar [OK]

Hint: basinhopping objective must return scalar for vector x0 [OK]

Common Mistakes:

• Assuming no error; overlooking non-scalar function return
• Thinking x0 list causes the error
• Believing x0 must be scalar or explicit numpy array

5. You want to find the global minimum of a function with many local minima using basin-hopping. Which parameter should you adjust to increase the chance of escaping local minima?

hard

A. Increase the 'stepsize' parameter to allow bigger jumps

B. Decrease the 'niter' parameter to reduce iterations

C. Set 'minimizer_kwargs' to None

D. Use a fixed starting point without randomization

Solution

1. Step 1: Understand basin-hopping parameters

   'stepsize' controls how big the random jumps are between local minimizations. Bigger steps help jump out of local minima.

2. Step 2: Evaluate options

   Decreasing 'niter' reduces attempts, lowering success. Setting 'minimizer_kwargs' to None disables local minimization, which is needed. Fixed start without randomization limits exploration.

3. Final Answer:

   Increase the 'stepsize' parameter to allow bigger jumps -> Option A

4. Quick Check:

   Bigger stepsize = better escape from local minima [OK]

Hint: Bigger stepsize helps jump out of local minima [OK]

Common Mistakes:

• Reducing iterations thinking it speeds up convergence
• Disabling local minimization by setting minimizer_kwargs to None
• Using fixed start point limits search space