Convexity and why it matters

One valley, one answer

A function is convex if the straight segment between any two points of its graph lies on or above the graph: $f(\theta\mathbf x+(1-\theta)\mathbf y)\le\theta f(\mathbf x)+(1-\theta)f(\mathbf y)$ for every $\theta\in[0,1]$ . For a twice-differentiable function there is a practical test: $f$ is convex exactly when its Hessian is positive semidefinite everywhere, meaning all eigenvalues are $\ge0$ . Sums of convex functions, positive multiples of them and the maximum of convex functions are convex again, which is how large convex objectives are built from small pieces.

H(\mathbf w)\succeq0\ \ \forall\,\mathbf w\ \Longrightarrow\ \nabla f(\mathbf w^{*})=0\ \Rightarrow\ f(\mathbf w^{*})=\min_{\mathbf w}f(\mathbf w)

(1)

Convexity is what makes optimisation reliable. Every local minimum is a global minimum, a zero gradient is enough to stop, and the answer does not depend on where the solver starts. If the function is strictly convex the minimiser is also unique, and if it is strongly convex, with curvature at least $\mu>0$ in every direction, gradient descent converges at the geometric rate you saw before. Without convexity none of this is guaranteed: the solver may stop in a valley that is not the deepest one.

A check and a counterexampleFor

f(x)=x^2

take the points

0

and

4

with

\theta=\tfrac12

. The midpoint value is

f(2)=4

, while the average of the end values is

(0+16)/2=8

; the gap of

4

is positive, as convexity demands. Now take

f(x,y)=x^2+4xy+y^2

. Its Hessian

\begin{pmatrix}2&4\\4&2\end{pmatrix}

has eigenvalues

6

and

-2

. One is negative, so

f

is not convex: the origin is a saddle point.

In finance the convex objectives include the portfolio variance $\mathbf w^{T}\Sigma\mathbf w$ (because a covariance matrix is positive semidefinite), least-squares losses, the $\ell_1$ norm $\lVert\mathbf w\rVert_1$ and the expected shortfall (CVaR) as a function of the weights. Value-at-risk, a cap on the number of non-zero weights and the Sharpe ratio taken as it stands are not convex. A sample covariance matrix estimated from fewer observations than assets is positive semidefinite but singular, so the variance is convex without being strictly convex, and many weight vectors tie for the minimum.

Hessian test: all eigenvalues $\ge0$ everywhere means convex; one negative eigenvalue means not convex.
Payoff: every local minimum is global, so the start point does not matter.
Building blocks: sums, positive multiples and maxima of convex functions stay convex.

Relax what is not convexWhen a requirement is not convex, such as at most

k

non-zero weights, a common move is to replace it with a convex cousin, here the

\ell_1

penalty. The relaxed problem is solved reliably and usually gives a good answer, but it is a different problem, so check the result against the original requirement before you use it.

Lab · what's graded

A convexity gap15 pts
The eigenvalue that breaks convexity15 pts
Which Hessian is convex15 pts
Convex objectives in finance15 pts
A zero gradient10 pts
Convexity vocabulary15 pts
Why solvers like convex problems15 pts

One valley, one answer

H(\mathbf w)\succeq0\ \ \forall\,\mathbf w\ \Longrightarrow\ \nabla f(\mathbf w^{*})=0\ \Rightarrow\ f(\mathbf w^{*})=\min_{\mathbf w}f(\mathbf w)

(1)

A check and a counterexampleFor

f(x)=x^2

take the points

0

and

4

with

\theta=\tfrac12

. The midpoint value is

f(2)=4

, while the average of the end values is

(0+16)/2=8

; the gap of

4

is positive, as convexity demands. Now take

f(x,y)=x^2+4xy+y^2

. Its Hessian

\begin{pmatrix}2&4\\4&2\end{pmatrix}

has eigenvalues

6

and

-2

. One is negative, so

f

is not convex: the origin is a saddle point.

Hessian test: all eigenvalues $\ge0$ everywhere means convex; one negative eigenvalue means not convex.
Payoff: every local minimum is global, so the start point does not matter.
Building blocks: sums, positive multiples and maxima of convex functions stay convex.

Relax what is not convexWhen a requirement is not convex, such as at most

k

non-zero weights, a common move is to replace it with a convex cousin, here the

\ell_1

penalty. The relaxed problem is solved reliably and usually gives a good answer, but it is a different problem, so check the result against the original requirement before you use it.

Lab · what's graded

A convexity gap15 pts
The eigenvalue that breaks convexity15 pts
Which Hessian is convex15 pts
Convex objectives in finance15 pts
A zero gradient10 pts
Convexity vocabulary15 pts
Why solvers like convex problems15 pts

One valley, one answer

Lab · what's graded

Log in to run your code.

Convexity and why it matters

One valley, one answer

Lab · what's graded

Log in to run your code.