Week 6 — Convex Optimisation

Theory, Duality & CVXPY

Optimisation & Mathematical Methods for Economics The University of Edinburgh · School of Economics

---

Convex optimisation is special: every local minimum is global, and powerful algorithms solve even large problems efficiently. This week covers convex theory and introduces CVXPY, a Python library for specifying and solving convex programs.

1. Convex Sets and Functions

A set \(C\) is convex if \(\lambda \mathbf{x} + (1-\lambda)\mathbf{y} \in C\) for all \(\mathbf{x}, \mathbf{y} \in C\) and \(\lambda \in [0,1]\).

A function \(f\) is convex if \(\text{dom}(f)\) is convex and \(f(\lambda x + (1-\lambda)y) \leq \lambda f(x) + (1-\lambda)f(y)\).

Operations preserving convexity: non-negative weighted sums, composition with affine maps, pointwise maximum, perspective.

2. Lagrangian Duality

For \(\min f(\mathbf{x})\) s.t. \(g_i(\mathbf{x}) \leq 0\), \(h_j(\mathbf{x}) = 0\):

Lagrangian: \(L(\mathbf{x}, \boldsymbol{\mu}, \boldsymbol{\lambda}) = f(\mathbf{x}) + \sum \mu_i g_i(\mathbf{x}) + \sum \lambda_j h_j(\mathbf{x})\)

Dual function: \(d(\boldsymbol{\mu}, \boldsymbol{\lambda}) = \inf_\mathbf{x} L(\mathbf{x}, \boldsymbol{\mu}, \boldsymbol{\lambda})\)

Weak duality: \(d^* \leq p^*\) always. Strong duality: \(d^* = p^*\) (holds for convex problems under Slater’s condition).

import numpy as np

# Install cvxpy if needed
try:
    import cvxpy as cp
except ImportError:
    import subprocess
    subprocess.check_call(['pip', 'install', 'cvxpy', '-q', '--break-system-packages'])
    import cvxpy as cp

# Example: Least-squares with non-negativity constraints
# min ||Ax - b||^2 subject to x >= 0
np.random.seed(1)
m, n = 30, 10
A = np.random.randn(m, n)
b = np.random.randn(m)

x = cp.Variable(n)
objective = cp.Minimize(cp.sum_squares(A @ x - b))
constraints = [x >= 0]
prob = cp.Problem(objective, constraints)
prob.solve()

print(f"Status: {prob.status}")
print(f"Optimal value: {prob.value:.4f}")
print(f"Optimal x: {np.round(x.value, 3)}")

Status: optimal
Optimal value: 26.3132
Optimal x: [ 0.134  0.142 -0.     0.069 -0.     0.115  0.501  0.164 -0.     0.177]

# Economic example: Production planning with CVXPY
# A firm produces 3 goods using 2 inputs
# Maximise revenue subject to input availability

revenue = np.array([10, 15, 8])   # price per unit of each good
input_use = np.array([            # input requirements
    [2, 3, 1],   # input 1 per unit
    [1, 2, 3],   # input 2 per unit
])
capacity = np.array([120, 100])   # available inputs

q = cp.Variable(3)  # quantities
objective = cp.Maximize(revenue @ q)
constraints = [
    input_use @ q <= capacity,
    q >= 0
]
prob = cp.Problem(objective, constraints)
prob.solve()

print("Production planning solution:")
for i in range(3):
    print(f"  Good {i+1}: {q.value[i]:.2f} units")
print(f"\nMaximum revenue: ${prob.value:.2f}")
print(f"\nShadow prices (dual values):")
for i in range(2):
    print(f"  Input {i+1}: ${constraints[0].dual_value[i]:.2f}")

Production planning solution:
  Good 1: 52.00 units
  Good 2: 0.00 units
  Good 3: 16.00 units

Maximum revenue: $648.00

Shadow prices (dual values):
  Input 1: $4.40
  Input 2: $1.20

Exercises

Exercise 1: Formulate and solve a Markowitz portfolio optimisation problem in CVXPY: minimise portfolio variance subject to achieving a target return of 10% and weights summing to 1.

import cvxpy as cp
w = cp.Variable(4)
ret = mu @ w
risk = cp.quad_form(w, Sigma)
prob = cp.Problem(cp.Minimize(risk), [cp.sum(w) == 1, ret >= 0.10, w >= 0])
prob.solve()