Bounds and constraints in SciPy - Time & Space Complexity

Time Complexity: Bounds and constraints

O(n^2)

Understanding Time Complexity

When using bounds and constraints in optimization with scipy, it is important to know how the time to find a solution changes as the problem size grows.

We want to understand how adding bounds and constraints affects the work the solver must do.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

from scipy.optimize import minimize

# Objective function
fun = lambda x: (x[0] - 1)**2 + (x[1] - 2.5)**2

# Bounds for variables
bounds = [(0, 2), (0, 3)]

# Constraint: x0 + x1 must be at least 2
cons = ({'type': 'ineq', 'fun': lambda x: x[0] + x[1] - 2})

# Run optimization
result = minimize(fun, x0=[0, 0], bounds=bounds, constraints=[cons])

This code finds the minimum of a function with two variables, using bounds and one inequality constraint.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The solver repeatedly evaluates the objective and constraint functions while searching for the minimum.
• How many times: The number of evaluations depends on the solver's iterations, which grow with problem size and complexity.

How Execution Grows With Input

As the number of variables and constraints increases, the solver must do more work to check bounds and satisfy constraints.

Input Size (n variables)	Approx. Operations
10	Hundreds of function and constraint checks
100	Thousands to tens of thousands of checks
1000	Hundreds of thousands or more checks

Pattern observation: The work grows faster than the number of variables because constraints add extra checks each iteration.

Final Time Complexity

Time Complexity: O(n^2)

This means the time to solve grows roughly with the square of the number of variables when bounds and constraints are involved.

Common Mistake

[X] Wrong: "Adding bounds or constraints does not affect the solver's time much."

[OK] Correct: Bounds and constraints require extra checks and calculations each iteration, increasing the total work significantly.

Interview Connect

Understanding how constraints affect solver time helps you explain trade-offs in optimization problems clearly and confidently.

Self-Check

"What if we remove all constraints but keep bounds? How would the time complexity change?"

Practice

1. What is the main purpose of bounds in scipy.optimize functions?

easy

A. To set the maximum number of iterations

B. To define the objective function to minimize

C. To limit the range of values each variable can take

D. To specify the initial guess for variables

Solution

1. Step 1: Understand the role of bounds

   Bounds restrict each variable to a specific range, for example, between 0 and 1.

2. Step 2: Differentiate bounds from other parameters

   Bounds are not about the objective function, initial guess, or iteration limits; they only limit variable values.

3. Final Answer:

   To limit the range of values each variable can take -> Option C

4. Quick Check:

   Bounds = variable limits [OK]

Hint: Bounds always restrict variable ranges, not function or iterations [OK]

Common Mistakes:

• Confusing bounds with constraints
• Thinking bounds set initial guesses
• Assuming bounds limit iterations

2. Which of the following is the correct way to define bounds for two variables x and y where x is between 0 and 5, and y is between -1 and 1 in scipy.optimize.minimize?

easy

A. bounds = [(0, 5), (-1, 1)]

B. bounds = {0:5, -1:1}

C. bounds = [0, 5, -1, 1]

D. bounds = (0, 5, -1, 1)

Solution

1. Step 1: Recall bounds format in scipy.optimize

   Bounds are given as a list of tuples, each tuple for one variable's (min, max).

2. Step 2: Check each option's format

   bounds = [(0, 5), (-1, 1)] uses a list of tuples correctly. Options A (flat list), B (dictionary), and D (flat tuple) are invalid formats.

3. Final Answer:

   bounds = [(0, 5), (-1, 1)] -> Option A

4. Quick Check:

   Bounds = list of (min, max) tuples [OK]

Hint: Use list of (min, max) tuples for bounds [OK]

Common Mistakes:

• Using dictionary instead of list
• Passing flat list instead of tuples
• Confusing tuple and list syntax

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

from scipy.optimize import minimize

func = lambda x: (x[0]-1)**2 + (x[1]+2)**2
bounds = [(0, 2), (-3, -1)]
result = minimize(func, x0=[0, 0], bounds=bounds)
print(result.x)

medium

A. [0.5 -1.5]

B. [0. -3.]

C. [2. -1.]

D. [1. -2.]

Solution

1. Step 1: Understand the objective function and bounds

   The function is minimized when x[0] = 1 and x[1] = -2. Bounds allow x[0] between 0 and 2, and x[1] between -3 and -1.

2. Step 2: Check if the minimum is within bounds

   Since (1, -2) is inside the bounds, the optimizer will find this point.

3. Final Answer:

   [1. -2.] -> Option D

4. Quick Check:

   Minimum inside bounds = [1, -2] [OK]

Hint: Minimum inside bounds is the solution [OK]

Common Mistakes:

• Ignoring bounds and picking unconstrained minimum
• Confusing bounds order
• Assuming initial guess is final answer

4. Identify the error in the following code that uses bounds in scipy.optimize.minimize:

from scipy.optimize import minimize

func = lambda x: x[0]**2 + x[1]**2
bounds = [0, 1, 0, 1]
result = minimize(func, x0=[0.5, 0.5], bounds=bounds)
print(result.x)

medium

A. Initial guess x0 is outside bounds

B. Bounds should be a list of tuples, not a flat list

C. Objective function must return a scalar

D. Bounds must be specified as a dictionary

Solution

1. Step 1: Check bounds format

   The code uses bounds = [0, 1, 0, 1], which is a flat list. scipy expects a list of tuples for bounds.

2. Step 2: Confirm other parameters

   Initial guess is inside bounds, function returns scalar, and bounds as dictionary is not required.

3. Final Answer:

   Bounds should be a list of tuples, not a flat list -> Option B

4. Quick Check:

   Bounds = list of tuples, not flat list [OK]

Hint: Use list of tuples for bounds, not flat list [OK]

Common Mistakes:

• Using flat list instead of list of tuples
• Setting initial guess outside bounds
• Misunderstanding bounds format

5. You want to minimize the function f(x, y) = (x-3)^2 + (y+1)^2 with the constraints that x + y = 2 and bounds 0 ≤ x ≤ 4, -2 ≤ y ≤ 2. Which of the following correctly sets up the constraints and bounds for scipy.optimize.minimize?

hard

A. constraints = {'type': 'eq', 'fun': lambda v: v[0] + v[1] - 2}; bounds = [(0, 4), (-2, 2)]

B. constraints = [{'type': 'ineq', 'fun': lambda v: v[0] + v[1] - 2}]; bounds = [(0, 4), (-2, 2)]

C. constraints = {'type': 'eq', 'fun': lambda v: v[0] - v[1] - 2}; bounds = [(0, 4), (-2, 2)]

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

Solution

1. Step 1: Define the equality constraint

   The constraint is x + y = 2, so the function should return zero when this holds: lambda v: v[0] + v[1] - 2. It must be an equality constraint ('eq').

2. Step 2: Set the correct bounds

   Bounds are 0 ≤ x ≤ 4 and -2 ≤ y ≤ 2, so bounds = [(0, 4), (-2, 2)].

3. Final Answer:

   constraints = {'type': 'eq', 'fun': lambda v: v[0] + v[1] - 2}; bounds = [(0, 4), (-2, 2)] -> Option A

4. Quick Check:

   Equality constraint + correct bounds = constraints = {'type': 'eq', 'fun': lambda v: v[0] + v[1] - 2}; bounds = [(0, 4), (-2, 2)] [OK]

Hint: Equality constraint returns zero when condition met [OK]

Common Mistakes:

• Using inequality instead of equality constraint
• Swapping bounds limits
• Incorrect constraint function expression