actually USING the lagrangian dual to solve a problem

Question

I don't get the maximisation bit in the dual problem...

Let's consider the standard form LP:

minimise $c^\top x$

subject to $Ax = b, x \geq 0$

This has lagrangian $$\mathcal{L} = c^\top x + \nu ^\top (Ax-b) - \lambda^\top x$$ $$= -\nu^\top b + (c^\top + \nu^\top A - \lambda^\top) x = -\nu^\top b + (c + A^\top\nu -\lambda)^\top x$$

so the dual function is

$$g(\lambda,\nu) = \inf_x\ \mathcal{L}=\begin{cases}-\nu^\top b, & \text{if } c + A^\top\nu -\lambda=0\\-\infty, & \text{otherwise}\end{cases}$$

and consequently, the dual we're trying to solve is

maximise $-\nu^\top b$

subject to $c + A^\top\nu -\lambda\geq 0$

This will yield some optimal $\lambda_*,\nu_*$ for which $g(\lambda_*,\nu_*) \geq c^\top x_*$ for optimal $x_*$.

Alright, I stared at this long enough to convince myself it (kind of) makes sense, so let's try that with, say,

$c = \begin{bmatrix}3\\9\\1\end{bmatrix}$, $A = \begin{bmatrix}2 & 1 & 0\\1 & 0 & 2\end{bmatrix}$, $b = \begin{bmatrix}8\\8\end{bmatrix}$

or

minimise $3x+9y + z$

subject to:

$2x + y = 8$

$x + 2z = 8$

$x,y,z \geq 0$

I do believe the result should be $x = 4, y = 0, z = 2$ with a minimum objective of $14$.

So ...

$-\nu^\top b = -8\nu_1 - 8\nu_2$, which we want to maximise

$c + A^\top \nu - \lambda = 0 \equiv \begin{cases} 3 + 2\nu_1 + \nu_2 -\lambda_1 = 0\\ 9 + \nu_1 - \lambda_2 = 0\\ 1 + 2\nu_2 - \lambda_3 = 0\end{cases}$

That's three equations for five variables and I expect the remaining two equations to be produced by the fact we're maximising (why else would we have bothered to determine the dual?)...

Except I have no idea how to continue from here.

Any help?

Answer 1

I think the problem you are facing is because you're adding the sign constraints into the lagrangian. For a linear program in standard form: $$\begin{align} \text{min} \quad c^Tx &\phantom{=} \\ \text{such that}\quad \mathrm{A}x &= b \\ x &\geq 0\end{align}$$ , the usual way to form the lagrangian for the above is: $$\begin{align} \min_{x\geq0} \quad c^Tx &\phantom{=} + p^T(b-\mathrm{A})x \\ \end{align}$$ If we now form the cost function for the lagrangian $g(p)$: $$\begin{align} g(p) &= \min_{x\geq0} \big(c^Tx + p^T(b - \mathrm{A}x) \big)\\ &= p^Tb \ + \ \min_{x\geq0} (c^T - p^T\mathrm{A})x \end{align}$$ Now this has the dual:

$$\begin{align} \max \quad p^Tb &\phantom{=} \\ \text{such that}\quad p^T\mathrm{A} &\leq c^T \\ p &\lessgtr 0\end{align}$$

Now, in case of your example, the dual would be:

$$\begin{align} \max \quad 8p_1 +8p_2 &\phantom{=} \\ \text{such that}\quad 2p_1 + 2p_2 &\leq 3 \\ p_1 &\leq 9 \\ 2p_2 &\leq 1\\ p &\lessgtr 0\end{align}$$

This could easily be solved by the graphical method to find the optimal value and $p$.