After reading some papers, this problem confuses me.
There are different forms of dual problem to the primal problem:
$$\underset{x}\min \ \ f(x)$$
where $f(x)$ is a convex function.
By forming the Lagrangian and doing:(S. Boyd convex optimization ch. 6) $$\underset{\lambda\geq 0}\sup \underset{x}\inf \ \ L(x,\lambda)$$
Form the lower linear model: (Y. Nesterov
Primal-dual subgradient methods for convex optimization)
The minimization of the right hand side is the lower bound of the primal problem.
And the paper says
dual problem can be posed in different forms depending on the structure of the problem.
My questions is:
How to get intuition or an efficient observation to form a dual problem based on the structure of the primal problem? (In a broad view and sense)