理解 Conjugate Function

共轭函数是最优化问题中非常重要的概念，常用来在原问题和对偶问题之间进行转换。

定义

对于原函数 $f(x), x\in D$ ，其共轭函数为
$f^{\star}(y)=\sup_{x\in D}\left(<y, x>-f(x)\right)$ 其中， $<y, x>$ 表示两个变量的内积。

注意，这个的共轭函数的定义域要求对 $x\in D, <y, x>-f(x)$ 有上界。即，共轭函数的值不能无穷大。

几何意义

对于共轭函数的每一个自变量 $y=\hat{y}$ ，其取值相当于一条直线与原函数之差的最大值： $f^{\star}(y)=\sup_{x\in D}\left(l(x)-f(x)\right)$ 这条直线 $l(x)=<\hat{y}, x>$ ，其斜率由 $\hat{y}$ 决定。

两条曲线之差随着 $x$ 变化，其最大值可以对 $x$ 求导得到： $\frac{\partial(<y, x>-f(x))}{\partial x}=0 \Rightarrow f'(x)=y$ 即：曲线斜率与直线斜率相同处的 $x$ ，能够得到最大值。
带入满足条件的x，即可得到共轭函数。

例子

原函数（Negative entropy）： $f(x)=x\log x, x>0$ 原函数为增函数。
对于 $y<0$ ， $l(x)$ 为减函数。则 $l(x)−f(x)$ 为减函数，不超过其在零点取值。
对于 $y\geq0$ ， $l(x)$ 也是增函数 $\lim_{x \rightarrow\infty}l(x)/f(x)=\lim_{x \rightarrow\infty}l'(x)/f'(x)=\lim_{x \rightarrow\infty}y/(\log x+x)=0$ $l(x)$ 增速小于 $f(x)$ 增速，故其差有上界。
故， $f^{\star}(y)$ 的定义域为 $y∈R$ 。