Inertial proximal gradient methods with Bregman regularization for a class of nonconvex optimization problems

Abstract

This paper proposes an inertial Bregman proximal gradient method for minimizing the sum of two possibly nonconvex functions. This method includes two different inertial steps and adopts the Bregman regularization in solving the subproblem. Under some general parameter constraints, we prove the subsequential convergence that each generated sequence converges to the stationary point of the considered problem. To overcome the parameter constraints, we further propose a nonmonotone line search strategy to make the parameter selections more flexible. The subsequential convergence of the proposed method with line search is established. When the line search is monotone, we prove the stronger global convergence and linear convergence rate under Kurdyka–Łojasiewicz framework. Moreover, numerical results on SCAD and MCP nonconvex penalty problems are reported to demonstrate the effectiveness and superiority of the proposed methods and line search strategy.

Appendix

1.1 A.1 Proof of Lemma 3

Proof

Since $\nabla f$ is Lipschitz continuous with the modulus $L_f$, it follows from Lemma 1 that

$$\begin{aligned} f(x^{k+1}) - f(z^{k})\le \langle \nabla f(z^{k}),x^{k+1}-z^{k}\rangle +\frac{L_f}{2}\Vert x^{k+1}-z^{k}\Vert ^2. \end{aligned}$$

(30)

On the other hand, recall that $f=f_1-f_2$ with $f_1$ and $f_2$ being convex, and their gradients $\nabla f_1$ and $\nabla f_2$ being Lipschitz continuous with moduli $L_f$ and $l_f$, respectively, thus we have

$$\begin{aligned} {\left\{ \begin{array}{ll} f_1(z^{k})+ \langle \nabla f_1(z^{k}),x^k-z^{k}\rangle \le f_1(x^k), \\ f_2(x^k)-f_2(z^{k})-\langle \nabla f_2(z^{k}),x^k-z^{k}\rangle \le \frac{l_f}{2}\Vert x^k-z^{k}\Vert ^2. \end{array}\right. } \end{aligned}$$

Summing the above two inequalities, and associating with $f=f_1-f_2$ and $\nabla f=\nabla f_1-\nabla f_2$, we get

$$\begin{aligned} f(z^{k})-f(x^k) \le \langle \nabla f(z^{k}),z^{k}-x^k\rangle +\frac{l_f}{2}\Vert x^k-z^k\Vert ^2. \end{aligned}$$

(31)

Next, from the minimization subproblem (9c), and the fact that $D_h(x^{k},x^k)=0$ by the definition in (8), we have

$$\begin{aligned}&g(x^{k+1})+\left\langle \nabla f(z^{k})-\frac{1}{\lambda _k}(y^k-x^k),x^{k+1}\right\rangle +\frac{1}{\lambda _k}D_h(x^{k+1},x^k)\\&\quad \le g(x^k)+\left\langle \nabla f(z^{k})-\frac{1}{\lambda _k}(y^k-x^k),x^k\right\rangle . \end{aligned}$$

Rearranging the terms, we obtain

$$\begin{aligned} g(x^{k+1})-g(x^k)\le \left\langle \nabla f(z^{k})-\frac{1}{\lambda _k}(y^k-x^k),x^k-x^{k+1}\right\rangle -\frac{1}{\lambda _k}D_h(x^{k+1},x^k). \end{aligned}$$

(32)

Combining the inequalities (30), (31) and (32) and recalling $F:=f+g$, we obtain

$$\begin{aligned}&F(x^{k+1})-F(x^k)\nonumber \\&\quad =f(x^{k+1})-f(z^{k})+f(z^{k})-f(x^k)+g(x^{k+1})-g(x^k)\nonumber \\&\quad \le \frac{1}{\lambda _k}\langle y^{k}-x^{k},x^{k+1}-x^k\rangle +\frac{L_f}{2}\Vert x^{k+1}-z^{k}\Vert ^2+\frac{l_f}{2}\Vert x^k-z^{k}\Vert ^2-\frac{1}{\lambda _k}D_h(x^{k+1},x^k). \end{aligned}$$

(33)

Next, recall that $\varDelta _k:=x^k-x^{k-1}$ in (13), then it follows from (9a) and (9b) that

$$\begin{aligned} y^{k}-x^{k}=\alpha _k \varDelta _k,\quad z^{k}-x^k=\beta _k\varDelta _k \end{aligned}$$

and

$$\begin{aligned} z^{k}-x^{k+1}=\beta _k \varDelta _k-\varDelta _{k+1}. \end{aligned}$$

Substituting the above equalities into (33), we have

$$\begin{aligned}&F(x^{k+1})-F(x^k) \nonumber \\&\quad \le \frac{1}{\lambda _k}\langle \alpha _k\varDelta _k, \varDelta _{k+1}\rangle +\frac{L_f}{2}\Vert \beta _k \varDelta _k-\varDelta _{k+1}\Vert ^2 +\frac{l_f}{2}\Vert \beta _k\varDelta _k\Vert ^2-\frac{1}{\lambda _k}D_h(x^{k+1},x^k)\nonumber \\&\quad \le \frac{1}{\lambda _k}\langle \alpha _k\varDelta _k, \varDelta _{k+1}\rangle +\frac{L_f}{2}\Vert \beta _k \varDelta _k-\varDelta _{k+1}\Vert ^2 +\frac{l_f}{2}\Vert \beta _k\varDelta _k\Vert ^2-\frac{\sigma _h}{2\lambda _k}\Vert \varDelta _{k+1}\Vert ^2\nonumber \\&\quad = \left( \frac{L_f}{2}-\frac{\sigma _h}{2\lambda _k}\right) \Vert \varDelta _{k+1}\Vert ^2+\frac{L_f+l_f}{2}\beta _k^2\Vert \varDelta _{k}\Vert ^2+\left( \frac{\alpha _k}{\lambda _k}-\beta _k L_f\right) \langle \varDelta _k,\varDelta _{k+1}\rangle \nonumber \\&\quad \le \left( \frac{L_f}{2}-\frac{\sigma _h}{2\lambda _k}+\frac{\alpha _k}{2\lambda _k}-\frac{\beta _k L_f}{2}\right) \Vert \varDelta _{k+1}\Vert ^2+\left( \frac{L_f+l_f}{2}\beta _k^2+\frac{\alpha _k}{2\lambda _k} -\frac{\beta _k L_f}{2}\right) \Vert \varDelta _{k}\Vert ^2, \end{aligned}$$

(34)

where the second inequality follows from the $\sigma _h$-strong convexity of h, i.e.,

$$\begin{aligned} D_h(x^{k+1},x^k)\ge \frac{\sigma _h}{2}\Vert x^{k+1}-x^k\Vert ^2 \end{aligned}$$

and the last inequality follows from $\beta _k L_f \le \frac{\alpha _k}{\lambda _k}$ (see Assumption 2) and

$$\begin{aligned} \langle \varDelta _k,\varDelta _{k+1}\rangle \le \frac{\Vert \varDelta _k\Vert ^2}{2} +\frac{\Vert \varDelta _{k+1}\Vert ^2}{2}. \end{aligned}$$

Then, by the definition of $\delta _k$ in (14) and the nondecreasing behavior of $\{\lambda _k\}$ in Assumption 2, we get

$$\begin{aligned}&(F(x^{k+1})+\delta _{k+1}\Vert \varDelta _{k+1}\Vert ^2) -(F(x^k)+\delta _k\Vert \varDelta _{k}\Vert ^2) \\&\quad \le \left( \frac{L_f}{2}-\frac{\sigma _h}{2\lambda _k}+\frac{\alpha _k}{2\lambda _k} +\frac{\alpha _{k+1}}{2\lambda _{k+1}}-\frac{\beta _k L_f}{2}\right) \Vert \varDelta _{k+1}\Vert ^2+\frac{\beta _k^2(L_f+l_f)-\beta _k L_f}{2} \Vert \varDelta _k\Vert ^2\\&\quad \le \left( \frac{L_f}{2}-\frac{\sigma _h}{2\lambda _k}+\frac{\alpha _k +\alpha _{k+1}}{2\lambda _k}-\frac{\beta _k L_f}{2}\right) \Vert \varDelta _{k+1}\Vert ^2+\frac{\beta _k^2(L_f+l_f)-\beta _k L_f}{2} \Vert \varDelta _k\Vert ^2. \end{aligned}$$

From the definition of $H_{\delta _k}(x^{k},x^{k-1})$ in (14) and the condition $\beta _k \le {L_f}/{(L_f+l_f)}$ in Assumption 2, we obtain

$$\begin{aligned}&(F(x^{k+1})+\delta _{k+1}\Vert \varDelta _{k+1}\Vert ^2) -(F(x^k)+\delta _k\Vert \varDelta _{k}\Vert ^2) \nonumber \\&\quad \le \left( \frac{L_f}{2}-\frac{\sigma _h}{2\lambda _k}+\frac{\alpha _k +\alpha _{k+1}}{2\lambda _k}-\frac{\beta _k L_f}{2}\right) \Vert \varDelta _{k+1}\Vert ^2. \end{aligned}$$

(35)

Moreover, by the condition (10), it holds that

$$\begin{aligned} (1-\beta _k)\lambda _k L_f\le \sigma _h-\alpha _k-\alpha _{k+1}-\varepsilon . \end{aligned}$$

Then, we have

$$\begin{aligned} \frac{L_f}{2}-\frac{\sigma _h}{2\lambda _k}+\frac{\alpha _k+\alpha _{k+1}}{2\lambda _k} -\frac{\beta _kL_f}{2} =\frac{(1-\beta _k)\lambda _kL_f-(\sigma _h-\alpha _k-\alpha _{k+1})}{2\lambda _k} \le -\frac{\varepsilon }{2\lambda _k}. \end{aligned}$$

Together with (35), we get the assertion (12) immediately. Furthermore, it follows from $-\frac{\varepsilon }{2\lambda _k}<0$ by Assumption 2 that $\{H_{\delta _k}(x^{k},x^{k-1})\}$ is monotonically nonincreasing. This completes the proof. $\square$

1.2 A.2 Proof of Theorem 1

Proof

(i) For any initial point $x^0\in {\mathbb {R}}^n$, we know that $x^1\in \mathrm{dom}F$ and thus $F(x^1)<\infty$. It follows from Lemma 3 that the sequence $\{H_{\delta _k}(x^{k},x^{k-1})\}$ is monotonically nonincreasing, thus we have

$$\begin{aligned} F(x^k)&\le F(x^k)+\delta _k\Vert \varDelta _k\Vert ^2=H_{\delta _k}(x^k,x^{k-1})\\&\le \cdots \le H_{\delta _1}(x^1,x^{0}){=} F(x^1)+\delta _1\Vert \varDelta _1\Vert ^2<\infty . \end{aligned}$$

Thus the sequence $\{x^k\}_{k\ge 1}$ is contained in the level set $\{x\in {\mathbb {R}}^n\,|\,F(x)\le F(x^1)\}$, which is bounded regardless of the choice of $x^0$ by the coercivity of F in Assumption 1. This is enough for showing that the whole sequence $\{x^k\}_{k\ge 0}$ is bounded.

(ii) We first conclude that there exists an upper bound ${\bar{\lambda }} = {\sigma _h}/{L_f}$ such that $\lambda _k\le {\bar{\lambda }}$ for any $k \ge 0$ from the condition (10). Otherwise, there is a $k_0 \ge 0$ such that for any $k \ge k_0$

$$\begin{aligned} \left\{ \begin{array}{l} \frac{\alpha _k}{\beta _k L_f}> \frac{\sigma _h}{L_f}, \\ \frac{\sigma _h-\alpha _k-\alpha _{k+1}-\varepsilon }{(1-\beta _k)L_f} > \frac{\sigma _h}{L_f}, \end{array}\right. \Rightarrow \quad \frac{\alpha _k+\alpha _{k+1}+\varepsilon }{\sigma _h}< \beta _k < \frac{\alpha _k}{\sigma _h}. \end{aligned}$$

Obviously, there is no $\beta _k$ satisfying the above inequalities. Therefore, we have $\lambda _k\le {\bar{\lambda }}=\sigma _h/L_f$ and it holds that $\frac{\varepsilon }{2\lambda _k}\ge \frac{\varepsilon }{2{\bar{\lambda }}}$. Summing up (12) with $k=1,2,\ldots ,N$ and combining the inequality $\frac{\varepsilon }{2\lambda _k}\ge \frac{\varepsilon }{2{\bar{\lambda }}}$ yield that

$$\begin{aligned} \sum _{k=1}^N \frac{\varepsilon }{2{\bar{\lambda }}}\Vert \varDelta _{k+1}\Vert ^2&\le \sum _{k=1}^N \left( H_{\delta _k}(x^{k},x^{k-1})-H_{\delta _{k+1}}(x^{k+1},x^k)\right) \\&=H_{\delta _1}(x^{1},x^{0})-H_{\delta _{N+1}}(x^{N+1},x^N)\\&=F(x^1)+\delta _1\Vert \varDelta _{1}\Vert ^2-H_{\delta _{N+1}}(x^{N+1},x^N)\\&\le F(x^1)+\delta _1\Vert \varDelta _{1}\Vert ^2-{\underline{F}}<\infty . \end{aligned}$$

Letting N tend to $\infty$ and recalling that $\varepsilon >0$ and ${\bar{\lambda }} >0$, the assertion (ii) follows directly.

(iii) From the definition of $H_{\delta _k}(x^k,x^{k-1})$ in (14), we know that $\{H_{\delta _k}(x^k,x^{k-1})\}$ is bounded from below since $F\ge {\underline{F}}>-\infty$. On the other hand, it follows from Lemma 3 that $\{H_{\delta _k}(x^k,x^{k-1})\}$ is monotonically nonincreasing, hence $\{H_{\delta _k}(x^k,x^{k-1})\}$ is convergent. This together with the boundedness of $\delta _k$,

$$\begin{aligned} H_{\delta _k}(x^k, x^{k-1}):= F(x^k)+\delta _k\Vert x^k-x^{k-1}\Vert ^2 \end{aligned}$$

and $\lim _{k\rightarrow \infty }\Vert \varDelta _k\Vert =0$ in the assertion (ii), we obtain that $\{F(x^k)\}$ is convergent.

(iv) Since $\{x^k\}$ is bounded, there exists at least one cluster point. Let ${\tilde{x}}$ be a cluster point and $\{x^{k_n}\}$ be the subsequence of $\{x^k\}$ such that $\lim _{n\rightarrow \infty }x^{k_n}={\tilde{x}}$. From the iterative step (9c), we know that for any integer k,

$$\begin{aligned} x^{k+1}\in \arg \min \left\{ g(x)+\left\langle x-x^k,\nabla f(z^k)-\frac{1}{\lambda _k}(y^k-x^k)\right\rangle +\frac{1}{\lambda _k}D_h(x,x^k)\right\} . \end{aligned}$$

Then, we have

$$\begin{aligned}&g(x^{k+1})+\left\langle x^{k+1}-x^k,\nabla f(z^{k})-\frac{1}{\lambda _k}(y^k-x^k)\right\rangle +\frac{1}{\lambda _k}D_h(x^{k+1},x^k)\\&\quad \le g({\tilde{x}})+\left\langle {\tilde{x}}-x^k,\nabla f(z^k)-\frac{1}{\lambda _k}(y^k-x^k)\right\rangle +\frac{1}{\lambda _k}D_h({\tilde{x}},x^k). \end{aligned}$$

Using the fact $D_h(x^{k+1},x^k)\ge \frac{\sigma _h}{2}\Vert x^{k+1}-x^k\Vert ^2$ and choosing $k:=k_n-1\,(n\ge 1)$, we obtain

$$\begin{aligned}&g(x^{k_n})+\left\langle x^{k_n}-x^{k_n-1},\nabla f(z^{k_n-1})-\frac{1}{\lambda _{k_n-1}}(y^{k_n-1}-x^{k_n-1})\right\rangle +\frac{\sigma _h}{2\lambda _{k_n-1}}\Vert x^{k_n}-x^{k_n-1}\Vert ^2\\&\quad \le g({\tilde{x}})+\left\langle {\tilde{x}}-x^{k_n-1},\nabla f(z^{k_n-1})-\frac{1}{\lambda _{k_n-1}}(y^{k_n-1}-x^{k_n-1})\right\rangle +\frac{1}{\lambda _{k_n-1}}D_h({\tilde{x}},x^{k_n-1}). \end{aligned}$$

By taking the superior limit above as $n\rightarrow \infty$, and using the fact in (ii), the continuity of $\nabla f$ and h, $x^{k_n}\rightarrow {\tilde{x}}$ as $n\rightarrow \infty$, and the fact that $\{z^k\}$ is bounded and so is $\nabla f(z^k)$, we have

$$\begin{aligned} \lim \sup _{n\rightarrow \infty } g(x^{k_n}) \le g({\tilde{x}}). \end{aligned}$$

On the other hand, by the lower semicontinuity of g, we get

$$\begin{aligned} g({\tilde{x}})\le \lim \inf _{n\rightarrow \infty }g(x^{k_n}). \end{aligned}$$

Hence, we have $\lim _{n\rightarrow \infty } g(x^{k_n}) = g({\tilde{x}}).$ Together with the definition of F in (1) and the continuity of f, we have

$$\begin{aligned} \lim _{n\rightarrow \infty }F(x^{k_n}) =F({\tilde{x}}). \end{aligned}$$

(36)

Define $\xi ^{k_n}:= -\frac{1}{\lambda _{k_n-1}}\left[ (x^{k_n-1}-y^{k_n-1})-(\nabla h(x^{k_n})-\nabla h(x^{k_n-1}))\right] +\nabla f(x^{k_n})-\nabla f(z^{k_n-1}),\,n\ge 1$. Then, by the optimality condition (11), we have

$$\begin{aligned} \xi ^{k_n} \in \nabla f(x^{k_n})+\partial g(x^{k_n}). \end{aligned}$$

(37)

Recalling (9a) and (9b), $\lim _{n\rightarrow \infty }\Vert \varDelta _{k_n}\Vert =0$ by statement (ii), the continuity of $\nabla h$ and $\nabla f$, and the boundedness of $\{\alpha _{k}\}$, $\{\beta _{k_n}\}$ and $\{\lambda _{k_n}\}$ by Assumption 2, we get $\lim _{n\rightarrow \infty }\xi ^{k_n}=0$. Together with $\lim _{n\rightarrow \infty }x^{k_n}= {\tilde{x}}$, (36) and (37), we obtain

$$\begin{aligned} 0\in \nabla f({\tilde{x}})+\partial g({\tilde{x}}), \end{aligned}$$

which implies that ${\tilde{x}}\in \mathrm{crit}F$. Furthermore, it is easy to derive that F is finite and constant on the set of all cluster point ${\tilde{x}}$ from Assumption 1 and the above conclusions as that in [13, Lemma 5]. This completes the proof. $\square$