Python - Optimization and Minimization

Optimization and Minimization in Python

Introduction

Optimization is a fundamental aspect of many scientific and engineering applications. In Python, optimization refers to finding the best solution from a set of feasible solutions. Minimization is a type of optimization problem where the goal is to find the minimum value of an objective function, possibly subject to constraints.

Python provides several libraries for optimization tasks, with SciPy being one of the most comprehensive and widely used. The scipy.optimize module offers algorithms for function minimization (scalar or multi-dimensional), curve fitting, root finding, and more.

Key Concepts in Optimization

• Objective Function: The function to be minimized or maximized.
• Constraints: Conditions that must be satisfied for a solution to be valid.
• Bounds: Limitations on the values of variables.
• Local vs Global Minimum: A local minimum is smaller than neighboring points, while a global minimum is the lowest over the entire domain.

scipy.optimize Module Overview

The scipy.optimize module includes the following tools:

• minimize: Minimization of scalar or vector functions
• root: Root finding
• least_squares: Solving least-squares problems
• curve_fit: Fit a function to data using least squares
• linprog: Linear programming

Function Minimization Using minimize()

Unconstrained Minimization

from scipy.optimize import minimize
import numpy as np

def objective(x):
    return x**2 + 4*x + 4

result = minimize(objective, x0=0)
print(result)

Multivariable Function Minimization

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

initial_guess = [1, 1]
result = minimize(objective, initial_guess)
print(result.x)

Method Selection

Different algorithms can be chosen using the `method` parameter:

• 'Nelder-Mead'
• 'BFGS'
• 'CG'
• 'L-BFGS-B' (supports bounds)

result = minimize(objective, [1, 1], method='BFGS')
print(result.x)

Minimization with Bounds and Constraints

Using Bounds

bounds = [(0, None), (0, None)]

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

res = minimize(obj, [1, 1], bounds=bounds)
print(res.x)

Using Constraints

Constraints can be defined using dictionaries:

cons = {'type': 'ineq', 'fun': lambda x: x[0] - 1}

res = minimize(obj, [0.5, 0.5], constraints=cons)
print(res.x)

Multiple Constraints

constraints = [
    {'type': 'ineq', 'fun': lambda x: x[0] - 1},
    {'type': 'ineq', 'fun': lambda x: 2 - x[1]}
]

res = minimize(obj, [0.5, 0.5], constraints=constraints)
print(res.x)

Root Finding with root()

Single Variable Root

from scipy.optimize import root

def equation(x):
    return x**3 - x - 2

sol = root(equation, x0=1)
print(sol.x)

Multivariable System of Equations

def equations(vars):
    x, y = vars
    return [x**2 + y**2 - 1, x - y]

sol = root(equations, [0.5, 0.5])
print(sol.x)

Curve Fitting with curve_fit()

from scipy.optimize import curve_fit
import matplotlib.pyplot as plt

def model(x, a, b):
    return a * np.exp(b * x)

xdata = np.array([0, 1, 2, 3, 4])
ydata = model(xdata, 2, 0.5) + np.random.normal(0, 0.2, 5)

params, _ = curve_fit(model, xdata, ydata)
a, b = params

plt.scatter(xdata, ydata)
plt.plot(xdata, model(xdata, a, b), color='red')
plt.show()

Least Squares with least_squares()

from scipy.optimize import least_squares

def residuals(x):
    return [x[0]**2 + x[1] - 11, x[1]**2 + x[0] - 7]

res = least_squares(residuals, [1, 1])
print(res.x)

Linear Programming with linprog()

Example: Maximize 3x + 4y subject to constraints

from scipy.optimize import linprog

c = [-3, -4]
A = [[2, 1], [1, 2]]
b = [20, 20]

bounds = [(0, None), (0, None)]

res = linprog(c, A_ub=A, b_ub=b, bounds=bounds)
print(res.x)

Global Optimization Techniques

Basinhopping

from scipy.optimize import basinhopping

def func(x):
    return np.sin(x) + 0.05 * x**2

res = basinhopping(func, x0=2.0)
print(res.x)

Differential Evolution

from scipy.optimize import differential_evolution

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

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

Using Custom Gradient (Jacobian)

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

def grad(x):
    return np.array([2*x[0], 2*x[1]])

res = minimize(f, [1, 1], jac=grad, method='BFGS')
print(res.x)

Callback Functions

def callback(xk):
    print(f"Current solution: {xk}")

res = minimize(f, [2, 2], callback=callback)

Visualizing Optimization

import matplotlib.pyplot as plt

def f(x):
    return x**2 + 4*x + 4

x = np.linspace(-5, 5, 100)
y = f(x)

plt.plot(x, y, label="Objective Function")
plt.scatter(result.x, f(result.x), color='red', label="Minimum")
plt.legend()
plt.show()

Common Pitfalls and Tips

• Always provide a good initial guess, especially for local solvers.
• Use bounded methods like 'L-BFGS-B' if your variables should remain within a range.
• Inspect convergence messages in the result object.
• Try multiple solvers if the first fails to converge.

When to Use What?

• minimize: General minimization with or without constraints.
• least_squares: Nonlinear least squares problems.
• curve_fit: Model fitting to data.
• linprog: Linear optimization.
• basinhopping or differential_evolution: Global optimization.

Real-World Applications

• Portfolio optimization in finance
• Engineering design optimization
• Fitting models in machine learning
• Optimizing hyperparameters in AI
• Resource allocation and logistics

Summary

Python's rich set of optimization tools allows users to solve a broad range of problems from simple scalar minimization to complex global optimization. The scipy.optimize module is a powerful and versatile part of the SciPy library that supports various optimization and root-finding techniques. With the appropriate choice of solver and constraints, you can model and solve real-world problems effectively.