Doubt when applying Complementary Slackness Theorem

Question

I have a doubt about an application of the Complementary Slackness theorem. I want to show that $\mathbf{x}^{\ast} = (7.25, 0 , 3.25 , 0.75)$ is an optimal solution of the linear program (which is, checking on a software)

\begin{align*} \max \quad x_1 + x_2 - 2x_3 + 2x_4 \\ x_1 - x_2 - x_3 - 2x_4 = 2.5 \\ x_1 + x_2 + x_4 = 8 \\ x_1 + 2x_2 - x_3 = 4 \\ x_1, x_2, x_3, x_4 \geq 0 \ . \end{align*} What I did was write the dual problem, test the feasibility of $\mathbf{x}^{\ast}$, and it happens that $\mathbf{x}^{\ast}$ satisfies all constraints with equality, so, by Complementary Slackness, there should be a $\mathbf{y} ^{\ast} = (y_1^{\ast}, y_2^{\ast}, y_3^{\ast})$ such that equality holds on the dual problem constraints, that is

\begin{align*} y_1^{\ast} + y_2^{\ast} + y_3^{\ast} = 1 \\ -y_1^{\ast} + y_2^{\ast} + 2y_3^{\ast} = 1 \\ y_1^{\ast} + y_2^{\ast} = 2 \\ -2y_1^{\ast} + y_2^{\ast} = 2 \ , \end{align*}

and... the system has no solution.

EDIT: One of the problems I was having was finding the proper dual problem, which is

\begin{align*} \min \quad 2.5y_1 + 8y_2 + 4y_3 \\ y_1 + y_2 + y_3 \geq 1 \\ -y_1 + y_2 + 2y_3 \geq 1 \\ -y_1 - y_3 \geq -2 \\ -2y_1 + y_2 \geq 2\ , \end{align*}

so, by the version of the Complementary Slackness Theorem I am familiar with, a solution for the primal is optimal if and only if the dual problem constraints are satisfied as an equality for some $y^{\ast} = (y_1^{\ast}, y_2^{\ast}, y_3^{\ast})$, everytime a constraint is satisfied with equality (and in this case, ALL constraints are satisfied with equality). So, either this version of the theorem is false, or it doesn't hold when all constrains are satisfied with equality in the primal problem, and that is my doubt.

Answer 1

General strategy

To apply duality, use the SOB table.

In this case, we have

• primal equality constraints transformed to unrestricted dual variables, and
• positive primal variables transformed to $\ge$ constraints in the dual.
• Your mistake is wrong type of dual constraints.

You may want to see MIT's notes section 4.3 for the derivations of such transform.

Theoretical explanation for the mistake

Your attempt: Transform $$\max z=\sum_{j} c_jx_j \\ \text{s.t. } \sum_{j} a_{ij}x_j = b_j \quad (i=1,\dots,m) \\ x_j \ge 0 \quad (j=1,\dots,n)$$ into $$\min v=\sum_{i} b_iy_i \\ \text{s.t. } \sum_{i} a_{ji}y_i = c_i \quad (j=1,\dots,n) \\ y_i \ge 0 \quad (i=1,\dots,m)$$

In fact, if you transform it into the standard form $$\max z=\sum_{j} c_jx_j \\ \text{s.t. } \sum_{j} a_{ij}x_j \le b_j \quad (i=1,\dots,m)\\ \sum_{j} -a_{ij}x_j \le -b_j \\ x_j \ge 0 \quad (j=1,\dots,n)$$ you'll see the dual is $$\min v=\sum_{i} b_iy_i^+ +\sum_{i} -b_iy_i^- \\ \text{s.t. } \sum_{i} a_{ji}y_i^+ \sum_{i} -a_{ji}y_i^- \ge c_i \quad (j=1,\dots,n) \\ y_i^+,y_i^- \ge 0 \quad (i=1,\dots,n)$$ Collecting $y_i^+-y_i^-$, we get the expected form. $$\min v=\sum_{i} b_iy_i \\ \text{s.t. } \sum_{i} a_{ji}y_i \ge c_i \quad (j=1,\dots,n) \\ y_i \text{ unrestricted} \quad (i=1,\dots,n)$$

---

Additional response to updated question

So, either this version of the theorem is false, or it doesn't hold when all constrains are satisfied with equality in the primal problem, and that is my doubt.

My correction

• This version of the theorem is true.
• It does hold when all constraints are satisfied with equality in the primal problaem, and
• that is not my doubt. (Since this is the Strong Duality Theorem.)

Remarks:

1. After answering this linear-programming question, I'll change my old complementary slackness habits to solve problem faster using the SOB table.

2. I find it difficult to understand this in the question body.

   by the version of the Complementary Slackness Theorem I am familiar with ... and in this case, ALL constraints are satisfied with equality.

   It takes time to guess where the constraints are. (In the primal or dual?) To be concise and precise, I'll describe this as complementary slackness in words (to facilitate oral commumincation when there's no writing tool).

   In the optimal feasible solution,

   • A nonzero primal decision variable makes its corresponding dual slack/surplus variable zero.
   • A nonzero primal slack/surplus variable makes its corresponding dual decision variable zero.

   N.B.: The words "primal" and "dual" can be interchanged in the above sentences.

   The advantage of using "primal/dual slack/surplus variable" variables over "the inequality constraints is satisfied with equality" is the conciseness and clearity. You won't confuse the given equality constraints with the ones found by complementary slackness.

Verification using your optimal solution

I suggest you to DIY, then check the solution.

Given optimal solution $\mathbf{x}^{\ast} = (7.25, 0 , 3.25 , 0.75)$. Apply complementary slackness. $$\begin{cases}x_1^*:& y_1+y_2+y_3 &= 1\\x_3^*:& -y_1\phantom{+y_2}-y_3 &= -2\\x_4^*:& -2y_1+y_2\phantom{+y_3} &= 2\end{cases}$$ Explanation: nonzero 1st, 3rd & 4th primal decision variables $\implies$ zero 1st, 3rd & 4th dual surplus variables. Solving this linear system gives $\mathbf{y}^*=(-1,-1.5,3.5)$. Check if 2nd dual constraint satisfied: $$-y_1^{\ast} + y_2^{\ast} + 2y_3^{\ast}=1.5 -1 + 2(3.5)=7.5 \ge 1,$$ then check optimality $$2.5y_1^*+8y_2^*+4y_3^*=2.5(-1.5)+8(-1)+4(3.5)=-3.75-8+14=2.25 \\ x_1^* + x_2^* - 2x_3^* + 2x_4^*=7.5+0-2(3.25)+2(0.75)=2.25.$$ So we can conclude the optimality from the weak duality theorem.