Minimizing multivariate functions (minimize) in SciPy - Time & Space Complexity

Time Complexity: Minimizing multivariate functions (minimize)

O(n^2)

Understanding Time Complexity

When we use scipy to find the lowest point of a function with many variables, it takes some steps to get there.

We want to know how the number of steps grows as the problem size grows.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

from scipy.optimize import minimize
import numpy as np

def func(x):
    return np.sum(x**2)

x0 = np.zeros(100)  # start point with 100 variables
result = minimize(func, x0, method='BFGS')
print(result.success)

This code tries to find the minimum of a function with 100 variables using the BFGS method.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Each iteration computes the function value and its gradient over all variables.
• How many times: The optimizer repeats these calculations many times until it converges.

How Execution Grows With Input

As the number of variables grows, each step takes longer because it must check all variables.

Input Size (n)	Approx. Operations
10	Few hundred operations per iteration
100	Thousands of operations per iteration
1000	Hundreds of thousands of operations per iteration

Pattern observation: The work per iteration grows roughly with the square of the number of variables.

Final Time Complexity

Time Complexity: O(n^2)

This means the time to do one iteration grows roughly with the square of the number of variables.

Common Mistake

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

[OK] Correct: Because methods like BFGS update matrices of size n x n, the work per step grows faster than just the number of variables.

Interview Connect

Understanding how optimization time grows helps you explain choices in real problems and shows you know what affects performance.

Self-Check

What if we changed the method from BFGS to a simpler gradient descent? How would the time complexity change?

Practice

1. What is the main purpose of scipy.optimize.minimize in data science?

easy

A. To find the minimum value of a multivariate function

B. To sort data in ascending order

C. To calculate the mean of a dataset

D. To generate random numbers

Solution

1. Step 1: Understand the function's goal

   scipy.optimize.minimize is designed to find the lowest point of a function with multiple variables.

2. Step 2: Compare options with the function's purpose

   Sorting, calculating mean, or generating random numbers are unrelated to minimizing functions.

3. Final Answer:

   To find the minimum value of a multivariate function -> Option A

4. Quick Check:

   Minimize means find lowest point [OK]

Hint: Minimize means find lowest point of a function [OK]

Common Mistakes:

• Confusing minimize with sorting or statistics
• Thinking it generates random data
• Assuming it calculates averages

2. Which of the following is the correct way to call scipy.optimize.minimize for a function f with initial guess x0?

easy

A. minimize(f, x0, method='max')

B. minimize(f, x0)

C. minimize(f(x0))

D. minimize(x0, f)

Solution

1. Step 1: Recall the function signature

   The correct call is minimize(fun, x0) where fun is the function and x0 is the starting guess.

2. Step 2: Check each option

   minimize(f, x0) matches the correct order. minimize(x0, f) reverses arguments. minimize(f(x0)) calls the function instead of passing it. minimize(f, x0, method='max') uses an invalid method 'max'.

3. Final Answer:

   minimize(f, x0) -> Option B

4. Quick Check:

   Function first, guess second [OK]

Hint: Pass function first, then initial guess [OK]

Common Mistakes:

• Swapping function and initial guess
• Calling function instead of passing it
• Using invalid method names

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

from scipy.optimize import minimize

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

result = minimize(f, [0, 0])
print(result.x.round(2))

medium

A. [1.00, 2.00]

B. [0.00, 0.00]

C. [-1.00, 2.00]

D. [1.00, -2.00]

Solution

1. Step 1: Understand the function to minimize

   The function is (x0-1)^2 + (x1+2)^2, which is smallest when x0=1 and x1=-2.

2. Step 2: Check the minimize result

   Starting from [0,0], minimize finds the point closest to the minimum, which is [1, -2].

3. Final Answer:

   [1.00, -2.00] -> Option D

4. Quick Check:

   Minimum at x=1, y=-2 [OK]

Hint: Minimum at points making squared terms zero [OK]

Common Mistakes:

• Confusing signs inside the function
• Expecting initial guess as output
• Misreading the function formula

4. Identify the error in this code that tries to minimize a function:

from scipy.optimize import minimize

def f(x):
    return x[0]**2 + x[1]**2

result = minimize(f, 0)
print(result.x)

medium

A. Initial guess should be a list or array, not a single number

B. Function f should return a list, not a number

C. minimize requires method='BFGS' explicitly

D. print statement should be inside a function

Solution

1. Step 1: Check the initial guess type

   The function expects a vector input like [x0, x1], but the initial guess is a single number 0, which is invalid.

2. Step 2: Understand the correct input format

   Initial guess must be a list or array with the same dimension as the function input, e.g., [0, 0].

3. Final Answer:

   Initial guess should be a list or array, not a single number -> Option A

4. Quick Check:

   Input vector must match function variables [OK]

Hint: Initial guess must match function input shape [OK]

Common Mistakes:

• Passing scalar instead of vector as initial guess
• Thinking function output must be list
• Assuming method must be specified always

5. You want to minimize the function f(x, y) = (x-3)^2 + (y+1)^2 but only allow y to be between -2 and 0. Which code correctly applies this constraint using scipy.optimize.minimize?

hard

A. minimize(lambda v: (v[0]-3)**2 + (v[1]+1)**2, [0, 0], constraints={'type':'ineq', 'fun': lambda v: v[1] + 2})

B. minimize(lambda v: (v[0]-3)**2 + (v[1]+1)**2, [0, 0], bounds=[(-2, 0), (None, None)])

C. minimize(lambda v: (v[0]-3)**2 + (v[1]+1)**2, [0, 0], bounds=[(None, None), (-2, 0)])

D. minimize(lambda v: (v[0]-3)**2 + (v[1]+1)**2, [0, 0], constraints={'type':'eq', 'fun': lambda v: v[1] + 1})

Solution

1. Step 1: Understand bounds parameter

   Bounds are given as a list of (min, max) tuples for each variable. Here, x has no bounds, y is between -2 and 0.

2. Step 2: Match bounds to variables

   minimize(lambda v: (v[0]-3)**2 + (v[1]+1)**2, [0, 0], bounds=[(None, None), (-2, 0)]) correctly sets bounds as [(None, None), (-2, 0)] meaning x unbounded, y bounded. minimize(lambda v: (v[0]-3)**2 + (v[1]+1)**2, [0, 0], bounds=[(-2, 0), (None, None)]) reverses bounds. Options A and D use constraints incorrectly for this case.

3. Final Answer:

   minimize(lambda v: (v[0]-3)**2 + (v[1]+1)**2, [0, 0], bounds=[(None, None), (-2, 0)]) -> Option C

4. Quick Check:

   Bounds list matches variable order [OK]

Hint: Bounds list order matches variables order [OK]

Common Mistakes:

• Swapping bounds order for variables
• Using constraints instead of bounds incorrectly
• Setting equality constraint instead of bounds