Convexity and Convex Optimization

⚡ Key Takeaways

One line: A set is convex if it contains every segment between its points, and a function is convex if its graph lies below its chords; minimizing a convex function over a convex set guarantees that any local minimum is global. Key result in words: Convexity turns optimization from a search riddled with traps into a problem with a single, certifiable answer. Where it applies: machine learning, economics, control theory, signal processing, statistics, operations research. Who/when: Foundations in Jensen (1906), Minkowski (1900s), Fenchel (1949); modern algorithmic theory from Dantzig, Karush–Kuhn–Tucker (1939/1951), and the interior-point revolution of Karmarkar (1984) and Nesterov–Nemirovski (1994).

💡 The Core Insight

Local equals global. In a general optimization landscape you can be trapped at a local minimum that is far worse than the best solution. Convexity destroys this possibility: because the function never "curves back down," any point that is the best in its neighborhood is the best everywhere. This single structural property — together with the existence of separating hyperplanes that certify optimality — is the engine behind every theorem and algorithm in the field.

DefinitionConvex Set

A set $C \subseteq \mathbb{R}^n$ is convex if for all $x, y \in C$ and all $\theta \in [0,1]$ ,

1

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

Derivation hint: The point $\theta x + (1-\theta)y$ traces the straight segment from $y$ (at $\theta=0$ ) to $x$ (at $\theta=1$ ); demanding membership for every $\theta$ is exactly "the segment stays inside." Here $x,y$ are points in $\mathbb{R}^n$ , $\theta$ is a scalar mixing weight, and $\theta x + (1-\theta)y$ is a convex combination of $x$ and $y$ . More generally a convex combination of points $x_1,\dots,x_k$ is $\sum_i \theta_i x_i$ with $\theta_i \ge 0$ and $\sum_i \theta_i = 1$ .

DefinitionConvex Function

A function $f : C \to \mathbb{R}$ with convex domain $C$ is convex if for all $x,y \in C$ and $\theta \in [0,1]$ ,

2

\quad f\big(\theta x + (1-\theta)y\big) \;\le\; \theta f(x) + (1-\theta) f(y).

Derivation hint: The left side is $f$ evaluated on the segment; the right side is the corresponding point on the straight chord connecting $(x,f(x))$ to $(y,f(y))$ . Convexity says graph $\le$ chord. The function is strictly convex if the inequality is strict for $x\ne y$ and $\theta\in(0,1)$ . It is concave if $-f$ is convex. Symbols: $f(x)$ is the function value, the right-hand side is a linear interpolation of endpoint values.

DefinitionEpigraph and First/Second-Order Conditions

The epigraph of $f$ is $\operatorname{epi} f = \{(x,t) : x \in C,\ t \ge f(x)\}$ . Then $f$ is convex $\iff$ $\operatorname{epi} f$ is a convex set. If $f$ is differentiable, convexity is equivalent to the first-order condition: for all $x,y$ ,

3

\quad f(y) \;\ge\; f(x) + \nabla f(x)^{\mathsf T}(y - x).

Derivation hint: Rearrange [2] as $\frac{f(x+\theta(y-x)) - f(x)}{\theta} \le f(y)-f(x)$ and let $\theta \to 0^+$ ; the left side becomes the directional derivative $\nabla f(x)^{\mathsf T}(y-x)$ . If $f$ is twice differentiable, convexity is equivalent to the second-order condition: the Hessian is positive semidefinite everywhere,

4

\quad \nabla^2 f(x) \succeq 0 \quad \text{for all } x \in C.

Derivation hint: Apply the multivariate Taylor expansion with remainder along a segment; the second-order term is $\tfrac12 (y-x)^{\mathsf T}\nabla^2 f(\xi)(y-x)$ , which is $\ge 0$ for all directions exactly when $\nabla^2 f \succeq 0$ . Here $\nabla f(x)$ is the gradient, $\nabla^2 f(x)$ the Hessian matrix, and $A \succeq 0$ means $z^{\mathsf T} A z \ge 0$ for all $z$ (positive semidefinite).

DefinitionConvex Optimization Problem

A convex optimization problem in standard form is

5

\quad \min_{x \in \mathbb{R}^n} \; f_0(x) \quad \text{s.t.} \quad f_i(x) \le 0,\ i=1,\dots,m, \qquad a_j^{\mathsf T} x = b_j,\ j=1,\dots,p,

Derivation hint: The feasible set is the intersection of the sublevel sets $\{f_i \le 0\}$ (convex when $f_i$ convex) and affine sets $\{a_j^{\mathsf T}x = b_j\}$ (always convex); intersections of convex sets are convex. where $f_0$ (objective) and each $f_i$ (inequality constraints) are convex, and the equality constraints are affine (linear). The requirement that equalities be affine — not merely "convex equations" — is essential, because $\{g(x)=0\}$ for a nonlinear convex $g$ is generally not convex.

TheoremGlobal Optimality of Local Minima

Let $f$ be convex on a convex set $C$ . If $x^\star \in C$ is a local minimum of $f$ over $C$ , then $x^\star$ is a global minimum. If $f$ is strictly convex, the global minimizer (if one exists) is unique.

ProofLocal minima are global

Step 1 (setup). Suppose $x^\star$ is a local minimum: there is $r>0$ with $f(x^\star) \le f(z)$ for all feasible $z$ within distance $r$ of $x^\star$ . Assume for contradiction that some feasible $y$ has $f(y) < f(x^\star)$ .

Step 2 (build a nearby competitor). For small $\theta \in (0,1]$ , the point $z = \theta y + (1-\theta) x^\star$ is feasible (convex combination of feasible points in convex $C$ ) and can be made arbitrarily close to $x^\star$ by shrinking $\theta$ . Concretely, choose $\theta$ so that $\theta \|y - x^\star\| < r$ ; then $z$ lies in the neighborhood.

Step 3 (apply convexity). By the convex inequality [2],

f(z) \le \theta f(y) + (1-\theta) f(x^\star) = f(x^\star) + \theta\big(f(y) - f(x^\star)\big).

Step 4 (contradiction). Since $f(y) - f(x^\star) < 0$ and $\theta > 0$ , we get $f(z) < f(x^\star)$ for a point $z$ inside the neighborhood — contradicting local optimality. Hence no such $y$ exists, and $x^\star$ is global. $\blacksquare$

Uniqueness under strict convexity. If $x_1 \ne x_2$ were two global minimizers with common value $v$ , the midpoint $m = \tfrac12 x_1 + \tfrac12 x_2$ satisfies, by strict [2], $f(m) < \tfrac12 v + \tfrac12 v = v$ , contradicting that $v$ is the minimum. $\blacksquare$

∎

ProofFirst-order condition

\Rightarrow

optimality certificate

For an unconstrained convex differentiable $f$ , the inequality [3] gives, at any $x^\star$ with $\nabla f(x^\star) = 0$ :

f(y) \ge f(x^\star) + 0 = f(x^\star) \quad \text{for all } y.

So a vanishing gradient is sufficient for global optimality — no second-order check needed. This is the convex world's defining luxury: stationarity certifies the global answer. $\blacksquare$

∎

mathematician · Werner Fenchel | 1905–1988

A German-Danish mathematician who, in his 1949 paper and 1951 Princeton lecture notes, systematized convex conjugacy — the Legendre–Fenchel transform $f^*(y) = \sup_x \big(y^{\mathsf T}x - f(x)\big)$ — and laid the dual foundations of modern convex analysis. Fenchel's duality theorem unified the scattered inequalities of the early 20th century (Jensen, Hölder, Young) into one geometric framework: every convex function has a conjugate, and minimization in the primal corresponds to maximization in the dual. His work, later expanded by Rockafellar's monumental Convex Analysis (1970), turned convexity from a collection of tricks into a coherent theory.

🧠 Intuition

Picture a bowl. A convex function is a (possibly multidimensional) bowl: drop a marble anywhere and it rolls to the unique bottom — there are no side pockets to get stuck in. The chord condition [2] says: stretch a string between any two points on the bowl's rim, and the string never dips below the bowl's surface; the surface always stays underneath the string. Now picture a convex set as a blob with no dents: any two interior points can "see" each other in a straight line without the line leaving the blob. A crescent moon is not convex (the segment between the horns cuts through empty space); a full disk is. The deepest intuition is the supporting hyperplane: at any boundary point of a convex set you can rest a flat plate so the entire set lies on one side. Algorithmically, this plate is what lets us prove a point is optimal — we separate the optimum from everything better with a single linear inequality. Convex optimization is, at heart, the art of finding and certifying these separating planes.

Figure

Convex vs. non-convex: the chord test and the supporting hyperplane

ExampleMinimizing a quadratic — unconstrained

Given. Minimize $f(x_1,x_2) = 2x_1^2 + 3x_2^2 - 4x_1 - 6x_2 + 7$ .

Step 1 — verify convexity. The Hessian is

\nabla^2 f = \begin{pmatrix} 4 & 0 \\ 0 & 6 \end{pmatrix} \succeq 0 \quad(\text{eigenvalues }4,6>0),

so $f$ is strictly convex; any stationary point is the unique global minimum.

Step 2 — set the gradient to zero.

\nabla f = \begin{pmatrix} 4x_1 - 4 \\ 6x_2 - 6 \end{pmatrix} = 0 \;\Rightarrow\; x_1 = 1,\ x_2 = 1.

Step 3 — evaluate.

f(1,1) = 2 + 3 - 4 - 6 + 7 = 2.

Answer.

\boxed{x^\star = (1,1), \quad f_{\min} = 2 \ \text{(dimensionless)}}

ExampleConstrained convex problem with KKT

Given. Minimize $f(x,y) = x^2 + y^2$ subject to $x + y \ge 4$ (a convex objective on a convex half-plane).

Step 1 — geometric read. We want the point on or above the line $x+y=4$ closest to the origin. The unconstrained minimum $(0,0)$ violates $x+y\ge4$ , so the constraint is active: $x+y=4$ .

Step 2 — Lagrangian / KKT. Write the constraint as $g(x,y)=4-(x+y)\le 0$ with multiplier $\lambda \ge 0$ :

\mathcal L = x^2+y^2 + \lambda(4 - x - y).

Stationarity:

\frac{\partial \mathcal L}{\partial x} = 2x - \lambda = 0,\quad \frac{\partial \mathcal L}{\partial y} = 2y - \lambda = 0 \;\Rightarrow\; x = y = \tfrac{\lambda}{2}.

Step 3 — complementary slackness & primal feasibility. Active constraint gives $x+y=4 \Rightarrow \lambda = 4 \Rightarrow x = y = 2$ , with $\lambda = 4 \ge 0$ ✓.

Step 4 — evaluate.

f(2,2) = 4 + 4 = 8.

Answer.

\boxed{(x^\star,y^\star) = (2,2), \quad f_{\min} = 8, \quad \lambda^\star = 4}

The KKT conditions, sufficient here because the problem is convex, certify this as the global optimum.

⚠️ Common mistake

"Nonlinear means hard; linear means easy." False dichotomy. Many nonlinear problems (least squares, logistic regression, entropy maximization) are convex and solved efficiently, while some innocuous-looking problems with combinatorial or nonconvex equality constraints are NP-hard. The real frontier is convex vs. nonconvex, not linear vs. nonlinear.

" $\nabla f = 0$ means I found the minimum." Only in the convex case. For nonconvex $f$ , a stationary point may be a saddle or local max. Convexity is precisely the property that upgrades stationarity to global optimality.

"A convex equality constraint keeps the problem convex." No. $\{x : f(x) = 0\}$ for convex $f$ is generally a curved (nonconvex) surface; only affine equalities preserve convexity. Equation [5] requires linear equalities for this reason.

"The intersection or union of convex sets is convex." Intersections always are; unions almost never are (two disjoint disks).

Counterexample

Consider $f(x) = x^4 - 8x^2$ on $\mathbb{R}$ . It is smooth and has $f'(x) = 4x^3 - 16x = 4x(x^2-4)$ , vanishing at $x = 0, \pm 2$ . The point $x=0$ is a local maximum, and $x=\pm2$ are global minima. A naive "set the derivative to zero and you're done" recipe would happily report $x=0$ . This cannot happen for a convex function — and indeed $f$ is not convex, since $f''(x) = 12x^2 - 16 < 0$ near the origin. The double-well shape is the prototypical nonconvex trap that convexity outlaws.

connection

Convexity is the unifying thread across applied optimization. The simplest convex problems are <a class="wiki-link" href="/wiki/ncert-12-maths-linear-programming">Linear Programming</a> (linear objective, polyhedral feasible set), solved by the simplex method or interior-point methods. Adding a convex quadratic objective gives Quadratic Programming, and allowing matrix-valued constraints yields Semidefinite Programming, where the variable is constrained to the convex cone of positive semidefinite matrices. The dual viewpoint connects to Lagrangian Duality and the Karush-Kuhn-Tucker Conditions, which generalize Lagrange multipliers to inequality constraints. The analytic machinery rests on Convex Analysis (subgradients, conjugate functions), while the algorithmic side draws on <a class="wiki-link" href="/wiki/cs-ml-gradient-descent">Gradient Descent</a> and its accelerated and stochastic variants, whose convergence guarantees are cleanest precisely under convexity. Finally, Jensen's Inequality is the probabilistic incarnation of equation [2], pervading information theory and statistics.

🔬 Where this appears

⏳ History

- 1840s–1890s — Otto Hölder and Johan Jensen develop the foundational inequalities; the chord characterization of convex functions crystallizes.

- 1906 — Jensen publishes his inequality, the probabilistic form of equation [2], giving convexity a central role in analysis.

- 1900s–1910s — Hermann Minkowski develops the geometry of convex bodies, supporting hyperplanes, and the Minkowski sum, founding modern convex geometry.

- 1939 / 1951 — William Karush (master's thesis, 1939) and, independently, Harold Kuhn & Albert Tucker (1951) derive the KKT optimality conditions for inequality-constrained optimization.

- 1947 — George Dantzig invents the simplex method for linear programming, the first practical large-scale convex solver.

- 1949–1951 — Werner Fenchel formalizes convex conjugacy and duality.

- 1970 — R. Tyrrell Rockafellar publishes Convex Analysis, the definitive synthesis of the field's theory.

- 1979 / 1984 — Leonid Khachiyan's ellipsoid method proves LP is polynomial-time; Narendra Karmarkar's interior-point method makes it practical, igniting the interior-point revolution.

- 1994 — Yurii Nesterov & Arkadi Nemirovski extend interior-point methods to general convex programming via self-concordant barriers, enabling semidefinite programming at scale.

open-problem

Convexity is powerful but not the end of the story. (1) Recognizing convexity is itself hard: deciding whether a given polynomial is convex over $\mathbb{R}^n$ is NP-hard, so "is my problem convex?" can be a nontrivial modeling task. (2) Convex relaxations of nonconvex problems: for hard combinatorial problems (Max-Cut, sparse recovery), semidefinite and LP relaxations give bounds and sometimes exact recovery — characterizing when a relaxation is tight is an active research area. (3) Nonconvex optimization in deep learning: modern neural networks are wildly nonconvex, yet gradient methods find excellent minima; understanding why (overparameterization, benign landscapes, implicit regularization) is a leading open problem that asks how much of convexity's good behavior survives in its absence. (4) Beyond first-order: balancing the per-iteration cost of interior-point methods against the scalability of first-order methods for billion-variable problems remains an engineering and theoretical frontier.

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also