Lagmental Vicfred

Complementary Slackness Identifies Which Constraints Bind by Vicfred

tags: mathematics, polynomial algorithms, optimization, duality

Optimal primal and dual solutions pair positive variables only with tight opposing constraints. Keeping the exact identity in view prevents the geometric or probabilistic intuition from drifting.

The data

Fast algebraic algorithms exploit structure in a transform, matrix, or convex objective. The Fourier transform evaluates \(A(x)\) at roots \(\omega_n^k\), while linear-programming duality supplies certificates.

$$ x\ge0,\ Ax\le b,\qquad y\ge0,\ A^{\mathsf T}y\ge c $$

I read the first line as input and the second as output. The symbols \(\forall\) and \(\exists\) are not interchangeable, and neither may be upgraded silently to \(\Longleftrightarrow\).

$$ x_j((A^{\mathsf T}y)_j-c_j)=0,\qquad y_i(b_i-(Ax)_i)=0 $$

Derivation

The following line is the smallest calculation that still exercises the mechanism. It keeps nested delimiters and the order of operations explicit.

$$ b^{\mathsf T}y-c^{\mathsf T}x=\underbrace{y^{\mathsf T}(b-Ax)}_{\ge0}+\underbrace{x^{\mathsf T}(A^{\mathsf T}y-c)}_{\ge0}=0 $$

Invariant content

The two-row display is also a debugging tool: if the conclusion changes when only notation changes, some hidden choice has entered the argument.

$$ \begin{aligned} \mathsf{D}\;&:\quad x\ge0,\ Ax\le b,\qquad y\ge0,\ A^{\mathsf T}y\ge c,\\[5pt] \mathsf{C}\;&:\quad x_j((A^{\mathsf T}y)_j-c_j)=0,\qquad y_i(b_i-(Ax)_i)=0. \end{aligned} $$

Scope

An asymptotically fast method still needs algebraic preconditions: an NTT modulus needs suitable roots, and convex-hull optimization needs monotone slopes or queries for its simplest form.

$$ \boxed{\begin{gathered} \text{compact conclusion}\\[-2pt] x_j((A^{\mathsf T}y)_j-c_j)=0,\qquad y_i(b_i-(Ax)_i)=0 \end{gathered}} $$

The important habit is to remember what was fixed before the calculation began and what was proved only afterward. The final display preserves that order.

This article was posted on Sat 30 April 2016. Facts and circumstances may have changed since publication.
Please contact me before jumping to conclusions if something seems wrong or unclear.