Conjugation duality is used to solve non-linear optimization problems (including indicator functions), using a duality property between auxiliary variables.
Let us define a function \(f(x)\), where the convex conjugate (Legendre transform, if \(f\) is differentiable) of which is defined by
\[ f^*(y) = \sup_{x\in\textbf{dom}f} (y^Tx - f(x)). \]
Properties:
- Fenchel’s inequality: for any \(x\), \(y\), \(f(x) + f^*(y) \ge x^Ty\).
Proof: See definition
- Conjugate of Conjugate \(f^{**} \le f\)
Proof: From the definition, it can be easily shown that \(-\max_{z}z^Ty - f(z) \le x^Ty-f(x)\), for all \(x\). From this, the following condition holds
\[ \begin{aligned} &f^{**}(x) = \max_y x^T y - f^*(y)\\ &= \max_y \{x^T y - \max_z\{z^Ty - f(z)\} \}\\ &\le \max_y\{ x^Ty - x^Ty + f(x) \}\\ &=f(x). \end{aligned} \]
Example1 (Quadratic)
\(f(x) = \frac{1}{2}x^TA^{-1}x\)
\(f^*(y) = \max y^T x - f(x)\) –> \(x=Ay\). –> \(f^*(y) = \frac{1}{2} y^T A y\).
Example 2 (Indicator Fuction)
\(f(x)=I_C(x)\), where \(I_C(x)=\infty~ \text{ if } ~ x\in C\), 0 otherwise.
\(f^*(y) = \max_{x} y^T x - I_C(x)\) \(= \max_{x\in C}y^Tx\)
reference 1. https://arxiv.org/pdf/1606.03476.pdf 2. https://en.wikipedia.org/wiki/Fenchel%27s_duality_theorem