# weak duality theorem

Studying duality theory I have not found clear this point

considering the primal a minimize problem, if $x$ and $p$ are feasible solution to the primal and to the dual then $p^tb \leq c^tx$

for any vector $x$ and $p$ we define

$u_i=p_i(a^t_ix-b_i)$

$v_j=x_j(c_j-p^tA_j)$

for the definition of the dual problem the sign of $p_i$ must be the same of the sign of $(a^t_ix-b_i)$ and the sign of $x_j$ must be the same of the sign of $(c_j-p^tA_j)$ so $u_i$ and $v_j$ are both $\ge 0$ ... etc

I don't understand why the sign must be the same and what these amounts mean.

## 1 Answer

In order for you to understand, I'll first type out the primal and dual problem first in vector form, then prove the weak duality theorem, and finally explain what $u_i$ and $v_j$ mean, so as to clear your doubts.

\begin{array}{ll} \text{min} & c^t x \\ \text{s.t.} & Ax \ge b \\ & x \ge 0 \tag{P} \end{array}

\begin{array}{ll} \text{max} & b^t p \\ \text{s.t.} & A^t p \le c \\ & p \ge 0 \tag{D} \end{array}

If you think of $u_i$ and $v_j$ as components of vectors, from the RHS of these two equations, it's not hard to see that the scalar $x^t A^t p$ is the "man in the middle".

$$b^t p \le x^t A^t p \le c^t x \tag{1}\label{pf}$$

The first half of the above inequality is from the primal constraint $Ax \ge b$ and the second half is from $A^t p \le c$. We've finished the proof the weak duality theorem. From the above inequality, we have

\begin{array}{r@{}c@{}l} 0 &{}\le (x^t A^t - b^t) p &{}= p^t (Ax - b) \\ 0 &{}\le c^t x - x^t A^t p &{}= x^t (c - A^t p) \tag{2} \label{eq2} \end{array}

Therefore, comparing these two inequality with $u_i=p_i(\color{red}{A^t_i} x-b_i)$ and $v_j=x_j(c_j-p^tA_j)$, we know that

1. To calculate $Ax - b$, we need to multiply the $i$-th row of $A$ by $x$. (i.e. The $i$-th column of $A^t$, which is denoted by $A_i^t$. $p_i$ is simply the $i$-th component of $p$, and $u_i$ is the $i$-th term of the sum $p^t (Ax - b)$.
2. To calculate $c - A^t p$, we need to multiply the $j$-th row of $A^t$ by $p$. (i.e. The $j$-th column of $A$, which is denoted by $A_j$. $x_j$ is simply the $j$-th component of $x$, and $v_j$ is the $j$-th term of the sum $x^t (c - A^t p)$.

• $p_i,x_j$ are due to $x,p \ge 0$
• $\color{red}{A^t_i} x-b_i \ge 0$ and $c_j-p^tA_j \ge 0$ are due to $Ax \ge b$ and $A^t p \le c$.
• i.e. We have $u_i=p_i(\color{red}{A^t_i} x-b_i) \ge 0$ and $v_j=x_j(c_j-p^tA_j) \ge 0$

The importance of $u_i$ and $v_j$ is that they allow us to get \eqref{eq2}, which implies \eqref{pf}.