Epigraphical projection and proximal tools for solving constrained convex optimization problems

Abstract

We propose a proximal approach to deal with a class of convex variational problems involving nonlinear constraints. A large family of constraints, proven to be effective in the solution of inverse problems, can be expressed as the lower-level set of a sum of convex functions evaluated over different blocks of the linearly transformed signal. For such constraints, the associated projection operator generally does not have a simple form. We circumvent this difficulty by splitting the lower-level set into as many epigraphs as functions involved in the sum. In particular, we focus on constraints involving $\varvec{\ell }_q$-norms with $q\ge 1$, distance functions to a convex set, and $\varvec{\ell }_{1,p}$-norms with $p\in \{2,{+\infty }\}$. The proposed approach is validated in the context of image restoration by making use of constraints based on Non-Local Total Variation. Experiments show that our method leads to significant improvements in term of convergence speed over existing algorithms for solving similar constrained problems.

Appendix

1.1 Proof of Proposition 1

For every $(y,\zeta )\in {{\mathcal {H}}}\times {\mathbb {R}}$, let $(p,\theta )=P_{\hbox {epi}\varphi }(y,\zeta )$. If $\varphi (y) \le \zeta$, then $p = y$ and $\theta = \zeta = \max \{\varphi (p),\zeta \}$. In addition,

$$\begin{aligned} (\forall u \in {{\mathcal {H}}})\;\; 0&= \frac{1}{2} \Vert p-y\Vert ^2 + \frac{1}{2} \big (\max \{\varphi (p)-\zeta ,0\}\big )^2\nonumber \\&\le \frac{1}{2} \Vert u-y\Vert ^2 + \frac{1}{2} \big (\max \{\varphi (u)-\zeta ,0\}\big )^2,\nonumber \\ \end{aligned}$$

(38)

which shows that (18) holds. Let us now consider the case when $\varphi (y) > \zeta$. From the definition of the projection, we get

$$\begin{aligned} (p,\theta ) = \underset{(u,\xi )\in \hbox {epi}\varphi }{\mathrm{argmin }}\; \Vert u-y\Vert ^2+(\xi -\zeta )^2. \end{aligned}$$

(39)

From the Karush–Kuhn–Tucker theorem [67, Theorem 5.2],⁶ there exists $\alpha \in [0,+\infty [$ such that

$$\begin{aligned} (p,\theta )&= \underset{(u,\xi )\in {{\mathcal {H}}}\times {\mathbb {R}}}{\mathrm{argmin }}\; \frac{1}{2} \Vert u-y\Vert ^2+ \frac{1}{2} (\xi -\zeta )^2\nonumber \\&+ \alpha (\varphi (u)-\xi ) \end{aligned}$$

(40)

where the Lagrange multiplier $\alpha$ is such that $\alpha (\varphi (p)-\theta )\!=\!0$. Since the value $\alpha = 0$ is not allowable (otherwise it would lead to $p=y$ and $\theta = \zeta$), it can be deduced from the above equality that $\varphi (p) = \theta$. In addition, differentiating the Lagrange functional in (40) w.r.t. $\xi$ yields $\varphi (p)\! =\! \theta \!=\! \zeta + \alpha \ge \zeta$. Hence, $(p,\theta )$ in (39) is such that $\theta \!=\! \varphi (p) \!=\! \max \{\varphi (p),\zeta \}$ and

$$\begin{aligned} p = \underset{\begin{array}{c} u\in {{\mathcal {H}}}\\ \varphi (u)\ge \zeta \end{array}}{\mathrm{argmin }} \Vert u-y\Vert ^2+(\varphi (u)-\zeta )^2. \end{aligned}$$

(41)

Furthermore, as $\varphi (y) > \zeta$, we obtain

$$\begin{aligned} \underset{\begin{array}{c} u\in {{\mathcal {H}}}\\ \varphi (u)\le \zeta \end{array}}{\inf } \Vert u-y\Vert ^2 = \Vert P_{{{{{\hbox {lev}}}_{\le \zeta }}\,}\varphi }(y)-y\Vert ^2 = \underset{\begin{array}{c} u\in {{\mathcal {H}}}\\ \varphi (u)= \zeta \end{array}}{\inf } \Vert u-y\Vert ^2,\nonumber \\ \end{aligned}$$

(42)

where we have used the fact that $P_{{{{{\hbox {lev}}}_{\le \zeta }}\,}\varphi }(y)$ belongs to the boundary of ${{{{\hbox {lev}}}_{\le \zeta }}\,}\varphi$ which is equal to $\big \{{u \in {{\mathcal {H}}}}~\big |~{\varphi (u)= \zeta }\big \}$ since $\varphi$ is lower-semicontinuous and $\hbox {dom}\varphi$ is open [38, Corollary 8.38]. We have then

$$\begin{aligned} \underset{\begin{array}{c} u\in {{\mathcal {H}}}\\ \varphi (u)\le \zeta \end{array}}{\inf } \Vert u-y\Vert ^2&= \!\!\!\! \underset{\begin{array}{c} u\in {{\mathcal {H}}}\\ \varphi (u)= \zeta \end{array}}{\inf } \Vert u-y\Vert ^2 \ge \!\!\!\underset{\begin{array}{c} u\in {{\mathcal {H}}}\\ \varphi (u)\ge \zeta \end{array}}{\inf } \Vert u-y\Vert ^2\nonumber \\&+(\varphi (u)-\zeta )^2. \end{aligned}$$

(43)

Altogether, (41) and (43) lead to

$$\begin{aligned} p = \underset{u\in {{\mathcal {H}}}}{\mathrm{argmin }}\; \frac{1}{2}\Vert u-y\Vert ^2+\frac{1}{2}\big (\varphi (u)-\zeta \big )^2\quad \end{aligned}$$

(44)

which is equivalent to (18) since $\frac{1}{2}(\max \{\varphi -\zeta ,0\})^2 \in \Gamma _0({{\mathcal {H}}})$.

1.2 Proof of Proposition 3

Since $(\max \{\varphi -\zeta ,0\})^2$ is an even function, $\hbox {prox}_{\frac{1}{2} (\max \{\varphi -\zeta ,0\})^2}$ is an odd function [22, Remark 4.1(ii)]. In the following, we thus focus on the case when $y \in ]0,+\infty [$. If $\zeta \in ]-\infty ,0]$, then $(\max \{\varphi -\zeta ,0\})^2= (\varphi -\zeta )^2$ is differentiable and, according to the fact that $p = \hbox {prox}_f(y)$ is uniquely defined as $y-p \in \partial f(p)$, we deduce that $p = \hbox {prox}_{\frac{1}{2} (\varphi -\zeta )^2}(y)$ is such that

$$\begin{aligned} p-y + q\tau p^{q-1} (\tau p^q-\zeta ) = 0, \end{aligned}$$

(45)

where $p \ge 0$ by virtue of [68, Corollary 2.5]. This allows us to deduce that $p = \chi _0$.

Let us now focus on the case when $\zeta \in ]0,{+\infty }[$. If $y\in ]0,(\zeta /\tau )^{1/q}[$, it can be deduced from [68, Corollary 2.5], that $p = \hbox {prox}_{\frac{1}{2} (\max \{\varphi -\zeta ,0\})^2}(y) \in [0,(\zeta /\tau )^{1/q}[$. Since $(\forall v \in [0,(\zeta /\tau )^{1/q}[)$ $\max \{\varphi (v)-\zeta ,0\}=0$, we have $p=y$. On the other hand if $y > (\zeta /\tau )^{1/q}$, as the proximity operator of a function from ${\mathbb {R}}$ to ${\mathbb {R}}$ is continuous and increasing [68, Proposition 2.4], we obtain

$$\begin{aligned} p&= \hbox {prox}_{\frac{1}{2} (\max \{\varphi -\zeta ,0\})^2}(y) \ge \nonumber \\&\quad \hbox {prox}_{\frac{1}{2}(\max \{\varphi -\zeta ,0\})^2}\big ((\zeta /\tau )^{1/q}\big ) =(\zeta /\tau )^{1/q}. \end{aligned}$$

(46)

Since $(\max \{\varphi -\zeta ,0\})^2$ is differentiable and, for each $v \ge (\zeta /\tau )^{1/q}$, $(\max \{\varphi (v)-\zeta ,0\})^2=(\tau v^q-\zeta )^2$, we deduce that $p$ is the unique value in $[(\zeta /\tau )^{1/q},{+\infty }[$ satisfying (45).

1.3 Proof of Proposition 4

Let us notice that $\frac{1}{2}(\max \{\tau d_{C}^{q}-\zeta ,0\})^2 = \psi \circ d_{C}$ where $\psi = \frac{1}{2} (\max \{\tau |\cdot |^{q}-\zeta ,0\})^2$. According to [47, Proposition 2.7], for every ${ y}\in {{\mathcal {H}}}$,

$$\begin{aligned} \hbox {prox}_{\psi \circ d_{C}}({ y}) = \left\{ \begin{array}{ll} { y}, &{} \hbox {if }\,{ y}\in \, C,\\ P_{C}({ y}), &{} \hbox {if}\, d_{C}({ y}) \le \max \partial \psi (0),\\ \alpha { y} + (1-\alpha ) P_{C}({ y}),&{} \hbox {if }\,d_{C}({ y}) > \max \partial \psi (0) \end{array}\right. \nonumber \\ \end{aligned}$$

(47)

where $\alpha = \frac{\hbox {prox}_{\psi }\big (d_{C}({ y})\big )}{d_{C}({ y})}$. In addition, we have

$$\begin{aligned} \partial \psi (0) = {\left\{ \begin{array}{ll} [\tau \zeta ,-\tau \zeta ], &{} \text{ if } \zeta < 0 \text{ and } q = 1,\\ \{0\}, &{} \text{ otherwise }, \end{array}\right. } \end{aligned}$$

(48)

and, according to Proposition 2, when $\zeta \!\! <\!\! 0$ and $d_{C}({ y}) \!\le \! -\tau \zeta$, $\hbox {prox}_{\psi }\big (d_{C}({ y})\big ) = 0$. This shows that (47) reduces to (25).

1.4 Proof of Proposition 5

For every $({ y},\zeta ) \in {\mathbb {R}}^{M}\times {\mathbb {R}}$, in order to determine $P_{\hbox {epi}\varphi }(y,\zeta )$, we have to find

$$\begin{aligned} \min _{\theta \in [0,+\infty [}\Big ((\theta -\zeta )^2 + \min _{\begin{array}{c} |{ p}^{(1)}|\le \theta /\tau ^{(1)}\\ \dots \\ |{ p}^{(M)}|\le \theta /\tau ^{(M)} \end{array}} \Vert { p}-{ y}\Vert ^2\Big ). \end{aligned}$$

(49)

For all $\theta \in [0,+\infty [$, the inner minimization is achieved when, $\forall m\in \{1,\ldots ,M\}, { p}^{(m)}$ is the projection of ${ y}^{(m)}$ onto the range $[-\theta /\tau ^{(m)},\theta /\tau ^{(m)}]$, as given by (31). Then, (49) reduces to

$$\begin{aligned} \underset{\theta \in [0,+\infty [}{\mathrm{min }}\;\Big ((\theta -\zeta )^2 + \sum _{m=1}^{M} (\max \{|{ y}^{(m)}|-\theta /\tau ^{(m)},0\})^2\Big )\quad \end{aligned}$$

(50)

which is equivalent to calculate $\theta =\hbox {prox}_{\phi +\iota _{[0,+\infty [}}(\zeta )$ where

$$\begin{aligned} \phi (v) = \frac{1}{2}\sum _{m=1}^{M} (\max \{(\tau ^{(m)})^{-1}(\nu ^{(m)}-v),0\})^2. \end{aligned}$$

(51)

The function $\phi$ belongs to $\Gamma _0({\mathbb {R}}\!)$ since, for each $m\!\in \! \{1,\ldots ,M\}$, $\max \{(\tau ^{(m)})^{-1}(\nu ^{(m)} - \cdot ),0\}$ is finite convex and $(\cdot )^2$ is finite convex and increasing on $[0,+\infty [$. In addition, $\phi$ is differentiable and such that, for every $v\in {\mathbb {R}}$ and $k \in \{1,\ldots ,M+1\}$,

$$\begin{aligned} \nu ^{(k-1)} \!<\! v \!\le \! \nu ^{(k)} \;\Rightarrow \; \phi (v) \!=\! \frac{1}{2} \sum _{m=k}^{M} (\tau ^{(m)})^{-2} \big (v-\nu ^{(m)} \big )^2.\nonumber \\ \end{aligned}$$

(52)

By using [23, Prop. 12], $\theta = P_{[0,+\infty [}(\chi )$ with $\chi =\hbox {prox}_{\phi }(\zeta )$. Therefore, there exists an $\overline{m} \in \{1,\ldots ,M+1\}$ such that$\nu ^{(\overline{m}-1)} < \chi \le \nu ^{(\overline{m})}$ and $\zeta -\chi = \phi '(\chi )$, so leading to

$$\begin{aligned} \zeta -\chi = \sum _{m=\overline{m}}^{M} (\tau ^{(m)})^{-2} (\chi -\nu ^{(m)}) \quad \Leftrightarrow \quad (32) \end{aligned}$$

(53)

and $\nu ^{(\overline{m}-1)} < \chi \le \nu ^{(\overline{m})} \,\Leftrightarrow \,$ (33). The uniqueness of $\overline{m} \in \{1,\ldots ,M+1\}$ follows from that of $\hbox {prox}_{\phi }(\zeta )$.