Closed
Closed set
A set \(\mathcal{C}\) is closed if it contains its boundary: \[x^k\in\mathcal{C},x^k\rightarrow\bar{x}\Rightarrow\bar{x}\in\mathcal{C}\]
- the intersection of closed sets is closed
- the union of a finite number of closed sets is closed
- inverse under linear mapping \[\{x|Ax\in\mathcal{C}\}\] is closed if \(\mathcal{C}\) is closed
Closed function
a function is closed if its epigraph is a closed set or if all its sublevel set is a closed set
- If \(f\) is continuous and \(dom~f\) is closed, then \(f\) is closed
- If \(f\) is continuous and \(dom~f\) is open, then \(f\) is closed iff it converges to \(\infty\) along every sequence converging to a boundary point of \(dom~f\)
Properties
- sublevel sets: \(f\) is closed iff all its subsevel sets are closed
- minimum: if \(f\) is closed with bounded sublevel sets then it has a minimizer
Conjugate function
Conjugate functions: recall
- the conjugate of a function \(f\) is always closed and convex
- The indicator function of convex set \(\mathcal{C}\): conjugate is support function of \(\mathcal{C}\)
- Norm: conjugate is indicator of unit dual norm ball
Second conjugate
\[f^{**}(x)=\sup_{y\in{}dom~f^*}(x^\top{}y-f^*(y)))\]
- \(f^{**}\) is closed and convex
- \(f^{**}\leq{}f(x)\)
- if \(f\) is closed and convex, then \(f^{**}\leq{}f(x)\)
Calculus rules
Separable sum
\[f(x_1,x_2)=g(x_1)+h(x_2),f^*(y_1,y_2)=g^*(y_1)+h^*(y_2)\]
Scalar multiplication
\[\alpha{}>0,f(x)=\alpha{}g(x),f^*(y)=\alpha{}g^*(y/\alpha{})\]
Addition to affine function
\[f(x)=g(x)+a^\top+b,f^*(y)=g^*(y-a)-b\]
Infimal convolution
\[f(x)=\inf_{u+v=x}(g(u)+h(v)),f^*(y)=g^*(y)+h^*(y)\]
Proximal mapping
Definition: the proximal mapping of a closed convex function \(f\) is: \[\text{prox}_f(x)=\arg\min_u\left(f(u)+\frac{1}{2}||u-x||_2^2\right)\]
Example
\[u=\text{prox}_f(x)\Leftrightarrow{}0\in\partial{}f(u)+u-x\Leftrightarrow{}x-u\in\partial{}f(u)\Leftrightarrow{}f(z)\geq{}f(u)+(x-u)^\top(z-u)\] If \(f(x)=\delta_C(x)\), \(C\) is closed and convex \(\Rightarrow{}(x-u)^\top(z-u)\leq0\)
Calculus rules
\[f(x)=\lambda{}g(x/\lambda)\Rightarrow{}\text{prox}_f(x)=\lambda\text{prox}_{\lambda^{-1}g}(x/\lambda)\]
Proof
\[\text{prox}_f(x)=\arg\min_y\{f(y)+\frac{1}{2}||y-x||^2\}=\arg\min_{y,z}\{\lambda{}g(z)+\frac{1}{2}||\lambda{}z-x||_2^2\left|z=\frac{y}{\lambda}\}\right.\] \[L(y,z;\mu)=\lambda{}g(z)+\frac{1}{2}||\lambda{}z-x||_2^2+<\lambda{}z-y,\mu>\] \[\partial_yL=0,\partial_zL=0\Rightarrow{}z=\text{prox}_{\lambda^{-1}g}(x/\lambda)\]
Moreau decomposition
\[x=\text{prox}_f(x)+\text{prox}_{f^*}(x)\quad{}\text{for all }x\]
Composition with affine mapping
- for general \(A\), prox-operator of \(f\) does not follow easily from prox-operator of \(g\)
- however, if \(AA^\top=(1/\alpha)I\)
\[f(x)=g(Ax+b)\Rightarrow{}\text{prox}_f(x)=x-\alpha{}A^\top(Ax+b-\text{prob}_{\alpha^{-1}g}(Ax+b))\]
Projections
Affine sets
\(C=\{x|Ax=b\}\), with \(A\in{}R^{p\times{}n}\) and \(\textbf{rank}(A)=p\) \[P_C(x)=x+A^\top(AA^\top)^{-1}(b-Ax)\] inexpensive if \(p\ll{}n\), or \(AA^\top=I\)
Simple polyhedral sets
Halfspace
\(C=\{x|a^\top{}x\leq{}b\}\) \[P_C(x)=x+\frac{b-a^\top{}x}{||a||_2^2}a\quad\text{if }a^\top{}x>b,\quad{}P_C(x)=x\quad\text{if }a^\top{}x\leq{}b\]
Probability simplex
\(C=\{x|\textbf{1}^\top{}x=1,x\succeq0\}\) \[P_C(x)=(x-\lambda\textbf{1})_{+}\] where \(\lambda\) is the solution of the equation \[\textbf{1}^\top(x-\lambda\textbf{1})_{+}=\sum_{i=1}^n\max\{0,x_k-\lambda\}=1\]
Support function, Norm and Distance
Support function
- conjugate of support function of closed convex set is indicator function
\[f(x)=\sup_{y\in{}C}x^\top{}y,f^*(y)=\delta_C(y)\]
- prox-operator of support function follows from Moreau decomposition
\[\text{prox}_{tf}(x)=x-t\text{prox}_{t^{-1}f^*}(x/t)=x-tP_C(x/t)\]
Norm
- conjugate of norm is indicator function of dual norm
\[f(x)=||x||,f^*(y)=\delta_B(y),B=\{y|~||y||_*\leq1\}\]
- prox-operator of norm follows from Moreau decomposition
\[\text{prox}_{tf}(x)=-P_{tB}(x)\]
Euclidean distance to a set
\[d(x)=\inf_{y\in{}C}||x-y||_2\] \[\text{prox}_{td}(x)=\left\{\begin{aligned}&x+\frac{t}{d(x)}(P_C(x)-x)&d(x)\geq{}t\\&P_C(x)&~\text{otherwise}\end{aligned}\right.\]
