An optimization problem has two ingredients: the set of permitted decisions and the quantity assigned to each decision. A derivative can suggest a candidate, but the shape of both ingredients determines what that candidate means. Convexity is useful because every segment between feasible decisions remains feasible, and the objective lies below the straight interpolation of its endpoint values. This turns local information into global information.
Convex sets and functions
Definition 1.1.1
(Convex set)
A set is convex if, for every and , the point is in .
The empty set and singletons are convex. Intersections of convex sets are convex: a segment joining two points of the intersection lies in each set separately. In particular, an affine equality and a half-space are convex; a polyhedron, being a finite intersection of these sets, is convex. A union of convex sets need not be convex: omits zero.
Definition 1.1.2
(Convex and strictly convex functions)
Let be convex. A function is convex if
for all and . It is strictly convex if the inequality is strict whenever and .
Concept lensGeometric
Convexity of a function as convexity of a set
The epigraph is convex exactly when is convex. To see this, apply the function inequality to two epigraph points; conversely, use the epigraph points and . The function inequality is therefore the set definition applied one dimension up, and closure properties of convex sets become closure properties of convex functions. The same picture explains why every sublevel set is convex. The converse is false: has interval sublevel sets on but is not convex there.
First-order inequality
For differentiable functions, convexity can be tested through tangent planes and, for twice differentiable ones, through curvature.
Theorem 1.1.3
(First- and second-order characterizations of convexity)
Let be open and convex and let be differentiable on . Then is convex if and only if
If is twice continuously differentiable on , it is convex exactly when is positive semidefinite at every .
Proof
(Difference quotients, then restriction to lines)
For necessity, convexity gives for . Let . For sufficiency, put and apply the inequality at once with and once with . Multiply by and , respectively, and add. The linear terms cancel and yield the definition.
For the second-order criterion, the second derivative of along a segment is . If the Hessian is positive semidefinite, is nondecreasing, so , which is the first-order inequality. Conversely, restricting a convex function to a line through in direction gives a convex function of one variable on an open interval, whose second derivative is nonnegative.
Thus a tangent plane to a differentiable convex function is a global lower bound, not merely an approximation near the contact point. A positive definite Hessian everywhere implies strict convexity, but is not necessary: is strictly convex although .
Minima and existence
A feasible point is a local minimum if for feasible sufficiently near it; it is global if the inequality holds for every feasible . For convex on convex , every local minimum is global. If a better feasible existed, points with small positive would be arbitrarily close and have value at most , a contradiction.
Proposition 1.1.4
(Strict convexity and uniqueness)
A strictly convex function on a convex feasible set has at most one global minimizer. If it is continuous and the feasible set is nonempty and compact, it has exactly one.
Proof
(A midpoint for uniqueness, compactness for existence)
If were two global minimizers with value , the midpoint is feasible and strict convexity gives it value below , a contradiction. If the feasible set is nonempty and compact and is continuous, the extreme value theorem supplies a minimizer, which is then the only one.
Existence and uniqueness are logically different statements: is strictly convex on but has infimum zero and no minimizer. Compactness is sufficient, not necessary: attains its minimum on the noncompact real line. A common alternative for continuous functions on a closed feasible set is coercivity, meaning along feasible sequences with . A minimizing sequence then lies in a bounded sublevel set; closedness and continuity supply a convergent subsequence with a feasible limit attaining the infimum.
For differentiable convex objectives, a single inequality certifies a constrained minimizer.
Theorem 1.1.5
(A global certificate on a convex feasible set)
Let be a nonempty convex subset of an open convex domain and let be differentiable and convex there. A point minimizes on if and only if for all .
Proof
(A feasible segment for necessity, a tangent plane for sufficiency)
Let be a minimizer and . By convexity of , the points , , are feasible, so satisfies . Hence the right derivative at zero, , is nonnegative. Conversely, if the inequality holds, the first-order characterization gives for every .
Proof X-ray
Where each convexity assumption enters
The two directions use different hypotheses. Necessity uses only differentiability and convexity of the feasible set, which keeps the whole segment from toward feasible; convexity of the objective plays no role there. Sufficiency uses only convexity of the objective, through the tangent-plane lower bound; it never moves along a segment. Because the tangent plane is a global under-estimator, the local first-order information at is enough, and one inequality per feasible point closes the argument. When , the inequality can be tested at both and , which collapses it to .
Each hypothesis is needed for the direction that uses it.
Counterexample mode
Dropping convexity of the set or of the objective
Claim: the directional inequality characterizes minimizers for any differentiable objective on any feasible set. For necessity, let and . Both feasible points are global minimizers, but at the displacement toward gives ; the objective is convex, and it is the nonconvex feasible set that breaks the segment argument. For sufficiency, let on . At we have for every feasible , yet . The repaired statement is the theorem: necessity needs a convex feasible set, and sufficiency needs a convex objective.
At a boundary, a nonzero gradient is possible: minimizing over gives , and every feasible displacement has nonnegative product with the gradient.
Worked example: a constrained quadratic
Worked example 1.1.6
(A boundary minimizer certified by the directional inequality)
Minimize subject to . The unconstrained minimizer is infeasible. Consider on the boundary. Its gradient is . For every feasible ,
The first-order condition proves global optimality. The Hessian is , so strict convexity proves uniqueness; the minimum value is . This certificate is more informative than checking only a drawing or a few boundary points.
Strong convexity and quadratic growth
Strict convexity separates values at different points, but it does not quantify the separation. For a numerical estimate, one asks for a positive constant.
Definition 1.1.7
(Strong convexity)
Let . A function on a convex set is -strongly convex if is convex on .
When the domain is open and is differentiable, applying the first-order inequality to this difference and expanding the squared norm gives
The last term distinguishes strong convexity from ordinary convexity. If a feasible minimizer exists on a convex set, its directional optimality condition makes the middle term nonnegative for every feasible . Thus the objective gap is at least . A small gap then bounds distance to the optimizer, a useful stopping interpretation when a separate lower bound on the optimal value is available. Strict convexity alone gives no fixed positive quadratic lower bound: near zero, tends to zero.
Worked examples: checking the hypotheses
Worked example 1.1.8
(A quadratic with a flat direction)
Consider on . Its Hessian is , whose quadratic form is . Thus is convex. Every point on has value zero, so there are infinitely many minimizers. The Hessian is singular in direction , and strict convexity fails. Positive semidefiniteness certifies convexity, not uniqueness.
Worked example 1.1.9
(Projection onto an interval)
Minimize over . For , the derivative is and every feasible satisfies . Therefore . The first-order certificate proves that is a global minimizer; strict convexity makes it unique. The nonzero derivative is consistent with optimality because moving right is infeasible. Directly, on the interval, so the value is .
Worked example 1.1.10
(Why a stationary point alone is not enough)
Let . Its gradient is zero at the origin, yet and for nonzero . Every neighborhood therefore contains values on both sides of , so the origin is a saddle, not a minimum. Its Hessian is indefinite. This example illustrates precisely why the vanishing-gradient equation must be supplemented by a curvature or other global argument.
How to use a certificate
A practical proof should identify the domain, show that the candidate is feasible, establish the convexity assumptions, and then check the directional inequality. For an unconstrained problem, solve and use the supporting-plane inequality to certify the solution. For a boundary problem, identify feasible directions and test their products with the gradient. In either case, if a problem asks for a unique solution, explain strict convexity or another uniqueness argument separately.
An indefinite Hessian at one point rules out convexity for a twice differentiable function on an open convex domain, but a positive semidefinite Hessian at a single point says nothing about the rest of the domain. The quantifier “at every point” matters in the Hessian criterion. A feasible set can be convex even if its chosen algebraic description contains a nonconvex function; conversely, a convex objective on a disconnected feasible set need not have the local-to-global property.
Linear combinations, composition, and a caution
Convex functions can be combined without repeating a Hessian calculation. If are convex on the same convex domain and , then is convex. Apply the convexity inequality to each summand, multiply by its nonnegative coefficient, and add. A negative coefficient generally reverses an inequality, so this proof does not permit arbitrary signed sums. Adding an affine function preserves convexity, because an affine function satisfies the segment identity with equality and can also be subtracted without changing the result.
A pointwise maximum of finitely many convex functions is convex. Indeed, for each , ; taking the maximum over proves the claim. For instance, is convex even though it is not differentiable at zero. The differentiable first-order criterion is therefore a powerful test for its stated class, not the definition of all convexity.
A subgradient takes over the role of the tangent plane, and the unconstrained certificate becomes membership of zero in the set of subgradients.
A path to generalization
What replaces the gradient when the objective has a kink?
A subgradient takes over the role of the tangent plane, and the unconstrained certificate becomes membership of zero in the set of subgradients.
For convex on , a vector is a subgradient at if for all ; this is the tangent-plane inequality with the gradient's uniqueness dropped. The sufficiency argument above then reads: is a global minimizer exactly when is a subgradient at . For at zero the subgradients form , which contains zero. With constraints, a normal cone of enters, and combining it with the subgradients needs a qualification condition.
For a separate composition rule, let be convex and let be convex and nondecreasing on an interval containing the range of . Then is convex: first use monotonicity to apply to the bound for , then use convexity of . Monotonicity matters. The outer function is convex but not nondecreasing on all of ; with , the composition is not convex on , since its value at zero exceeds the average of its values at and .
These closure rules can simplify modeling. A sum of squared affine residuals is convex because each squared affine function is convex and nonnegative sums preserve convexity. For , the Hessian is , and its quadratic form is . If has full column rank, the form is strictly positive for every nonzero , giving strict convexity and a unique least-squares minimizer. If has a nonzero null vector, moving along that vector leaves the objective unchanged; uniqueness then fails whenever a minimizer exists. This example connects geometric curvature to an algebraic rank condition.
Common mistakes
Common mistake
(Checking convexity at a few points or on a plot)
Convexity concerns every pair of points in the stated domain; checking a few examples or a graph on a small plotted range is not a proof on an unbounded domain. A single counterexample, by contrast, does disprove it, as on shows in the exercises.
Common mistake
(Forcing the gradient to vanish at a boundary minimizer)
A stationary point is globally optimal only when the relevant convexity assumptions apply, and a boundary minimizer need not be stationary in the unconstrained sense. In the projection example the minimizer has ; the correct test is the directional inequality over feasible displacements.
Common mistake
(Reading curvature or uniqueness as existence)
Positive semidefinite curvature supports convexity but not necessarily strict convexity or uniqueness, as the flat-direction example shows. Uniqueness without an existence argument means only that there can be at most one solution: is strictly convex and has none.
Summary
Use feasible segments to reason about the geometry, supporting planes to turn differentiability into a global lower bound, and the directional inequality to certify a constrained minimizer. Establish existence and uniqueness as separate claims. These tools prepare the way for multiplier certificates when the feasible set is given by explicit equations and inequalities.
Exercises
Quick check
(Show that has a unique global minimizer and find it.)
Complete the square.
Solution · Answer
Completing the square gives ; the unique minimizer is , with value .
Quick check
(Is convex on ? Give a direct counterexample to the defining inequality.)
Try two points on the left half of the interval.
Solution · Answer
No. Take , , . The left side is , larger than the right side , so the convexity inequality fails.
Quick check
(Minimize over . Why need the derivative not vanish at the answer?)
Identify the feasible directions at the minimizer.
Solution · Answer
The minimizer is : throughout the interval. Although , feasible displacements at the left endpoint are nonnegative, so for every feasible and the directional condition holds.