Noesis
4.10.17 · D5Advanced Topics (Elite Level)

Question bank — Convex optimization — convex sets, convex functions

1,764 words8 min read↑ Back to topic
🇮🇳 Yeh page Hinglish mein padho →

True or false — justify

Every one of these is answered with a reason, not a verdict alone. The verdict is the cheap part.

The empty set is convex.
True — the definition "for every pair the segment lies inside" is vacuously satisfied when there are no pairs to test; there is nothing to violate.
A single point is convex.
True — the only pair is , and stays in the set for all ; a degenerate segment is still a segment.
The union of two convex sets is always convex.
False — take two disjoint disks; a point in one joined to a point in the other has a segment crossing the empty gap. (Intersection is preserved, union is not.)
If is convex then is convex.
False — is concave; its chords lie below the graph. The only functions that are both convex and concave are the affine ones .
A straight line is convex.
True — the chord equals the graph, so "chord on or above graph" holds with equality; equivalently . It is simultaneously concave.
The set (the sphere shell) is convex.
False — pick two antipodal points; their midpoint is , whose norm is , so the segment leaves the shell. Only the filled ball is convex.
If both and are convex, then is convex.
True — add the two chord inequalities term by term; the sum of two "bowls" is still a bowl. More generally any with stays convex.
The maximum of two convex functions is convex.
True — its epigraph is the intersection of the two epigraphs (a point is above iff it is above both), and intersection preserves convexity. (Contrast: of convex functions need not be convex.)
is strictly convex even though .
True — strict convexity is the chord inequality with strict "", which satisfies; everywhere is sufficient but not necessary for strict convexity.
Every convex function is differentiable.
False — is convex (triangle inequality) but has a kink at . Convexity forces continuity on the interior of the domain, but not differentiability.

Spot the error

Each statement below contains one flaw. Name it.

"The circle looks round with no corners, so it must be convex."
The error confuses smoothness with convexity: convexity is about the filled region versus its chords, not the absence of corners. A square (all corners) is convex; a circle rim (no corners) is not.
" is convex, so it needs everywhere."
Convexity only requires ; the weak inequality is essential. Lines () are convex, and is strictly convex despite .
"Convex plus concave gives something nice, by symmetry."
There is no such guarantee — convex concave can be neither. Convexity is preserved only under nonnegative combinations of convex functions, not by mixing curvatures.
"Since gradient descent works on convex objectives, any step size will reach the global minimum."
Convexity removes local-minimum traps but does not guarantee convergence by itself; you still need a sensible step-size rule and smoothness (Lipschitz-gradient) assumptions. See Gradient Descent.
"The set (outside the ball) is convex because norms are convex."
A convex function gives convex sublevel sets , not superlevel sets. The exterior fails: join two opposite points on the shell and the segment dips inside where .
"KKT conditions solved, so I found the minimum — always."
In general KKT is only necessary. It becomes sufficient for a global minimum only when the problem is convex; otherwise a KKT point can be a saddle or max. See Lagrange Multipliers and KKT Conditions.
"The Hessian is positive definite at my point, so the whole function is convex."
A local Hessian check certifies convexity only if everywhere on the domain, not at one point. Convexity is a global property. See Positive Definite Matrices.

Why questions

Why does convexity make "local minimum = global minimum" true, in one sentence?
If some far point were lower, the segment to it (staying in the convex set) would, by the chord inequality, produce nearby points below the "local" min — contradicting locality; so no lower point can exist.
Why is the first-order condition the "engine" behind global min?
It says the graph lies above every tangent; if the tangent is flat at height , so for all — that is exactly a global minimum.
Why must the domain of a convex function itself be a convex set?
The definition requires the chord inequality to hold for every in the domain, so the point must lie in the domain (else isn't even defined there) — and " in the domain for all " is exactly the statement that the domain is convex.
Why is every norm a convex function?
The triangle inequality plus absolute homogeneity give , which is the chord inequality itself. See Norms and Inner Products.
Why is Jensen's inequality just the convexity definition "grown up"?
The two-point chord inequality extends to any weighted average and then to expectations, giving — the definition applied to a probability-weighted convex combination. See Jensen's Inequality.
Why is an intersection of half-spaces (a polyhedron) always convex?
Each half-space is convex, and intersection preserves convexity, so any is convex — this is exactly the feasible region of a linear program. See Linear Programming.
Why do we care that the epigraph is convex rather than just the graph?
The graph (a surface) is never a convex set on its own; recasting convexity as "the region on/above the graph is convex" lets us reuse all the set-based tools (intersection, half-spaces) on functions.

Edge cases

What is the convex combination when ?
It collapses to the single point for every — a degenerate segment; this is why singletons pass the convexity test trivially.
Is a set convex if the segment condition holds only for (midpoints)?
Not in general — this "midpoint convexity" upgrades to full convexity only under an extra topological hypothesis, e.g. the set is closed (or locally bounded) in a real vector space; without it a pathological midpoint-convex set can fail to be convex, so the true definition demands all .
Is the function (constant) convex, concave, or neither?
Both — a constant is affine, its chord equals the graph with equality, satisfying convex () and concave () simultaneously; it is convex but not strictly convex.
Can a strictly convex function have more than one global minimizer?
No — if two distinct points both attained the minimum, the strict chord inequality at their midpoint would give a strictly lower value, a contradiction; so the minimizer, if it exists, is unique.
Does a convex function always attain its minimum?
Not necessarily — is strictly convex on but its infimum is never reached; you need a closed bounded (compact) domain or coercivity to guarantee a minimizer exists.
Is the whole space convex?
Yes — any segment between two points of is still in ; it is the largest convex set and the "no constraints" feasible region.
What happens to convexity of as drops below ?
For the function fails the triangle inequality, so it is not a norm and its unit ball is non-convex (a star/pinched shape); convexity of the ball requires .
Recall One-line self-test

If you can answer "why local = global," "why the tangent lies below," and "why the circle rim isn't convex" each in a full sentence, you own this topic.

Connections