At komplementær slakkhet fører til optimalitet er ganske greit å se, men hvorfor fører optimalitet til komplementær slakkhet?

La oss si at vi har primal \(\min cx : Ax \geqslant b\) og dual \(\max yb : yA\leqslant c\), der \(x, y\geqslant 0\). Det følger at \(cx\geqslant yAx \geqslant yb\), og ved optimum har vi, fra dualitetssetningen, at

\[cx = yAx = yb\mathrlap{\,.}\]

Vi ser at hvis

\[(Ax)_i \neq b_i \implies y_i=0\]

så har vi \(yAx = cx\), og hvis

\[(yA)_j \neq c_j \implies x_j=0\]

så har vi \(yb=yAx\), så om begge disse betingelsene holder – det vi altså kaller komplementær slakkhet – så har vi \(yb = cx\), så \(x\) og \(y\) er optimale. Men det er også tilfelle at dersom \(yb = cx\) så følger de to betingelsene – med andre ord, de er både tilstrekkelige og nødvendige for optimalitet.

Williamson og Shmoys sier, i beviset for sitt korollar A.3 følgende (lett omskrevet):

If \(x\) and \(y\) are optimal solutions, then by strong duality the two inequalities \(cx\geqslant yAx\) and \(yAx\geqslant yb\) must hold with equality, which implies that the complementary slackness conditions are obeyed.

Men er det helt opplagt? Det kan se ut som om Williamson og Shmoys har vært litt kjappe, og utelatt deler av resonnementet. Som det ble nevnt av en student i dag, så kunne vi jo tenke oss f.eks.

\[y = \begin{bmatrix} 1 & 1 \end{bmatrix}\,, \quad Ax = \begin{bmatrix} 1\\ 2 \end{bmatrix}\,, \quad b = \begin{bmatrix} 2\\ 1 \end{bmatrix} \mathrlap{\,.}\]

Vi har jo da \(yAx=yb\), men ikke komplementær slakkhet: Ingen av primalrestriksjonene er stramme, og ingen av dualvariablene er \(0\). Hva er det som ikke stemmer her? Hvorfor vil det være umulig å velge \(A\) og \(c\) så vi får \(cx = yA\), og dermed optimalitet? Det følger av at \(Ax\geqslant b\), som vi ikke har tatt hensyn til her.

La oss skrive om ligningen vår til \(y(Ax-b)=0\). Vi vet at \(y_i\geqslant 0\) og \((Ax-b)_i\geqslant 0\) for \(i=1\dots m\) (det siste altså fordi vi krever \(Ax\geqslant b\)) så om vi skal ha

\[y(Ax-b) = \sum_{i=1}^m y_i(Ax-b)_i = 0\]

så må vi ha \(y_i(Ax-b)_i=0\) for \(i=1\dots m\), dvs., \((Ax)_i\neq b_i\implies y_i=0\). Det samme argumentet gjelder for den andre betingelsen.