A local minimum of a convex function is a global minimum
ProvedFamousTheorems.convex_local_min_is_global_7aA local minimum of a convex function is a global minimum. Let be a real normed space, , and convex on . If is a local minimum of on , then for every .
This is why convex optimization problems are tractable: any local search method that finds a local minimum has found a global one. The proof restricts to the segment from to and uses convexity to compare with values of near .
Formalization note. Mathlib's IsMinOn.of_isLocalMinOn_of_convexOn, specialised to real-valued functions on a real normed space. Mathlib states it for ordered modules as codomains. IsLocalMinOn f s a means that for all in some neighbourhood of , and IsMinOn f s a means that this holds for all .
Preamble
import Mathlib
Formal statement
namespace FamousTheorems
theorem convex_local_min_is_global_7a {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E] {s : Set E} {f : E → ℝ} {a : E} (ha : a ∈ s)
(hmin : IsLocalMinOn f s a) (hf : ConvexOn ℝ s f) : IsMinOn f s a := by sorry
end FamousTheoremsSource
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `IsMinOn.of_isLocalMinOn_of_convexOn`. Proof here reduces to that Mathlib result.