Home / MLF / Week 8

Week 8 · Bowls, not bumpy hills: convexity

Official syllabus line: Convex sets, functions, and optimisation problems

About 75 minQuiz 2 material (see exam radar)BSCS2004 · Harish Guruprasad Ramaswamy, Arun Rajkumar, Prashanth LA

Before you start: Week 5 (positive semi-definite matrices) and week 7 (Hessian, critical points).

Watch first: the animated story of this weekAbout 1-2 minutes of real 3D animation with a friendly voice. Pause any time.

Read the words of the video

Imagine rolling a marble in a smooth bowl; it always finds the single lowest spot. But on a bumpy field, it might get stuck in a small dip, not the true bottom. Mathematicians call 'bowl-shaped' problems 'convex'. In these, if you find a bottom, it's the real bottom, no fake dips!
Convex means 'no dents'. A convex 'set' is a shape where a straight line between any two points stays inside. A convex 'function' is like a bowl; its graph never goes above a straight chord. We check this using something called the Hessian. Convex problems are easy because any bottom you find is the true, deepest one.
Let's check if a function, like 'x squared plus a times x times y plus y squared', is convex. We use a tool called the Hessian. If its special numbers, called eigenvalues, are all positive or zero, the function is convex. For our example, this happens only if 'a' is between minus two and plus two.
Remember, convex sets have no dents, and convex functions are bowl-shaped. The Hessian helps us check them! For convex problems, finding any local minimum means you've found the true global minimum. This topic is super important for your exams and for understanding advanced machine learning. You've got this!

The one-minute story

Think of it like this

Roll a marble inside a smooth bowl. Wherever you drop it, it ends up at the one lowest point. Now roll a marble on a bumpy field. It may settle in a small dip that is not the lowest place on the field, and you would never know there was a deeper valley elsewhere.

Convex is the mathematician's word for "bowl-shaped". For a convex problem there are no fake dips: if you reach a bottom, it is the bottom. That is why convex problems are the happy, solvable corner of machine learning, and why week 7's gradient descent is trustworthy for them.

This week: what convex sets are (shapes with no dents), what convex functions are (bowls), how to check convexity quickly (using the Hessian from week 7 and positive semi-definiteness from week 5), and why it matters.

By the end of this week you can:

test whether a set is convex, and build convex combinations and convex hulls;
test whether a function is convex using the definition, the Hessian, or closure rules;
say what concave, strictly convex and the epigraph mean;
explain why a local minimum of a convex function is global.

Words you need

Convex set - a shape where the straight segment between any two of its points stays inside the shape.
Convex combination - a mix $\theta\mathbf x+(1-\theta)\mathbf y$ with $0\le\theta\le1$ ; the points on the segment between $\mathbf x$ and $\mathbf y$ .
Convex hull - the smallest convex set that contains some given points (stretch a rubber band round them).
Convex function - a function whose graph never goes above the straight chord between two of its points.
Concave - the upside-down version: $f$ is concave if $-f$ is convex.
Epigraph - the region on or above the graph of a function.
Strictly convex - convex with no flat stretches; its minimum, if it exists, is unique.

Idea 1: Convex sets

A set $S$ is convex if for any $\mathbf x,\mathbf y\in S$ and any $\theta\in[0,1]$ , the point $\theta\mathbf x+(1-\theta)\mathbf y$ is also in $S$ . In words: walk in a straight line between any two points of the set and you never leave it.

The idea

Convex: a line, a plane, a filled disc, a filled ball, a square, a triangle, a half-plane $\{\mathbf x:\mathbf a^T\mathbf x\le b\}$ , any intersection of convex sets (so a polygon cut out by several half-planes is convex).

Not convex: a ring (annulus), the outside of a disc, a crescent, a star shape, the union of two separate discs, the set of points with $x^2+y^2=4$ (just the circle line).

Useful rules:

Intersection of convex sets is convex.
Union of convex sets is generally not convex.
If $S$ is convex and $f$ is a linear map, the image $f(S)$ is convex.

Convex hull

A convex combination of points $\mathbf x_1,\dots,\mathbf x_k$ is $\sum\theta_i\mathbf x_i$ with all $\theta_i\ge0$ and $\sum\theta_i=1$ . The set of all convex combinations is the convex hull.

Solved example: 1. Is a point inside the hull?

Question. The convex hull of $(0,0),\,(4,0),\,(0,4)$ is a triangle. Is $(1,1)$ in it? Is $(3,3)$ ?

Solution. The triangle is the set $x\ge0,\;y\ge0,\;x+y\le4$ .

$(1,1)$ : $1\ge0,\,1\ge0,\,1+1=2\le4$ . Inside. (Explicitly, $(1,1)=\frac14(4,0)+\frac14(0,4)+\frac12(0,0)$ : weights $\frac14,\frac14,\frac12$ are $\ge0$ and add to 1.)
$(3,3)$ : $3+3=6>4$ . Outside.

Idea 2: Convex functions

A function $f$ is convex if the straight chord between any two points on 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)\qquad\text{for }0\le\theta\le1

The chord test. For a convex function, no chord ever pokes under the graph.

Three ways to check convexity

The idea

Second derivative (one variable): convex $\iff f''(x)\ge0$ everywhere.
Hessian (many variables): convex $\iff$ the Hessian is positive semi-definite at every point. (If it is positive definite everywhere, the function is strictly convex.) This is weeks 5 and 7 joining hands.
First-order: $f$ is convex $\iff$ $f(\mathbf y)\ge f(\mathbf x)+\nabla f(\mathbf x)\cdot(\mathbf y-\mathbf x)$ for all $\mathbf x,\mathbf y$ . The right side is exactly the linear approximation from week 2, so the statement says: the tangent line (plane) always lies below the graph.

Convexity and the epigraph

The epigraph of $f$ is $\{(\mathbf x,t):t\ge f(\mathbf x)\}$ , everything on or above the graph. Then: $f$ is a convex function $\iff$ its epigraph is a convex set. This is the link between the two halves of the week.

Building convex functions from others

Sum of convex functions is convex. Non-negative multiple $c\,f$ ( $c\ge0$ ) is convex.
Maximum of convex functions is convex. (So $\max(0,\,1-t)$ , the hinge loss, is convex.)
$f(A\mathbf x+\mathbf b)$ is convex if $f$ is (compose with an affine map).
If $f$ is convex and $g$ is convex and non-decreasing, then $g(f(\mathbf x))$ is convex. (E.g. $e^{f}$ .)
Not safe: difference of convex functions, or a product of convex functions.

Well-known convex functions: $x^2$ , $x^4$ , $|x|$ , $e^x$ , $-\ln x$ on $x>0$ , any norm $\|\mathbf x\|$ , and $\mathbf x^TA\mathbf x$ when $A$ is PSD. Not convex: $x^3$ on all of $\mathbb R$ , $\sin x$ , $x^4-2x^2$ (two dips), $-x^2$ (that is concave).

Solved example: 2. Convex or not? Use the Hessian

Question. Decide whether (a) $f(x,y)=x^2+xy+y^2$ and (b) $g(x,y)=(x+y)^2$ are convex, and (c) for which $a$ is $h(x,y)=x^2+axy+y^2$ convex.

Solution.

(a) $H=\begin{pmatrix}2&1\\1&2\end{pmatrix}$ , eigenvalues $3,1>0$ , so strictly convex.

(b) $g=x^2+2xy+y^2$ , so $H=\begin{pmatrix}2&2\\2&2\end{pmatrix}$ with eigenvalues $4$ and $0$ . PSD but not PD: convex, but not strictly (it is flat along the line $x+y=0$ , where it is identically 0).

(c) $H=\begin{pmatrix}2&a\\a&2\end{pmatrix}$ has eigenvalues $2\pm a$ . Both are $\ge0$ iff $|a|\le2$ . So $h$ is convex exactly when $-2\le a\le2$ .

Idea 3: Why convexity makes life easy

The idea

For a convex function on a convex set, every local minimum is a global minimum. Also, the set of all minimisers is itself convex, and for a strictly convex function the minimiser is unique. Moreover, $\nabla f(\mathbf x^*)=\mathbf 0$ is enough to guarantee a global minimum (no Hessian check needed).

Why? Suppose $\mathbf x$ is a local minimum but some other point $\mathbf y$ has a lower value, $f(\mathbf y)<f(\mathbf x)$ . Walk a tiny fraction $\theta$ of the way from $\mathbf x$ towards $\mathbf y$ , to $\mathbf z=(1-\theta)\mathbf x+\theta\mathbf y$ . The chord rule gives $f(\mathbf z)\le(1-\theta)f(\mathbf x)+\theta f(\mathbf y)<f(\mathbf x)$ . But $\mathbf z$ can be as close to $\mathbf x$ as we like (make $\theta$ small), so there are points arbitrarily near $\mathbf x$ that are lower. That contradicts " $\mathbf x$ is a local minimum". So no such $\mathbf y$ exists.

Where do convex problems turn up?

Least squares $\|X\mathbf w-\mathbf y\|^2$ has Hessian $2X^TX$ , which is always PSD: convex.
Ridge regression adds $\lambda\|\mathbf w\|^2$ : strictly convex (MLT week 6).
The logistic loss and the SVM objective are convex (MLT weeks 9 and 10).
k-means and neural networks are not convex; that is why they only promise "a local minimum".

Jensen's inequality: for a convex $f$ , $f(E[X])\le E[f(X)]$ . For example $(E[X])^2\le E[X^2]$ , which is just "variance $\ge0$ ".

Your turn

Your turn: 1. Convex sets

Which are convex? (a) $\{(x,y):x^2+y^2\le9\}$ (b) $\{(x,y):x^2+y^2\ge9\}$ (c) $\{(x,y):x+y\le1,\;x\ge0,\;y\ge0\}$ (d) the union of two touching discs

Need a hint?

Draw them.

Show the full solution

(a) convex (filled disc). (b) not convex (the outside of a disc: take two points on opposite sides, the segment cuts through the hole). (c) convex (triangle, intersection of three half-planes). (d) generally not convex: two discs side by side leave a pinched waist, and a segment between far points can leave the union.

Your turn: 2. Convex hull

Is $(2,1)$ in the convex hull of $(0,0),\,(4,0),\,(0,3)$ ?

Need a hint?

The triangle is $x\ge0$ , $y\ge0$ , and above the hypotenuse? Find the hypotenuse line.

Show the full solution

The hypotenuse joins $(4,0)$ and $(0,3)$ : $\frac x4+\frac y3\le1$ . At $(2,1)$ : $\frac24+\frac13=\frac{5}{6}\le1$ . Yes, inside.

Your turn: 3. Convex function?

Is $f(x)=x^3$ convex on all of $\mathbb R$ ? On $[0,\infty)$ ?

Need a hint?

$f''(x)=6x$ .

Show the full solution

$f''$ is negative for $x<0$ , so not convex on $\mathbb R$ . For $x\ge0$ we have $f''\ge0$ , so it is convex on $[0,\infty)$ .

Your turn: 4. A difference of convex functions

Is $g(x)=|x|-x^2$ convex?

Need a hint?

Test the chord between $x=0$ and $x=1$ at the midpoint.

Show the full solution

$g(0)=0$ and $g(1)=1-1=0$ , so the chord at $x=\frac12$ has height $0$ . But $g(\frac12)=\frac12-\frac14=\frac14>0$ : the graph is above the chord. So not convex. (Convex minus convex is not guaranteed convex.)

Your turn: 5. Which are convex?

Which of these are convex functions of $(x,y)$ ? (a) $x^2+y^2$ (b) $\max(x^2,\,y^2)$ (c) $-\ln x$ for $x>0$ (d) $xy$

Need a hint?

Use closure rules and the Hessian.

Show the full solution

(a) convex. (b) convex: the max of two convex functions. (c) convex: $f''=1/x^2>0$ . (d) Hessian $\begin{pmatrix}0&1\\1&0\end{pmatrix}$ has eigenvalues $1$ and $-1$ : indefinite, not convex.

Exam radar

Convexity belongs to the End Term. Summaries mention convex functions in 21 papers, convex sets in 13, convexity in 8, convex set in 9, Hessian matrix in 13, alongside the optimisation topics of weeks 7 and 9.

Typical questions: "Which of the following functions are convex?", "For what values of $a$ is this function convex?" (Hessian eigenvalues), "Which statements about convex sets are true?", "Is this point in the convex hull?", and "what does the composition of two functions look like near a point".

The newest papers (2025 to 2026) still carry convexity MSQs every time: sets, hull, epigraph and composition.

Watch out - real exam trap

Union of convex sets is usually not convex. Intersection is.
Convex function $\ne$ "has one minimum": $f(x)=0$ and $f(x)=(x+y)^2$ are convex with many minimisers. Only strictly convex gives uniqueness.
A convex function need not have a minimum at all ( $e^x$ ).
Convex means PSD Hessian (allowing zero eigenvalues), strictly convex means PD.
Concave $\ne$ not convex. $-x^2$ is concave; $x^3-3x$ is neither.

Quick quiz

The Hessian of f has eigenvalues 3 and 0 everywhere. The function f is...

not convex
convex but not strictly convex
strictly convex
concave

All eigenvalues are at least 0, so the Hessian is PSD: convex. A zero eigenvalue means it is not strictly convex.

Which set is convex?

a circle line (only the boundary)
the union of two separate discs
the intersection of two discs
a ring (annulus)

Intersection of convex sets is convex. The others have gaps or dents.

A local minimum of a convex function is...

always a local maximum too
always a global minimum
never unique
always zero

For convex functions every local minimum is a global minimum.

Select all convex functions. (select all that apply)

x squared
|x|
x cubed on all of the real line
sin x

x cubed has a negative second derivative for x below 0, and sin x curves both ways.

Recap

Remember this

Convex set: segments between its points stay inside. Intersections convex, unions not.
Convex function: chord above graph; $f''\ge0$ ; Hessian PSD; tangent plane below graph; epigraph is a convex set.
Sum, non-negative multiple, max, and affine composition preserve convexity.
Convex $\Rightarrow$ local minimum = global minimum, and zero gradient is enough. Least squares, ridge, logistic loss, SVM are convex; k-means and neural nets are not.

Formulas to keep

Convex set: $\theta\mathbf x+(1-\theta)\mathbf y\in S$ for $\theta\in[0,1]$
Convex function: $f(\theta\mathbf x+(1-\theta)\mathbf y)\le\theta f(\mathbf x)+(1-\theta)f(\mathbf y)$
1-D: $f''\ge0$ ; many variables: $H\succeq0$ (PSD); strictly convex: $H\succ0$
First-order: $f(\mathbf y)\ge f(\mathbf x)+\nabla f(\mathbf x)\cdot(\mathbf y-\mathbf x)$
Jensen: $f(E[X])\le E[f(X)]$
Epigraph: $\{(\mathbf x,t):t\ge f(\mathbf x)\}$ convex $\iff f$ convex

Connected weeks (learn them together)

MLT week 6 - Ridge and LASSO: taming overfitting: Ridge and LASSO are convex problems, so a global best exists and can be found.

Practise with real exam questions

These come straight from past papers (with the real figures and the official answer key). Open 13 real questions on this week All Quiz 2 papers