Day 26: Constrained Optimisation & Lagrange Multipliers

Theory

The Lagrangian

To maximise or minimise $f(x)$ subject to $g(x) = c$ , form

\mathcal{L}(x, \lambda) = f(x) - \lambda\,(g(x) - c)

and solve $\nabla_x\mathcal{L} = 0$ together with the constraint. At the optimum, $\nabla f = \lambda\nabla g$ : the objective's gradient is parallel to the constraint's, so no feasible direction improves $f$ (geometrically, a level curve is tangent to the constraint). With several constraints, use one multiplier per constraint.

The shadow price

Let $V(c)$ be the optimal value. The envelope theorem says

\frac{dV}{dc} = \lambda^*,

so the multiplier is the marginal value of relaxing the constraint: the marginal utility of income, the marginal cost of output, the value of one more unit of budget.

Inequality constraints (KKT)

For $\min f(x)$ subject to $h(x) \le 0$ : $\nabla f + \mu\nabla h = 0$ , $\mu \ge 0$ , $h(x) \le 0$ and complementary slackness $\mu\,h(x) = 0$ . Either the constraint binds, or its multiplier is zero.

Where constraints appear in causal inference

Allocating a fixed budget across treatment and control arms, or across strata.
Synthetic control: weights that are non-negative and sum to one (Day 85).
Entropy balancing / calibration: weights closest to uniform that exactly match covariate means (Day 84).
Restricted least squares: imposing $R\beta = r$ .

Part 1 · Warm-up

Exercise 1 · A classic

Maximise $xy$ subject to $x + y = 10$ .

Show solution

$\mathcal L = xy - \lambda(x + y - 10)$ : $y = \lambda$ , $x = \lambda$ , so $x = y = 5$ , $\lambda = 5$ , value 25.

Exercise 2 · Closest point on a line

Minimise $x^2 + y^2$ subject to $x + 2y = 5$ .

Show solution

Step 1. Lagrangian: $\mathcal L = x^2 + y^2 - \lambda(x + 2y - 5)$ .

Step 2. FOCs: $2x = \lambda$ and $2y = 2\lambda$ , so $y = 2x$ .

Step 3. Constraint: $x + 2(2x) = 5 \Rightarrow x = 1$ , $y = 2$ , $\lambda = 2$ .

Answer: $(1, 2)$ with value 5: the point on the line closest to the origin (a projection, Day 20).

Exercise 3 · Cobb–Douglas demand

Maximise $U = x^{0.3}y^{0.7}$ with prices $p_x = 2$ , $p_y = 7$ and income $M = 100$ .

Show solution

Step 1. Cobb–Douglas spends the share $\alpha$ of income on $x$ and $1 - \alpha$ on $y$ (Exercise 6).

Step 2. $x = 0.3 \times 100/2 = 15$ .

Step 3. $y = 0.7 \times 100/7 = 10$ .

Answer: 15 units of $x$ and 10 of $y$ (spending $30 and $70).

Exercise 4 · Shadow price check

In Exercise 1 with constraint $x + y = c$ , compute $V(c)$ and verify $dV/dc = \lambda$ .

Show solution

$x = y = c/2$ , $V(c) = c^2/4$ , $dV/dc = c/2 = 5 = \lambda$ at $c = 10$ . ✓

Exercise 5 · A binding inequality

Minimise $(x - 3)^2$ subject to $x \le 2$ .

Show solution

The unconstrained minimum $x = 3$ is infeasible, so the constraint binds: $x = 2$ . KKT: $2(x - 3) + \mu = 0 \Rightarrow \mu = 2 \ge 0$ . ✓

Part 2 · Proofs

Exercise 6 · Cobb–Douglas demand

Derive the demand for $x$ when maximising $x^{\alpha}y^{1-\alpha}$ subject to $p_xx + p_yy = M$ .

Show solution

Step 1. Maximise the log, $\alpha\ln x + (1 - \alpha)\ln y$ .

Step 2. FOCs: $\alpha/x = \lambda p_x$ and $(1 - \alpha)/y = \lambda p_y$ .

Step 3. So $p_xx = \alpha/\lambda$ and $p_yy = (1 - \alpha)/\lambda$ ; adding, $M = 1/\lambda$ .

Step 4. Hence $x = \alpha M/p_x$ .

Exercise 7 · The envelope theorem

Prove $dV/dc = \lambda^*$ for $V(c) = \max f(x)$ s.t. $g(x) = c$ .

Show solution

Step 1. $V(c) = f(x^*(c))$ , so $V'(c) = \nabla f^{\top}\frac{dx^*}{dc} = \lambda^*\nabla g^{\top}\frac{dx^*}{dc}$ using the FOC.

Step 2. Differentiating the constraint $g(x^*(c)) = c$ gives $\nabla g^{\top}\frac{dx^*}{dc} = 1$ .

Step 3. So $V'(c) = \lambda^*$ .

Exercise 8 · Minimum-variance weights

Minimise $w^{\top}\Sigma w$ subject to $\mathbf 1^{\top}w = 1$ ( $\Sigma$ PD).

Show solution

Step 1. Lagrangian: $\mathcal L = w^{\top}\Sigma w - \lambda(\mathbf 1^{\top}w - 1)$ .

Step 2. FOC (Day 24 rules, $\Sigma$ symmetric): $2\Sigma w - \lambda\mathbf 1 = 0 \Rightarrow w = \frac\lambda2\Sigma^{-1}\mathbf 1$ .

Step 3. Impose the constraint: $\mathbf 1^{\top}w = \frac\lambda2\mathbf 1^{\top}\Sigma^{-1}\mathbf 1 = 1 \Rightarrow \frac\lambda2 = \frac{1}{\mathbf 1^{\top}\Sigma^{-1}\mathbf 1}$ .

Step 4. Substitute back:

w^* = \frac{\Sigma^{-1}\mathbf 1}{\mathbf 1^{\top}\Sigma^{-1}\mathbf 1}.

Step 5. With independent estimates, $\Sigma = \operatorname{diag}(v_j)$ and $w_j^* \propto 1/v_j$ : inverse-variance weighting (Day 8), the efficient way to pool estimates.

Exercise 9 · Restricted least squares

Minimise $\|y - Xb\|^2$ subject to $Rb = r$ and show

\tilde b = \hat\beta - (X^{\top}X)^{-1}R^{\top}\big[R(X^{\top}X)^{-1}R^{\top}\big]^{-1}(R\hat\beta - r).

Show solution

Step 1. Lagrangian (the factor 2 on $\lambda$ keeps the algebra tidy): $\mathcal L = \|y - Xb\|^2 + 2\lambda^{\top}(Rb - r)$ .

Step 2. FOC in $b$ : $-2X^{\top}(y - Xb) + 2R^{\top}\lambda = 0$ , i.e. $X^{\top}Xb = X^{\top}y - R^{\top}\lambda$ .

Step 3. Solve for $b$ : $\tilde b = \hat\beta - (X^{\top}X)^{-1}R^{\top}\lambda$ , where $\hat\beta$ is unrestricted OLS.

Step 4. Impose $R\tilde b = r$ : $R\hat\beta - R(X^{\top}X)^{-1}R^{\top}\lambda = r$ .

Step 5. Solve for the multiplier: $\lambda = \big[R(X^{\top}X)^{-1}R^{\top}\big]^{-1}(R\hat\beta - r)$ .

Step 6. Substitute into Step 3:

\tilde b = \hat\beta - (X^{\top}X)^{-1}R^{\top}\big[R(X^{\top}X)^{-1}R^{\top}\big]^{-1}(R\hat\beta - r).

The correction is large when $\hat\beta$ badly violates the restriction: the idea behind Wald and LR tests.

Exercise 10 · Optimal allocation between arms

With outcome sds $\sigma_1, \sigma_0$ and per-unit costs $c_1, c_0$ , minimise $\operatorname{Var}(\hat\tau) = \sigma_1^2/n_1 + \sigma_0^2/n_0$ subject to $c_1n_1 + c_0n_0 = B$ .

Show solution

Step 1. FOCs: $\sigma_1^2/n_1^2 = \lambda c_1$ and $\sigma_0^2/n_0^2 = \lambda c_0$ .

Step 2. Dividing,

\frac{n_1}{n_0} = \frac{\sigma_1}{\sigma_0}\sqrt{\frac{c_0}{c_1}}.

Step 3. Put more units where outcomes are noisier and where they are cheaper.

Step 4. With equal costs and variances, split evenly.

Part 3 · Applied

Exercise 11 · An expensive treatment

Treatment costs $40 per unit, control $10, the budget is $12,000 and outcome variances are equal. How many units go to each arm?

Show solution

Step 1. Optimal ratio (Exercise 10) with equal variances: $n_1/n_0 = \sqrt{c_0/c_1} = \sqrt{10/40} = 0.5$ .

Step 2. Budget: $40n_1 + 10n_0 = 12{,}000$ with $n_1 = 0.5n_0$ : $20n_0 + 10n_0 = 30n_0 = 12{,}000$ .

Step 3. $n_0 = 400$ , $n_1 = 200$ . Check: $40(200) + 10(400) = 12{,}000$ . ✓

Answer: 200 treated and 400 controls.

Exercise 12 · Neyman allocation across strata

Two strata have sizes 6,000 and 4,000 and outcome sds 10 and 30. Allocate a sample of 300 to minimise the variance of the stratified mean (allocation $n_h \propto N_h\sigma_h$ ).

Show solution

Step 1. Allocation weights $N_h\sigma_h$ : $6{,}000 \times 10 = 60{,}000$ and $4{,}000 \times 30 = 120{,}000$ .

Step 2. Shares: $60{,}000/180{,}000 = 1/3$ and $2/3$ .

Step 3. Sample: $300/3 = 100$ and $200$ .

Answer: 100 from the large, homogeneous stratum and 200 from the smaller but noisier one.

Exercise 13 · Cost minimisation

Produce $q = K^{0.5}L^{0.5} = 10$ at minimum cost with $w = 4$ , $r = 1$ .

Show solution

Step 1. Tangency (MRTS = input-price ratio): $\frac{MP_L}{MP_K} = \frac{0.5K^{0.5}L^{-0.5}}{0.5K^{-0.5}L^{0.5}} = \frac KL = \frac wr = 4$ , so $K = 4L$ .

Step 2. Output constraint: $\sqrt{4L \cdot L} = 2L = 10 \Rightarrow L = 5$ , $K = 20$ .

Step 3. Cost: $4(5) + 1(20) = 40$ .

Answer: 5 units of labour, 20 of capital, minimum cost 40.

Exercise 14 · Synthetic-control weights are not always unique

A treated region has pre-period outcome 3; donor regions have 1, 5 and 6. Find two different weight vectors with $w \ge 0$ , $\sum w = 1$ that reproduce 3 exactly.

Show solution

Step 1. We need $w_1(1) + w_2(5) + w_3(6) = 3$ with $w \ge 0$ and $w_1 + w_2 + w_3 = 1$ .

Step 2. Try $w = (0.5, 0.5, 0)$ : $0.5 + 2.5 = 3$ . ✓

Step 3. Try $w = (0.6, 0, 0.4)$ : $0.6 + 2.4 = 3$ . ✓

Answer: both fit perfectly. With one pre-period outcome, many weight vectors match exactly, which is why synthetic control matches many pre-periods and why penalised versions exist.

Exercise 15 · Entropy-balancing weights

Minimise $\sum_iw_i\ln(w_i/q_i)$ subject to $\sum_iw_i = 1$ and $\sum_iw_ix_i = \bar x_{\text{target}}$ . Show the solution has the form $w_i \propto q_i\,e^{\lambda x_i}$ .

Show solution

Step 1. Lagrangian:

\mathcal L = \sum_iw_i\ln(w_i/q_i) - \lambda_0\Big(\sum_iw_i - 1\Big) - \lambda\Big(\sum_iw_ix_i - \bar x_{\text{target}}\Big).

Step 2. FOC for $w_i$ : $\ln(w_i/q_i) + 1 - \lambda_0 - \lambda x_i = 0$ .

Step 3. Solve: $w_i = q_i\,e^{\lambda_0 - 1}\,e^{\lambda x_i}$ ; the factor $e^{\lambda_0 - 1}$ is the same for everyone, so $w_i \propto q_ie^{\lambda x_i}$ .

Step 4. Choose $\lambda$ so the weighted mean of $x$ equals the target, and $\lambda_0$ so the weights sum to one.

Answer: entropy-balancing weights tilt the base weights exponentially in the covariate (Day 84).

Verify in Python

import numpy as np
from scipy import optimize

res = optimize.minimize(lambda v: -(v[0]**0.3 * v[1]**0.7), [10, 10],
                        constraints={"type": "eq", "fun": lambda v: 2 * v[0] + 7 * v[1] - 100})
print("Cobb-Douglas demand:", res.x.round(3))

Sig = np.array([[100, 60], [60, 400.]]); one = np.ones(2)
w = np.linalg.solve(Sig, one); w /= w.sum()
print("minimum-variance weights:", w.round(4))

n0 = 12_000 / (40 * 0.5 + 10); print("arm sizes (n1, n0):", n0 * 0.5, n0)
N, s = np.array([6000, 4000]), np.array([10, 30]); print("Neyman allocation:", 300 * N * s / (N * s).sum())

# Entropy balancing: tilt uniform weights on x so the weighted mean is 4
x = np.array([1, 2, 3, 4, 5, 6.]); q = np.ones(6) / 6
lam = optimize.brentq(lambda l: (q * np.exp(l * x) * x).sum() / (q * np.exp(l * x)).sum() - 4, -5, 5)
wts = q * np.exp(lam * x); wts /= wts.sum()
print("entropy-balancing weights:", wts.round(3), " weighted mean:", round(wts @ x, 4))

Key takeaways

At a constrained optimum, the objective's gradient is a multiple of the constraint's; the multiple is the shadow price.
Budget allocation in experiments and stratified samples is a Lagrange problem: favour noisy and cheap arms.
Weighting estimators (minimum variance, synthetic control, entropy balancing) are constrained optimisation problems.

Day 26. Constrained Optimisation & Lagrange Multipliers

Theory

The Lagrangian

The shadow price

Inequality constraints (KKT)

Where constraints appear in causal inference

Part 1 · Warm-up

Exercise 1 · A classic

Exercise 2 · Closest point on a line

Exercise 3 · Cobb–Douglas demand

Exercise 4 · Shadow price check

Exercise 5 · A binding inequality

Part 2 · Proofs

Exercise 6 · Cobb–Douglas demand

Exercise 7 · The envelope theorem

Exercise 8 · Minimum-variance weights

Exercise 9 · Restricted least squares

Exercise 10 · Optimal allocation between arms

Part 3 · Applied

Exercise 11 · An expensive treatment

Exercise 12 · Neyman allocation across strata

Exercise 13 · Cost minimisation

Exercise 14 · Synthetic-control weights are not always unique

Exercise 15 · Entropy-balancing weights

Verify in Python

Key takeaways

Simulation Lab: Constrained Optimum: Budget & Indifference