Concept

Relaxation

A weaker problem obtained by dropping a constraint, whose answer bounds the original's. When its corners happen to satisfy the dropped constraint the two problems coincide, and when they do not the difference is a measurable gap.

Named by 2 essays across 2 fields — each of them below, with the objects they name alongside it.

The corner that is a half on every edge. A 3-vertex graph beside a table of the 5 corners of its matching relaxation. 4 are whole and one assigns a half to every edge.

Where the corners stop being whole

Everything on this ladder rests on one property — the relaxation of the assignment problem has whole-numbered corners. Add a single edge that closes an odd cycle and the property fails, a corner appears with a half in every coordinate, and the problem changes character completely.

applied · Assignment

One minimum, or several. Two curves side by side with their local minima marked: a convex one with a single minimum, and a fourth-power well with 2.

Where the guarantee stops

Convexity converts every downhill method into a correct one, and its absence removes the guarantee entirely rather than degrading it. What is left is a collection of partial answers, and knowing which of them apply to a given problem is most of what non-convex optimisation is.

analysis · Convexity

Named alongside it

The objects these essays reach for when they reach for this one.

Complexity Assignment Bipartite Convexity Counterexample Gradient Integrality Linear programming Local minimum Matching Optimisation Polytope

All concepts