Diagnosing Separation With Linear Programming

Why Use Linear Programming?

Separation is a geometric property of a binary-response design: a linear combination of the predictors assigns higher linear predictors to one response group than to the other. It is also a practical diagnostic problem. A linear program can turn the existence of such a direction into an optimization calculation, rather than relying on visual inspection or on whether a fitting algorithm appears to converge.

Let \(y_i\in\{0,1\}\) be the response for observation \(i\), and let \(x_i\in\mathbb{R}^p\) be its design vector, including an intercept column if the model has an intercept. Define the signed design vector \(z_i=(2y_i-1)x_i\). For any coefficient vector \(b\), the signed margin is \(z_i^\mathsf{T}b\): it is \(x_i^\mathsf{T}b\) when \(y_i=1\), and \(-x_i^\mathsf{T}b\) when \(y_i=0\).

A direction \(b\) is called a separating direction because moving the logistic coefficient vector along \(b\) moves every fitted linear predictor in a direction consistent with its observed response. The distinction between strictly positive margins and nonnegative margins matters: a quasi-complete direction may put some observations exactly on the separating boundary.

Normalize the Search Before Optimizing

The inequalities defining complete separation are strict. A solver for linear programs works with non-strict linear constraints, so replacing every strict inequality with \(z_i^\mathsf{T}b\geq\epsilon\) for a chosen positive \(\epsilon\) is not a valid general test: the scale of \(b\) can be changed. Instead, constrain the size of \(b\) and optimize the smallest margin.

Use the \(L^1\) normalization \(\lVert b\rVert_1=1\), where \(\lVert b\rVert_1=\sum_{j=1}^p |b_j|\). To express this with linear constraints, write \(b=u-v\), with \(u,v\in\mathbb{R}^p\) componentwise nonnegative, and impose \(\sum_j(u_j+v_j)=1\). This representation allows cancellation between \(u\) and \(v\), so it can have \(\lVert b\rVert_1<1\); that does not invalidate the tests below. A positive objective ensures \(b\neq 0\), and such a vector can be rescaled to have \(L^1\) norm one.

The variables \(u\), \(v\), and \(\delta\) enter linearly, so this is a linear program. Its objective is the smallest signed margin under the normalization. If it has a positive optimum, every observation has positive margin. If the design has a complete separating direction, that direction can be normalized to \(L^1\) norm one and gives a positive minimum margin.

Linear Program for Quasi-Complete Separation

A second program checks whether all margins can be nonnegative while at least one is positive. Under the same normalization, maximize the sum of the margins subject to nonnegativity of each margin. The objective is positive precisely when at least one of those nonnegative margins is positive.

This program may return a zero vector \(b=u-v\), because the split representation permits \(u=v\). Such a solution has objective zero and cannot falsely signal separation. In particular, a positive objective requires that the margins sum to a positive number, so at least one margin is positive and \(b\) is nonzero.

Proof. First suppose the complete-separation program has a feasible solution with \(\delta>0\). Set \(b=u-v\). For every \(i\), \(z_i^\mathsf{T}b\geq\delta>0\), so \(b\) is a complete separating direction. Conversely, suppose a complete separating direction \(b_0\) exists. It is nonzero. Rescale it to \(b=b_0/\lVert b_0\rVert_1\), and choose \(u_j=\max(b_j,0)\), \(v_j=\max(-b_j,0)\). Then \(b=u-v\), \(\sum_j(u_j+v_j)=1\), and \(\min_i z_i^\mathsf{T}b>0\). Taking \(\delta\) equal to that minimum gives a positive feasible objective. The feasible set relevant to maximizing \(\delta\) is bounded in \(u,v\), and \(\delta\) is bounded above by the finite margins, so the optimum is attained. Thus a positive optimum is equivalent to complete separation.

For the second program, a positive optimum gives margins that are all nonnegative and whose sum is positive. At least one margin is therefore positive, as required. Conversely, suppose \(b_0\) has all margins nonnegative and at least one positive. Normalize \(b_0\) to \(L^1\) norm one and represent it by \(u-v\) as above. The normalized margins remain nonnegative and their sum remains positive, giving a positive feasible objective. The feasible set for \(u,v\) is compact, so the optimum is attained. \(\square\)

For classification, first check the complete-separation optimum. If it is positive, the design is completely separated. If it is not positive, check the nonnegative-margin program: a positive optimum means quasi-complete separation; otherwise there is no separating direction of either type.

Worked Examples

Applying the Diagnostic Carefully

A practical analysis starts by assembling the design matrix with exactly the columns used by the binary logistic model. The response determines the sign of each row: use \(x_i\) for a one and \(-x_i\) for a zero. Then solve the two programs and inspect both the objective values and the returned direction. The direction is useful for understanding the pattern: observations with zero margin lie on its boundary, while positive-margin observations are on the response-consistent side.

The test is tied to the design actually supplied to the model. Changing factor coding, adding or removing an intercept, or changing the set of observations changes the design matrix and can change the diagnostic. Linear reparameterizations that preserve the same column space do not change whether a separating direction exists, but they can change its numerical coordinates.

For grouped binary data, a row representing a group with both successes and failures must not be treated as if all its outcomes were identical. The individual binary outcomes, or an equivalent formulation that accounts for both response types at that design point, are needed to reflect the margins correctly. The examples above make the issue visible: the same predictor value with both responses forces its linear predictor to zero for any weak separating direction.

Common Pitfall: Replacing Strict Inequalities With a Fixed Epsilon

A tempting check is to ask whether \(z_i^\mathsf{T}b\geq 0.01\) for all \(i\). If this fails, one might conclude that there is no complete separation. That reasoning is incorrect: a separating direction can have margins smaller than \(0.01\) simply because its coefficients were scaled down. Conversely, treating a numerical answer close to zero as an exact zero can misclassify a design.

The correction is to normalize the coefficient direction and optimize the minimum margin, as in the complete-separation program. In computation, interpret the solver’s result using its feasibility and optimality tolerances, and check the returned margins in the original design. If the optimum is very close to zero, the classification may be numerically delicate; report the tolerance or use higher precision rather than treating an arbitrary fixed epsilon as a mathematical criterion.

These programs diagnose the geometry of the observed binary-response design. They provide a reproducible way to distinguish strict separation, boundary separation, and the absence of either, and to identify the direction responsible when one exists.