Constrained optimization in SciPy - Time & Space Complexity

Time Complexity: Constrained optimization

O(n^3)

Understanding Time Complexity

When solving constrained optimization problems with scipy, it is important to understand how the time needed grows as the problem size increases.

We want to know how the number of calculations changes when we add more variables or constraints.

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

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

# Initial guess
x0 = [2, 0]

# Run constrained optimization
res = minimize(fun, x0, constraints=cons, method='SLSQP')

This code finds the minimum of a function with one inequality constraint using the SLSQP method.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Iterative calls to the objective and constraint functions during optimization steps.
• How many times: The optimizer runs multiple iterations, each evaluating the functions and gradients.

How Execution Grows With Input

As the number of variables and constraints grows, the optimizer must do more work each iteration.

Input Size (n variables)	Approx. Operations
10	Thousands of function and gradient evaluations
100	Millions of evaluations and matrix operations
1000	Billions of calculations, much slower convergence

Pattern observation: The work grows quickly because each iteration involves matrix calculations that scale roughly with the square or cube of the number of variables.

Final Time Complexity

Time Complexity: O(n^3)

This means the time to solve the problem grows roughly with the cube of the number of variables, due to matrix operations inside the optimizer.

Common Mistake

[X] Wrong: "Adding more constraints or variables only increases time a little bit."

[OK] Correct: Each new variable or constraint can greatly increase the size of matrices the optimizer handles, causing time to grow much faster than expected.

Interview Connect

Understanding how optimization time grows helps you explain trade-offs when solving real problems, showing you know what affects performance beyond just writing code.

Self-Check

"What if we switched from SLSQP to a gradient-free method? How would the time complexity change?"