Linear optimization and the dual

45 Views Asked by At

Write the dual of:

$$\min c^Tx\quad \text{s.t.}\quad Ax=b,\quad l\le x\le f$$

where $l$ and $f$ are fixed lower and upper bounds on the variables $x$.

Simplify the dual so that it has the fewest possible number of variables and constraints.

I find in standard form that $x\ge l$, $-x \ge -f$

So far for the dual I have

$$\max b^Tu,\quad\text{s.t.}\quad A^Tu \le c$$

$u$ is free because the $x$ is an equality constraint.

I think I should also consider the bounds on $x$ when writing the dual, but am not sure how to incorporate this.

1

There are 1 best solutions below

0
On

Through the Lagrangian

(This is the usual bazooka when you're not sure what to do)

So if you write the Lagrangian, you get:

$$ L(x,\lambda,\nu,\omega) = c^T x + \lambda^T(Ax-b) + \nu^T(l-x) + \omega^T(x-f) $$

which you can rearrange as

$$ L(x,\lambda,\nu,\omega) = -\lambda^T b +\nu^T l - \omega^T f + (A^T\lambda - \nu + \omega + c)^Tx $$

The dual is the function given by the infimum of the Lagrangian in $x$:

$$g(\lambda,\nu,\omega) = (-\lambda^T b +\nu^T l - \omega^T f) + \inf_x \,\,(A^T\lambda - \nu + \omega + c)^Tx$$

which is $-\infty$ unless $(A^T\lambda - \nu + \omega + c)=0$. That's one of your dual constraint.

Now you should maximize the dual with that constraint. The constraints over $\lambda, \nu, \omega$ are simple: since $\lambda$ corresponds to an equality constraint, it is unconstrained, $\omega,\nu$ have to be non-negative. In other words:

$$ \max_{\lambda,\nu,\omega}\,\, (-b^T\lambda +l^T\nu - f^T\omega) $$

such that

$$ (A^T\lambda - \nu + \omega +c) = 0, \nu\ge0, \omega\ge 0. $$

(Boyd and Vandenberghe's book is probably a good reference for this type of stuff)

Through the standard form

(This is the nicer technique if you remember your LP stuff)

You can put your problem in the standard inequality form by defining:

$$ M:= \left(\begin{array}{c} A\\-A\\-I\\+I\end{array}\right), \quad d:= \left(\begin{array}{c} b\\-b\\-l\\f\end{array}\right)$$

the problem then reads

$$ \min c^T x\quad \text{s.t.}\quad Mx\le d $$

which has dual

$$ \max -d^T\lambda\quad \text{s.t.}\quad M^T\lambda + c = 0,\quad \lambda \ge 0 $$

Note that here the lambda has the size of $d$ so its not the same dimensions as in the first approach. If you correspondingly write

$$ \lambda := \left(\begin{array}{c} \lambda_1\\\lambda_2\\\lambda_3\\\lambda_4\end{array}\right) $$

then the inequality can be written

$$ (A^T(\lambda_1-\lambda_2) - \lambda_3 +\lambda_4 +c)=0 $$

whilst the objective can be written

$$ (b^T(\lambda_1-\lambda_2) +l^T\lambda_3 - f^T\lambda_4)$$

Let $\lambda_0:=\lambda_1-\lambda_2$, it is now unconstrained while $\lambda_3$ and $\lambda_4$ still have to be $\ge 0$. Rewriting:

$$ \max_{\lambda_0,\lambda_3,\lambda_4} \quad (-b^T\lambda_0+l^T\lambda_3-f^T\lambda_4) $$

such that

$$ (A^T\lambda_0 - \lambda_3 +\lambda_4 +c)=0, \quad \lambda_3,\lambda_4\ge 0$$

which is obviously identical to the previous solution identifying $\lambda\leftrightarrow \lambda_0, \nu\leftrightarrow \lambda_3, \omega\leftrightarrow \lambda_4$