A single linear feasibility formulation that exactly captures all the optimal solutions of both primal and dual.

Question

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?

Answer 1

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}$$