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

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?

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

• You mean imposing the strong duality constraint ($c^Tx = y^Tb$) in the proof of the forward direction or in the original linear feasibility formulation? For the forward direction, are we trying to show that if $(x^*,y^*)$ are feasible, and if we can show $c^Tx^* = y^*Tb$, then we can conclude $(x^*,y^*)$ are optimal? Can you explain more about the forward direction of the proof? Apr 20, 2021 at 7:31
• I mean the formulation. your formulation is not equivalent yet. Apr 20, 2021 at 7:51
• So I was able to get something like this $\begin{pmatrix}A & -1 \\ -1 & -A^T \end{pmatrix}$$\begin{pmatrix}x \\ y\end{pmatrix} \leq \begin{pmatrix}b \\ -c\end{pmatrix}$. But I am stuck at trying to impose those two inequalities $c^Tx \leq y^Tb$ and $-c^Tx \leq -y^Tb$ in the matrix, can you give me some hint how to do that or am I on the right track? Apr 20, 2021 at 9:25
• I have written them in matrix form. Apr 20, 2021 at 9:46
• The weak duality constraint is redundant, so you need to enforce only one side of the equality. Apr 21, 2021 at 2:28