I recently read the proofs of three optimization theorems (which I state below for convenience) in Optimization by Vector Space Methods by Luenberger. Each time, the story was remarkably similar and went like this: Take two convex sets $A,B\subset \mathbb{R}\times E$, where $B$ has interior points and $A$ contains no interior points of $B$. Apply the Hahn-Banach separation theorem, which gives a nonzero linear functional $(\lambda, w)\in (E\times \mathbb{R})^*$. Show that $\lambda,w\geq 0$, then that $\lambda>0$ by contradiction. Conclude.
I am a bit puzzled by the fact that these proofs are so similar. Is there an intuition that connects these three results? Even better, is there some unifying framework/theory that contains them?
Result 1: Rockafellar-Fenchel Duality. Let $E$ be a normed vector space, $E^*$ its topological dual space, $\varphi, \psi : E\rightarrow(-\infty,+\infty]$ two convex functions. Let $\varphi^*, \psi^*$ be the Legendre-Fenchel transforms of $\varphi, \psi$ respectively. Assume that there is some $x_0\in D(\varphi)\cap D(\psi)$ such that $\varphi$ is continuous at $x_0$. Then
$$\inf_{x\in E}\left\{\varphi(x)+\psi(x)\right\} = \max_{f\in E^*}\left\{-\varphi(-f^*)-\psi^*(f)\right\}$$
Result 2: Lagrange Multipliers for Global Constrained Optimization. Let $E$ be a linear vector space, $Z$ a normed space, $\Omega$ a convex subset of $E$, and $P$ the positive cone in $Z$. Assume that $P$ contains an interior point. Let $\varphi:\Omega\rightarrow \mathbb{R}$ and $G:\Omega\rightarrow Z$ be two convex functions Assume the existence of a point $x_1\in\Omega$ for which $G(x_1)$ is an interior point of $N=-P$. Let
$$\mu_0=\inf f(x) \text{ subject to } x\in\Omega, G(x)\leq 0$$
and assume $\mu_0$ is finite. Then there is an element $z_0^*\geq 0$ in $Z^*$ such that
$$\mu_0 = \inf_{x\in\Omega}\left\{f(x)+\langle G(x), z_0^*\rangle\right\}$$
Result 3: Kuhn-Tucker Theorem. Let $E$ be a vector space and $Z$ a normed space having positive cone $P$. Assume that $P$ contains an interior point. Let $f$ be a Gateaux differentiable real-valued functional on $E$ and $G$ a Gateaux differentiable mapping from $E$ into $Z$. Assume that the Gateaux-differentials are linear in their increments. Suppose $x_0$ minimizes $f$ subject to $G(x)\leq 0$ and that $x_0$ is a regular point of the inequality $G(x)\leq 0$. Then there is a $Z_0^*\in Z^*, z_0^*\geq 0$ such that the Lagrangian
$$f(x) + \langle G(x), z_0^*\rangle$$
is stationary at $x_0$; furthermore, $\langle G(x_0), z_0^*\rangle=0$
Best Answer
(Quasi-)convex functions have convex lower contour sets, and (quasi-)concave functions have convex upper contour sets.
Most maximization problems take the form of a (quasi-)concave or (quasi-)convex functions over a compact, convex set. This leads naturally to the issue of separating the feasible set from the (infeasible) upper contour sets of the function. The optimization condition $\nabla f(x^*) - \lambda \nabla g(x^*) = 0$ is really saying that the gradient of the objective and the gradient of the constraints are normals to a supporting hyperplanes of the constraint set. That is where the Hahn-Banach theorem happens.
I don't know the Duality stuff as well. My intuition about it was, if $f$ is (quasi-)convex then $-f$ is (quasi-)concave, and vice versa; likewise, $-\max = \min-$. Then if the epigraphs of a concave and convex function do not intersect, there is a separating hyperplane between them, and such a separating hyperplane can be characterized by those functionals in the dual space. So, there is a linear functional so that if you maximize it over one of the function's epigraphs, the same solution applies to minimizing the functional over the other function's endograph. Again, you have two convex sets, and you are separating them by a hyperplane.
Maybe a more intuitive version of the HB theorem for you would be: Let $K_1$ and $K_2$ be convex sets in a normed vector space $X$ so that $K_1$ has interior points and $K_2$ contains no interior point of $K_1$. Then there is a closed hyperplane $H$ separating $K_1$ and $K_2$: there exists an $x^* \in X^*$ such that $\sup_{x \in K_1} \langle x,x^*\rangle \le \inf_{x \in K_2} \langle x, x^*\rangle$.
The feasible set and upper contour sets, the epi- and endo-graphs, etc can all be understood as taking the roles of $K_1$ or $K_2$, and then the HB theorem provides the existence of the separating hyperplane, which is a supporting hyperplane to the graphs or constraint sets. The geometric intuition of all the situations is basically the same.
You might like Variational Inequalities as a next step in understanding some of these ideas.