0
$\begingroup$

I am trying to employ a particular technique required to determine a dual problem of the following linear programming:

$$ \text{min } x_1 -3x_2-x_3 $$ $$ \text{subject to}\begin{cases} 3x_1 - x_2 + 2x_3 \geq 1\\ -2x_1 + 4x_2 +0x_3 \leq 12\\-4x_1 + 3x_2 +3x_3 = 14 \end{cases} $$ The first thing I tried was to reformulate in terms of dot products, giving us the equivalent problem $$ \text{min } c_0^Tx $$ $$ \text{subject to}\begin{cases} c_1^Tx \leq -1\\ c_2^Tx \leq 12\\c_3^Tx \leq 14\\c_4^Tx \leq -14 \end{cases} $$ where the equality has been turned into two inequalites and we have that $$ c_0 = (1,-3,-1), c_1 =(-3,1,-2),c_2 = (-2,4,0), c_3 = (-4,3,3), c_4 = (4,-3,-3) $$ Thus, we can further simplify to

$$ \text{min } c_0^Tx $$ $$ \text{subject to }Ax\leq b $$ Where we have put the $c_i$s into $A$ as rows, and $b^T = (-1,12,14,-14)$.

Thus, we can write our Lagrange function $$ L(x,\lambda) = \langle c_0, x \rangle + \langle \lambda, Ax-b \rangle $$ and our dual Lagrangian function as \begin{align*} h(\lambda) &= \text{inf}_{x\in\mathbb{R}^n} \{\langle c_0, x \rangle + \langle \lambda, Ax-b \rangle\}\\ &= -\text{sup}_{x\in\mathbb{R}^n} \{-\langle c_0, x \rangle - \langle A^T\lambda, x \rangle\} - \langle b, \lambda \rangle \end{align*} We notice that this is the definition of the convex conjugate, so \begin{align*} h(\lambda) &= -f^{\ast}(-A^T\lambda)-\langle b, \lambda\rangle\\ &=\begin{cases} \langle b, \lambda \rangle,& \text{if } -A^T\lambda = c_0\\ -\infty,& \text{if }-A^T\lambda \neq c_0 \end{cases} - \langle b, \lambda\rangle\\ &=\begin{cases} 0,& \text{if } -A^T\lambda = c_0\\ -\infty,& \text{if } -A^T\lambda \neq c_0 \end{cases} \end{align*}

Which just results in the dual problem of maximising zero, which is strange, and I am not sure I have the right answer, as I plugged this problem into a dual problem calculator and it didn't give me this result.

$\endgroup$
2
$\begingroup$

This problem is unconstrained, you can show that if you use the last constraint $−4x_1+3x_2+3x_3=14$ and solve for $x_3$, the problem is reduced to

$$ \text{min } \frac{1}{3}(-14 - x_1 - 6x_2) $$ $$ \text{subject to}\begin{cases} 17x_1 - 9x_2 &\geq& -25\\ x_1 - 2x_2 &\geq& -6 \end{cases} $$

If you move along the line $x_2 = 0$, the constraint on $x_1$ becomes $25+17x_1 \geq 0 $ and the objective function will have the form

$$ \frac{1}{3}(-14 - x_1) $$

which continuously decreases for increasing values of $x_1$, so the problem is unbound!

$\endgroup$
  • $\begingroup$ Hi Caverac, thanks for your answer. I am not sure how unboundedness relates to finding the dual problem? I see that the reduced problem is going to be much easier for finding the dual though. Can you give me a hint on how to proceed? Thanks $\endgroup$ – jamesmartini Jun 4 '18 at 6:26
  • $\begingroup$ @jamesmartini Can you further explain the meaning of this "Which just results in the dual problem of maximising zero, which is strange"? Why do you think it is strange? What solution did you find? Thanks $\endgroup$ – caverac Jun 4 '18 at 11:35
  • $\begingroup$ I didn't know what solution to expect, as I dont really have any intuition for the translation to dual problems for linear programs. It seems strange because I found the objective function to be zero. Which I suppose makes sense due to the fact that the primal problem doesn't have an optimal solution.. $\endgroup$ – jamesmartini Jun 5 '18 at 2:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.