I'm learning about dual problems and was trying to get to an understanding of how to take the dual of a problem that has a sum in it.
For example if we try to optimize the sum of all values while keeping their cost bellow a certain value (knapsack)
max sum i=1...n(sixi)
where
sum i=1...n(pixi)<=p
x>0
how would I go about taking the dual of such a problem (doesn't have to be this problem this is only the example)?
I know that standard way for getting a dual problem is to try and get it in the following formula:
max cx
where Ax <b
x>0
corresponds to
min b^T y
where
A^T > c^T
y >0
But how does this work when there is a sum involved? I'm sorry if I'm screwing this up I'm mainly used towards thinking in terms of algorithms and procedures rather then pure mathematical expressions.
A summation typically leads to an indexed equation in the dual. Let me try with your example:
Primal problem: $$ \begin{array}{ll} \max & \sum_i s_i x_i \\ & \sum_i p_i x_i \le P \perp y\\ & x_i \ge 0 \end{array} $$
This is a knapsack problem: one constraint. So we have one dual variable $y$. The notation $\perp$ can be read as "with dual...". In the dual problem we will have as many equations as there are variables in the primal.
Dual problem: $$ \begin{array}{lll} \min & Py \\ & p_i y \ge s_i \perp x_i & \forall i \\ & y \ge 0 \end{array} $$