Question

(p1) here we investigate the relevance of the kkt multipliers in a familiar setting. consider the l.o.p.
below:
max $z = 8x_1 + 11x_2$,
such that
$x_1 + 3x_2 \leq 12$,
$7x_1 + 9x_2 \leq 35$,
$4x_1 - 5x_2 \leq 20$,
and $x_1, x_2 \geq 0$.
suppose $\vec{x}^* = (x_1^*, x_2^*)$ is optimal and that $\mu_1, \cdots, \mu_5$ are corresponding kkt multipliers satisfying the kkt conditions at $\vec{x}^*$. answer the following.
(a) show that $\mu_1, \cdots, \mu_5$ satisfy the constraints in the dual problem. which $\mu_k$ are decision variables and which are slack variables?
(b) is $\vec{\mu} = (\mu_1, \cdots, \mu_5)$ an optimal solution to the dual problem? justify your answer.

Explanation:

First, we identify the optimal primal solution $\vec{x}^*=(x_1^*,x_2^*)$ by solving the linear program graphically or via simplex method:

Step 1: Find optimal primal solution

The constraints are:

1. $x_1 + 3x_2 \leq 12$
2. $7x_1 + 9x_2 \leq 35$
3. $4x_1 - 5x_2 \leq 20$
4. $x_1 \geq 0, x_2 \geq 0$

Solving the intersection of active constraints 1 and 2:
From $x_1 = 12 - 3x_2$, substitute into $7x_1 + 9x_2 = 35$:
$7(12-3x_2)+9x_2=35$
$84-21x_2+9x_2=35$
$-12x_2=35-84=-49$
$x_2^*=\frac{49}{12}\approx4.083$, $x_1^*=12-3\times\frac{49}{12}=12-\frac{49}{4}=\frac{48-49}{4}=-\frac{1}{4}$ (invalid, negative $x_1$)

Next, solve intersection of constraint 2 and $x_1=0$:
$9x_2=35\Rightarrow x_2=\frac{35}{9}\approx3.889$, check constraint 1: $0+3\times\frac{35}{9}=\frac{35}{3}\approx11.667\leq12$ (valid)
Objective value: $z=0+11\times\frac{35}{9}=\frac{385}{9}\approx42.778$

Solve intersection of constraint 1 and $x_2=0$:
$x_1=12$, check constraint 2: $7\times12+0=84>35$ (invalid)

Solve intersection of constraint 3 and $x_2=0$:
$x_1=5$, check constraint 2: $7\times5=35\leq35$ (valid), objective value: $z=8\times5+0=40<\frac{385}{9}$

Solve intersection of constraint 1 and 3:
$x_1=12-3x_2$, substitute into $4x_1-5x_2=20$:
$4(12-3x_2)-5x_2=20$
$48-12x_2-5x_2=20$
$-17x_2=20-48=-28$
$x_2=\frac{28}{17}\approx1.647$, $x_1=12-3\times\frac{28}{17}=\frac{204-84}{17}=\frac{120}{17}\approx7.059$
Check constraint 2: $7\times\frac{120}{17}+9\times\frac{28}{17}=\frac{840+252}{17}=\frac{1092}{17}\approx64.235>35$ (invalid)

The valid optimal solution is $\vec{x}^*=(0,\frac{35}{9})$, with active constraints: constraint 2 ($7x_1+9x_2=35$) and non-negativity $x_1\geq0$ (active, $x_1=0$). Constraints 1, 3, and $x_2\geq0$ are slack.

---

Part (a)

Step1: Write KKT conditions

Primal max $z=8x_1+11x_2$, constraints:
$g_1(x)=x_1+3x_2-12\leq0$, $g_2(x)=7x_1+9x_2-35\leq0$, $g_3(x)=4x_1-5x_2-20\leq0$, $g_4(x)=-x_1\leq0$, $g_5(x)=-x_2\leq0$

KKT conditions:

1. Gradient condition: $

abla z = \mu_1
abla g_1+\mu_2
abla g_2+\mu_3
abla g_3+\mu_4
abla g_4+\mu_5
abla g_5$

1. Complementary slackness: $\mu_i g_i(\vec{x}^*)=0$ for $i=1,...,5$
2. $\mu_i\geq0$ for $i=1,...,5$

Step2: Apply gradient condition

$
abla z=(8,11)$, $
abla g_1=(1,3)$, $
abla g_2=(7,9)$, $
abla g_3=(4,-5)$, $
abla g_4=(-1,0)$, $
abla g_5=(0,-1)$

$$\begin{cases} 8 = \mu_1 + 7\mu_2 + 4\mu_3 - \mu_4 \\ 11 = 3\mu_1 + 9\mu_2 - 5\mu_3 - \mu_5 \end{cases}$$

Step3: Apply complementary slackness

• $g_1(\vec{x}^*)=0+3\times\frac{35}{9}-12=\frac{35}{3}-12=\frac{35-36}{3}=-\frac{1}{3}

eq0\Rightarrow\mu_1=0$

• $g_2(\vec{x}^*)=0+9\times\frac{35}{9}-35=0\Rightarrow\mu_2\geq0$
• $g_3(\vec{x}^*)=0-5\times\frac{35}{9}-20=-\frac{175}{9}-20<0\Rightarrow\mu_3=0$
• $g_4(\vec{x}^*)=-0=0\Rightarrow\mu_4\geq0$
• $g_5(\vec{x}^*)=-\frac{35}{9}

eq0\Rightarrow\mu_5=0$

Step4: Solve for $\mu_2,\mu_4$

Substitute $\mu_1=\mu_3=\mu_5=0$ into gradient equations:

1. $8=0+7\mu_2+0-\mu_4$
2. $11=0+9\mu_2+0-0\Rightarrow\mu_2=\frac{11}{9}$

Then $\mu_4=7\times\frac{11}{9}-8=\frac{77}{9}-\frac{72}{9}=\frac{5}{9}$

Step5: Verify non-negativity

$\mu_1=0\geq0$, $\mu_2=\frac{11}{9}\geq0$, $\mu_3=0\geq0$, $\mu_4=\frac{5}{9}\geq0$, $\mu_5=0\geq0$ (all satisfy $\mu_i\geq0$)

Slack variables correspond to inactive constraints: $\mu_1$ (constraint 1), $\mu_3$ (constraint 3), $\mu_5$ (non-negativity $x_2\geq0$) are slack (equal to 0). Decision variables are $\mu_2,\mu_4$ (positive, correspond to active constraints).

Step1: Formulate dual problem

Primal: $\max z=8x_1+11x_2$
s.t.
$x_1+3x_2\leq12$
$7x_1+9x_2\leq35$
$4x_1-5x_2\leq20$
$x_1,x_2\geq0$

Dual problem (minimize, with $\mu_1,\mu_2,\mu_3\geq0$ for $\leq$ constraints, $\mu_4,\mu_5\geq0$ for $x_1,x_2\geq0$):
$\min w=12\mu_1+35\mu_2+20\mu_3+0\mu_4+0\mu_5$
s.t.
$\mu_1+7\mu_2+4\mu_3-\mu_4\geq8$
$3\mu_1+9\mu_2-5\mu_3-\mu_5\geq11$
$\mu_1,\mu_2,\mu_3,\mu_4,\mu_5\geq0$

Step2: Check feasibility of $\vec{\mu}$

Substitute $\mu_1=0$, $\mu_2=\frac{11}{9}$, $\mu_3=0$, $\mu_4=\frac{5}{9}$, $\mu_5=0$:

1. $0+7\times\frac{11}{9}+0-\frac{5}{9}=\frac{77-5}{9}=\frac{72}{9}=8\geq8$ (satisfies)
2. $0+9\times\frac{11}{9}-0-0=11\geq11$ (satisfies)

All $\mu_i\geq0$, so feasible.

Step3: Check strong duality

Primal objective value: $z^*=8\times0+11\times\frac{35}{9}=\frac{385}{9}$
Dual objective value: $w^*=12\times0+35\times\frac{11}{9}+20\times0+0+0=\frac{385}{9}$
Since $z^*=w^*$, by strong duality theorem, $\vec{\mu}$ is optimal for the dual.

Answer:

(a):
The KKT multipliers are $\mu_1=0$, $\mu_2=\frac{11}{9}$, $\mu_3=0$, $\mu_4=\frac{5}{9}$, $\mu_5=0$. The slack multipliers are $\mu_1,\mu_3,\mu_5$ (equal to 0), and the decision variables are $\mu_2,\mu_4$ (positive values).

---

Part (b)