{"word_count": 274, "character_count": 4003}
In the MAT7381 course (graduate course on regression models), we will talk about optimization, and a classical tool is the so-called conjugate. Given a function [latex]f:\mathbb{R}^p\to\mathbb{R}[/latex] its conjugate is function [latex]f^{\star}:\mathbb{R}^p\to\mathbb{R}[/latex] such that [latex display="true"]f^{\star}(\boldsymbol{y})=\max_{\boldsymbol{x}}\lbrace\boldsymbol{x}^\top\boldsymbol{y}-f(\boldsymbol{x})\rbrace[/latex]so, long story short, [latex]f^{\star}(\boldsymbol{y})[/latex] is the maximum gap between the linear function [latex]\boldsymbol{x}^\top\boldsymbol{y}[/latex] and [latex]f(\boldsymbol{x})[/latex].Just to visualize, consider a simple parabolic function (in dimension 1) [latex]f(x)=x^2/2[/latex], then [latex]f^{\star}(\color{blue}{2})[/latex] is the maximum gap between the line [latex]x\mapsto\color{blue}{2}x[/latex] and function [latex]f(x)[/latex].x = seq(-100,100,length=6001)f  = function(x) x^2/2vf = Vectorize(f)(x)fstar = function(y) max(y*x-vf)vfstar = Vectorize(fstar)(x)We can see it on the figure below.viz = function(x0=1,YL=NA){idx=which(abs(x)&#60;=3) par(mfrow=c(1,2)) plot(x[idx],vf[idx],type="l",xlab="",ylab="",col="blue",lwd=2) abline(h=0,col="grey") abline(v=0,col="grey") idx2=which(x0*x&#62;=vf)polygon(c(x[idx2],rev(x[idx2])),c(vf[idx2],rev(x0*x[idx2])),col=rgb(0,1,0,.3),border=NA)abline(a=0,b=x0,col="red")i=which.max(x0*x-vf)segments(x[i],x0*x[i],x[i],f(x[i]),lwd=3,col="red")if(is.na(YL)) YL=range(vfstar[idx])plot(x[idx],vfstar[idx],type="l",xlab="",ylab="",col="red",lwd=1,ylim=YL)abline(h=0,col="grey")abline(v=0,col="grey")segments(x0,0,x0,fstar(x0),lwd=3,col="red")points(x0,fstar(x0),pch=19,col="red")}viz(1)orviz(1.5)In that case, we can actually compute [latex]f^{\star}[/latex], since [latex display="true"]f^{\star}(y)=\max_{x}\lbrace xy-f(x)\rbrace=\max_{x}\lbrace xy-x^2/2\rbrace[/latex]The first order condition is here [latex]x^{\star}=y[/latex] and thus[latex display="true"]f^{\star}(y)=\max_{x}\lbrace xy-x^2/2\rbrace=\lbrace x^{\star}y-(x^{\star})^2/2\rbrace=\lbrace y^2-y^2/2\rbrace=y^2/2[/latex]And actually, that can be related to two results. The first one is to observe that [latex]f(\boldsymbol{x})=\|\boldsymbol{x}\|_2^2/2[/latex] and in that case [latex]f^{\star}(\boldsymbol{y})=\|\boldsymbol{y}\|_2^2/2[/latex] from the following general result : if [latex]f(\boldsymbol{x})=\|\boldsymbol{x}\|_p^p/p[/latex] with [latex]p&#62;1[/latex], where [latex]\|\cdot\|_p[/latex] denotes the standard [latex]\ell_p[/latex] norm, then [latex]f^{\star}(\boldsymbol{y})=\|\boldsymbol{y}\|_q^q/q[/latex] where[latex display="true"]\frac{1}{p}+\frac{1}{q}=1[/latex]The second one is the conjugate of a quadratic function. More specifically if [latex]f(\boldsymbol{x})=\boldsymbol{x}^{\top}\boldsymbol{Q}\boldsymbol{x}/2[/latex] for some definite positive matrix [latex]\boldsymbol{Q}[/latex],  [latex]f^{\star}(\boldsymbol{y})=\boldsymbol{y}^{\top}\boldsymbol{Q}^{-1}\boldsymbol{y}/2[/latex]. In our case, it was a univariate problem with [latex]\boldsymbol{Q}=1[/latex].For the conjugate of the [latex]\ell_p[/latex] norm, we can use the following code to visualize itp = 3f = function(x) abs(x)^p/pvf = Vectorize(f)(x)fstar = function(y) max(y*x-vf)vfstar = Vectorize(fstar)(x)viz(1.5)orp = 1.1f = function(x) abs(x)^p/pvf = Vectorize(f)(x)fstar = function(y) max(y*x-vf)vfstar = Vectorize(fstar)(x)viz(1, YL=c(0,10))Actually, in that case, we almost visualize that if [latex]f(x)=|x|[/latex] then[latex display="true"]\displaystyle{f^{\star}\left(y\right)={\begin{cases}0,&#38;\left|y\right|\leq 1\\\infty ,&#38;\left|y\right|&#62;1.\end{cases}}}[/latex]To conclude, another popular case, [latex]f(x)=\exp(x)[/latex] then[latex display="true"]{\displaystyle f^{\star}\left(y\right)={\begin{cases}y\log(y)-y,&#38;y&#62;0\\0,&#38;y=0\\\infty ,&#38;y&#60;0.\end{cases}}}[/latex]We can visualize that case belowf = function(x) exp(x)vf = Vectorize(f)(x)fstar = function(y) max(y*x-vf)vfstar = Vectorize(fstar)(x)viz(1,YL=c(-3,3))