Convex optimization — convex sets, convex functions: Foundations

This page assumes nothing. Every squiggle in the parent note is built here from the ground up, in an order where each symbol is earned before the next one uses it. Read top to bottom.

0. The very first symbols: numbers, points, and $R^{n}$

The picture. $R^{1}$ is a line. $R^{2}$ is a flat sheet — a point is $(x_{1}, x_{2})$ , an address "go right $x_{1}$ , go up $x_{2}$ ". $R^{3}$ is space around you. Beyond $3$ we can't draw it, but the rules stay identical, so we picture $R^{2}$ and trust it.

Why the topic needs it. Optimization asks "which point is best?" — you cannot ask that until you know what a "point" is and what "space" it lives in. Everything else is decoration on top of $R^{n}$ .

1. Mixing points: scalar multiplication and vector addition

Before any " $θ x + (1 - θ) y$ " makes sense, we must know what it means to stretch a point and to add two points. These two operations are the whole grammar of $R^{n}$ .

What it looks like — read the figure. The figure shows $x$ scaled to $\frac{1}{2} x$ (shorter, same direction), and two arrows added tip-to-tail. Once you can stretch and add, you can build any mix $θ x + (1 - θ) y$ : scale $x$ by $θ$ , scale $y$ by $1 - θ$ , then add the two scaled arrows.

Figure — Convex optimization — convex sets, convex functions

Why the topic needs it. Every convex combination, every gradient step, every chord is literally "scale, then add." These are the only two moves; the rest of the chapter just chooses clever numbers to scale by.

2. A set, and the line segment between two points

Now the single most important construction of the entire chapter: the line segment between two points, written with a knob $θ$ you can slide. It is built purely from the scale-and-add operations of Section 1.

What it looks like — read the figure. As $θ$ slides from $0$ to $1$ :

at $θ = 0$ : the point is $0 \cdot x + 1 \cdot y = y$ (you're standing on $y$ ),
at $θ = 1$ : the point is $1 \cdot x + 0 \cdot y = x$ (you've walked to $x$ ),
at $θ = \frac{1}{2}$ : the point is $\frac{1}{2} x + \frac{1}{2} y$ , the exact midpoint.

So the formula traces the straight segment from $y$ to $x$ , and $θ$ is your position along it. The two weights $θ$ and $1 - θ$ always add to $1$ — that "adds to $1$ " is exactly what keeps you on the segment and never off it.

Why the topic needs it. "No dents, no holes" has to be said in symbols. The only tool for that is: pick two points, walk the straight segment between them, ask whether the segment stays inside. That question is convexity.

3. The dot product and $a^{⊤} x$ — how flat walls are written

The parent writes half-spaces like ${x : a^{⊤} x \leq b}$ . That needs three new symbols: $a^{⊤}$ , the dot product, and $\leq$ used on a whole expression.

What it looks like. Fix the arrow $a$ . The equation $a^{⊤} x = b$ (for a fixed number $b$ ) draws a flat wall — a line in 2-D, a plane in 3-D — sitting perpendicular ("at right angles") to $a$ . Sliding $b$ up and down shifts that wall parallel to itself. See the figure: the arrow $a$ points across the wall, and $a^{⊤} x$ measures how far along $a$ 's direction the point $x$ has travelled.

Why the topic needs it. A half-space is the simplest possible convex region with a flat boundary. Stack ("intersect") many of them and you carve out a polyhedron — the feasible region of every linear program. So $a^{⊤} x \leq b$ is the atom that convex feasible regions are built from. The dot product also returns in norms and inner products and in the gradient (Section 6).

4. Length of a vector: the norm $∥ x ∥$

What it looks like. ${x : ∥ x ∥ \leq r}$ = "all points within distance $r$ of the centre" = a filled ball (a disk in 2-D). ${x : ∥ x ∥ = r}$ = "points at exactly distance $r$ " = the rim only. Same $r$ , wildly different sets — the filled disk is convex, the rim is not.

Why the topic needs it. Balls are the standard example of a convex set, and the norm function $f (x) = ∥ x ∥$ is the standard example of a convex function built from the triangle inequality: $∥ u + v ∥ \leq ∥ u ∥ + ∥ v ∥ ("a detour is never shorter than going straight") .$ This is the picture behind "every norm is convex," and it links straight to Norms and Inner Products.

5. The graph, the chord, and the epigraph

What it looks like — read the figure. Pick two points on a bowl-shaped graph and draw the chord between them. For a convex function the chord sits on or above the curve (the bowl never bulges up past its own strings). The epigraph — the sand above the curve — is then a dent-free region, i.e. a convex set. That is the deep secret of the whole topic: a function is convex exactly when its "above-region" is a convex set. One idea wearing two hats.

Why the topic needs it. This inequality is the engine of the whole chapter: it forces "no fake dips," which is why a convex function has exactly one bottom.

6. Slopes in many directions: gradient $\nabla f$ and Hessian $\nabla^{2} f$

To test convexity by calculus we need "slope" and "curvature" for landscapes.

Why a second derivative and not the first? Convexity is about bending, not about tilting. A straight ramp tilts ( $f^{'} \neq = 0$ ) but doesn't bend ( $f^{''} = 0$ ) — and a ramp is convex. Only the second derivative sees the bend, which is exactly what "bowl-shaped" means. That's why the curvature test uses $f^{''}$ , not $f^{'}$ .

This is why the first-order convexity test $f (y) \geq f (x) + \nabla f (x)^{⊤} (y - x)$ looks the way it does: the right-hand side is the flat tangent plane's prediction, and convex means the true surface always sits above that flat prediction. It's also the object Gradient Descent follows downhill (walk against $\nabla f$ ).

Why the topic needs it. In more than one dimension a surface can curve up along one axis and down along another (a saddle). A single number can't capture that; the Hessian and the test $⪰ 0$ can, direction by direction, through $v^{⊤} M v$ .

7. The prerequisite map

Here is how these foundations flow into the two central definitions of the topic.

Equipment checklist

Read each question, answer out loud, then reveal. If any one trips you, reread its section above before tackling the parent note.

What does

x \in C

mean in plain words?

The point

x

is a member of (lives inside) the set

C

What does the colon mean in

{x : x > 0}

"Such that" — the collection of all

x

satisfying the rule after it.

How do you compute

λ x

and

x + y

Scale every coordinate of

x

λ

; add

x

and

y

coordinate by coordinate (tip-to-tail arrows).

θ

slides

0 \to 1

, where does

θ x + (1 - θ) y

go?

Along the straight segment from

y

(at

θ = 0

) to

x

(at

θ = 1

), hitting the midpoint at

θ = \frac{1}{2}

State the definition of a convex set.

For all

x, y \in C

and all

θ \in [0, 1]

θ x + (1 - θ) y \in C

— the whole segment stays inside.

State the definition of a convex function.

f (θ x + (1 - θ) y) \leq θ f (x) + (1 - θ) f (y)

for all

x, y

and

θ \in [0, 1]

— the chord lies on/above the graph.

Why must the weights

θ

and

1 - θ

sum to

1

So the combined point stays exactly on the segment between

x

and

y

, never drifting off it.

What kind of object is the dot product

a^{⊤} x

— vector or number?

A single number (it collapses two vectors into one "alignment" value).

What shape is

{x : a^{⊤} x \leq b}

A half-space — all points on one side of the flat wall

a^{⊤} x = b

General formula for the norm

∥ x ∥

R^{n}

∥ x ∥ = x_{1}^{2} + x_{2}^{2} + \dots + x_{n}^{2}

Difference between

{∥ x ∥ \leq 1}

and

{∥ x ∥ = 1}

The first is the filled disk (convex); the second is only the rim circle (not convex).

What does the epigraph of

f

look like?

Everything on or above the graph — the sand poured above the surface;

{(x, t) : t \geq f (x)}

What does a partial derivative

\partial f / \partial x_{i}

measure?

The slope of

f

in the

x_{i}

direction only, holding all other coordinates fixed.

Why does the curvature test use

f^{''}

and not

f^{'}

Convexity is about bending, which only

f^{''}

detects;

f^{'}

only measures tilt, and a tilted straight ramp is still convex.

What are the entries of the Hessian

\nabla^{2} f

, and why is it symmetric?

Entry

ij

\partial^{2} f / \partial x_{i} \partial x_{j}

; symmetry of second derivatives makes entry

ij

equal entry

j i

What does

\nabla^{2} f ⪰ 0

mean, spelled out?

For every direction

v

v^{⊤} \nabla^{2} f v \geq 0

— the surface bends upward (or stays flat) in every direction.

Connections

Parent topic — the full convexity note
Linear Programming — the half-space of Section 3 stacks into the feasible polyhedron.
Norms and Inner Products — the norm (Section 4) and dot product (Section 3) formalised.
Gradient Descent — follows the gradient arrow of Section 6 downhill.
Positive Definite Matrices — the Hessian test $⪰ 0$ of Section 6.
Jensen's Inequality — the chord picture of Section 5 pushed to averages.
Lagrange Multipliers and KKT Conditions — builds on gradients once convexity is set.