For $f:\mathbb Z_2^n \to [0, \infty)$, the entropy of $f$ is defined as $$ {\rm Ent}(f) = \mathbb E[f(X) \log f(X)] - \mathbb E f(X) \log(\mathbb E f(X)), $$ where $X$ is a random element of $\mathbb Z_2^n$. The variational formulation of entropy claims that $$ {\rm Ent}(f) = \sup\{\mathbb E[f(X) \times g(X)]~:~ \mathbb E e^{g(X)} \le 1, g:\mathbb Z_2^n \to \mathbb R \}. $$ How can we prove it?
I know the hint is to define $$ L(g, \lambda) = \mathbb E[f(X)g(X)] - \lambda (\mathbb E[g(X)] - 1). $$ and then we just need to show that $\sup_g \inf_{\lambda \ge 0} L(g, \lambda) = {\rm Ent}(f)$. But I don't know what technique can be applied to find the extremal value of $L(g, \lambda)$.