Global optimization (differential_evolution) in SciPy - Time & Space Complexity

Time Complexity: Global optimization (differential_evolution)

O(k * m * n)

Understanding Time Complexity

When using global optimization like differential_evolution, we want to know how the time needed grows as the problem size grows.

We ask: How does the number of calculations change when we try to find the best solution over more variables?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

from scipy.optimize import differential_evolution

def objective(x):
    return sum(x**2)

bounds = [(-5, 5)] * 3
result = differential_evolution(objective, bounds)
print(result.x, result.fun)

This code tries to find the minimum of a simple function with 3 variables using differential evolution.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Evaluating the objective function many times for different candidate solutions.
• How many times: The algorithm tests many candidate points across multiple generations until it converges.

How Execution Grows With Input

As the number of variables (dimensions) increases, the number of candidate solutions needed grows, so the total evaluations grow quickly.

Input Size (n variables)	Approx. Evaluations
3	Thousands
10	Tens of thousands
50	Hundreds of thousands or more

Pattern observation: The work grows faster than just adding variables; it grows roughly exponentially because the search space gets much bigger.

Final Time Complexity

Time Complexity: O(k * m * n)

This means the time grows with the number of generations (k), the population size (m), and the number of variables (n), which all increase the work.

Common Mistake

[X] Wrong: "The time to find the best solution grows linearly with the number of variables."

[OK] Correct: Because the search space grows exponentially with variables, the algorithm needs many more evaluations, so time grows faster than linearly.

Interview Connect

Understanding how optimization time grows helps you explain trade-offs when solving real problems, showing you know how algorithms behave as problems get bigger.

Self-Check

"What if we increase the population size in differential_evolution? How would the time complexity change?"

Practice

1. What is the main purpose of the differential_evolution function in scipy.optimize?

easy

A. To perform linear regression on data

B. To calculate the derivative of a function

C. To find the global minimum of a function within given bounds

D. To generate random numbers for simulations

Solution

1. Step 1: Understand the purpose of differential evolution

   Differential evolution is a global optimization algorithm designed to find the minimum value of a function over a specified range.

2. Step 2: Compare options with the purpose

   Only To find the global minimum of a function within given bounds describes finding the global minimum within bounds, which matches the function's purpose.

3. Final Answer:

   To find the global minimum of a function within given bounds -> Option C

4. Quick Check:

   Global optimization = find minimum [OK]

Hint: Remember: differential_evolution finds global minimum [OK]

Common Mistakes:

• Confusing optimization with differentiation
• Thinking it performs regression
• Assuming it generates random numbers only

2. Which of the following is the correct way to import the differential_evolution function from scipy.optimize?

easy

A. import differential_evolution from scipy.optimize

B. from scipy.optimize import differential_evolution

C. from scipy import differential_evolution.optimize

D. import scipy.optimize.differential_evolution

Solution

1. Step 1: Recall Python import syntax

   The correct syntax to import a function from a module is: from module import function.

2. Step 2: Match syntax with options

   from scipy.optimize import differential_evolution matches the correct syntax exactly. Other options have incorrect order or syntax.

3. Final Answer:

   from scipy.optimize import differential_evolution -> Option B

4. Quick Check:

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

Hint: Use 'from module import function' for importing functions [OK]

Common Mistakes:

• Using 'import function from module' which is invalid
• Trying to import submodules incorrectly
• Using dot notation in import statements wrongly

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

from scipy.optimize import differential_evolution

def func(x):
    return (x[0] - 2)**2 + (x[1] + 3)**2

result = differential_evolution(func, bounds=[(-5, 5), (-5, 5)])
print(round(result.fun, 2))

medium

A. 0.00

B. 5.00

C. 13.00

D. Error due to wrong bounds

Solution

1. Step 1: Understand the function and bounds

   The function calculates the sum of squares of (x0-2) and (x1+3). The minimum is at x0=2, x1=-3, which is inside the bounds (-5,5).

2. Step 2: Evaluate the minimum function value

   At x0=2 and x1=-3, func returns (2-2)^2 + (-3+3)^2 = 0 + 0 = 0. So the minimum function value is 0.

3. Final Answer:

   0.00 -> Option A

4. Quick Check:

   Minimum value at (2,-3) = 0 [OK]

Hint: Minimum of squared terms is zero at exact target points [OK]

Common Mistakes:

• Misunderstanding bounds causing error
• Calculating function value at wrong points
• Ignoring rounding in output

4. Identify the error in the following code using differential_evolution and how to fix it:

from scipy.optimize import differential_evolution

def f(x):
    return x**2

bounds = [(-3, 3)]
result = differential_evolution(f, bounds)
print(result.x)

medium

A. No error; code runs correctly

B. Bounds should be a tuple, not a list; fix by changing bounds to a tuple

C. Missing import of numpy; fix by adding import numpy as np

D. Function f expects a scalar but receives an array; fix by defining f(x) to accept array input

Solution

1. Step 1: Analyze function input requirements

   The differential_evolution function passes an array to f, but f expects a scalar and tries to square it directly, which causes an error.

2. Step 2: Fix function to accept array input

   Modify f to accept an array input and return a scalar, for example: def f(x): return x[0]**2.

3. Final Answer:

   Function f expects a scalar but receives an array; fix by defining f(x) to accept array input -> Option D

4. Quick Check:

   Function input shape mismatch = Function f expects a scalar but receives an array; fix by defining f(x) to accept array input [OK]

Hint: Functions must accept array input for differential_evolution [OK]

Common Mistakes:

• Assuming function gets scalar input
• Incorrect bounds format
• Ignoring error messages about input types

5. You want to minimize the function f(x) = sin(x[0]) + cos(x[1]) over the bounds x[0] in [0, 6] and x[1] in [-3, 3]. Which of the following code snippets correctly uses differential_evolution to find the minimum and print the best input values?

hard

A. from scipy.optimize import differential_evolution
import numpy as np

def f(x):
return np.sin(x[0]) + np.cos(x[1])

bounds = [(0, 6), (-3, 3)]
result = differential_evolution(f, bounds)
print(result.x)

B. from scipy.optimize import differential_evolution
import numpy as np

def f(x):
return np.sin(x) + np.cos(x)

bounds = [(0, 6), (-3, 3)]
result = differential_evolution(f, bounds)
print(result.x)

C. from scipy.optimize import differential_evolution
import numpy as np

def f(x):
return np.sin(x[0]) + np.cos(x[1])

bounds = [0, 6, -3, 3]
result = differential_evolution(f, bounds)
print(result.x)

D. from scipy.optimize import differential_evolution
import numpy as np

def f(x):
return np.sin(x[0]) + np.cos(x[1])

bounds = [(0, 6), (-3, 3)]
result = differential_evolution(f)
print(result.x)

Solution

1. Step 1: Check function definition

   The function f correctly uses array indexing for x[0] and x[1] and applies numpy sine and cosine functions.

2. Step 2: Verify bounds and function call

   Bounds are correctly given as a list of tuples for each variable. The differential_evolution call includes both the function and bounds.

3. Final Answer:

   Code snippet C correctly defines the function, bounds, and calls differential_evolution -> Option A

4. Quick Check:

   Correct function and bounds usage = from scipy.optimize import differential_evolution import numpy as np def f(x): return np.sin(x[0]) + np.cos(x[1]) bounds = [(0, 6), (-3, 3)] result = differential_evolution(f, bounds) print(result.x) [OK]

Hint: Use list of tuples for bounds and array input function [OK]

Common Mistakes:

• Passing bounds as flat list instead of list of tuples
• Defining function without indexing array input
• Calling differential_evolution without bounds argument