I'm trying to solve the following problem:
Show that the dual of ht epolynomial regression program $$\min t, -t \leq \sum_{i=0}^{d} c_is^i - f(s) \leq t, \quad \forall s\in S $$ is equivalent to the program $$\max_{\lambda, \sigma} \frac{1}{2}\big(\sum_{s\in S} \lambda_s f(s) - \sum_{s\in S} \sigma_s f(s)\big) $$ $$ \sum_{s\in S} \lambda_s s^i = \sum_{s\in S} \sigma_s s^i, \quad \forall i\in \{1,\dots,d\} $$ $$ \sum_{s\in S} \lambda_s = \sum_{s\in S} \sigma_s = 1, \lambda\geq 0, \sigma\geq 0$$
And in the solutions it makes the following step that I do not understand:
First we rewrite the nequality constraints of the regression program as: $$t+\sum_{i=0}^{d} c_is^i \geq f(s), \forall s\in S$$ $$t-\sum_{i=0}^{d} c_is^i \geq -f(s), \forall s\in S$$
And now comes the part where I lose it:
Using $\alpha^+, \alpha^- \geq 0$ as the dual multipliers (?) for the first and second set of constraints respectively, this yields the dual program:
$$\max \sum_{s\in S} f(s)(\alpha^+ - \alpha^-)$$ $$\sum_{s\in S}(\alpha^+ + \alpha^-) = 1 $$ $$\sum_{s\in S} s^i(\alpha^+ - \alpha^-) = 0, \forall i\in\{0,\dots,d\} $$ $$\alpha^+, \alpha^- \geq 0$$
I do not understand where this step follows from. I've tried to find an explanation for what the dual of a program is and what the dual multipliers are, but I just can't find anything that makes me understand what we've formed here and why it is the dual problem.