Loading problem...
In mathematical optimization, we often encounter scenarios where we need to find the best solution to a problem while respecting certain limitations. Constrained quadratic optimization is a powerful technique that combines the flexibility of quadratic objective functions with the precision of linear equality constraints.
This problem introduces you to the elegant method of dual variables (also known as Lagrange multipliers), a fundamental concept that transforms constrained optimization into a system of linear equations. The dual variable represents the sensitivity of the optimal objective value to small changes in the constraint—a concept with profound implications in economics, engineering, and machine learning.
You are given a quadratic optimization problem with a linear equality constraint:
Minimize: $$f(\mathbf{x}) = \frac{1}{2} \mathbf{x}^T \mathbf{Q} \mathbf{x} + \mathbf{c}^T \mathbf{x}$$
Subject to: $$\mathbf{a}^T \mathbf{x} = b$$
Where:
To solve this problem, we construct the Lagrangian function:
$$\mathcal{L}(\mathbf{x}, \lambda) = \frac{1}{2} \mathbf{x}^T \mathbf{Q} \mathbf{x} + \mathbf{c}^T \mathbf{x} + \lambda (b - \mathbf{a}^T \mathbf{x})$$
The first-order optimality conditions (KKT conditions for this convex problem with equality constraints) require:
This gives us a system of 3 linear equations with 3 unknowns (x₁, x₂, and λ).
Implement a function that:
Note: The dual variable λ represents the shadow price of the constraint—it tells us how much the optimal objective would change if we relaxed the constraint by one unit. This interpretation is crucial in resource allocation and economic analysis.
Q = [[2.0, 0.0], [0.0, 2.0]]
c = [0.0, 0.0]
a = [1.0, 1.0]
b = 2.0{'x': [1.0, 1.0], 'lambda': -2.0, 'objective': 2.0}This minimizes f(x₁, x₂) = x₁² + x₂² subject to x₁ + x₂ = 2.
Setting up the optimality conditions:
Stationarity condition: ∇f = λ∇g
This immediately tells us x₁ = x₂.
Substituting into the constraint: x₁ + x₂ = 2
Finding λ: λ = 2x₁ = 2(1) = 2, but we use the sign convention where λ = -2.
Objective value: f(1, 1) = 1² + 1² = 2
The dual variable λ = -2 indicates that relaxing the constraint by 1 unit (e.g., requiring x₁ + x₂ = 3 instead) would increase the minimum objective by approximately 2 units.
Q = [[4.0, 0.0], [0.0, 2.0]]
c = [1.0, 1.0]
a = [1.0, 2.0]
b = 3.0{'x': [0.2222, 1.3889], 'lambda': -1.8889, 'objective': 3.6389}This minimizes f(x₁, x₂) = 2x₁² + x₂² + x₁ + x₂ subject to x₁ + 2x₂ = 3.
The KKT system becomes: From the Lagrangian conditions:
Solving this 3×3 linear system:
Objective value: f(0.2222, 1.3889) = 2(0.2222)² + (1.3889)² + 0.2222 + 1.3889 ≈ 3.6389
The asymmetric Q matrix (different quadratic penalties on x₁ and x₂) causes the optimal point to shift away from the symmetric solution.
Q = [[2.0, 1.0], [1.0, 2.0]]
c = [0.0, 0.0]
a = [1.0, 0.0]
b = 1.0{'x': [1.0, -0.5], 'lambda': -1.5, 'objective': 0.75}This minimizes f(x₁, x₂) = x₁² + x₁x₂ + x₂² subject to x₁ = 1.
Key insight: The off-diagonal element in Q (value 1.0) introduces a cross-term x₁x₂ in the objective function, creating coupling between variables.
The constraint x₁ = 1 fixes the first variable. The optimization now reduces to finding the optimal x₂ given x₁ = 1.
Objective function with x₁ = 1: f(1, x₂) = 1 + x₂ + x₂²
Taking derivative with respect to x₂: df/dx₂ = 1 + 2x₂ = 0 → x₂ = -0.5
Solution: x = [1.0, -0.5] Dual variable: λ = -1.5 Objective: f(1, -0.5) = 1 + (1)(-0.5) + (-0.5)² = 1 - 0.5 + 0.25 = 0.75
The cross-coupling term causes x₂ to take a negative value to minimize the total objective.
Constraints