I have a question about linear optimization in which I have a double summation and I can't find out how I can convert this to it's dual.
This is the problem:
\begin{align}
\min \quad & \sum_{l=1}^M \sum_{m=1}^l p_{ml} x_{ml} \\
\text{s.t.} \quad & \sum_{m=1}^i \sum_{l=i}^M x_{ml} \geq d_i \text{ for all } i=1,\ldots,M \\
& x_{ml} \geq 0 \text{ for all } m=1,\ldots,M, l=1,\ldots,M
\end{align}
Any help would be greatly appreciated.
Best Answer
The easiest way is via the Lagrangian:
$$L(x,y) = \sum_{l=1}^M \sum_{m=1}^l p_{ml} x_{ml} + \sum_{i=1}^M y_i (d_i - \sum_{m=1}^i \sum_{l=i}^M x_{ml})$$
Note that $$\sum_{i=1}^M y_i \sum_{m=1}^i\sum_{l=i}^M x_{ml} = \sum_{i=1}^M \sum_{l=i}^M \sum_{m=1}^i y_i x_{ml} = \sum_{l=1}^M \sum_{i=1}^l \sum_{m=1}^i y_i x_{ml} = \sum_{l=1}^M \sum_{m=1}^l \sum_{i=m}^l y_i x_{ml}$$
So you can separate each $x_{ml}$ in the Lagrangian by writing it as: $$L(x,y) = \sum_i d_i y_i + \sum_{l=1}^M \sum_{m=1}^l \left( p_{ml} - \sum_{i=m}^l y_i \right) x_{ml} $$
The dual is:
$$\max_{y \geq 0} \min_{x \geq 0} L(x,y) = \max_{y \geq 0} \begin{cases} \sum_i d_i y_i & \text{if } p_{ml} - \sum_{i=m}^l y_i \geq 0 \text{ for all } l=1,\ldots,M, m=1,\ldots,l \\ -\infty & \text{otherwise}\end{cases}$$ So the dual is: $$\max_{y\geq 0} \left\{ \sum_i d_i y_i : p_{ml} - \sum_{i=m}^l y_i \geq 0 \text{ for all } l=1,\ldots,M, m=1,\ldots,l \right\}$$