Convex optimization — convex sets, convex functions

1. Convex Sets

WHAT is $\theta x + (1-\theta)y$ ? As $\theta$ sweeps from $0$ to $1$ , this point sweeps along the straight segment from $y$ (at $\theta=0$ ) to $x$ (at $\theta=1$ ). It is a convex combination of two points.

WHY this definition? "No dents, no holes." A disk is convex; a crescent moon is not (a chord can poke outside). A donut is not (a chord crosses the hole).

Worked example Testing convexity

Convex: $\mathbb{R}^n$ , any line, any ball $\{x : \|x-c\|\le r\}$ , any half-space $\{x : a^\top x \le b\}$ , any hyperplane.
Not convex: the unit circle $\{x:\|x\|=1\}$ (the segment between two points dips inside, leaving the circle); the set $\{x : \|x\| \ge 1\}$ (exterior of a ball).

Why a half-space is convex (step): take $x,y$ with $a^\top x\le b,\ a^\top y\le b$ . Then $a^\top(\theta x+(1-\theta)y)=\theta a^\top x+(1-\theta)a^\top y \le \theta b+(1-\theta)b=b$ . ✔ — Why this step? linearity of $a^\top(\cdot)$ lets the inequality pass straight through the convex combination.

Figure — Convex optimization — convex sets, convex functions

2. Convex Functions

WHY this inequality? LHS = the function's actual height at the midpoint-ish point. RHS = the chord's height there. Convex means the bowl never bulges above its own chords.

Curvature tests (HOW to check in practice)

Formula First-order condition (derived)

If $f$ is differentiable, convexity $\iff$ $f(y)\ \ge\ f(x) + \nabla f(x)^\top (y-x)\quad \forall x,y.$ WHY: start from the chord definition written with the point $x+\theta(y-x)=\theta y+(1-\theta)x$ : $f\big(x+\theta(y-x)\big)\ \le\ (1-\theta)f(x)+\theta f(y).$ Subtract $f(x)$ from both sides and divide by $\theta>0$ : $\frac{f\big(x+\theta(y-x)\big)-f(x)}{\theta}\ \le\ f(y)-f(x).$ Let $\theta\to 0^+$ : the left side is the directional derivative $\nabla f(x)^\top(y-x)$ , giving $\nabla f(x)^\top(y-x)\le f(y)-f(x)$ , i.e. the stated inequality. ∎ Meaning: the tangent plane at any point lies entirely below the graph — the graph sits above all its tangents. This is the engine behind " $\nabla f=0 \Rightarrow$ global min."

Common mistake Steel-manning the classic errors

Mistake 1: "The boundary circle $\|x\|=1$ is convex because a circle is round." Why it feels right: "round = no corners = convex." The fix: convexity is about the filled region vs the boundary curve. The closed disk $\|x\|\le1$ is convex; the circle (just the rim) is not — a chord goes through the empty middle. Convexity ≠ smoothness.

Mistake 2: " $f$ convex needs $f''>0$ (strict)." Why it feels right: parabolas have $f''=2>0$ . The fix: convex only needs $f''\ge 0$ . A straight line ( $f''=0$ ) is convex (and concave!). And be careful the other way too: $f''>0$ everywhere is sufficient for strict convexity but not necessary — e.g. $f(x)=x^4$ is strictly convex even though $f''(0)=0$ . Strict convexity is the chord inequality with " $<$ ", which $x^4$ satisfies.

Mistake 3: "Sum of a convex and a concave function is... something nice." Why it feels right: symmetry. The fix: convex + convex = convex (chords add), but convex + concave can be neither. Preserve convexity only via nonnegative combinations of convex functions: $\sum \alpha_i f_i,\ \alpha_i\ge0$ .

Recall Feynman: explain it to a 12-year-old

Imagine a skate ramp shaped like a bowl. Drop a marble anywhere inside — it always rolls to the same lowest point. That's a convex function: there's just one bottom, so you can never get tricked into stopping at a fake "low spot." A convex set is a region with no dents and no holes: pick any two spots in it, stretch a string straight between them, and the string never leaves the region. Optimization is "find the bottom"; convexity guarantees the bottom is easy to find and there's only one.

Connections

Linear Programming — feasible region = intersection of half-spaces = convex polyhedron.
Gradient Descent — for a convex objective it converges to the global min (rather than a local one), provided the usual algorithmic conditions hold: a sensible step-size rule and smoothness/Lipschitz-gradient assumptions. Convexity removes local-min traps; it does not by itself guarantee convergence.
Lagrange Multipliers and KKT Conditions — KKT becomes sufficient (not just necessary) under convexity.
Positive Definite Matrices — the Hessian test $\nabla^2 f\succeq 0$ .
Jensen's Inequality — the convexity inequality generalized to expectations.
Norms and Inner Products — every norm is a convex function.

Flashcards

Define a convex set.

For all

x,y\in C,\ \theta\in[0,1]

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

— the whole segment lies inside.

Define a convex function.

f(\theta x+(1-\theta)y)\le \theta f(x)+(1-\theta)f(y)

; the chord lies on/above the graph.

Geometric link between convex set and convex function?

f

convex

\iff

its epigraph

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

is a convex set.

First-order convexity condition?

f(y)\ge f(x)+\nabla f(x)^\top(y-x)

— graph lies above every tangent.

Second-order convexity condition?

Hessian

\nabla^2 f(x)\succeq 0

for all

x

(in 1-D:

f''\ge0

Why does convexity guarantee global minima?

A nearby better point + segment-staying-inside + chord inequality contradicts local-minimality, so local = global.

Is the circle

\|x\|=1

convex?

No — a chord passes through the empty interior. The closed disk

\|x\|\le1

is convex.

What preserves convexity of sets?

Intersection and affine images (and thus polyhedra

\{x:Ax\le b\}

What preserves convexity of functions?

Nonnegative weighted sums, max of convex functions, composition with affine map.

Does strict convexity require

f''>0

everywhere?

No —

f''>0

everywhere is sufficient but not necessary; e.g.

x^4

is strictly convex with

f''(0)=0

. Non-strict convex only needs

f''\ge0

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, convex optimization ka pura funda ek hi line mein hai: agar problem "bowl-shaped" hai, toh local minimum aur global minimum same ho jaate hain. Iska matlab gradient descent jaisa algorithm sahi global answer tak pahunch sakta hai — par yaad rakhna, convexity local-min trap hata deti hai, magar actual convergence ke liye sahi step-size rule aur gradient ki smoothness (Lipschitz) bhi chahiye. Isiliye convex problems woh family hai jise hum reliably solve kar paate hain.

Do cheezein samajhni hain. Pehli — convex set: koi bhi region jismein dent ya hole na ho. Test simple hai: region ke andar koi bhi do points lo, unke beech seedhi line (segment) kheencho — agar line poori region ke andar rahti hai toh set convex hai. Disk convex hai, crescent (chand) ya donut nahi, kyunki chord bahar nikal jaati hai. Half-space aur unka intersection (yani polyhedron $Ax\le b$ ) hamesha convex — yahi LP ka feasible region hai.

Doosri — convex function: graph par do points lo, unke beech chord (seedhi line) kheencho. Agar chord hamesha graph ke upar ya barabar rahe, toh function convex hai. Equivalent test: $f''(x)\ge 0$ (multi-dimension mein Hessian PSD, yani $\nabla^2 f \succeq 0$ ). Aur ek khoobsurat property — graph apni har tangent ke upar hota hai: $f(y)\ge f(x)+\nabla f(x)^\top(y-x)$ . Isi se proof aata hai ki $\nabla f=0$ matlab global minimum.

Common galti: "circle convex hai kyunki round hai" — galat! Bhari hui disk convex hai, sirf rim (circle) nahi, kyunki chord khaali andar se guzarti hai. Aur convex ke liye sirf $f''\ge0$ chahiye; strict convexity ke liye $f''>0$ "everywhere" zaroori nahi hai — jaise $x^4$ strictly convex hai par $f''(0)=0$ . Yaad rakhna: chord upar, set beech mein, tangent neeche.

Convex optimization — convex sets, convex functions

1. Convex Sets

2. Convex Functions

Curvature tests (HOW to check in practice)

Connections

Flashcards

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Advanced Topics (Elite Level)

Connections