Lagrangian duality in convex analysis: A (not so) summarized account
I've been dabbling in some convex optimization and decided to write this post to summarize the ideas in a (hopefully) clear and linear fashion. The material is mostly straight out of Boyd and Vandenberghe (freely available), inspired by this very helpful MSE post. Let's get started. We'll work with $\mathbb{R}^n$ for concreteness, though the theory extends to much more general contexts (such as Banach spaces). I presume you know a convex set $C \subseteq \mathbb{R}^n$ is one for which $x, y \in C$ and $0 \leq t \leq 1$ implies $tx + (1-t)y \in C$, and that a real-valued function $f$ is convex if its domain is convex and \[ f(tx + (1-t)y) \leq tf(x) + (1-t)f(y) \] for $x, y \in \text{dom}(f)$ and $0 \leq t \leq 1$ as before. I said $f$ is real-valued, but we also allow it to take on $\pm \infty$, adopting the standard conventions for arithmetic and inequalities with infinities, which will be useful later. Because of that, we define a proper convex function to be one wh...