Basic properties and examples
Definition
\(f:R^n\rightarrow{}R\) is convex if dom\(f\) is a convex set and \[f(\theta{}x+(1-\theta)y)\leq\theta{}f(x)+(1-\theta)f(y)\] for all \(x,y\in\) dom\(f\), \(0\leq\theta\leq1\)
- strictly convex if we choose \(<\) instead of \(\leq\)
Examples on \(R\), \(R^n\) and \(R^{m\times{}n}\)
Restriction of a convex function to a line
\(f:R^n\rightarrow{}R\) is convex if and only if the function \(g:R\rightarrow{}R\) \[g(t)=f(x+tv), dom g=\{\}\]
Proof
\[\forall{}t_1,t_2,x+t_1v\in{}dom~f,x+t_2v\in{}dom~f\] \[g(\theta{}t_1+(1-\theta)t_2)=f(x+(\theta{}t_1+(1-\theta{})t_2)v)\] \[=f(\theta(x+t_1v)+(1-\theta)(x+t_2v))\] \[\leq{}\theta{}f(x+t_1v)+(1-\theta)f(x+t_2v)\]
\[let~x_1,x_2\in{}dom~f, de\!{}fine~x=x_1,v=x_2-x_1,g(t)=f(x+tv)\] \[f(\theta{}x_1+(1-\theta)x_2)=f(x_1+(1-\theta)(x_2-x_1))=g(1-\theta)\] \[\leq{}\theta{}g(0)+(1-\theta)g(1)=\theta{}f(x_1)+(1-\theta)f(x_2)\]
Example
\(f:S^n\rightarrow{}R\) with \(f(X)=\log\det{}X\), dom \(f=S^n_{++}\)
First-order condition
Differentiable \(f\) with convex domain is convex iff \[f(y)\geq{}f(x)+\nabla{}f(x)^T(y-x)\quad\forall{}x,y\in{}dom~f\]
Proof
\[t>0,~f(x+t(y-x))\leq{}(1-t)f(x)+tf(y)\] \[f(y)\geq{}f(x)+\frac{f(x+t(y-x))-f(x)}{t}\] \[f(y)\geq{}f(x)+f^{'}(x)(y-x)\]
\[f(x)\geq{}f^{'}(z)(x-z),f(y)\geq{}f^{'}(z)(y-z)\] \[let~z=\theta{}x+(1-\theta{})y\] \[\theta{}f(x)+(1-\theta)f(y)\geq{}f(z)\]
Second-order condition
Twice differentiable \(f\) with convex domain is convex iff \[\nabla^2f(x)\succeq0\quad\forall{}x\in{}dom~f\] if \(\nabla^2f(x)\succ0\) for all \(x\in{}dom~f\), then \(f\) is strictly convex
Epigraph and sublevel set
\(\alpha\)-sublevel set of \(f:R^n\rightarrow{}R\) \[C_\alpha=\{x\in{}dom~f|f(x)\leq\alpha\}\] sublevel sets of convex functions are convex (converse is false) epigraph of \(f:R^n\rightarrow{}R\) \[epi~f=\{(x,t)\in{}R^{n+1}|x\in{}dom~f,f(x)\leq{}t\}\] \(f\) is convex iff \(epi~f\) is a convex set
Operations that preserve convexity
Positive weighted sum & composition with affine function
- nonnegative multiple
- sum
- composition with affine function
Pointwise Maximum
if \(f_1,...,f_m\) are convex, then \[f(x)=\max\{f_1(x),...,f_m(x)\}\] is convex
Pointwise Supremum
if \(f(x,y)\) is convex in \(x\) for each \(y\in\mathcal{A}\), then
\[g(x)=\sup_{y\in\mathcal{A}}f(x,y)\] is convex
Theorem
Let \(f:R^n\rightarrow{}R\) convex and \(dom~f:R^n\), then
\[f(x)=\sup\{g(x)|g~is~af\!{}fine,g(z)\leq{}f(z),\forall{}z\}\]
Proof
\(\geq\), obvious
\(\leq\)
\[(x,f(x))\in{}bd~epi~f\]
\[\exists{}(a,b)\neq0~s.t.~a^Tz+bt\leq{}a^Tx+bf(x)\]
\[a^Tz+b(f(z)+s)\leq{}a^Tx+bf(x)\]
\[b\leq0,\text{otherwise }bs\rightarrow{}\infty\]
\[b=0,z=x+a\rightarrow{}a=0,\text{contradiction}\]
\[b<0,s=0\rightarrow{}f(z)\geq{}f(x)+\frac{a^T(x-z)}{b}=g(z)\]
Jensen's inequality
if \(f\) is convex, then\[f(Ez)\leq{}Ef(z)\]
Proof
\[Let~x_0=\int_{\Omega}x\rho{}(x)dx\]
\[\exists{}a,b~s.t.~ax+b\leq{}f(x)~\text{and}~ax_0+b=f(x_0)\]
\[\int_{\Omega}f(x)\rho{}(x)dx\geq{}\int_{\Omega}(ax+b)\rho(x)dx=ax_0+b=f(x_0)\]
Composition with scalar functions
composition of \(g:R^n\rightarrow{}R\) and \(h:R\rightarrow{}R\) \[f(x)=h(g(x))\] \(f\) is convex if
- \(g\) convex, \(h\) convex, \(\tilde{h}\) nondecreasing
- \(g\) concave, \(h\) convex, \(\tilde{h}\) nonincreasing
Minimization
if \(f(x,y)\) is convex in \((x,y)\) and \(C\) is a convex set, then\[g(x)=\inf_{y\in{}C}f(x,y)\] is convex
Perspective
the perspective of a function \(f:R^n\rightarrow{}R\) is the function \(g:R^n\times{}R\rightarrow{}R\) \[g(x,t)=tf(x/t),~dom~g=\{(x,t)|x/t\in{}dom~f,t>0\}\] \(g\) is convex if \(f\) is convex
Proof
use epi graph \[(x,t,s)\in{}epi~g\] \[s\geq{}tf(x/t)\] \[s/t\geq{}f(x/t)\] \[(x/t,s/t)\in{}epi~f\]
Conjugate function
the conjugate of a function \(f\) is \[f^*(y)=\sup_{x\in{}dom~f}(y^Tx-f(x))\]
- \(f^*\) is convex (even if \(f\) is not)
- \(f(x)+f(y)\geq{}x^Ty\)
- \(f\) is convex and closed (\(epi~f\) is closed), then \(f^{**}=f\)
Proof
Proof
\[f(x)\geq{}x^Ty-f(y)\]
\[f(x)\geq{}\sup_{y\in{}dom~f^*}(y^Tx-f(x))=f^{**}(x)\]
\[epi~f\subseteq{}epi~f^{**}\]
\[Let~(x,f^{**}(x))\notin{}epi~f\]
\[\exists{}[a,b]\neq0,~s.t.[a,b][z-x,t-f^{**}(x)]^T\leq{}c<0,\forall(z,t)\in{}epi~f\]
\[t=f(z)+s,s\geq0\]
\[b<0,a^T(z-x)+b(f(z)-f^{**}(x)+s)\leq{}c\]
\[\text{Define }y=-\frac{a}{b},~y^Tz-f(z)-s-y^Tx+f^{**}(x)\leq-\frac{c}{b}\]
\[\text{Let }s=0,\text{make }\sup\]
\[b=0,Let~y\in{}dom~f^{*} and \varepsilon>0\]
\[[a+\varepsilon{}\hat{y},-\varepsilon][z-x,t-f^{**}(x)^T\]
\[=a^T(z-x)+\varepsilon\hat{y}^T(z-x)-\varepsilon(t-f^{**}(x))\]
\[\leq{}c+\varepsilon(f^*(\hat{y})+f^{**}(x)-\hat{y}^Tx)=\tilde{c}<0\]
Example
\[f(X)=\log\det{}X,X\in{}S_+^n\]
\[f^*(Y)=\sup_{X>0}\{<X,Y>-f(X)\}\]
\[Y\geq0,f^*(Y)=+\infty\]
\[Y<0,Y-(X^*)^{-1}=0\rightarrow{}f^*(Y)=Tr(I)-\log\det{}Y^{-1}\]
\[Y \ngeq \&\nleq0\rightarrow{}f^*(Y)=+\infty(\exists{}u,s.t.Yu=\lambda{}u,\text{choose }X=tuu^T,t>0)\]
Quasiconvex functions
Definition
\(f:R^n\rightarrow{}R\) is quasiconvex if dom \(f\) is convex and its sublevel sets are all convex
Modified Jensen inequality
\[0\leq\theta\leq1\rightarrow{}f(\theta{}x+(1-\theta)y)\leq\max\{f(x),f(y)\}\]
Proof
\[\alpha=f(x)>f(y)\rightarrow{}S_\alpha=\{x|f(x)\leq\alpha\}\]
\[[x,y]\subset{}S_\alpha\rightarrow{}f([x,y])\leq\alpha\]
First-order condition
Differentiable \(f\) with convex domain is quasiconvex iff
\[f(y)\leq{}f(x)\rightarrow\triangledown{}f(x)^T(y-x)\leq0\]
Proof
\[g(t)=f(x+t(y-x))\rightarrow{}g^{'}(0)=\triangledown{}f(x)^T(y-x)\leq0\]
\[\text{Assume } z\in[x,y],f(z)>f(x)\&{}f(z)>f(y)\]
\[\triangledown{}f(z)^T(x-z)\leq0~\&~\triangledown{}f(z)^T(y-z)\leq0\]
\[\triangledown{}f(z)=0\]
\(z_0\) in the neighbour of \(z\), \(\triangledown{}f(z)\neq0,f(z_0)>f(x),f(z_0)>f(y)\), contradict
Second-order condition
Differentiable \(f\) with convex domain is quasiconvex iff
\[f^{'}(x)=0\rightarrow{}f^{''}(x)\geq0\]
Proof
\[\exists{}c\in[a,b],f^{'}(c)=0\land{}f^{''}(c)<0\]
\[\exists{}\varepsilon{}f(c)>f(c-\varepsilon),f(c)>f(c+\varepsilon)\]
\[\exists{}\delta>0,f(c)-\delta>f(c-\varepsilon),f(c)+\delta>f(c+\varepsilon)\]
\[c-\varepsilon,c+\varepsilon\in\{x|f(x)\leq{}f(c)-\delta\},c\notin\{x|f(x)\leq{}f(c)-\delta\}\]
\(\{x|f(x)\leq{}f(c)-\delta\}\) is not convex, contradict
\[f^{'}\neq0\rightarrow{}f\uparrow{}or\downarrow\rightarrow{}f\in\text{quasiconvex}\]
\[d=\sup\{c|f^{'}(c)=0\}\]
\[\forall{}x\geq{}d,f{'}(x)\geq0\rightarrow{}f(x)\geq{}f(d)\]
\[\forall{}x\leq{}d,f{'}(x)\leq0\rightarrow{}f(x)\leq{}f(d)\]
Log-concave and Log-convex functions
Definition
A positive function \(f\) is
log-concave if \(\log{}f\) is
concave
A positive function \(f\) is
log-convex if \(\log{}f\) is convex
- powers:\(x^a\) on \(R_{++}\) is log-convex for \(a\leq0\), log-concave for \(a\geq0\)
- many common probability densities are log-concave
- cumulative Gaussian distribution function is log-concave
Second-order condition
Twice differentiable \(f\) with convex domain is log-concave if and only if \[\forall{}x,f(x)\triangledown^2f(x)\preceq\triangledown{}f(x)\triangledown{}f(x)^T\]
Properties
- product of log-concave functions is log-concave
- sum of log-concave functions is not always log-concave
- if \(f:R^n\times{}R^m\rightarrow{}R\) is log-concave, then \[g(x)=\int{}f(x,y)dy\] is log-concave (not easy to show)
- convolution \(f*g\) of log-concave functions \(f,g\) is log-concave
\[(f*g)(x)=\int{}f(x-y)g(y)dy\]
