The conjugate function (Fenchel conjugate)
- Counterpart to Fourier transform in Convex Analysis
The conjugate of \(f\) (\(f\) not necessarily convex):
\[ f^*(y) = \underset{x\in \text{dom }f}{\sup} (y^Tx - f(x)) \]
The domain of \(f^*\) consists of \(y\in \mathbb{R}^n\) for which the supermum is finite, i.e. for which the difference \(y^T x - f(x)\) is bounded above on \(\text{dom }f\).
\(f^*\) is convex, since it is the pointwise supremum of a family of affine functions of \(y\).
Examples:
\[ f^*(y) = \left\{ \begin{array}
-b &y=a\\
\infty &\text{otherwise}
\end{array} \right. \] with \(\text{dom }f^* = \{a\}\).
The function \(xy + \log x\) is unbound above if \(y\ge 0\) and reaches its max at \(x=-1/y\) otherwise.
\[ f^*(y) = \left\{ \begin{array}
-1-\log (-y) &y\lt 0\\
\infty &\text{otherwise}
\end{array} \right. \] with \(\text{dom }f^* = \{y\; |\; y\lt 0 \}\)
Fenchel's inequality
\(f^*\) is convex, since it is the pointwise supremum of a family of affine functions of \(y\).
Examples:
- Affine function. \(f(x)=ax+b\). \(f^*(y) = yx-ax-b = (y-a)x-b\).
\[ f^*(y) = \left\{ \begin{array}
-b &y=a\\
\infty &\text{otherwise}
\end{array} \right. \] with \(\text{dom }f^* = \{a\}\).
- Negative logarithm. \(f(x) = -\log x\), with \(\text{dom }f=\mathbb{R}_{++}\).
The function \(xy + \log x\) is unbound above if \(y\ge 0\) and reaches its max at \(x=-1/y\) otherwise.
\[ f^*(y) = \left\{ \begin{array}
-1-\log (-y) &y\lt 0\\
\infty &\text{otherwise}
\end{array} \right. \] with \(\text{dom }f^* = \{y\; |\; y\lt 0 \}\)
Fenchel's inequality
Fenchel's inequality can be obtained from the definition of conjugate function
\[ f(x) + f^*(y) \ge x^T y , \quad \forall x,y\]
since for each \(y\),
\[ f^*(y) \ge x^Ty - f(x) \Leftrightarrow f(x) + f^*(y) \ge x^Ty \]
since for each \(y\),
\[ f^*(y) \ge x^Ty - f(x) \Leftrightarrow f(x) + f^*(y) \ge x^Ty \]
No comments:
Post a Comment