Quadratic Programming
Quadratic Programming: Standard Form
Positive Definite Hessian
Active Set Methods
Interior Point Methods
Wolfe Dual
Ridge Regression as QP
SVM as QP
Python Implementation: cvxpy
import cvxpy as cp
import numpy as np
# Generate data for a QP: min 0.5*x'*Q*x + c'*x
np.random.seed(42)
n = 5
Q = np.random.randn(n, n)
Q = Q.T @ Q # Make positive definite
c = np.random.randn(n)
# Decision variable
x = cp.Variable(n)
# Objective
objective = cp.Minimize(0.5 * cp.quad_form(x, Q) + c @ x)
# Constraints
A = np.random.randn(3, n)
b = np.ones(3)
constraints = [A @ x <= b, cp.sum(x) == 1]
# Solve
prob = cp.Problem(objective, constraints)
prob.solve()
print(f"Optimal value: {prob.value:.4f}")
print(f"Optimal x: {x.value}")
print(f"Status: {prob.status}")
print(f"Solver: {prob.solver_stats.solver_name}")
Python Implementation: scipy
from scipy.optimize import minimize
import numpy as np
np.random.seed(42)
n = 5
Q = np.random.randn(n, n)
Q = Q.T @ Q
c = np.random.randn(n)
# Unconstrained QP via scipy
def objective(x):
return 0.5 * x @ Q @ x + c @ x
def gradient(x):
return Q @ x + c
def hessian(x):
return Q
x0 = np.zeros(n)
result = minimize(objective, x0, jac=gradient, hess=hessian, method='trust-constr')
print(f"Optimal value: {result.fun:.4f}")
print(f"Optimal x: {result.x}")
print(f"Converged: {result.success}")
# Constrained QP with bounds
from scipy.optimize import minimize
bounds = [(0, 1) for _ in range(n)]
eq_constraint = {'type': 'eq', 'fun': lambda x: np.sum(x) - 1}
result2 = minimize(objective, x0, jac=gradient, hess=hessian,
method='SLSQP', bounds=bounds, constraints=[eq_constraint])
print(f"Constrained optimal: {result2.fun:.4f}")
Applications in AI / Machine Learning
Common Mistakes
| Mistake | Why It Fails | Correct Approach |
|---|---|---|
| Using a non-symmetric Q | Gradient is ½(Q + Qᵀ)x, not Qx | Symmetrize: Q <- ½(Q + Qᵀ) before solving |
| Ignoring positive semi-definiteness | Non-convex QP may have many local minima | Verify Q ≽ 0 via eigenvalue decomposition; use global solver if not |
| Confusing ½ convention | Gradient off by factor of 2 | Always verify: ∇(½xᵀQx) = Qx, not 2Qx |
| Not scaling constraints | Poorly scaled A, b cause numerical issues | Normalize rows of A so ‖aᵢ‖ ≈ 1 |
| Assuming unbounded feasible region | QP may be infeasible or unbounded | Check feasibility before solving; add bounds |
| Using QP for non-quadratic objectives | QP solver assumes quadratic curvature | Use nonlinear solver (IPOPT, SNOPT) for general NLP |
| Ignoring warm-starting | Repeated QPs (MPC, online learning) waste time | Use previous solution as warm start for next solve |