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}$


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?


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$.


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.