Given a linear program, we have the primal as follows:
\begin{array}{lll}
\max: & c^Tx\\
\text{s.t.} & Ax \leq b\\
& x\geq 0\\
\end{array}
And we also have the dual as follows:
\begin{array}{lll}
\min: & y^Tb\\
\text{s.t.} & y^TA \geq c\\
& y \geq 0\\
\end{array}
Now, the question is (a)to design a single linear feasibility formulation (i.e. Find $z$ such that $Bz \leq k$) that exactly captures all the optimal solutions of both primal and dual. (b)show that $(x^*,y^*)$ is feasible in the formulation if and only if $x^*$ is an optimal solution of the primal and $y^*$ is an optimal solution of the dual.
Here's what I got so far:
The single linear feasibility formulation is the following:
$\begin{pmatrix}A & 0 \\ 0 & -A^T \end{pmatrix}$$\begin{pmatrix}x \\ y\end{pmatrix} \leq \begin{pmatrix}b \\ -c^T\end{pmatrix}$, where $A \in \mathbb{R}^{m\times n},x\in\mathbb{R}^{n\times 1}, y\in\mathbb{R}^{m\times 1}$.
From this formulation, it should capture all the optimal solution of both primal and dual.
Now,for part (b), the converse direction is trivial because if $x^*$ is an optimal, then it means $Ax^* \leq b$ and $y^*$ is an optimal solution of the dual means $-A^Ty^* \leq -c^T$, so $z=(x^*,y^*)$ is feasible in the formulation.
However, I am stuck in the forward direction, which is if $(x^*,y^*)$ is feasible in the formulation, then $x^*$ is an optimal solution of the primal and $y^*$ is an optimal solution of the dual. Can I get some help for that? Do I have to use the strong duality theorem in order to prove that?
Best Answer
You want to impose the duality constraint as well, that is $c^Tx \ge y^Tb$.
Also, don't forget the sign constraint, which is $x \ge 0$ and $y \ge 0$.
Here is the equivalent single linear feasibility formulation which captures optimal solution of primal and dual:
\begin{align} -c^Tx &\le -y^Tb \\ x &\ge 0 \\ y &\ge 0 \\ Ax &\le b \\ -A^Ty &\le -c \end{align}
You just have to write it as a single inequality.
Edit:
$$\begin{bmatrix} -c^T & b^T \\ -I & 0 \\ 0 & -I \\ A & 0 \\ 0 & -A^T\end{bmatrix} \begin{bmatrix}x \\ y \end{bmatrix} \le \begin{bmatrix} 0 \\ 0\\ 0 \\ b \\ -c\end{bmatrix}$$