Convex optimization — convex sets, convex functions: Worked examples

The scenario matrix

Cell	Case class	What makes it tricky	Example
A	Convex set, prove by definition	must handle the general segment, all $θ$	Ex 1
B	Not convex set — build the counterexample	must exhibit specific $x, y, θ$ that escape	Ex 2
C	1-D function, smooth, $f^{''} \geq 0$ test	sign of $f^{''}$ , and the $f^{''} = 0$ edge case	Ex 3
D	1-D function, non-smooth (kink) — no Hessian	must fall back on the definition	Ex 4
E	Multivariable, Hessian PSD test, all cases	eigenvalues / definiteness incl. degenerate	Ex 5
F	Composition / combination rules	which operations preserve convexity	Ex 6
G	Real-world word problem (optimization)	translate words → convex program, use global-min theorem	Ex 7
H	Exam twist — a false-looking claim to disprove	limiting/degenerate behaviour	Ex 8

Worked example Ex 1 — Cell A · A ball is convex (prove from the raw definition)

Statement. Show the closed ball $B = {x \in R^{n} : ∥ x - c ∥ \leq r}$ is convex, for centre $c$ and radius $r \geq 0$ .

Forecast: guess why the segment can't escape a ball — is it the triangle inequality or the Hessian doing the work?

Take two members. Let $x, y \in B$ , so $∥ x - c ∥ \leq r$ and $∥ y - c ∥ \leq r$ . Pick any $θ \in [0, 1]$ ; let $z = θ x + (1 - θ) y$ . Why this step? The definition of a convex set is a statement about every pair and every $θ$ — so we must start with a fully general pair, not a special one.
Measure $z$ 's distance from the centre. Write $c = θ c + (1 - θ) c$ (legal since $θ + (1 - θ) = 1$ ), so $z - c = θ (x - c) + (1 - θ) (y - c) .$ Why this step? We want $∥ z - c ∥$ ; rewriting the centre as a convex combination lets the difference split cleanly.
Apply the triangle inequality, then absolute homogeneity ( $∥ α v ∥ = ∣ α ∣ ∥ v ∥$ , and $θ, 1 - θ \geq 0$ ): $∥ z - c ∥ \leq θ ∥ x - c ∥ + (1 - θ) ∥ y - c ∥ \leq θ r + (1 - θ) r = r .$ Why this step? The norm is itself convex — the triangle inequality is exactly the tool that pushes an inequality through a weighted average. That is why this, and not the Hessian, is the natural engine here.
Conclude. $∥ z - c ∥ \leq r$ means $z \in B$ . Since $x, y, θ$ were arbitrary, $B$ is convex. $■$

Verify: the degenerate cases confirm nothing breaks. $r = 0$ → $B = {c}$ , a single point: a segment from $c$ to $c$ is just $c$ , still inside. $θ = 0$ → $z = y \in B$ ; $θ = 1$ → $z = x \in B$ . All endpoints and the point-set limit pass.

Figure s01 (below). The violet disk is the ball $B$ ; the two navy dots are an arbitrary pair $x, y$ ; the magenta segment joins them; the orange dot is $z = \frac{1}{2} x + \frac{1}{2} y$ , sitting inside the disk — the picture of step 4. The arrow from the centre marks the radius $r$ that step 3 never exceeds.

Figure — Convex optimization — convex sets, convex functions

Worked example Ex 2 — Cell B · The unit

circle (the rim) is NOT convex Statement. Prove $S = {x \in R^{2} : ∥ x ∥ = 1}$ (the circle itself, not the disk) is not convex.

Forecast: to disprove a "for all" claim you need just one escaping segment. Which two points make the cleanest counterexample?

Pick two members of $S$ . Take $x = (1, 0)$ and $y = (- 1, 0)$ . Both have $∥ x ∥ = ∥ y ∥ = 1$ , so both lie on the circle. Why this step? Diametrically opposite points give the segment that dives straight through the centre — the most obvious escape.
Take the midpoint ( $θ = \frac{1}{2}$ ): $z = \frac{1}{2} x + \frac{1}{2} y = (0, 0)$ . Why this step? One concrete $θ$ is all a counterexample needs.
Check membership. $∥ z ∥ = ∥ (0, 0) ∥ = 0 \neq = 1$ , so $z \in / S$ . Why this step? We found a pair and a $θ$ violating the definition — that is exactly the logical negation of "convex."
Conclude. $S$ is not convex. $■$ (Contrast: the filled disk $∥ x ∥ \leq 1$ is convex — Ex 1 with $c = 0, r = 1$ .)

Verify: sanity — the chord length here is $2$ , the diameter, and its midpoint sits at distance $0$ from centre, well inside the empty middle. This is precisely the parent note's Mistake 1: round $\neq =$ convex.

Figure s02 (below). Only the violet rim is the set $S$ (the middle is empty). The magenta chord joins $x = (1, 0)$ and $y = (- 1, 0)$ ; its orange midpoint lands at the origin — a point not on the rim, exactly the escape found in step 3.

Worked example Ex 3 — Cell C · Smooth 1-D, including the

$f^{''} = 0$ trap Statement. Classify each as convex / strictly convex / concave / neither on its natural domain: (a) $f (x) = x^{4}$ , (b) $g (x) = x^{3}$ , (c) $h (x) = 3 x + 2$ .

Forecast: which of these is strictly convex despite having $f^{''} = 0$ somewhere?

(a) $f^{''} (x) = 12 x^{2}$ . This is $\geq 0$ for all $x$ , so $f$ is convex. It equals $0$ only at the single point $x = 0$ . Why this step? The second-order test $f^{''} \geq 0$ certifies convexity; a single zero doesn't kill it. Is it strictly convex? Here is the precise justification (not just a picture). Sufficient condition for strict convexity: if $f^{''} (x) \geq 0$ everywhere and $f^{''} > 0$ except on a set with no interval (isolated points), then $f$ is strictly convex. Reason: strict convexity is equivalent to $f^{'}$ being strictly increasing; and $f^{'}$ is strictly increasing whenever $f^{''} \geq 0$ with $f^{''} > 0$ off isolated points, because on any interval $[a, b]$ we get $f^{'} (b) - f^{'} (a) = \int_{a}^{b} f^{''} > 0$ (the integrand is positive except at isolated points, so the integral is still strictly positive). For $x^{4}$ : $f^{''} = 12 x^{2} > 0$ except at the isolated point $x = 0$ , so $f^{'} = 4 x^{3}$ is strictly increasing, hence $x^{4}$ is strictly convex. This is the parent's Mistake 2: $f^{''} > 0$ everywhere is sufficient but not necessary.
(b) $g^{''} (x) = 6 x$ . Positive for $x > 0$ , negative for $x < 0$ . Sign flips, so $g$ is convex on $[0, \infty)$ , concave on $(- \infty, 0]$ , and neither on all of $R$ . Why this step? Convexity is a property over the whole stated domain; one sign change anywhere disqualifies it globally.
(c) $h^{''} (x) = 0$ everywhere. So $h^{''} \geq 0$ (convex) and $h^{''} \leq 0$ (concave). A straight line is both convex and concave — but not strictly either, since its chords coincide with the graph (equality, so the " $<$ " of the strict definition fails). Why this step? Covers the boundary case where $f^{''} = 0$ on a whole interval, not just isolated points — so the sufficient condition of step 1 does not apply, and strictness genuinely fails.

Verify: numeric chord check for (a) at $x = - 1, y = 1, θ = \frac{1}{2}$ : LHS $f (0) = 0$ , RHS $\frac{1}{2} (1) + \frac{1}{2} (1) = 1$ ; $0 < 1$ ✔ strict. For (c) at $x = 0, y = 2, θ = \frac{1}{2}$ : LHS $h (1) = 5$ , RHS $\frac{1}{2} (2) + \frac{1}{2} (8) = 5$ ; $5 = 5$ ✔ equality confirms "both, not strict."

Worked example Ex 4 — Cell D · Non-smooth function: no Hessian, use the definition

Statement. Is $f (x) = ∣ x ∣$ convex? It has a corner at $0$ where $f^{'}$ doesn't exist.

Forecast: the Hessian test is unavailable at the kink. What tool replaces it?

Note the obstruction. $f^{'} (x) = + 1$ for $x > 0$ , $- 1$ for $x < 0$ , undefined at $0$ . So $f^{''} (0)$ doesn't exist — the second-order test is inapplicable at the corner. Why this step? You must recognise when a test is legal. The Hessian test requires twice-differentiability, which fails here.
Fall back to the raw chord definition. For any $x, y$ and $θ \in [0, 1]$ , use the triangle inequality and absolute homogeneity: $∣ θ x + (1 - θ) y ∣ \leq ∣ θ x ∣ + ∣ (1 - θ) y ∣ = θ ∣ x ∣ + (1 - θ) ∣ y ∣.$ Why this step? The definition never needs derivatives — it works at corners, at cusps, everywhere. The triangle inequality is doing the lifting, exactly as in Ex 1.
Read off the result. That is precisely $f (θ x + (1 - θ) y) \leq θ f (x) + (1 - θ) f (y)$ : $f = ∣ x ∣$ is convex. Why this step? Matching the derived line to the definition closes the proof.
Strict? No: on $[0, \infty)$ , $∣ x ∣ = x$ is linear, so chords there coincide with the graph (equality) — the " $<$ " of the strict definition fails on that whole interval. Convex but not strictly.

Verify: at $x = - 2, y = 4, θ = \frac{1}{2}$ : LHS $∣1∣ = 1$ , RHS $\frac{1}{2} (2) + \frac{1}{2} (4) = 3$ ; $1 \leq 3$ ✔. At $x = 2, y = 4$ (same sign): LHS $∣3∣ = 3$ , RHS $\frac{1}{2} (2) + \frac{1}{2} (4) = 3$ ; $3 = 3$ ✔ (equality — hence not strict).

Worked example Ex 5 — Cell E · Multivariable Hessian: PSD, PD, and the degenerate case

Statement. For each function on $R^{2}$ decide convexity via the Hessian: (a) $f = x^{2} + x y + y^{2}$ , (b) $g = x^{2} - y^{2}$ , (c) $h = (x + y)^{2}$ .

Forecast: one of these is convex but not strictly — its Hessian is PSD but not PD. Which?

Recall the test. $f$ is convex $⟺$ Hessian $\nabla^{2} f ⪰ 0$ (positive semidefinite) everywhere. " $⪰ 0$ " means all eigenvalues $\geq 0$ ; strictly convex is guaranteed by " $≻ 0$ " (all $> 0$ ). Why this step? We must name the exact threshold before testing — this is the PSD criterion.
(a) $\nabla^{2} f = (2112)$ . Eigenvalues solve $(2 - λ)^{2} - 1 = 0 \Rightarrow λ = 1, 3$ . Both $> 0$ → positive definite → strictly convex. Why this step? A constant Hessian means "everywhere" is automatic; eigenvalues decide the sign class.
(b) $\nabla^{2} g = (20 0 - 2)$ , eigenvalues $2$ and $- 2$ . A negative eigenvalue → indefinite → neither convex nor concave (a saddle). Why this step? One negative eigenvalue is enough to break PSD, hence convexity fails.
(c) $\nabla^{2} h = (2222)$ , eigenvalues $0$ and $4$ . All $\geq 0$ → PSD but not PD → convex but NOT strictly. The zero eigenvalue points along the flat valley $x + y = const$ where the function is constant, so the strict " $<$ " fails along that whole line. Why this step? This is the degenerate case: the " $= 0$ " eigenvalue is the direction with no curvature — a whole flat trough of minima, so no unique minimiser.

Verify: eigenvalue products = determinants: (a) $det = 3$ , $λ$ -product $1 \cdot 3 = 3$ ✔; (b) $det = - 4 = 2 \cdot (- 2)$ ✔; (c) $det = 0 = 0 \cdot 4$ ✔. Traces: (a) $4 = 1 + 3$ ✔, (c) $4 = 0 + 4$ ✔.

Figure s03 (below). A contour map of $h = (x + y)^{2}$ . The orange dashed line is the flat valley $x + y = 0$ (the zero-eigenvalue direction, where $h = 0$ all along); the magenta arrow points uphill along the eigenvalue- $4$ direction where curvature is positive. Convex everywhere, but flat along the dashed line — hence not strictly convex.

Worked example Ex 6 — Cell F · Combination rules (which operations preserve convexity)

Statement. Given $f_{1} (x) = x^{2}$ (convex) and $f_{2} (x) = e^{x}$ (convex), decide: (a) is $3 f_{1} + 5 f_{2}$ convex? (b) is $f_{1} - f_{2}$ necessarily convex? (c) is $max {f_{1} (x), f_{2} (x)}$ convex?

Forecast: exactly one of these can fail. Which operation is not safe?

(a) Nonnegative weighted sum. Convex $+$ convex, with weights $3, 5 \geq 0$ , is convex: chords add, and scaling by a nonnegative constant preserves the " $\leq$ ." So $3 f_{1} + 5 f_{2}$ is convex. Why this step? This is the safe rule from the parent note: $\sum α_{i} f_{i}$ convex when all $α_{i} \geq 0$ .
(b) Difference. Convex $-$ convex $=$ convex $+$ concave, which can be anything. Concretely $f_{1} - f_{2}$ has second derivative $2 - e^{x}$ , negative once $x > lo g 2$ . So it is not convex. Why this step? Subtraction sneaks in a negative weight, which is exactly what the safe rule forbids — this is the parent's Mistake 3.
(c) Pointwise maximum. Recall from the page-top definition that the epigraph of a function is everything on or above its graph, $epi (f) = {(x, t) : t \geq f (x)}$ , and $f$ is convex iff its epigraph is a convex set. Now the epigraph of $max {f_{1}, f_{2}}$ is exactly ${(x, t) : t \geq f_{1} (x) and t \geq f_{2} (x)} = epi (f_{1}) \cap epi (f_{2})$ — the intersection of two convex sets, which is convex (parent note). So $max {x^{2}, e^{x}}$ is convex. Why this step? "Max = intersection of epigraphs" turns a function claim into the set fact we already proved.

Verify: (b) at $x = 2$ : $f_{1}^{''} - f_{2}^{''} = 2 - e^{2} \approx 2 - 7.389 = - 5.389 < 0$ ✔ (convexity broken). (a) at $x = 1$ : second derivative $3 \cdot 2 + 5 e \approx 6 + 13.59 > 0$ ✔.

Worked example Ex 7 — Cell G · Word problem: cheapest fence, guaranteed global

Statement. A farmer must enclose an area of exactly $A = 100 m^{2}$ in a rectangle. Fence costs are the same per metre on all sides. Minimise the perimeter $P$ . Show the problem is convex after a change of variable, and find the minimiser — then argue it is the global optimum.

Forecast: the raw perimeter as a function of width alone — is it convex? Guess the shape before computing.

Set up. Width $w > 0$ , height $= A / w$ (area constraint). Perimeter $P (w) = 2 w + 2 A / w = 2 w + 200/ w$ . Why this step? Eliminate the constraint by substitution so we minimise one variable.
Check convexity. $P^{''} (w) = \frac{d}{d w} (2 - \frac{200}{w ^{2}}) = \frac{400}{w ^{3}}$ . For $w > 0$ this is $> 0$ , so $P$ is strictly convex on the domain $w > 0$ . Why this step? Convexity on the (convex) feasible set ${w > 0}$ means any stationary point is the unique global minimiser — the theorem from the parent note ("every local min is global"). No need to worry about other traps.
Minimise. Set $P^{'} (w) = 2 - 200/ w^{2} = 0 \Rightarrow w^{2} = 100 \Rightarrow w = 10$ (take $w > 0$ ). Then height $= 100/10 = 10$ : a square. Minimum perimeter $P (10) = 2 (10) + 200/10 = 40$ m. Why this step? For a strictly convex 1-D function, $P^{'} = 0$ pins the single global minimum. Ties into Gradient Descent: a convex objective means gradient methods land here with no local-min trap.
Uniqueness. Strict convexity $\Rightarrow$ at most one minimiser, so the square is the answer.

Verify: perimeter check $P (10) = 40$ . Compare a non-square feasible point $w = 5$ (height $20$ ): $P (5) = 10 + 40 = 50 > 40$ ✔ and $w = 20$ (height $5$ ): $P (20) = 40 + 10 = 50 > 40$ ✔ — both worse, confirming $40$ is the min.

Worked example Ex 8 — Cell H · Exam twist: a plausible-but-false claim

Statement. True or false: "If $f$ and $g$ are both convex, then their product $f g$ is convex." Give a proof or a counterexample.

Forecast: sums of convex are convex — does the same charm carry to products? Trust nothing.

Probe with simple pieces. Let $f (x) = x$ and $g (x) = x$ . Each is linear, hence convex (and concave). Their product is $f (x) g (x) = x^{2}$ — convex here. Why this step? One passing case does not prove a universal claim; it only fails to disprove. We must keep hunting.
Try a sign-changing factor. Let $f (x) = x$ (convex on $R$ ) and $g (x) = x^{2}$ (convex). Product $p (x) = x^{3}$ . Then $p^{''} (x) = 6 x$ , which is negative for $x < 0$ . Why this step? Deliberately test where one factor goes negative — that's where a product can "flip" curvature.
Confirm with the definition (not just $p^{''}$ ). Take $x = - 2, y = 0, θ = \frac{1}{2}$ . Then $p (θ x + (1 - θ) y) = p (- 1) = - 1$ , while $θ p (x) + (1 - θ) p (y) = \frac{1}{2} (- 8) + \frac{1}{2} (0) = - 4$ . The convexity requirement " $p (mid) \leq chord$ " reads $- 1 \leq - 4$ , which is false — the chord dips below the graph. Why this step? A watertight disproof should exhibit an explicit violating triple $(x, y, θ)$ of the chord definition, backing up the $p^{''} < 0$ signal.
Conclude FALSE. With both a negative $p^{''}$ on $(- \infty, 0)$ and an explicit chord violation, the claim is false: the product of convex functions need not be convex. (Bonus: products are convex if both factors are convex, nonnegative, and monotone in the same direction — the naive claim drops all three guards.)

Verify: $p^{''} (- 1) = 6 (- 1) = - 6 < 0$ ✔ (not convex). Chord violation at $x = - 2, y = 0, θ = \frac{1}{2}$ : LHS $p (- 1) = - 1$ , RHS $\frac{1}{2} (- 8) + \frac{1}{2} (0) = - 4$ ; the required $- 1 \leq - 4$ is false ✔ — confirming non-convex.

How the examples tile the matrix

Recall Self-check before you move on

Which test do you use when a function has a corner? ::: The definition (chord inequality), because the Hessian test needs twice-differentiability. A Hessian with eigenvalues $0$ and $4$ means the function is...? ::: Convex but not strictly — flat in the zero-eigenvalue direction (a valley of minima). Product of two convex functions — always convex? ::: No — e.g. $x \cdot x^{2} = x^{3}$ is not convex on $R$ . Why is the square the cheapest-perimeter rectangle guaranteed global? ::: $P (w) = 2 w + 200/ w$ is strictly convex on $w > 0$ , so its unique stationary point is the global min. Precise definition of strictly convex? ::: $f (θ x + (1 - θ) y) < θ f (x) + (1 - θ) f (y)$ for all $x \neq = y, θ \in (0, 1)$ — chord strictly above the graph except at endpoints.

Connections

Parent topic — definitions these examples exercise.
Norms and Inner Products — the triangle inequality powering Ex 1 and Ex 4.
Positive Definite Matrices — the Hessian eigenvalue test of Ex 5.
Gradient Descent — Ex 7's convex objective converges globally.
Linear Programming — polyhedra as intersections of half-spaces (Ex 6's intersection idea).
Jensen's Inequality — the chord inequality of Ex 3/Ex 4 generalised to averages.