4.5.3 Convex functions and convex problems

Convex sets

Lessons 4.5.1 and 4.5.2 produced candidates and then had to compare them. Some problems need no comparison: a candidate that passes the conditions is the answer. Those are the convex problems, and they start with a shape.

A set of points is convex when the whole straight segment between any two of its points, $P$ and $Q$ , lies in the set. The points of the segment are $tP + (1 - t)Q$ for $t$ from 0 to 1 (lesson 3.1.1). Here $t = 1$ gives $P$ , $t = 0$ gives $Q$ , and $t = \frac{1}{2}$ the midpoint.

Convex: a line, a half-plane such as $x + y \ge 3$ , a disc, and the triangle $a \ge 0$ , $b \ge 0$ , $a + b \le 1$ .
Not convex: the ring $1 \le x^2 + y^2 \le 4$ . The points $(-1.5, 0)$ and $(1.5, 0)$ are in it, but their midpoint, the origin, is in the hole.
Not convex: a circle, the curve $x^2 + y^2 = 5$ of lesson 4.5.1. The midpoint of $(1, 2)$ and $(-1, -2)$ is the origin, which is not on the circle.

A convex set holds every segment between its points. The ring is not convex: the segment from $P$ to $Q$ crosses the hole.

Rule: Linear constraints give convex sets

\begin{gathered} \mathbf{a} \cdot \mathbf{x} \le c, \quad \mathbf{a} \cdot \mathbf{x} = c \\[4pt] \text{and any list of them} \end{gathered}

Each linear inequality gives a half-plane (a half-space in more variables), and each linear equation a line or plane. The points meeting every constraint of a list form a convex set: a segment inside each set is inside all of them.

Q

import numpy as np def in_triangle(p): return p[0] >= 0 and p[1] >= 0 and p[0] + p[1] <= 1 def in_ring(p): return 1 <= p[0]**2 + p[1]**2 <= 4 ts = np.linspace(0, 1, 11) # 11 points along each segment P, Q = np.array([0.8, 0.1]), np.array([0.05, 0.7]) print(all(bool(in_triangle(t * P + (1 - t) * Q)) for t in ts)) P, Q = np.array([-1.5, 0.0]), np.array([1.5, 0.0]) print([bool(in_ring(t * P + (1 - t) * Q)) for t in ts])

⌘/Ctrl + Enter runs the cell

Convex functions

A function is convex when every chord of its graph lies on or above the graph. Between two inputs, the function is never above the straight line joining its two values.

Rule: Convex function

\begin{gathered} f\big(tP + (1 - t)Q\big) \\ \le t\,f(P) + (1 - t)\,f(Q) \\[4pt] \text{for every } P, Q \text{ and } 0 \le t \le 1 \end{gathered}

The left side is the function partway between $P$ and $Q$ ; the right side is the chord at the same place. A function is concave when $-f$ is convex. Lesson 2.4.2's "concave up" is this convex.

Take $f(x) = x^2$ between $-1$ and 3, where $f = 1$ and 9. At $x = 1$ , halfway, the curve is at 1 and the chord at 5.

$t$	0.25	0.5	0.75
$x = t(-1) + (1 - t)\,3$	2	1	0
curve $f(x)$	4	1	0
chord $t\,f(-1) + (1 - t)\,f(3)$	7	5	3

Now take $q(x) = x^4 - 4x^2 + x$ . It has a global minimum, the lowest value anywhere, $-5.4442$ at $x = -1.473$ , and a local one, lowest only nearby, $-2.6186$ at $x = 1.347$ . The chord between them passes under the hump, so $q$ is not convex: at $x = 0$ the curve is 0 and the chord $-3.9682$ .

A convex function lies under each of its chords. A function with two valleys has a chord that passes under the hump between them.

The tests

Checking every chord is impossible, but derivatives do it for you.

One variable: $f$ is convex where $f''(x) \ge 0$ at every point (lesson 2.4.2). For $q$ , $q''(x) = 12x^2 - 8$ , which is $-8$ at 0: the hump bends down.
Several variables: $f$ is convex where its Hessian $H$ (lesson 4.3.1) is positive semidefinite at every point. Lesson 3.7.1's eigenvalue test checks that: every eigenvalue of $H$ is $\ge 0$ .

A convex function also lies on or above each of its tangent planes (lesson 4.2.2), as lesson 2.4.2's concave-up curves lie above their tangents. The bowl $x^2 + 2y^2$ has tangent plane $3 + 2(x - 1) + 4(y - 1)$ at $(1, 1)$ . The bowl is above it by 3 at $(0, 0)$ , by 9 at $(2, -1)$ and by 6 at $(3, 2)$ .

Rule: Convexity tests

\begin{gathered} f''(x) \ge 0 \text{ for every } x \\[4pt] H \text{ positive semidefinite everywhere} \end{gathered}

Either test shows that $f$ is convex on a convex set. With $H$ positive definite everywhere, $f$ is strictly convex: every chord lies strictly above the graph, except at its ends.

$f(x, y)$	$H$	eigenvalues	convex?
$x^2 + 2y^2$	$\begin{pmatrix} 2 & 0 \\ 0 & 4 \end{pmatrix}$	2, 4	yes, strictly
$(x + y)^2$	$\begin{pmatrix} 2 & 2 \\ 2 & 2 \end{pmatrix}$	0, 4	yes, not strictly
$x^2 - y^2$	$\begin{pmatrix} 2 & 0 \\ 0 & -2 \end{pmatrix}$	$-2$ , 2	no: a saddle
$x^3 - 3x + y^2$	$\begin{pmatrix} 6x & 0 \\ 0 & 2 \end{pmatrix}$	$6x$ , 2	only where $x \ge 0$

A linear function such as $3x - y$ has $H = 0$ , whose eigenvalues are 0 and 0. It is convex and concave at once.

x^2

from scipy.optimize import brentq def f(x): return x**2 for t in [0.25, 0.5, 0.75]: x = t * -1 + (1 - t) * 3 print(t, x, f(x), t * f(-1) + (1 - t) * f(3)) def q(x): return x**4 - 4 * x**2 + x def dq(x): return 4 * x**3 - 8 * x + 1 lo, hi = brentq(dq, -2, -1), brentq(dq, 1, 2) print(round(lo, 4), round(q(lo), 4), round(hi, 4), round(q(hi), 4)) chord0 = q(lo) + (q(hi) - q(lo)) * (0 - lo) / (hi - lo) print(q(0), round(chord0, 4), 12 * 0**2 - 8)

⌘/Ctrl + Enter runs the cell

(1, 0)

import numpy as np hessians = { "x^2 + 2y^2": lambda x, y: [[2, 0], [0, 4]], "(x + y)^2": lambda x, y: [[2, 2], [2, 2]], "x^2 - y^2": lambda x, y: [[2, 0], [0, -2]], "x^3 - 3x + y^2": lambda x, y: [[6 * x, 0], [0, 2]], } for name, H in hessians.items(): for point in [(1, 0), (-1, 0)]: lam = np.linalg.eigvalsh(np.array(H(*point), dtype=float)) print(name, point, np.round(lam, 4) + 0.0) def f(x, y): return x**2 + 2 * y**2 def tangent(x, y): # the tangent plane at (1, 1) return 3 + 2 * (x - 1) + 4 * (y - 1) for p in [(0, 0), (2, -1), (3, 2)]: print(p, f(*p), tangent(*p), f(*p) - tangent(*p))

⌘/Ctrl + Enter runs the cell

Convex problems

A convex problem minimises a convex function over a convex set. Its constraints may be inequalities $g \le c$ with $g$ convex, and linear equations.

Rule: Convex problems

\begin{gathered} \text{local minimum} = \text{global minimum} \\[4pt] \text{KKT point} = \text{minimum} \end{gathered}

In a convex problem every local minimum is global, and any point that passes the KKT conditions of lesson 4.5.2 is a minimum. If $f$ is strictly convex, there is at most one minimum point.

The picture behind it: a convex function has no hump, so it cannot have a second, lower valley. The Proof Gym proves it.

A search can get stuck when the problem is not convex. A local search such as scipy.optimize.minimize walks downhill from where it starts. On $q$ , starts at 1 and 0.5 end at the local minimum 1.347; only the start $-1$ finds the global one.

In a convex problem one candidate settles it. Minimise $x + 2y$ over the disc $x^2 + y^2 \le 5$ : a linear function over a convex set.

Lesson 4.5.1's two candidates on the circle were $(1, 2)$ with $\lambda = \frac{1}{2}$ and $(-1, -2)$ with $\lambda = -\frac{1}{2}$ . A $\le$ constraint needs $\lambda \le 0$ (lesson 4.5.2), so $(-1, -2)$ passes, and convexity says it is the minimum, $-5$ , without comparing values.

q

import numpy as np from scipy.optimize import minimize def q(v): return v[0]**4 - 4 * v[0]**2 + v[0] for start in [1.0, 0.5, -1.0]: r = minimize(q, [start]) print(start, round(r.x[0], 4), round(r.fun, 4)) disc = [{"type": "ineq", "fun": lambda v: 5 - v[0]**2 - v[1]**2}] for start in [[0.0, 0.0], [1.0, 2.0], [2.0, -1.0]]: r = minimize(lambda v: v[0] + 2 * v[1], start, constraints=disc, method="SLSQP", options={"ftol": 1e-12}) print(start, np.round(r.x, 4) + 0.0, round(r.fun, 4))

⌘/Ctrl + Enter runs the cell

Flat bottoms, and no bottom

Convexity promises that minima are global, not that there is exactly one, or any.

Semidefinite: a flat bottom. $(x + y)^2$ is convex but not strictly. It is 0 at every point of the line $x + y = 0$ , such as $(1, -1)$ and $(-2, 2)$ : infinitely many minimum points, all with the same value.
No minimum. $e^{-x}$ is convex, since its second derivative $e^{-x}$ is positive, but it only falls towards 0: 0.006738 at 5, 0.000045 at 10. A linear function on a whole plane has no minimum either.

Quadratic forms with linear constraints

Take $f(\mathbf{x}) = \mathbf{x}^\top A\mathbf{x}$ with $A$ symmetric (lesson 3.7.1). Its Hessian is the constant matrix $2A$ . So $f$ is convex exactly when $A$ is positive semidefinite, and strictly convex when $A$ is positive definite.

Add linear constraints, which give a convex set. The result is a convex problem, and when $A$ is positive definite it has at most one minimum. That is why lesson 4.5.1's linear system for $x^2 + 2y^2 + 3z^2$ , with $A = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 3 \end{pmatrix}$ , gave the one global minimum.

Case study 4.5.5 relies on this. A portfolio's variance is $\mathbf{w}^\top\Sigma\mathbf{w}$ , a covariance matrix $\Sigma$ is positive semidefinite (lesson 3.7.1), and budgets and target returns are linear constraints.

\Sigma

import numpy as np sigma = np.array([0.12, 0.18, 0.25]) R = np.array([[1.0, 0.3, 0.1], [0.3, 1.0, 0.5], [0.1, 0.5, 1.0]]) Sigma = np.diag(sigma) @ R @ np.diag(sigma) print(np.round(np.linalg.eigvalsh(Sigma), 6)) J = np.array([[1.0, 1.0], [1.0, 1.0]]) for p in [(1, -1), (-2, 2), (0.5, -0.5)]: p = np.array(p, dtype=float) print(p, p @ J @ p)

⌘/Ctrl + Enter runs the cell

Common mistakes

One minimum does not make a function convex. The valley $(1 - x)^2 + 5(y - x^2)^2$ has one critical point, its minimum $(1, 1)$ , yet its Hessian at $(0, 1)$ has eigenvalue $-18$ . The chord from $(-1, 1)$ to $(1, 1)$ passes under the graph: 2 at the midpoint, where $f = 6$ .
Test $H$ everywhere, not at one point. $x^3 - 3x + y^2$ has a positive definite $H$ at $(1, 0)$ , yet it is not convex where $x < 0$ .
Semidefinite allows a flat bottom. $(x + y)^2$ has a whole line of minima.
A curved equation is not a convex constraint. A circle is not a convex set; only linear equations keep a problem convex.
Maximising a convex function is not a convex problem. Maximising a concave function is, since it is minimising $-f$ .
Convex does not promise a minimum. $e^{-x}$ falls for ever.

(0, 1)

import numpy as np def valley(x, y): return (1 - x)**2 + 5 * (y - x**2)**2 def hessian(x, y): return np.array([[2 - 20 * (y - x**2) + 40 * x**2, -20 * x], [-20 * x, 10.0]]) print(np.round(np.linalg.eigvalsh(hessian(0, 1)), 4), np.round(np.linalg.eigvalsh(hessian(1, 1)), 4)) print(valley(-1, 1), valley(1, 1), valley(0, 1), (valley(-1, 1) + valley(1, 1)) / 2) print(*[f"{np.exp(-x):.6f}" for x in [5, 10]])

⌘/Ctrl + Enter runs the cell

Convex functions and convex problems

0 of 12 correct

1.
The ring $1 \le x^2 + y^2 \le 4$ contains $(0, -1.5)$ and $(0, 1.5)$ . How far from the origin is their midpoint?
2.
Is the set of points with $2x + y \le 4$ and $x \ge 0$ convex? Type 1 for yes, 0 for no
3.
For $f(x) = x^2$ , find the chord's height halfway between $x = -2$ and $x = 4$
4.
Find $q''(0)$ for $q(x) = x^4 - 4x^2 + x$
5.
Find the smallest eigenvalue of the Hessian of $(x - y)^2$
6.
$x^3 + y^2$ has Hessian $\begin{pmatrix} 6x & 0 \\ 0 & 2 \end{pmatrix}$ . What is the smallest $x$ at which it is positive semidefinite?
7.
$\mathbf{x}^\top A\mathbf{x}$ with $A = \begin{pmatrix} 2 & k \\ k & 2 \end{pmatrix}$ . What is the largest $k$ for which it is convex?
8.
The bowl $x^2 + 2y^2$ has tangent plane $3 + 2(x - 1) + 4(y - 1)$ at $(1, 1)$ . How far is the bowl above it at $(1, 0)$ ?
9.
A strictly convex function on a convex set: at most how many minimum points can it have?
10.
$(x + y - 2)^2$ is minimal along a whole line. Find $y$ on that line when $x = 5$
11.
Minimise $3x + 4y$ over the disc $x^2 + y^2 \le 25$ , a convex problem. What is the smallest value?
12.
The valley $(1 - x)^2 + 5(y - x^2)^2$ is 4 at $(-1, 1)$ and 0 at $(1, 1)$ . Find its value at the midpoint $(0, 1)$

How to type answers

Powers with ^: x^7, 2^(1/3), a^-2.
Multiply with * or by writing side by side: 3x^2, 2(x+1).
ln(x) is the natural log, log(x, 2) is log base 2, e is Euler's number, sqrt(x) is a square root.
sin(x), cos(x) and tan(x) take radians; write pi for π and sin(x)^2 for sin²x.
Your first answer to each question is saved: it counts towards your score and brings the question back for review.
Exact answers like ln(20)/ln(3) are best. Decimals need about 4 significant figures.

f'' \ge 0

Convex functions and convex problems

Convex sets

Rule: Linear constraints give convex sets

Convex functions

Rule: Convex function

The tests

Rule: Convexity tests

Convex problems

Rule: Convex problems

Flat bottoms, and no bottom

Quadratic forms with linear constraints

Common mistakes

Convex functions and convex problems

Summary card

Free further reading