Constrained Optimization

$\min_{\mathbf{x}} f(\mathbf{x}) \quad \text{subject to} \quad g_i(\mathbf{x}) \le 0, \; i = 1,\ldots,m, \quad h_j(\mathbf{x}) = 0, \; j = 1,\ldots,p$$where: -$f$is the **objective function** -$g_i$are **inequality constraints** ($\le 0$by convention) -$h_j$are **equality constraints** The **feasible set** is${\mathbf{x} : g_i(\mathbf{x}) \le 0, ; h_j(\mathbf{x}) = 0 ; \forall i,j}$.

The Lagrangian of a constrained problem is:

$$\mathcal{L}(\mathbf{x}, \boldsymbol{\lambda}, \boldsymbol{\nu}) = f(\mathbf{x}) + \sum_{i=1}^{m} \lambda_i g_i(\mathbf{x}) + \sum_{j=1}^{p} \nu_j h_j(\mathbf{x})$$

The Karush-Kuhn-Tucker (KKT) conditions are necessary for optimality (and sufficient for convex problems):

1. Stationarity: $\nabla_{\mathbf{x}} \mathcal{L} = \mathbf{0}$
2. Primal feasibility: $g_i(\mathbf{x}) \le 0$, $h_j(\mathbf{x}) = 0$
3. Dual feasibility: $\lambda_i \ge 0$
4. Complementary slackness: $\lambda_i g_i(\mathbf{x}) = 0$

The multipliers $\lambda_i, \nu_j$ represent the sensitivity of the optimal value to constraint perturbations.

from scipy.optimize import minimize, Bounds, LinearConstraint

# Box constraints: lb <= x <= ub
bounds = Bounds(lb=[0, -np.inf], ub=[np.inf, 1])

# Linear constraint: lb <= A @ x <= ub
linear_con = LinearConstraint(
    A=np.array([[1, 1], [2, -1]]),
    lb=[0, -np.inf],
    ub=[10, 5],
)

# Nonlinear constraint (dict form for SLSQP)
nonlinear_con = {
    'type': 'ineq',  # g(x) >= 0
    'fun': lambda x: x[0]**2 + x[1]**2 - 1,
    'jac': lambda x: np.array([2*x[0], 2*x[1]]),
}

Use Bounds and LinearConstraint objects with trust-constr; use dict-form constraints with SLSQP.

SLSQP solves nonlinear constrained problems by solving a sequence of quadratic programming (QP) subproblems. At each iteration:

1. Approximate $f$ by a quadratic model around $\mathbf{x}_k$
2. Linearize the constraints
3. Solve the resulting QP to get a search direction
4. Perform a line search

result = minimize(f, x0, method='SLSQP',
                  jac=grad_f,
                  bounds=bounds,
                  constraints=[eq_con, ineq_con])

Pros: Handles equality + inequality + bounds; well-tested. Cons: Can be slow for large problems; may fail on highly nonlinear constraints.

The trust-constr method uses a trust-region approach with an interior-point or SQP algorithm. It is SciPy's most modern constrained solver and supports:

• Sparse Jacobians and Hessians
• Bounds, LinearConstraint, NonlinearConstraint objects
• Verbose iteration output

from scipy.optimize import NonlinearConstraint

nlc = NonlinearConstraint(
    fun=lambda x: x[0]**2 + x[1]**2,
    lb=0, ub=1,
    jac=lambda x: np.array([2*x[0], 2*x[1]]),
)

result = minimize(f, x0, method='trust-constr',
                  jac=grad_f, hess=hess_f,
                  constraints=nlc, bounds=bounds)

A linear program (LP) has a linear objective and linear constraints:

$$\min_{\mathbf{x}} \mathbf{c}^T \mathbf{x} \quad \text{s.t.} \quad \mathbf{A}_{\text{ub}} \mathbf{x} \le \mathbf{b}_{\text{ub}}, \; \mathbf{A}_{\text{eq}} \mathbf{x} = \mathbf{b}_{\text{eq}}, \; \mathbf{l} \le \mathbf{x} \le \mathbf{u}$$

from scipy.optimize import linprog

result = linprog(
    c,                      # cost vector
    A_ub=A_ub, b_ub=b_ub,  # inequality constraints
    A_eq=A_eq, b_eq=b_eq,  # equality constraints
    bounds=bounds,          # variable bounds
    method='highs',         # default: HiGHS solver
)

The HiGHS solver (default since SciPy 1.9) uses the revised simplex method or interior-point method and handles millions of variables.