Constrained optimization and KKT

Optimising under rules

Real portfolios obey rules: the weights add up to one, no short sales, a cap on turnover. A constrained problem is $\min f(\mathbf w)$ subject to equalities $h(\mathbf w)=0$ and inequalities $g(\mathbf w)\le0$ . With one equality, the best feasible point is where $\nabla f$ points straight through the constraint surface, because any sideways component could be used to improve $f$ without leaving the surface. That is the Lagrange condition $\nabla f+\lambda\nabla h=0$ , and the number $\lambda$ is the Lagrange multiplier. Collecting everything in the Lagrangian $L=f+\lambda h+\mu g$ turns the constrained problem into the search for a stationary point of $L$ .

\nabla f+\lambda\nabla h+\mu\nabla g=0,\qquad h=0,\quad g\le0,\qquad \mu\ge0,\qquad \mu\,g=0

(1)

For inequalities the full set of conditions, named after Karush, Kuhn and Tucker, has four parts: stationarity of the Lagrangian, primal feasibility (the constraints hold), dual feasibility ( $\mu\ge0$ ) and complementary slackness ( $\mu g=0$ ). Complementary slackness says each inequality is either inactive, with $g<0$ and $\mu=0$ , so it does not matter, or active, with $g=0$ and $\mu>0$ , so it acts like an equality. For a convex problem these conditions are necessary and sufficient for a global optimum. The multiplier is also a price: it is the rate at which the best value of $f$ improves when the constraint is relaxed by one unit.

Two small examplesMinimise

x^2+y^2

subject to

x+y=1

. The Lagrange conditions

2x+\lambda=0

and

2y+\lambda=0

give

x=y=-\lambda/2

, and the constraint then gives

\lambda=-1

and

x=y=0.5

, with value

0.5

. If the constraint is relaxed to

x+y=c

, the best value becomes

c^2/2

, whose slope at

c=1

1=-\lambda

. Next, minimise

(x-2)^2

subject to

x\le1

. The unconstrained minimum

x=2

breaks the rule, so the constraint is active at

x=1

and

2(x-2)+\mu=0

gives

\mu=2>0

. With the rule

x\le3

instead, the unconstrained minimum is allowed and

\mu=0

The minimum-variance portfolio is the model case: minimise $\mathbf w^{T}\Sigma\mathbf w$ subject to $\mathbf 1^{T}\mathbf w=1$ . The Lagrange condition $2\Sigma\mathbf w+\lambda\mathbf 1=0$ gives $\mathbf w\propto\Sigma^{-1}\mathbf 1$ . For two uncorrelated assets with variances $0.04$ and $0.09$ the weights are proportional to $1/0.04=25$ and $1/0.09=11.1$ , so $w_1=0.692$ , $w_2=0.308$ and the portfolio variance is $1/(25+11.1)=0.0277$ . The multiplier equals $-2$ times that minimum variance. In a real portfolio a long-only rule or a turnover cap has its own multiplier, and a large $\mu$ tells you that rule is costing you a lot.

Equality constraint: $\nabla f+\lambda\nabla h=0$ together with $h=0$ .
Inequality: $\mu\ge0$ and $\mu g=0$ ; active means $g=0$ , inactive means $\mu=0$ .
Price: a multiplier is the sensitivity of the best value to a relaxation of its constraint.

Check feasibility and signsAfter solving, verify the answer against all four conditions. The most common slips are a multiplier with the wrong sign for an inequality (it must be

\mu\ge0

when constraints are written

g\le0

) and an active constraint that was assumed inactive. Sign conventions differ between textbooks and libraries, so always read which form your solver expects.

Lab · what's graded

The multiplier10 pts
The optimal point10 pts
Relaxing the constraint10 pts
A two-asset minimum-variance weight15 pts
The minimum variance15 pts
The four KKT conditions15 pts
An active constraint10 pts
What a multiplier tells you15 pts

Optimising under rules

\nabla f+\lambda\nabla h+\mu\nabla g=0,\qquad h=0,\quad g\le0,\qquad \mu\ge0,\qquad \mu\,g=0

(1)

Two small examplesMinimise

x^2+y^2

subject to

x+y=1

. The Lagrange conditions

2x+\lambda=0

and

2y+\lambda=0

give

x=y=-\lambda/2

, and the constraint then gives

\lambda=-1

and

x=y=0.5

, with value

0.5

. If the constraint is relaxed to

x+y=c

, the best value becomes

c^2/2

, whose slope at

c=1

1=-\lambda

. Next, minimise

(x-2)^2

subject to

x\le1

. The unconstrained minimum

x=2

breaks the rule, so the constraint is active at

x=1

and

2(x-2)+\mu=0

gives

\mu=2>0

. With the rule

x\le3

instead, the unconstrained minimum is allowed and

\mu=0

Equality constraint: $\nabla f+\lambda\nabla h=0$ together with $h=0$ .
Inequality: $\mu\ge0$ and $\mu g=0$ ; active means $g=0$ , inactive means $\mu=0$ .
Price: a multiplier is the sensitivity of the best value to a relaxation of its constraint.

Check feasibility and signsAfter solving, verify the answer against all four conditions. The most common slips are a multiplier with the wrong sign for an inequality (it must be

\mu\ge0

when constraints are written

g\le0

) and an active constraint that was assumed inactive. Sign conventions differ between textbooks and libraries, so always read which form your solver expects.

Lab · what's graded

The multiplier10 pts
The optimal point10 pts
Relaxing the constraint10 pts
A two-asset minimum-variance weight15 pts
The minimum variance15 pts
The four KKT conditions15 pts
An active constraint10 pts
What a multiplier tells you15 pts

Constrained optimization and KKT

Optimising under rules

Lab · what's graded

Log in to run your code.

Constrained optimization and KKT

Optimising under rules

Lab · what's graded

Log in to run your code.