1

I tried to solve this problem, but I am not sure if I am right. Otherwise, I find some solution in one book and solution is very questionable. One more thing, I am not sure how to this problems when there are equality constraints. Find dual problem for min $-x_1+2x_2+3x_3$ subject to $x_1-x_2+2x_3=1$, $2x_1+x_2<=3$, $x_1<=0$, $x_2>=0$, $x_3>=0$ and solve it.

First, I use change $_1=−_1$ where $_1 \ge 0$ . I observe these three constraints: $−_1−_2+2_3\ge 1$ , $_1+_2−2_3\ge −1$, $−2_1+_2\ge −3$ and create dual problem: $\max _1−_2−3_3$ subject to $−_1+_2−2_3\le −1$ , $−_1+_2+1_3\le 2$, $2_1−2_2\le 3$ . Is this right?

Siong Thye Goh
  • 149,520
  • 20
  • 88
  • 149
Broj 1
  • 65
  • 8
  • include what you tried – Siong Thye Goh Aug 09 '21 at 14:53
  • First, I use change $x_1=-a_1$ where $a_1 \geq 0$. I observe these three constraints: $ -a_1 - a_2+2a_3 \geq 1$, $ a_1 + a_2-2a_3 \geq -1$, $-2a-1+a-2 \geq -3$ and create dual problem: max $y_1-y_2-3y_3$ subject to $-y_1+y_2-2y-3 \leq -1$ , $-y_1+y_2+1y-3 \leq 2$, $2y_1-2y_2 \leq 3$. Is this right? – Broj 1 Aug 09 '21 at 15:21

1 Answers1

1

This is not right. You primal problem is

\begin{align} & \texttt{Min} \ -x_1+2x_2+3x_3 \\ & \ \ x_1-x_2+2x_3=1 \qquad (\color{red}{y_1})\\ & 2x_1+x_2\leq 3 \qquad (\color{red}{y_2}) \\ & x_1\leq 0, x_2,x_3\geq 0 \end{align}

So $y_1$ and $y_2$ are your dual variables. We can use the table below to formulate the dual problem. We have to read it from the right to the left, since the primal problem is a min-problem:

\begin{align} & \texttt{Max} \ y_1+3y_2 \\ & \ \ y_1+2y_2\geq -1 \qquad (\color{blue}{x_1})\\ & -y_1+y_2\leq 2 \qquad (\color{blue}{x_2}) \\ & 2y_1\leq 3 \qquad (\color{blue}{x_3}) \\ & y_1 \textrm{free}, y_2 \leq 0 \end{align}

enter image description here

callculus42
  • 30,550
  • Thanks. Now this maximum problem we solve finding KKT points, don't we? One more thing, why is A transpose on both sides? – Broj 1 Aug 09 '21 at 18:11
  • I wouldn't call them kkt points. We just Look for the extreme point(s). Don't care much about the notation. In this case it has something to do wird the indexes, I guess. It always depends on the definition. – callculus42 Aug 09 '21 at 18:25
  • Allright. One more question, is same procedure when we solve maximum and when we solve minimum function finding KKT points? – Broj 1 Aug 09 '21 at 18:54
  • @Broj1 If you have to minimize $z$, then it is equivalent to maximize $-z$. z is the objective function here. // In this case the dual (max-problem) is probably more comfortable, since it has two variables only. That means one can try to solve it graphically. – callculus42 Aug 09 '21 at 19:26
  • Thank you. Bye. – Broj 1 Aug 09 '21 at 19:38
  • @Broj1 You´re welcome. Mark the answer as accepted. Thanks in advance. Bye. – callculus42 Aug 09 '21 at 19:48