Theorem 3.1 — faciality is sufficient for sequential convexifiability

This is Theorem 3.1 of Balas's Disjunctive Programming, the goal theorem of this mission: faciality is sufficient for a disjunctive program's convex hull to be computable one disjunction at a time.

Let $F$ be the constraint set of a disjunctive program with base polyhedron $F_0$ and disjunctions $(D_j)_{j \in S}$ as above. For an arbitrary ordering $\sigma$ of $S$, define the recursion $F_0, F_1, \dots, F_{|S|}$ as in the companion definition. If the program is facial — every inequality appearing in a disjunction defines a face of $F_0$ — then

regardless of which ordering $\sigma$ of $S$ was used. This means the convex hull of a facial disjunctive set can be generated in $|S|$ manageable stages, each requiring only the convex hull of a single elementary disjunction — a dramatically easier computation than generating $\mathrm{conv}(F)$ directly. The class of facial disjunctive programs includes (pure or mixed) 0-1 programming, nonconvex quadratic programming, separable programming, and the linear complementarity problem, but not general (pure or mixed) integer programming — for which, as the book's Example 1 shows explicitly, sequential convexification can fail.

Formalization Note. The universal quantification over σ in the theorem's own hypotheses (rather than fixing one ordering) is what encodes "for an arbitrary ordering" — the theorem asserts the conclusion for every choice of σ, matching the book's emphasis that the final result does not depend on the order in which disjunctions are imposed.