Indicator functions

Polyhedra - Lower-level sets - Epigraphs

Polyhedra

Name C ⊂ ℝN

(∀ x ∈ ℝN)

PC(x) Matlab Python Ref
Box $x \in [\eta_1, \eta_2]^N$

(with $\eta_1<\eta_2$)

$\Big[\max\big\{\eta_1,\min\{x_n,\eta_2\}\big\}\Big]_{1\le n\le N}$ [Function]
[Prox]
[Class]
Hyperplane $u^\top x = \eta$

(with $(u,\eta)\in\mathbb{R}^N\times \mathbb{R}$)

$x+u\dfrac{\eta - u^\top x }{\|u\|_2^2}$ [Function]
[Prox]
(coming soon)
Hyperslab $\eta_1 \le u^\top x \le \eta_2$

(with $\eta_1<\eta_2$)

$\left\{ \begin{aligned} &x+u\dfrac{\eta_1- u^\top x }{\|u\|_2^2} &&\quad \textrm{if $u^\top x<\eta_1$}\\[1em] &x+u\dfrac{\eta_2-u^\top x}{\|u\|_2^2} &&\quad \textrm{if $u^\top x > \eta_2$}\\[1em] &x &&\quad \textrm{otherwise}\\ \end{aligned}\right.$ [Function]
[Prox]
(coming soon)
Simplex $\begin{cases}x\in[0,+\infty[^N \\{\rm 1}^\top x = \eta\end{cases}$

(with $(1,\eta)\in\mathbb{R}^N\times \mathbb{R}$)

$\big[\max\{0,x_n-\lambda\}\big]_{1\le n\le N}$

with $\lambda\in\mathbb{R}$ such that $\displaystyle \sum_{n=1}^N \max\{0,x_n-\lambda\} = \eta$

[Function 1, Function 2]
[Prox 1, Prox 2]
[Mex-file]
(coming soon) [Michelot, 1986]
[Condat, 2016]
Monotone cone $x_1 \le x_2 \le\dots\le x_N$ $\displaystyle\left[\max_{1\le j\le n}\;\min_{n\le k\le N}\;\frac{1}{k-j+1}\sum_{\ell=j}^k x_\ell\right]_{1\le n\le N}$ [Function 1, Function 2]
[Prox 1, Prox 2]
(coming soon) [Ayer et al., 1955]

Lower-level sets

Name C ⊂ ℝN

(∀ x ∈ ℝN)

PC(x) Matlab Python Ref
$\ell_1$-ball $\|x\|_1 \le \eta$

(with $\eta\ge0$)

$x - \operatorname{prox}_{\eta\|\cdot\|_\infty}(x)$ [Function]
[Prox]
(coming soon) [van den Berg et al., 2008]
$\ell_2$-ball $\|x\|_2 \le \eta$

(with $\eta\ge0$)

$x - \operatorname{prox}_{\eta\|\cdot\|_2}(x)$ [Function]
[Prox]
(coming soon) [Combettes et al., 2005]
$\ell_\infty$-ball $\|x\|_\infty \le \eta$

(with $\eta\ge0$)

$P_{[-\eta,\eta]^N}(x) = \Big[\operatorname{sign}(x_n)\min\{|x_n|,\eta\}\Big]_{1\le n\le N}$ [Function]
[Prox]
(coming soon)
$\ell_{1,2}$-ball $\displaystyle\sum_{b=1}^B \|x^{(b)}\|_{2} \le \eta$

(with $x = \big[{x^{(1)}}^\top\,\dots\,{x^{(B)}}^\top\big]^\top$ and $\eta\ge0$)

$\left[p^{(b)}\right]_{1\le b\le B}$

with

$p^{(b)} =\begin{cases}0 &\textrm{if $\|x^{(b)}\|_2=0$}\\[1em] x^{(b)}\dfrac{\beta_b}{\|x^{(b)}\|_2} &\textrm{otherwise}\end{cases}$

and

$(\beta_1,\dots,\beta_B) = P_{\{\|\cdot\|_1\le\eta\}}\Big(\|x^{(1)}\|_2,\dots,\|x^{(B)}\|_2\Big)$
[Function]
[Prox]
(coming soon) [van den Berg et al., 2008]
Logarithm $\displaystyle \sum_{n=1}^N -\log x_n \le \eta$

(with $\eta\in\mathbb{R}$)

$\begin{cases} x &\textrm{if $\;\displaystyle\sum_{n=1}^N -\log x_n \leq \eta$}\\[1em] \left(\dfrac{x_n + \sqrt{x_n^2 + 4\overline{\lambda}}}{2}\right)_{1\le n\le N} & \textrm{otherwise} \end{cases}$

with $\overline{\lambda} > 0$ such that

$\displaystyle\sum_{n=1}^N -\log \left(\dfrac{x_n + \sqrt{x_n^2 + 4\overline{\lambda}}}{2}\right) =\eta$
[Function]
[Prox]
(coming soon) [Carlavan et al., 2011]

Epigraphs

Name φ(y) Pepiφ(y,ζ) Matlab Python Ref
Support function $\sigma_{\left[a,b\right]}(y)$

(with $y\in\mathbb{R}$ and $a< b$)

$\left\{\begin{aligned} &(y,\zeta) &&\textrm{if $\;a y \le \zeta\;$ and $\;b y \le \zeta$}\\[0.5em] &\big(1,b\big)\frac{y+b\zeta}{1+b^2} &&\textrm{if $\;b y > \zeta\;$ and $\;-\frac{y}{b} \le \zeta$}\\[0.5em] &\big(1,a\big)\frac{y+a\zeta}{1+a^2} &&\textrm{if $\;a y > \zeta\;$ and $\;-\frac{y}{a} \le \zeta$}\\[0.5em] &(0,0) && \textrm{otherwise}\end{aligned}\right.$ [Function]
[Prox]
(coming soon)
Absolute value $\tau |y|$

(with $y\in\mathbb{R}$ and $\tau > 0$)

$\left\{\begin{aligned} &(y,\zeta) &&\textrm{if $\tau |y| \le \zeta$}\\[0.5em] &\Big(\operatorname{sign}(y),\tau\Big)\frac{\max\{0,|y|+\tau\zeta\}}{1+\tau^2} &&\textrm{otherwise} \end{aligned}\right.$ [Function]
[Prox]
(coming soon) [Chierchia et al., 2015]
Power $\tau |y|^q$

(with $y\in\mathbb{R}$ and $\tau > 0$)

$\left\{\begin{aligned} &(y,\zeta) &&\textrm{if $\tau |y|^q \le \zeta$}\\[0.5em] &\Big(\operatorname{sign}(y)p,\tau |p|^q\Big) &&\textrm{otherwise} \end{aligned}\right.$

with $\small p\ge\sqrt[q]{\frac{\max\{\zeta,0\}}{\tau}}$ such that

$\small q\tau^2 p^{2q-1} - q\tau\zeta p^{q-1} + p - |y| = 0$
[Function]
[Prox]
(coming soon) [Chierchia et al., 2015]
Hinge loss $\tau \max\{y, 0\}$

(with $y\in\mathbb{R}$ and $\tau > 0$)

$\left\{\begin{aligned} &(y,\zeta) &&\textrm{if $\;\tau\max\{y,0\}\le\zeta$}\\[0.5em] &(y,0) && \textrm{if $\;\tau\max\{y,0\}>\zeta\;$ and $\;y\le0$}\\[0.5em] &\big(1,\tau\big)\frac{\max\{0,y+\tau\zeta\}}{1+\tau^2} &&\textrm{otherwise}\\ \end{aligned}\right.$ [Function]
[Prox]
(coming soon)
Squared hinge loss $\tau\left(\max\{y,0\}\right)^2$

(with $y\in\mathbb{R}$ and $\tau > 0$)

$\left\{\begin{aligned} &(y,\zeta) &&\textrm{if $\;\tau \left(\max\{y,0\}\right)^2 \le \zeta$}\\[0.5em] &(y,0) &&\textrm{if $\;\tau \left(\max\{y,0\}\right)^2 > \zeta\;$ and $\;y\le0$}\\[0.5em] &P_{\{\operatorname{epi}\tau|\cdot|^2\}}(y,\zeta) &&\textrm{otherwise} \end{aligned}\right.$ [Function]
[Prox]
(coming soon)
Logarithm $\begin{cases}-\tau\log(y) &\textrm{if $y>0$}\\+\infty&\textrm{otherwise}\end{cases}$

(with $y\in\mathbb{R}$ and $\tau > 0$)

$\left( \dfrac{y + \sqrt{y^2 + 4\tau\lambda}}{2}, \zeta+\lambda \right)$

with $\small \lambda\ge0$ such that

$-\tau\log\left(\frac{y + \sqrt{y^2 + 4\tau\lambda}}{2}\right) - \zeta-\lambda = 0$
[Function]
[Prox]
(coming soon) [Wang et al., 2016]
Exponential $\tau\exp(y)$

(with $y\in\mathbb{R}$ and $\tau > 0$)

$\left\{\begin{aligned} &(y,\zeta) && \textrm{if $\tau\exp(y)\le\zeta$}\\[0.5em] &\big( \log(p/\tau), p \big) && \textrm{otherwise} \end{aligned}\right.$

with $\small p>\max\{0,\zeta\}$ such that

$p^2-\zeta p + \log(p) - y = 0$
[Function]
[Prox]
(coming soon) [El Gheche et al., 2016]
Distance function $\tau d^{q}_C(y)$

(with $y\in\mathbb{R}^N$, $\tau > 0$, $q\ge1$, $C\subset\mathbb{R}^N$)

$\left\{\begin{aligned} &(y,\zeta) &&\quad \textrm{if $\;\tau d^q_C(y) \le \zeta$}\\[0.5em] &(y,0) &&\quad \textrm{if $\;d_C(y) = 0\;$ and $\;\zeta<0$}\\[0.5em] &\Big(p,\tau d^q_C(p)\Big) &&\quad\textrm{otherwise} \end{aligned}\right.$

where $\small p=P_C(y) + \dfrac{t}{d_C(y)} \Big(y-P_C(y)\Big)$ and

if $q=1$, then $t = \dfrac{\max\{0,d_C(y)+\tau\zeta\}}{1+\tau^2}$

if $q>1$, then $t\ge\sqrt[q]{\frac{\max\{\zeta,0\}}{\tau}}$ is such that: $q\tau^2 t^{2q-1} - q\tau\zeta t^{q-1} + t - d_C(y) = 0$

[Function]
[Prox]
(coming soon) [Chierchia et al., 2015]
Euclidean norm $\tau\|y\|_2$

(with $y\in\mathbb{R}^N$ and $\tau > 0$)

$\left\{\begin{aligned} &(y,\zeta) &&\quad \textrm{if $\;\tau \|y\|_2 \le \zeta$}\\[0.5em] &(0,0) &&\quad \textrm{if $\;y=0\;$ and $\;\zeta<0$}\\[0.5em] &\Big(y,\tau \|y\|_2\Big)\dfrac{\max\{0,\|y\|_2+\tau\zeta\}}{(1+\tau^2)\|y\|_2} &&\quad\textrm{otherwise} \end{aligned}\right.$ [Function]
[Prox]
(coming soon)
Infinity norm $\tau\|y\|_\infty$

(with $y\in\mathbb{R}^N$ and $\tau > 0$)

$\Big[\operatorname{sign}(y_n)\min\big\{|y_n|,\max\{\theta/\tau,0\}\big\}\Big]_{1\le n\le N}$

where

$(\nu_n)_{1\le n\le N}$ are the values $(\tau \, |y_n|)_{1\le n\le N}$ sorted in ascending order

$\theta = \dfrac{1}{\tau^2+N-\overline{n}+1}\left(\tau^2\zeta+\displaystyle\sum_{n=\overline{n}}^N \nu_n\right)$

$\overline{n}\in\{1,\dots,M+1\}$ is such that $\nu_{\overline{n}-1} < \theta \le \nu_{\overline{n}}$

[Function]
[Prox]
(coming soon) [Chierchia et al., 2015]
Max function $\displaystyle\tau\max_{1\le n\le N}\, y_n$

(with $y\in\mathbb{R}^N$ and $\tau > 0$)

$\Big[\min\{y_n,\theta/\tau\}\Big]_{1\le n\le N}$

where

$(\nu_n)_{1\le n\le N}$ are the values $(\tau \, y_n)_{1\le n\le N}$ sorted in ascending order

$\theta = \dfrac{1}{\tau^2+N-\overline{n}+1}\left(\tau^2\zeta+\displaystyle\sum_{n=\overline{n}}^N \nu_n\right)$

$\overline{n}\in\{1,\dots,M+1\}$ is such that $\nu_{\overline{n}-1} < \theta \le \nu_{\overline{n}}$

[Function]
[Prox]
(coming soon) [Chierchia et al., 2015]