How to obtain primal problem from Lagrangian?

Question

If you're trying to optimize $\min_x f_0(x)$ subject to $f_i(x) \leq 0$ then the Lagrangian would be

$$L(x, \lambda) = f_0(x) + \sum_i \lambda_i f_i(x)$$

The dual problem is $\max_\lambda g(y)$ where $g(\lambda)$ is obtained from the Lagrangian above:

$$g(\lambda) = \min_{x} \mathcal{L}(x, \lambda)$$

Now my question is, how do I obtain the primal problem itself from the Lagrangian?

I think the primal is $\min_x f(x)$ where

$$f(x) = \max_{\lambda} \mathcal{L}(x, \lambda)$$

but is this correct?

Oddly enough, I've never seen this mentioned anywhere, so I feel I might be missing something.

Answer 1

Yes, the primal optimal value is $\inf_x \sup_{\lambda \geq 0} L(x,\lambda)$ and the dual optimal value is $\sup_{\lambda \geq 0} \inf_x L(x,\lambda)$. A primal and dual optimal pair of variables gives you a saddle point of the Lagrangian. This is discussed on p. 238 (section 5.4.1) of Boyd and Vandenberghe, and is also discussed in other convex optimization books such as Borwein and Lewis (p. 88, section 4.3).