Convexity and Local versus Global Optima
Convexity is structure, not a synonym for “easy.” It tells us how feasible mixtures and objective values behave and, under the right problem form, lets local optimality imply global optimality.
Prerequisites
Complete feasibility, optimality, and certificates.
Learning goals
- Test the line-segment definition of a convex set.
- Distinguish convex functions, concave functions, and linear functions.
- State when a local optimum is also a global optimum.
- Avoid transferring convex guarantees to discrete or non-convex models.
Geometry and objective shape
A set is convex when for every and . Linear equalities, half-spaces, and boxes are convex; their intersection is convex. Therefore the allocation LP's feasible region is a convex set.
A minimization problem is convex when its feasible set is convex and its objective is convex. Equivalently, maximizing a concave objective over a convex set has the same global guarantee. A linear function is both convex and concave. Consequently, every local optimum of this LP is a global optimum, although the global optimum need not be unique and numerical algorithms still require care.
That statement does not apply automatically to integer restrictions, products of variables, fixed charges, or arbitrary neural objectives. A local optimum in a non-convex problem can be worse than another feasible point.
Worked example
The allocations and are feasible. Their midpoint must therefore be feasible, and linearity makes its objective exactly the average of endpoint objectives.
import numpy as np
from scipy.optimize import linprog
A = np.array([[2.0, 1.0], [1.0, 2.0]])
b = np.array([40.0, 50.0])
benefit = np.array([8.0, 6.0])
endpoint_a = np.array([0.0, 25.0])
endpoint_b = np.array([20.0, 0.0])
midpoint = 0.5 * endpoint_a + 0.5 * endpoint_b
feasible = lambda point: bool(np.all(point >= 0) and np.all(A @ point <= b + 1e-9))
result = linprog(-benefit, A_ub=A, b_ub=b,
bounds=[(0.0, None)] * 2, method="highs")
if result.status != 0:
raise RuntimeError(result.message)
print(f"endpoint_a_feasible={feasible(endpoint_a)} endpoint_b_feasible={feasible(endpoint_b)} midpoint_feasible={feasible(midpoint)}")
print(f"midpoint={midpoint.tolist()} midpoint_points={benefit @ midpoint:.1f} endpoint_average_points={0.5 * (benefit @ endpoint_a + benefit @ endpoint_b):.1f}")
print(f"lp_optimum={result.x.tolist()} global_points={-result.fun:.1f}")
Expected output:
endpoint_a_feasible=True endpoint_b_feasible=True midpoint_feasible=True
midpoint=[10.0, 12.5] midpoint_points=155.0 endpoint_average_points=155.0
lp_optimum=[10.0, 20.0] global_points=200.0
The midpoint property establishes convex feasibility, not optimality. The optimum follows from solving the LP and checking its certificate/status.
Limitations and common mistakes
- A convex feasible set does not rescue minimization of an arbitrary concave objective.
- A convex function can have flat regions and multiple global minima.
- Strict convexity can give uniqueness under suitable feasibility, but is not required for global optimality.
- Integer points are generally not a convex set: averaging two valid schedules can create an invalid fractional schedule.
- Global model optimality still says nothing about omitted effects or stakeholder legitimacy.
Practice
Add the non-convex requirement “either workshops are zero or at least 15.” Find two feasible points whose midpoint violates it. Explain why a continuous LP cannot encode that disjunction exactly without new discrete variables.
Next steps
Translate common business statements into reviewable algebra in linear-programming model patterns.
Primary sources
Checked 2026-10-18: Boyd and Vandenberghe, Convex Optimization and book PDF, chapters 2–4; Stanford EE364A, convex functions notes; SciPy 1.18.1, linprog.