Strict separation of disjoint linear polyhedra

ID: strict-separation-of-disjoint-linear-polyhedra

Nonempty disjoint linear polyhedra and admit with a strictly positive separation gap. A phase-I linear program minimizing common constraint violation has positive attained optimum. Its Lagrangian dual problem gives nonnegative with and . Then satisfies . The polyhedral hypothesis matters; arbitrary disjoint closed convex sets need not have a positive separation gap.

New to topics? Read the docs here!