The Central Idea
Convexity is fundamentally about what happens between points.
A set is convex if the line segment joining any two points in the set remains entirely inside the set.
A function is convex if its graph lies below the straight line segment joining any two points on the graph.
These two geometric ideas combine to produce unusually strong optimization guarantees.
Convex Combinations
Given two points \(\mathbf{x}\) and \(\mathbf{y}\), a convex combination has the form
\[ \boxed{ \lambda\mathbf{x} + (1-\lambda)\mathbf{y} } \]where
\[ 0\le\lambda\le1. \]As \(\lambda\) varies from \(0\) to \(1\), this expression traces the line segment from \(\mathbf{y}\) to \(\mathbf{x}\).
What Is a Convex Set?
A set \(C\) is convex if for every \(\mathbf{x},\mathbf{y}\in C\) and every \(0\le\lambda\le1\),
\[ \boxed{ \lambda\mathbf{x} + (1-\lambda)\mathbf{y} \in C }. \]In plain language: every line segment joining two points in the set stays inside the set.
Examples of Convex Sets
Common convex sets include:
- intervals on the real number line;
- lines and planes;
- half-planes and half-spaces;
- disks and solid balls;
- rectangles and boxes;
- triangles;
- polygons without inward dents;
- polyhedra defined by linear inequalities.
Example: An Interval Is Convex
Consider the interval
\[ [a,b]. \]If
\[ x,y\in[a,b], \]then every weighted average
\[ \lambda x+(1-\lambda)y \]with \(0\le\lambda\le1\) also lies between \(a\) and \(b\).
Therefore,
\[ \boxed{[a,b]\text{ is convex}.} \]Example: A Disk Is Convex
The set
\[ x^2+y^2\le r^2 \]is a disk centered at the origin.
Every line segment joining two points inside the disk remains inside the disk.
Therefore, the disk is convex.
Nonconvex Sets
A set is nonconvex if at least one line segment joining two points in the set leaves the set.
Examples include:
- a crescent-shaped region;
- a ring or annulus;
- a disconnected set;
- a polygon with an inward indentation.
Why Linear Feasible Regions Are Convex
Each linear inequality
\[ a^T\mathbf{x}\le b \]defines a half-space, which is convex.
The intersection of convex sets is convex.
Therefore, every feasible region defined entirely by linear inequalities is convex.
Intersections Preserve Convexity
If
\[ C_1,C_2,\ldots,C_m \]are convex sets, then
\[ \boxed{ C_1\cap C_2\cap\cdots\cap C_m } \]is also convex.
This fact is fundamental in constrained optimization.
What Is a Convex Function?
A function \(f\) defined on a convex set is convex if
\[ \boxed{ f\bigl( \lambda\mathbf{x} +(1-\lambda)\mathbf{y} \bigr) \le \lambda f(\mathbf{x}) +(1-\lambda)f(\mathbf{y}) } \]for every
\[ 0\le\lambda\le1. \]Geometric Meaning of Convexity
Choose two points on the graph of a convex function.
Draw the straight line segment connecting them.
The graph of the function lies on or below that segment.
This gives convex functions their characteristic bowl-like geometry.
Examples of Convex Functions
Common convex functions include
\[ f(x)=x^2, \] \[ f(x)=e^x, \] \[ f(x)=|x|, \]and, on \(x>0\),
\[ f(x)=-\ln x. \]A Linear Function Is Both Convex and Concave
For
\[ f(x)=ax+b, \]the graph coincides exactly with every secant line drawn between points on the graph.
Therefore, every affine function is both convex and concave.
Strict Convexity
A function is strictly convex if
\[ f\bigl( \lambda\mathbf{x} +(1-\lambda)\mathbf{y} \bigr) < \lambda f(\mathbf{x}) +(1-\lambda)f(\mathbf{y}) \]whenever
\[ \mathbf{x}\ne\mathbf{y} \]and
\[ 0<\lambda<1. \]The graph lies strictly below the secant line between distinct points.
Why Strict Convexity Matters
A strictly convex function can have at most one global minimizer on a convex feasible set.
Therefore, strict convexity provides a powerful uniqueness guarantee.
Concave Functions
A function \(f\) is concave if
\[ \boxed{ f\bigl( \lambda\mathbf{x} +(1-\lambda)\mathbf{y} \bigr) \ge \lambda f(\mathbf{x}) +(1-\lambda)f(\mathbf{y}) }. \]A concave function has the opposite curvature of a convex function.
Convexity and Concavity Are Related
A function \(f\) is concave exactly when
\[ -f \]is convex.
Therefore,
\[ \boxed{ f\text{ concave} \quad\Longleftrightarrow\quad -f\text{ convex} }. \]Minimization and Maximization
Convex functions are naturally associated with minimization.
Concave functions are naturally associated with maximization.
Since maximizing \(f\) is equivalent to minimizing \(-f\), these two viewpoints are mathematically connected.
First-Order Characterization
If \(f\) is differentiable and convex, then for all \(\mathbf{x}\) and \(\mathbf{y}\) in its domain,
\[ \boxed{ f(\mathbf{y}) \ge f(\mathbf{x}) + \nabla f(\mathbf{x})^T (\mathbf{y}-\mathbf{x}) }. \]The tangent plane lies below the graph of a differentiable convex function.
Tangent-Line Interpretation
In one variable, convexity implies
\[ f(y) \ge f(x) + f'(x)(y-x). \]The tangent line at \(x\) never rises above the graph.
This provides another geometric way to recognize convexity.
Stationary Points of Convex Functions
Suppose \(f\) is differentiable and convex.
If
\[ \nabla f(\mathbf{x}^*)=\mathbf{0}, \]then the first-order convexity inequality gives
\[ f(\mathbf{y}) \ge f(\mathbf{x}^*) \]for every feasible \(\mathbf{y}\).
Therefore,
\[ \boxed{ \mathbf{x}^*\text{ is a global minimizer} }. \]Local Minima Become Global
One of the defining optimization properties of convex functions is:
\[ \boxed{ \text{every local minimum of a convex function is global} }. \]This removes one of the major difficulties present in nonconvex optimization.
Strict Convexity Gives Uniqueness
If \(f\) is strictly convex on a convex feasible set, then two distinct global minimizers cannot exist.
Therefore, whenever a minimizer exists,
\[ \boxed{ \text{the minimizer is unique} }. \]Second-Derivative Test for Convexity
If a twice-differentiable one-variable function satisfies
\[ \boxed{ f''(x)\ge0 } \]throughout an interval, then \(f\) is convex on that interval.
Strict Convexity from the Second Derivative
If
\[ f''(x)>0 \]throughout an interval, then \(f\) is strictly convex there.
This condition is sufficient, though strict convexity can sometimes hold even when \(f''\) equals zero at isolated points.
Example: \(x^2\)
Let
\[ f(x)=x^2. \]Then
\[ f''(x)=2>0. \]Therefore,
\[ \boxed{ x^2\text{ is strictly convex} }. \]Its unique global minimum occurs at
\[ \boxed{x=0}. \]Example: Exponential Function
Let
\[ f(x)=e^x. \]Then
\[ f''(x)=e^x>0. \]Therefore, the exponential function is strictly convex on \(\mathbb{R}\).
Example: A Concave Quadratic
Consider
\[ f(x)=-x^2+4x. \]Then
\[ f''(x)=-2<0. \]Therefore, \(f\) is strictly concave.
Any local maximum is consequently the unique global maximum.
Multivariable Convexity
For a twice-differentiable multivariable function, convexity is determined by the Hessian matrix.
If
\[ H_f(\mathbf{x}) \]is positive semidefinite throughout a convex domain, then \(f\) is convex.
Positive Semidefinite Hessians
A symmetric matrix \(H\) is positive semidefinite if
\[ \boxed{ \mathbf{v}^TH\mathbf{v}\ge0 } \]for every vector \(\mathbf{v}\).
This means curvature is never negative in any direction.
Positive Definite Hessians
A symmetric matrix is positive definite if
\[ \mathbf{v}^TH\mathbf{v}>0 \]for every nonzero vector \(\mathbf{v}\).
A positive definite Hessian throughout a convex domain implies strict convexity.
Example: Multivariable Quadratic
Consider
\[ f(x,y)=x^2+2y^2. \]The Hessian is
\[ H_f = \begin{bmatrix} 2 & 0\\ 0 & 4 \end{bmatrix}. \]Both eigenvalues are positive.
Therefore, the Hessian is positive definite and \(f\) is strictly convex.
Quadratic Forms
A quadratic objective can be written
\[ f(\mathbf{x}) = \frac12\mathbf{x}^TQ\mathbf{x} + \mathbf{c}^T\mathbf{x} + d. \]If \(Q\) is positive semidefinite, then \(f\) is convex.
If \(Q\) is positive definite, then \(f\) is strictly convex.
Convex Feasible Sets and Convex Objectives
A standard convex minimization problem has the form
\[ \boxed{ \begin{aligned} \text{minimize}\quad &f(\mathbf{x})\\ \text{subject to}\quad &\mathbf{x}\in C, \end{aligned} } \]where \(f\) is convex and \(C\) is a convex feasible set.
Why Convex Optimization Is Special
In a general nonlinear problem, an algorithm may become trapped in a local minimum that is not globally best.
Convexity removes that ambiguity.
Any local minimum is already global.
Convexity of Linear Programming
Linear programming is a convex optimization problem because:
- linear objectives are convex;
- linear inequalities define convex feasible sets;
- their intersections remain convex.
This explains much of the strong global structure seen in linear programming.
Convex Sublevel Sets
For a convex function \(f\), a sublevel set has the form
\[ \boxed{ \{\mathbf{x}:f(\mathbf{x})\le c\} }. \]Every sublevel set of a convex function is convex.
Why Sublevel Sets Matter
Minimization repeatedly asks whether points can achieve objective values below a particular threshold.
Convex sublevel sets ensure that these threshold regions have simple geometry without separated pockets or inward dents.
Convexity Is Preserved by Positive Scaling
If \(f\) is convex and
\[ a\ge0, \]then
\[ af \]is convex.
Sums of Convex Functions
If \(f_1,\ldots,f_m\) are convex and the coefficients
\[ a_i\ge0, \]then
\[ \boxed{ a_1f_1+\cdots+a_mf_m } \]is convex.
This makes it possible to construct complex convex objectives from simpler convex pieces.
Maximum of Convex Functions
The pointwise maximum of convex functions is also convex.
If
\[ f(x)=\max\{f_1(x),f_2(x)\}, \]and both \(f_1\) and \(f_2\) are convex, then \(f\) is convex.
Absolute Value as a Convex Function
The absolute-value function
\[ f(x)=|x| \]is convex even though it is not differentiable at
\[ x=0. \]Convexity therefore does not require differentiability.
Nondifferentiable Convex Optimization
Convex functions can have corners.
In such cases, gradients are replaced by more general objects called subgradients.
This extends first-order optimization ideas to nondifferentiable convex objectives.
Subgradient Preview
A vector \(\mathbf{g}\) is a subgradient of a convex function \(f\) at \(\mathbf{x}\) if
\[ f(\mathbf{y}) \ge f(\mathbf{x}) + \mathbf{g}^T (\mathbf{y}-\mathbf{x}) \]for every \(\mathbf{y}\) in the domain.
When \(f\) is differentiable, the gradient is the unique subgradient.
Strong Convexity Preview
Strong convexity requires a function to curve upward by at least a specified amount.
A differentiable function is strongly convex with parameter \(m>0\) if it satisfies a strengthened first-order inequality containing
\[ \frac{m}{2}\|\mathbf{y}-\mathbf{x}\|^2. \]Strong convexity provides useful stability and convergence guarantees.
Convexity and Gradient Descent
Gradient descent moves according to
\[ \mathbf{x}_{k+1} = \mathbf{x}_k - \alpha_k\nabla f(\mathbf{x}_k). \]For convex objectives, descent methods benefit from the fact that local improvement is consistent with movement toward a global solution.
Convexity and Uniqueness of Solutions
Convexity guarantees globality, but not necessarily uniqueness.
Strict convexity adds uniqueness.
Thus:
\[ \boxed{ \text{convex} \Rightarrow \text{local minima are global} } \]while
\[ \boxed{ \text{strictly convex} \Rightarrow \text{at most one global minimizer} }. \]Example: Convex but Not Strictly Convex
Consider
\[ f(x,y)=x^2. \]The function is convex, but it does not depend on \(y\).
Every point satisfying
\[ x=0 \]has the minimum value
\[ 0. \]Therefore, the minimizer is not unique.
Nonconvex Functions
A nonconvex function may contain:
- several local minima;
- several local maxima;
- saddle points;
- separated valleys;
- flat and irregular regions.
These features make global optimization substantially more difficult.
Example: A Nonconvex Function
Consider
\[ f(x)=x^4-4x^2. \]Its second derivative is
\[ f''(x)=12x^2-8. \]This quantity is negative near \(x=0\) and positive for sufficiently large \(|x|\).
Therefore, \(f\) is not convex over all real numbers.
Convexity Can Depend on the Domain
A function may fail to be convex globally but become convex on a smaller interval or region.
Therefore, convexity should always be stated relative to a domain.
Example: Restricted Convexity
For
\[ f(x)=x^4-4x^2, \]we have
\[ f''(x)=12x^2-8. \]The function is convex wherever
\[ 12x^2-8\ge0. \]Thus it is convex on sufficiently far-left and far-right portions of its domain even though it is not globally convex.
Convex Constraints
A constraint of the form
\[ g(\mathbf{x})\le0 \]defines a convex feasible set when \(g\) is convex.
This is a basic building block of convex optimization.
Affine Equality Constraints
Equality constraints in standard convex optimization are typically affine:
\[ A\mathbf{x}=\mathbf{b}. \]An affine equality defines a convex set.
General Convex Optimization Form
A standard convex optimization problem can be written
\[ \boxed{ \begin{aligned} \text{minimize}\quad &f_0(\mathbf{x})\\ \text{subject to}\quad &f_i(\mathbf{x})\le0, \qquad i=1,\ldots,m,\\ &A\mathbf{x}=\mathbf{b}, \end{aligned} } \]where each \(f_i\) is convex.
Convexity and KKT Conditions
In general nonlinear optimization, KKT conditions are usually necessary under suitable regularity assumptions.
In convex optimization, they often become sufficient for global optimality as well.
This is another major advantage of convex structure.
Convexity in Least Squares
The least-squares objective
\[ \|A\mathbf{x}-\mathbf{b}\|^2 \]is convex.
If \(A\) has full column rank, the objective is strictly convex and the least-squares solution is unique.
Convexity in Statistics
Many estimation problems minimize convex loss functions.
Convexity helps ensure that numerical optimization is not trapped by inferior local minima.
Convexity in Economics
Convex cost functions model situations where marginal cost increases.
Concave utility or production functions often model diminishing marginal returns.
These structures connect optimization with economic equilibrium and allocation theory.
Convexity in Engineering
Convex optimization appears in:
- control systems;
- signal processing;
- network design;
- energy management;
- structural design;
- communications;
- estimation and filtering.
Common Error: Confusing Convex Sets with Convex Functions
A convex set is a geometric region.
A convex function is a mapping whose values satisfy a specific inequality.
The two concepts are related but not interchangeable.
Common Error: Assuming Bowl-Shaped Means Strictly Convex
A function can be convex without being strictly convex.
Flat directions or flat intervals can produce multiple minimizers.
Common Error: Assuming \(f''(x)>0\) Is Necessary
Positive second derivative is a convenient sufficient test for strict convexity, but it is not always necessary at every point.
For example,
\[ f(x)=x^4 \]is strictly convex even though
\[ f''(0)=0. \]Common Error: Ignoring the Domain
Convexity is always relative to the domain under consideration.
A function may be convex on one interval and nonconvex on a larger one.
Common Error: Assuming Convexity Guarantees Existence
Convexity guarantees strong structure if an optimum exists, but it does not by itself guarantee existence.
Domain closure, boundedness, coercivity, or other conditions may still be needed.
Common Error: Treating Every Stationary Point as Unique
For a convex differentiable function, a stationary point is global.
But uniqueness requires additional structure such as strict convexity.
A Reliable Convexity Workflow
- Identify the domain or feasible set.
- Determine whether the domain is convex.
- Check whether the objective is convex or concave.
- Use the defining inequality when appropriate.
- For one variable, inspect \(f''(x)\).
- For several variables, inspect the Hessian.
- Determine whether convexity is strict.
- Use first-order conditions to identify candidate optima.
- Apply global guarantees supplied by convexity.
- Check existence and uniqueness separately.
- Interpret the result in the original optimization model.
Practice 1: Convex Set
Is the interval
\[ [-3,5] \]convex?
Practice 2: Convex Combination
Compute the convex combination of \(2\) and \(10\) using
\[ \lambda=\frac14. \]Practice 3: Second-Derivative Test
Determine whether
\[ f(x)=3x^2-6x+1 \]is convex, strictly convex, concave, or neither.
Practice 4: Concavity
Determine the curvature of
\[ f(x)=-4x^2+8x. \]Practice 5: Global Minimum
Consider
\[ f(x)=x^2-8x+20. \]Use convexity to explain why its stationary point is a global minimum.
Practice 6: Hessian Test
Determine whether
\[ f(x,y)=2x^2+3y^2 \]is convex or strictly convex.
Practice 7: Convex but Not Strictly Convex
Explain why
\[ f(x,y)=x^2 \]is convex but does not have a unique minimizer over \(\mathbb{R}^2\).
Practice 8: Linear Function
Is
\[ f(x)=5x-2 \]convex, concave, both, or neither?
Practice 9: Nonconvex Function
Determine whether
\[ f(x)=x^4-4x^2 \]is convex on all of \(\mathbb{R}\).
Practice 10: Identify the Error
A student says: “If a function is convex, it must have exactly one minimizer.”
Explain the error.
Practice Answers
Practice 1
Yes.
Every line segment between two points of
\[ [-3,5] \]remains inside the interval.
Therefore,
\[ \boxed{[-3,5]\text{ is convex}.} \]Practice 2
\[ \frac14(2) + \frac34(10) = \frac12+\frac{30}{4} = 8. \]Therefore,
\[ \boxed{8}. \]Practice 3
We have
\[ f''(x)=6>0. \]Therefore,
\[ \boxed{ f\text{ is strictly convex} }. \]Practice 4
Since
\[ f''(x)=-8<0, \]the function is
\[ \boxed{ \text{strictly concave} }. \]Practice 5
The second derivative is
\[ f''(x)=2>0. \]Therefore, \(f\) is strictly convex.
Its stationary point is
\[ x=4. \]Because every local minimum of a convex function is global,
\[ \boxed{x=4\text{ is the unique global minimizer}.} \]Practice 6
The Hessian is
\[ H_f = \begin{bmatrix} 4 & 0\\ 0 & 6 \end{bmatrix}. \]Both eigenvalues are positive.
Therefore,
\[ \boxed{ f\text{ is strictly convex} }. \]Practice 7
The function satisfies
\[ f(x,y)=x^2\ge0. \]Every point with
\[ x=0 \]gives the minimum value \(0\), regardless of \(y\).
Thus there are infinitely many minimizers.
Practice 8
Every affine function is both convex and concave.
Therefore,
\[ \boxed{ f(x)=5x-2\text{ is both convex and concave} }. \]Practice 9
The second derivative is
\[ f''(x)=12x^2-8. \]It is negative near \(x=0\) and positive for sufficiently large \(|x|\).
Therefore,
\[ \boxed{ f\text{ is not convex on all of }\mathbb{R} }. \]Practice 10
Convexity guarantees that local minima are global, but it does not guarantee uniqueness.
Uniqueness generally requires strict convexity or another suitable condition.
What to Remember
Convexity provides geometric structure that turns many difficult optimization problems into globally understandable ones.
- a convex set contains every line segment joining its points;
- a convex function lies below its secant lines;
- strict convexity strengthens this inequality;
- concavity is convexity of the negative function;
- every local minimum of a convex function is global;
- a stationary point of a differentiable convex function is globally minimizing;
- strict convexity provides uniqueness when a minimizer exists;
- second derivatives and Hessians provide practical convexity tests;
- linear programming is a special case of convex optimization;
- convexity supports powerful first-order and algorithmic guarantees.
The central optimization principle is
\[ \boxed{ \text{convexity turns local information into global information} }. \]Where We Go Next
Convexity explains why many optimization problems have trustworthy global structure. The next question is how to exploit derivative information computationally to move toward an optimum.
The next lesson, Gradient-Based Methods, develops iterative optimization procedures that use gradients, search directions, step sizes, and convergence behavior to locate minima and maxima numerically.