= Solution
Associate nonnegative <Lagrange multipliers> $\alpha$ with $-Pz-\mathbf1\le0$ and $\beta$ with $Pz-\mathbf1\le0$. The <Lagrangian dual problem> is obtained from
$$
L(z,\alpha,\beta)=r_0^Tx-\mathbf1^T(\alpha+\beta)
+[x-P^T(\alpha-\beta)]^Tz.
$$
Its infimum over unrestricted $z$ is finite exactly when $P^T(\alpha-\beta)=x$. Thus the dual is
$$
\boxed{\sup_{\alpha,\beta\ge0}\ r_0^Tx-\mathbf1^T(\alpha+\beta)
\quad\text{subject to }P^T(\alpha-\beta)=x.}
$$
The precise finiteness condition is $x\in\operatorname{range}P^T$. If $x=P^Tq$, then $x^Tz=q^TPz\ge-\|q\|_1$ on the feasible set. The primal is feasible and bounded below, and splitting $q$ into positive and negative parts makes the dual feasible. <Linear programming duality> therefore gives attained equal finite optima. Equivalently, the strictly feasible point $z=0$ satisfies the <Slater condition>, with the required finiteness hypothesis. This is <strong duality> in the usual finite sense.
If $x\notin\operatorname{range}P^T=(\ker P)^\perp$, there is $d\in\ker P$ with $x^Td<0$. Every $z=td$, $t\ge0$, is feasible and the objective tends to $-\infty$. The dual is then infeasible. Equality of extended values still holds if its supremum over the empty feasible set is defined as $-\infty$, but there are no finite optimizers. The paper does not assume full column rank of $P$, so this qualification is necessary. The same calculation gives the <support function of an inverse image of an infinity-norm ball>, $\inf_r r^Tx=r_0^Tx-\min_{P^Tq=x}\|q\|_1$ for finite decisions.
Back to article page
