1
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ 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? $\endgroup$
    – kkkkstein
    Commented Apr 20, 2021 at 7:31
  • $\begingroup$ I mean the formulation. your formulation is not equivalent yet. $\endgroup$ Commented Apr 20, 2021 at 7:51
  • $\begingroup$ 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? $\endgroup$
    – kkkkstein
    Commented Apr 20, 2021 at 9:25
  • $\begingroup$ I have written them in matrix form. $\endgroup$ Commented Apr 20, 2021 at 9:46
  • 1
    $\begingroup$ The weak duality constraint is redundant, so you need to enforce only one side of the equality. $\endgroup$
    – RobPratt
    Commented Apr 21, 2021 at 2:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .