Theorem 3.3 — the constraint boundary condition

This is Theorem 3.3 of Balas's Disjunctive Programming: the exact condition under which one step of sequential convexification is valid.

Let $F_{j-1} \subseteq \mathbb{R}^n$, let $D_j := \bigvee_{i \in Q_j} (d_i x \ge d_{i0})$, i.e. $D_j = \bigcup_{i\in Q_j}\{x : d_i x \ge d_{i0}\}$, and let $\bar D_j := \{x : d_i x \le d_{i0},\ i \in Q_j\}$ be the system obtained by reversing every inequality of $D_j$ (the closure of the complement of $D_j$). Then

holds if and only if the constraint boundary condition holds: for every $x \in F_{j-1} \cap \bar D_j$ and $y \in F_{j-1} \cap D_j$,

where $\mathrm{bd}(\bar D_j)$ is the boundary of $\bar D_j$ relative to the affine space spanned by $\bar D_j$.

Formalization Note. The retired version defined $\bar D_j$ as the union $\bigcup_i \{d_i x \le d_{i0}\}$, whose boundary need not be where segments from outside $D_j$ enter $D_j$; with the terms $x \ge 0$, $x \ge 1$ in $\mathbb{R}$ and $F_{j-1} = \{-1, \tfrac12\}$, (3.6) held vacuously while (3.5) failed. The corrected definition Dbarj (module Disjunctive_SequentialConvex_Basic_v2) is the conjunction $\bigcap_i \{d_i x \le d_{i0}\}$ of the reversed inequalities, the convex set $C_j$ with $\mathbb{R}^n \setminus D_j = \{x : d_i x < d_{i0}\ \forall i\}$; the theorem is the reverse-convex result of Balas, Tama and Tind (1989) for $x \notin \operatorname{int} C_j$. The relative boundary is Mathlib's intrinsicFrontier; the book's "$\in$" in (3.6) is read as set inclusion. $F_{j-1}$ is an arbitrary set, as in the retired statement (the equivalence holds for every $F_{j-1}$).