Why a Dual Certificate Matters
A linear program can calculate the smallest or largest causal effect compatible with a collection of restrictions. But a numerical optimizer’s output is not, by itself, a proof that the reported endpoint is correct. A dual certificate provides an auditable inequality that applies to every feasible latent distribution. When its value matches the value from a feasible distribution, the two calculations together prove that the endpoint is sharp: no allowed distribution can do better, and at least one allowed distribution attains the bound.
The earlier material on Linear Programming For Sharp Causal Bounds establishes how a finite-support causal problem can be represented with nonnegative cell masses and linear restrictions. Here the emphasis is on what the dual says and how to verify a sharpness claim. The examples use hypothetical reduced-form programs: their constraint rows stand for restrictions obtained from observed data and maintained assumptions. The numerical restrictions are stipulated for illustration, not presented as data from a real study.
Primal and Dual Programs
Let \(x=(x_1,\ldots,x_J)^T\) contain the masses assigned to \(J\) possible latent states. The states might encode treatment status and potential outcomes. The restrictions are written \(Ax=b\), where \(A\) is a known \(K\)-by-\(J\) matrix and \(b\) is a known vector. The masses must satisfy \(x\geq 0\), component by component. Suppose the causal estimand for a distribution \(x\) is \(\theta=c^Tx\), where \(c_j\) is the contribution of state \(j\) to the estimand. For example, for a population average treatment effect, \(c_j\) can be the difference between the two potential outcomes in state \(j\).
The lower endpoint is the optimal value of the primal minimization problem. Since its constraints are equalities, the associated dual variables have no sign restrictions.
For the upper endpoint, the primal maximizes \(c^Tx\). Its dual minimizes \(b^Tz\), with \(A^Tz\geq c\). These directions matter: using the wrong inequality can turn a purported certificate into no certificate at all.
Why Matching Values Prove Sharpness
The key inequality is weak duality. If \(x\) is primal feasible and \(y\) is dual feasible for the minimization problem, then \(Ax=b\), \(x\geq0\), and \(A^Ty\leq c\) imply
Thus every dual-feasible \(y\) gives a lower bound \(b^Ty\) on the causal objective for every feasible latent distribution \(x\). If one feasible \(x^*\) and one feasible \(y^*\) satisfy \(c^Tx^*=b^Ty^*\), then no feasible distribution has objective smaller than \(c^Tx^*\), while \(x^*\) itself attains that value. It is therefore the minimum, not merely a plausible candidate.
For a maximization problem, \(A^Tz\geq c\) reverses the relevant comparison: \(c^Tx\leq z^TAx=z^Tb\). A feasible \(z\) therefore provides an upper bound on every feasible objective. If a feasible \(x^*\) attains that upper bound, the maximum is sharp. These arguments are finite-dimensional and require no asymptotic approximation.
Linear-programming strong duality says that if the primal feasible set is nonempty and the optimum is finite, the primal and dual optimal values agree; in these finite-dimensional programs the optima are attained. A matched pair of feasible solutions gives a direct certificate of this conclusion. For causal interpretation, there is one more requirement: \(x\) must represent a genuine distribution over allowed latent states, and the constraints must encode all and only the maintained restrictions. The certificate proves sharpness relative to that model, not relative to restrictions that were omitted.
Worked Example: Certifying Both Endpoints
Suppose three possible latent types have individual effects \(-1\), \(0\), and \(1\), respectively. Let their population masses be \(x_1,x_2,x_3\). A hypothetical set of restrictions requires total mass \(1\) and mass \(0.4\) on the two nonzero-effect types. The objective is the average effect \(\theta=-x_1+x_3\). Thus
For the lower endpoint, \(x^*=(0.4,0.6,0)^T\) is feasible: its masses are nonnegative, their sum is \(0.4+0.6+0=1\), and \(x_1+x_3=0.4+0=0.4\). Its effect is \(-0.4+0=-0.4\). Choose \(y=(0,-1)^T\). Then
The dual vector is feasible, and its value equals the feasible distribution’s value. Weak duality rules out any effect below \(-0.4\); the distribution attains \(-0.4\). The sharp lower endpoint is therefore \(-0.4\).
For the upper endpoint, \(x^*=(0,0.6,0.4)^T\) is feasible and has effect \(0.4\). Choose \(z=(0,1)^T\). The upper-bound dual conditions and value are
The feasible distribution and dual certificate match at \(0.4\), proving the sharp upper endpoint. The identified interval under these stipulated restrictions is \([-0.4,0.4]\). Because mixtures of feasible distributions remain feasible and the objective is linear, every value between the endpoints is also attainable.
Using the Dual as a Weighted Inequality
Each component of \(y\) assigns a weight to one equality restriction. The inequality \(A^Ty\leq c\) says that, for every latent state, the weighted combination of restriction coefficients does not exceed that state’s objective contribution. Multiplying these statewise inequalities by nonnegative masses and summing gives the bound. The dual variables are therefore useful algebraic weights; they are not probabilities, and they need not be positive.
A dual vector can be found computationally, proposed from the structure of the restrictions, or adjusted by hand. Whatever its source, the certificate is checked by evaluating \(A^Ty\) component by component and then \(b^Ty\). For a sharpness claim, also exhibit a feasible \(x\) and calculate \(c^Tx\). A solver’s status message can help find these vectors, but the displayed arithmetic is what makes the certificate independently checkable.
Worked Example: Two Different Sharp Endpoints
Consider three latent types again, with effects \(c=(-1,0,1)^T\), and masses satisfying total mass \(1\) and \(x_1+2x_2=0.6\). These give
For the minimum, take \(x=(0.6,0,0.4)^T\). The constraints hold because \(0.6+0+0.4=1\) and \(0.6+2(0)=0.6\); its effect is \(-0.6+0.4=-0.2\). The dual choice \(y=(1,-2)^T\) gives
The lower certificate matches the feasible effect, so the sharp minimum is \(-0.2\).
For the maximum, take \(x=(0,0.3,0.7)^T\). It satisfies \(0+0.3+0.7=1\) and \(0+2(0.3)=0.6\), and its effect is \(0.7\). Set \(z=(1,-0.5)^T\). Then
This proves a sharp maximum of \(0.7\). As a check on the endpoints, write \(x_1=0.6-2x_2\) and \(x_3=0.4+x_2\). Nonnegativity requires \(0\leq x_2\leq0.3\), and the effect is \(-x_1+x_3=-0.2+3x_2\). It ranges from \(-0.2\) to \(0.7\), consistent with both certificates.
Sharpness, Loose Certificates, and Common Mistakes
A dual-feasible vector proves a bound, but not necessarily the best bound. In the first example, \(y=(-1,0)^T\) is feasible for the lower-bound dual because
Its objective is \(b^Ty=1(-1)+0.4(0)=-1\). This establishes \(\theta\geq-1\), but the feasible distribution with effect \(-0.4\) shows that this certificate is loose: its value does not match the sharp endpoint. The matching certificate in the first example strengthens the lower bound to \(-0.4\).
Several checks help prevent false claims. Confirm that \(Ax=b\) and nonnegativity hold for the proposed masses. Check every dual inequality using the same ordering of states as the columns of \(A\) and the entries of \(c\). Recompute the dot products \(b^Ty\) or \(b^Tz\), including their signs. A lower-bound dual must satisfy \(A^Ty\leq c\); an upper-bound dual must satisfy \(A^Tz\geq c\). If constraints include inequalities rather than equalities, their associated dual sign restrictions must also be derived correctly, or the inequalities must first be represented consistently in the chosen program.
A numerical solution may be reported with rounding error, so a near match is not automatically an exact proof. For a rigorous certificate, report sufficient precision or use exact values when available, then verify feasibility and the objective gap at that precision. A gap larger than numerical tolerance means that the displayed pair has not yet certified sharpness.
- Wrong reasoning: “The optimizer returned \(-0.4\), so the lower bound is sharp.” Correction: show a feasible latent distribution attaining \(-0.4\) and a dual-feasible vector giving the same lower bound.
- Wrong reasoning: “Any feasible dual vector proves the sharp endpoint.” Correction: it proves a valid bound, which may be loose; matching primal and dual values establishes optimality.
- Wrong reasoning: “The dual variables are probabilities over latent types.” Correction: they weight restrictions in a bound; their entries may be negative and need not sum to one.
Primal optimization, dual certification, and direct algebra each have a role. A solver is efficient for a large finite-support model; the dual explains why a bound holds. Direct elimination or enumeration can be transparent for a small model, but becomes cumbersome as the number of states grows. All three approaches depend on the same support, observed restrictions, and maintained assumptions. None establishes that those assumptions are scientifically appropriate, and a sharp bound may still be wide.
Check Your Understanding
Answer each question, then compare your reasoning with the solutions below.
- For a lower-bound program, what two feasibility conditions must \(x\) and \(y\) satisfy before their objective values can certify sharpness?
- In the second worked example, set \(x_2=0.1\). Find \(x_1\), \(x_3\), and the effect.
- In the first worked example, explain why \(y=(0,-0.5)^T\) is not a valid lower-bound dual certificate.
- For an upper-bound program, state the dual inequality and explain which direction the resulting objective bound takes.
- A feasible primal distribution has objective \(-0.4\), and a feasible lower-bound dual vector has objective \(-0.3\). Do these values certify the minimum? Explain.
Solutions: (1) Require \(x\geq0\), \(Ax=b\), and \(A^Ty\leq c\). The values must match to certify sharpness. (2) The restriction \(x_1+2x_2=0.6\) gives \(x_1=0.4\); total mass gives \(x_3=1-0.4-0.1=0.5\). The effect is \(-0.4+0.5=0.1\). (3) Its first dual component is \(-0.5\), but the first entry of \(c\) is \(-1\); the required inequality \(-0.5\leq-1\) is false. (4) Require \(A^Tz\geq c\). Then every feasible effect satisfies \(c^Tx\leq b^Tz\), so the dual value is an upper bound. (5) No. A feasible lower-bound dual value of \(-0.3\) cannot be greater than the value \(-0.4\) of a feasible primal point, because weak duality requires \(b^Ty\leq c^Tx\). The stated pair is inconsistent with both feasibility claims, so at least one calculation or claim must be wrong.