Skip to main content

complementarity_gap

Function complementarity_gap 

Source
pub fn complementarity_gap(
    x: &[Number],
    z_l: &[Number],
    z_u: &[Number],
    x_l: &[Number],
    x_u: &[Number],
    g: &[Number],
    lambda: &[Number],
    g_l: &[Number],
    g_u: &[Number],
) -> Number
Expand description

The objective error a converged point carries from stopping at a tolerance rather than at the optimum: its complementarity gap in the model’s own units,

Σ_i |z_l,i|·|x_i - x_l,i| + |z_u,i|·|x_u,i - x_i|  +  Σ_j |λ_j|·d_j

over the finite bounds, d_j the distance from g_j to its nearest finite bound (0 for a free row). To first order a point is above the optimum of the branch it sits on by at most this much (weak duality on the local model), so two points on one branch differ by at most the sum of their gaps however close to zero their objectives are. Multipliers scale with the objective and distances do not, so the gap does too.

gh#1128 follow-up: with only the relative and slack terms, two exact points at f* = 0 agreed only if both read exactly 0. On min a·x + (y - 1)^2, 0 <= x ⟂ y >= 0 the continuation stopped at 1e-11 (z_l·x with z_l = a = 0.01) and the relaxed path at 5e-20, so the cold exact solve ran on a model whose two cheap answers were one point. +inf if any input is not finite or the lengths disagree, which the tests that use it read as “cannot tell”.