pip install proxop
from proxop import BoxConstraint
import numpy as np
x = np.array([-5, 1, 10., 0, 3])
BoxConstraint(-2., 2.).prox(x)
# result: array([-2., 1., 2., 0., 2.])
from proxop import AbsValue
x = np.array([ -3., 1., 6.])
AbsValue().prox(x, gamma=2)
#result: array([-1., 0., 4.])
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] |
[BoxConstraint] | |
Hyperplane | $u^\top x = \eta$ (with $(u,\eta)\in\mathbb{R}^N\times \mathbb{R}$) |
$x+\dfrac{\eta - u^\top x }{\|u\|_2^2}u$ |
[Function]
[Prox] |
[Hyperplane] | |
Hyperslab | $\eta_1 \le u^\top x \le \eta_2$ (with $\eta_1<\eta_2$) |
$\left\{ \begin{aligned} &x+\dfrac{\eta_1- u^\top x }{\|u\|_2^2}u &&\quad \textrm{if $u^\top x<\eta_1$}\\[1em] &x+\dfrac{\eta_2-u^\top x}{\|u\|_2^2}u &&\quad \textrm{if $u^\top x > \eta_2$}\\[1em] &x &&\quad \textrm{otherwise}\\ \end{aligned}\right.$ |
[Function]
[Prox] |
[Hyperslab] | |
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]
[Prox] [Mex-file] |
[Simplex] | [Michelot, 1986] [Condat, 2016] |
Extended simplex | $\begin{cases}x\in[0,+\infty[^N \\{\rm 1}^\top x \leq \eta\end{cases}$
(with $(1,\eta)\in\mathbb{R}^N\times \mathbb{R}$) |
$\begin{cases} \mathrm{max}(x,0) & \mathrm{if} \quad {\rm 1}^\top (\mathrm{max}(x,0)) \leq \eta \\ \mathrm{P}_{\{x | x \geq 0 \; \mathrm{and}\; {\rm 1}^\top x = \eta\}}(x) & \mathrm{otherwise} \end{cases}$ |
[Function]
[Prox] |
[ExtendedSimplex] | [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] |
[MonotoneCone] | [Ayer et al., 1955] |
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] |
[L1Ball] | [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] |
[L2Ball] | [Combettes et al., 2005] |
Positive $\ell_2$-ball | $\|x\|_2 \le \eta$ and $x \geq 0$ (with $\eta\ge0$) |
$ \begin{cases} \mathrm{max}(x,0) & \text{if } \| \mathrm{max}(x,0)\|_2 \leq \eta\\ \frac{\eta}{ \| \mathrm{max}(x,0)\|_2} \mathrm{max}(x,0) & \text{otherwise} \end{cases} $ |
[Function]
[Prox] |
[PositiveL2Ball] | [Combettes, 2018] |
$\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] |
[ LinfBall] | |
$\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] |
[ L1_2Ball] | [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] |
[LogProjection] | [Carlavan et al., 2011] |
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] |
[ EpiSupport ] | |
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] |
[ EpiAbsValue] | [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] |
[ EpiPower ] | [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] |
[ EpiHingeLoss] | |
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] |
[ EpiSquaredHingeLoss] | |
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] |
[EpiLog ] | [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] |
[EpiExp ] | [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] |
[ EpiDistance] | [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] |
[ EpiL2Norm] | |
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] |
[EpiLinfNorm ] | [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] |
[ EpiMax] | [Chierchia et al., 2015] |