Convex optimization

Convex optimization — “minimizing convex functions over convex sets” — is the exact / structured branch the synthesis said was missing: where the founding metaheuristics tackle arbitrary landscapes with no guarantees, convexity buys certainty. Source: Wikipedia.

The decisive property

“Every point that is a local minimum is also a global minimum.” This single fact dissolves the problem every metaheuristic is built to fight (local-optima traps): convex problems are “solvable with polynomial-time algorithms,” whereas “general optimization is NP-hard.” Solved by interior-point, subgradient/bundle, and Newton methods (often gradient-based).

Standard form and the subclass ladder

A convex problem minimizes a convex objective subject to convex inequality constraints gᵢ(x) ≤ 0 and affine equality constraints; the feasible set is convex because “the intersection of convex sets is convex” wikipedia-convex-optimization. The recognized subclasses nest, each more general than the last: LP (linear objective + constraints) ⊂ QP (convex-quadratic objective) ⊂ SOCP ⊂ SDP ⊂ conic optimization — so “convex” is a ladder of named, solvable regimes, not one method. Optimality is certified by Lagrange multipliers λᵢ ≥ 0 with complementary slackness λᵢ·gᵢ(x) = 0; strict convexity gives at most one optimum.

The polynomial-time guarantee has a date: “many classes of convex optimization problems admit polynomial-time algorithms,” a tractability that follows from interior-point methods and, in particular, Nesterov & Nemirovskii’s (1994) self-concordant barrier functions wikipedia-convex-optimization. The certainty the metaheuristics lack was an engineered result, not a given.

Why it matters here — the cleanest statement of the trade

Convex vs. metaheuristic is the sharpest face of the no-free-lunch-theorem in this wiki: structure ⇄ generality. “Convex problems trade generality for certainty; metaheuristics accept uncertainty for generality.” If you can prove your problem convex, you don’t want a swarm — you want an interior-point solver with a global guarantee. Metaheuristics exist precisely for the non-convex, black-box remainder where that structure is absent.

Related

gradient-descent · stochastic-gradient-descent · no-free-lunch-theorem · metaheuristic-optimization · exploration-vs-exploitation · wikipedia-convex-optimization