Convex Optimization
Convex optimization bridges pure mathematics and practical ML engineering. While non-convex problems (like training deep neural networks) dominate headlines, convex problems form the foundation: they have efficient solvers with provable guarantees, they appear as subroutines in larger algorithms, and many heuristics for non-convex problems work by solving convex relaxations. Mastering this topic means understanding why some optimization problems are "easy" and others are "hard," and having the tools to transform hard problems into tractable ones.
Convex Set
Convex Function
First-Order Condition
Second-Order Condition
Common Convex and Non-Convex Functions
| Function | Convex? | Notes |
|---|---|---|
| Yes | Constant functions are convex (and concave) | |
| Yes | Strictly convex | |
| Yes | Strictly convex, | |
| Yes | Strictly convex on | |
| Yes | Convex but not differentiable at 0 | |
| Yes | Strictly convex, though | |
| No | Inflection point at | |
| No | Concave and convex regions | |
| No | On ; convex on | |
| Yes | On (positive definite cone) | |
| Yes | Sum of convex functions | |
| No | Bilinear (saddle-shaped) |
Properties of Convex Functions
Strongly Convex Functions
Convex Optimization Problem
Common Convex Problems
Linear Programming (LP)
Quadratic Programming (QP)
Second-Order Cone Programming (SOCP)
Semidefinite Programming (SDP)
Problem Hierarchy
Duality
Weak and Strong Duality
Dual Interpretation in ML
Python Implementation
Using CVXPY
import cvxpy as cp
import numpy as np
# ============================================
# Example 1: Linear Program
# Minimize cost subject to constraints
# ============================================
n = 4 # number of variables
c = np.array([1.0, 2.0, 3.0, 4.0]) # cost vector
A = np.array([[1, 1, 0, 0],
[0, 0, 1, 1],
[1, 0, 1, 0]])
b = np.array([10.0, 8.0, 12.0])
x = cp.Variable(n)
constraints = [A @ x <= b, x >= 0]
objective = cp.Minimize(c @ x)
prob = cp.Problem(objective, constraints)
prob.solve()
print(f"Status: {prob.status}")
print(f"Optimal value: {prob.value:.4f}")
print(f"Optimal x: {x.value}")
# ============================================
# Example 2: Quadratic Program (Ridge Regression)
# ============================================
np.random.seed(42)
m, n = 50, 10
X = np.random.randn(m, n)
y = X @ np.random.randn(n) + 0.1 * np.random.randn(m)
w = cp.Variable(n)
lam = 0.5 # regularization parameter
objective = cp.Minimize(0.5 * cp.sum_squares(y - X @ w) + lam * cp.squares(w))
prob = cp.Problem(objective)
prob.solve()
print(f"\nRidge regression:")
print(f"Optimal w: {w.value[:3]}...")
print(f"Optimal loss: {prob.value:.4f}")
# ============================================
# Example 3: Second-Order Cone Program
# ============================================
x_socp = cp.Variable(3)
A_socp = np.array([[1, 0, 0], [0, 1, 0]])
b_socp = np.array([0.5, 0.5])
c_socp = np.array([1.0, 2.0, 3.0])
objective = cp.Minimize(c_socp @ x_socp)
constraints = [cp.norm(A_socp @ x_socp - b_socp, 2) <= 1.0]
prob = cp.Problem(objective, constraints)
prob.solve()
print(f"\nSOCP:")
print(f"Optimal value: {prob.value:.4f}")
print(f"Optimal x: {x_socp.value}")
# ============================================
# Example 4: Semidefinite Program
# ============================================
X_sdp = cp.Variable((3, 3), symmetric=True)
C = np.array([[1, 0, 0], [0, 2, 0], [0, 0, 3]])
A1 = np.array([[1, 0, 0], [0, 0, 0], [0, 0, 0]])
objective = cp.Minimize(cp.trace(C @ X_sdp))
constraints = [cp.trace(A1 @ X_sdp) == 1, X_sdp >> 0] # X >> 0 means PSD
prob = cp.Problem(objective, constraints)
prob.solve()
print(f"\nSDP:")
print(f"Optimal value: {prob.value:.4f}")
print(f"X is PSD: {np.all(np.linalg.eigvals(X_sdp.value) > -1e-8)}")
Using SciPy
from scipy.optimize import minimize, LinearConstraint, NonlinearConstraint
# ============================================
# Example 1: Unconstrained convex function
# ============================================
f = lambda x: (x[0] - 1)**2 + (x[1] - 2)**2
grad_f = lambda x: np.array([2*(x[0] - 1), 2*(x[1] - 2)])
result = minimize(f, x0=[0.0, 0.0], jac=grad_f, method='L-BFGS-B')
print(f"Unconstrained minimum: x = {result.x}, f(x) = {result.fun:.6f}")
# ============================================
# Example 2: Linear constraints (box constraints)
# ============================================
f2 = lambda x: (x[0] - 2)**2 + (x[1] - 3)**2
bounds = [(0, 4), (0, 4)]
result = minimize(f2, x0=[0, 0], bounds=bounds, method='L-BFGS-B')
print(f"Box-constrained: x = {result.x}, f(x) = {result.fun:.6f}")
# ============================================
# Example 3: Equality and inequality constraints
# ============================================
f3 = lambda x: x[0]**2 + x[1]**2 + x[2]**2
jac_f3 = lambda x: np.array([2*x[0], 2*x[1], 2*x[2]])
constraints = [
{'type': 'eq', 'fun': lambda x: x[0] + x[1] + x[2] - 1},
{'type': 'ineq', 'fun': lambda x: x[0] - 0.1}, # x[0] >= 0.1
{'type': 'ineq', 'fun': lambda x: x[1] - 0.1}, # x[1] >= 0.1
]
result = minimize(f3, x0=[1/3, 1/3, 1/3], jac=jac_f3, constraints=constraints, method='SLSQP')
print(f"Constrained: x = {result.x}, f(x) = {result.fun:.6f}")
Applications in AI/ML
Support Vector Machines
Ridge Regression (Tikhonov Regularization)
The closed-form solution is . This is a strictly convex problem (quadratic with ), guaranteeing a unique global minimum. Ridge regression is an unconstrained QP and is convex for any .
LASSO Regression
LASSO is convex (the L1 norm is convex) but not differentiable at . It promotes sparsity β many coefficients are driven exactly to zero, performing automatic feature selection. The proximal gradient method (ISTA/FISTA) is the standard solver.
Logistic Regression
Neural Network Training (Non-Convex but Informed)
Common Mistakes
| Mistake | Why It's Wrong | Correct Approach |
|---|---|---|
| Assuming means convex everywhere | is necessary for convexity, but a function can be convex even if at isolated points (e.g., ) | Check for all in the domain |
| Confusing convex and concave | Many people mix up "convex up" vs "convex down" | Convex = bowl-shaped (holds water); concave = umbrella-shaped |
| Treating local minima as global minima in non-convex problems | Local minima in non-convex problems may be far from global minima | Use convex relaxations, multi-start, or second-order methods |
| Forgetting that equality constraints must be affine | does NOT define a convex feasible set | Nonlinear equalities create non-convex manifolds |
| Ignoring Slater's condition | Strong duality requires strict feasibility | Verify and |
| Assuming all norms lead to convex problems | Some non-convex norms (like ) do not | Use , , or other convex norms |
| Using gradient descent without checking Lipschitz continuity | Non-Lipschitz gradients can cause divergence | Verify or bound the Lipschitz constant |
| Not checking if the Hessian is PSD | Using Newton's method on a non-convex function may find saddle points | Check eigenvalues of or use trust-region methods |
| Assuming the sum of convex functions is always strictly convex | Sum of convex functions is convex, but may not be strictly convex | is convex but not strictly convex |
| Forgetting perspective scaling | is convex in but many miss this | Use perspective to handle fractional objectives |
Interview Questions
Q1: What is the difference between convex and strictly convex?
Q2: Why are convex problems easier to solve than non-convex problems?
Q3: What is Slater's condition and why does it matter?
Q4: How does strong convexity improve convergence?
Q5: Explain the dual of an SVM and its significance.
Q6: What happens when strong duality does not hold?
Practice Problems
Problem 1: Verify Convexity
Problem 2: Duality Gap
Problem 3: Ridge Regression Closed Form
Problem 4: Strong Convexity Certificate
Quick Reference
Cross-References
- Constrained Optimization: KKT conditions, penalty methods, and interior-point methods -> Constrained Optimization
- Gradient Descent: First-order methods for convex optimization -> Gradient Descent
- Newton's Method: Second-order methods using Hessian curvature -> Newton's Method
- Linear Algebra: Positive Definite Matrices: Hessian and PSD conditions for convexity -> Positive Definite
- Linear Algebra: Norms: Norms used in regularization constraints -> Norms
- Matrix Calculus: Derivatives of matrix-valued functions for SDP and SVM -> Matrix Calculus
- Linear Programming: Specialized methods for LP problems -> Linear Programming
- Quadratic Programming: Specialized methods for QP problems -> Quadratic Programming
- Lagrange Multipliers: Foundation for duality and KKT -> Lagrange Multipliers
- Multivariable Calculus: Gradients, Jacobians, and Hessians -> Multivariable Calculus