#### 期刊菜单

A Modified Level Bundle Method with Inexact Data for Nonsmooth Constrained Optimization
DOI: 10.12677/AAM.2019.89179, PDF, HTML, XML, 下载: 1,023  浏览: 1,397  国家自然科学基金支持

Abstract: This paper presents a modified level bundle method with inexact data for nonsmooth constrained optimization. In the method, the inexact data and the approximate improvement function are in-troduced. Moreover, in the projection subproblem, the Bregman distance is used to replace the classical Euclidean distance, in order that the geometric structure of the feasible set can be taken into account, which can reduce the computation of the algorithm. Global convergence of the algo-rithm is proved and the iterative complexity is analyzed.

1. 引言

$\begin{array}{l}{f}^{\ast }:=\mathrm{min}\text{\hspace{0.17em}}\text{\hspace{0.17em}}f\left(x\right)\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{s}\text{.t}\text{.}\text{\hspace{0.17em}}\text{\hspace{0.17em}}c\left(x\right)\le 0,\\ \text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{ }\text{ }\text{\hspace{0.17em}}\text{ }x\in X,\end{array}$ (1)

$h\left(x;{f}^{\ast }\right)=\mathrm{max}\left\{f\left(x\right)-{f}^{\ast },c\left(x\right)\right\}.$ (2)

2. 算法设计

$\left\{\begin{array}{l}f\left(x\right)\ge {f}_{x}\ge f\left(x\right)-{\epsilon }_{f}^{x},\text{ }\text{ }\text{ }\text{ }{\stackrel{˜}{g}}_{f}^{x}\in {\partial }_{{\epsilon }_{f}^{x}}f\left(x\right),\\ c\left(x\right)\ge {c}_{x}\ge c\left(x\right)-{\epsilon }_{c}^{x},\text{ }\text{ }\text{ }\text{ }{\stackrel{˜}{g}}_{c}^{x}\in {\partial }_{{\epsilon }_{c}^{x}}c\left(x\right),\end{array}$ (3)

${\partial }_{\delta }f\left(x\right)=\left\{g\in {R}^{n}:f\left(y\right)\ge f\left(x\right)+〈g,y-x〉-\delta ,\forall y\in X\right\}.$

$f\left(\cdot \right)\ge f\left(x\right)+〈{\stackrel{˜}{g}}_{f}^{x},\cdot -x〉-{\epsilon }_{f}^{x},\text{\hspace{0.17em}}\text{\hspace{0.17em}}c\left(\cdot \right)\ge c\left(x\right)+〈{\stackrel{˜}{g}}_{c}^{x},\cdot -x〉-{\epsilon }_{c}^{x}.$

${\epsilon }_{f}^{x}\le {\eta }_{f},\text{\hspace{0.17em}}\text{\hspace{0.17em}}{\epsilon }_{c}^{x}\le {\eta }_{c},\text{\hspace{0.17em}}\text{\hspace{0.17em}}\forall x\in X.$

$\phi \left(x;\stackrel{^}{x}\right):=\omega \left(x\right)-\omega \left(\stackrel{^}{x}\right)-〈\nabla \omega \left(\stackrel{^}{x}\right),x-\stackrel{^}{x}〉,$

$\omega \left(y\right)\ge \omega \left(x\right)+〈\nabla \omega \left(x\right),y-x〉+\frac{{\sigma }_{\omega }}{2}{‖y-x‖}^{2},\text{\hspace{0.17em}}\forall x,y\in X.$

$〈\nabla \omega \left(x\right)-\nabla \omega \left(z\right),x-z〉\ge {\sigma }_{\omega }{‖x-z‖}^{2},\text{ }\text{ }\text{ }\text{ }\forall x,z\in X.$

${D}_{\omega ,X}^{2}:=\mathrm{max}\left\{\omega \left(x\right)-\left[\omega \left(z\right)+〈\nabla \omega \left(z\right),x-z〉\right],\forall x,z\in X\right\}.$ (4)

${‖x-z‖}^{2}\le \frac{2}{{\sigma }_{\omega }}{D}_{\omega ,X}^{2}=:{\Omega }_{\omega ,X},\text{ }\text{ }\text{ }\forall x,z\in X.$ (5)

$\left\{\begin{array}{l}{l}_{f}^{k}\left(\cdot \right):={f}_{{x}^{k}}+〈{\stackrel{˜}{g}}_{f}^{k},\cdot -{x}^{k}〉,\\ {l}_{c}^{k}\left(\cdot \right):={c}_{{x}^{k}}+〈{\stackrel{˜}{g}}_{c}^{k},\cdot -{x}^{k}〉.\end{array}$

${\stackrel{^}{f}}^{k}\left(x\right):=\underset{j\in {J}_{f}^{k}}{\mathrm{max}}{l}_{f}^{j}\left(x\right),\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }{\stackrel{^}{c}}^{k}\left(x\right):=\underset{j\in {J}_{c}^{k}}{\mathrm{max}}{l}_{c}^{j}\left(x\right),$

(6)

${f}_{\text{low}}^{k}\left(\le {f}^{*}\right)$ 是问题最优值的一个下界，定义非精确改进函数如下：

$\stackrel{˜}{h}\left(x;{f}_{\text{low}}^{k}\right)=\mathrm{max}\left\{{f}_{x}-{f}_{\text{low}}^{k},{c}_{x}\right\}.$ (7)

${h}_{\text{rec}}^{k}:=\left\{\begin{array}{l}\stackrel{˜}{h}\left({x}^{0};{f}_{\text{low}}^{0}\right),\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }k=0,\text{ }\\ \mathrm{min}\left\{\underset{j\in {J}_{f}^{k}\cap {J}_{c}^{k}}{\mathrm{min}}\stackrel{˜}{h}\left({x}^{j};{f}_{\text{low}}^{k}\right),{h}_{\text{rec}}^{k-1}\right\}\text{ },\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }k>0,\end{array}$ (8)

${x}_{\text{rec}}^{k}\in {\left\{{x}^{j}\right\}}_{j\le k}\text{ }\text{ }\text{ }\text{ }\text{ }\text{s}\text{.t}\text{.}\text{ }\text{ }\text{ }\text{ }\text{ }\stackrel{˜}{h}\left({x}_{\text{rec}}^{k};{f}_{\text{low}}^{j}\right)={h}_{\text{rec}}^{k},$ (9)

${f}_{\text{lev}}^{k}$ 为当前水平值，采用上述邻近函数代替欧氏距离，本文算法每次迭代求解如下子问题：

${x}^{k+1}:=\mathrm{arg}\underset{x\in {X}^{k}}{\mathrm{min}}\phi \left(x;{\stackrel{^}{x}}^{k}\right),$ (10)

${X}^{k}:=\left\{x\in X:{\stackrel{^}{f}}^{k}\left(x\right)\le {f}_{\text{lev}}^{k},{\stackrel{^}{c}}^{k}\left(x\right)\le 0\right\}.$ (11)

$\nabla \phi \left({x}^{k+1};{\stackrel{^}{x}}^{k}\right)+{s}^{k}+{\mu }_{f}^{k}{\stackrel{^}{g}}_{f}^{k}+{\mu }_{c}^{k}{\stackrel{^}{g}}_{c}^{k}=0,\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }{\mu }_{f}^{k}\left({\stackrel{^}{f}}^{k}\left({x}^{k+1}\right)-{f}_{\text{lev}}^{k}\right)=0,\text{ }\text{ }\text{ }\text{ }\text{ }{\mu }_{c}^{k}{\stackrel{^}{c}}^{k}\left({x}^{k+1}\right)=0.$ (12)

${\stackrel{¯}{f}}^{{a}_{k}}\left(x\right):={\stackrel{^}{f}}^{k}\left({x}^{k+1}\right)+〈{\stackrel{^}{g}}_{f}^{k},x-{x}^{k+1}〉$ 满足 ${\stackrel{¯}{f}}^{{a}_{k}}\left(x\right)\le {\stackrel{^}{f}}^{k}\left(x\right)\le f\left(x\right),\text{ }\text{ }\text{ }\text{ }\text{ }\forall x\in X,$ (13)

${\stackrel{¯}{c}}^{{a}_{k}}\left(x\right):={\stackrel{^}{c}}^{k}\left({x}^{k+1}\right)+〈{\stackrel{^}{g}}_{c}^{k},x-{x}^{k+1}〉$ 满足 ${\stackrel{¯}{c}}^{{a}_{k}}\left(x\right)\le {\stackrel{^}{c}}^{k}\left(x\right)\le c\left(x\right),\text{ }\text{ }\text{ }\text{ }\text{ }\forall x\in X.$ (14)

$\underset{x\in {X}^{k}}{\mathrm{arg}\mathrm{min}}\phi \left(x;{\stackrel{^}{x}}^{k}\right)=\underset{x\in {X}^{{a}_{k}}}{\mathrm{arg}\mathrm{min}}\phi \left(x;{\stackrel{^}{x}}^{k}\right)$ (15)

a) 对于情形I，序列 $\left\{{x}_{\text{rec}}^{k}\right\}$ 的任意聚点都是问题(1)的 $\epsilon$ 最优解，其中 $\epsilon :=\mathrm{max}\left\{{\epsilon }_{f},{\epsilon }_{c}\right\}$

b) 对于情形II，序列 $\left\{{x}_{\text{rec}}^{k}\right\}$ 的任意聚点都是问题(1)的最优解。

$0\ge \underset{k}{\mathrm{lim}}\left({f}_{{x}_{\text{rec}}^{k}}-{f}_{\text{low}}^{{j}_{k}}\right)\ge \underset{k}{\mathrm{lim}}\left(f\left({x}_{\text{rec}}^{k}\right)-{\epsilon }_{f}^{{j}_{k}}-{f}_{\text{low}}^{{j}_{k}}\right)\ge \underset{k}{\mathrm{lim}}\left(f\left({x}_{\text{rec}}^{k}\right)-{\epsilon }_{f}^{{j}_{k}}-{f}^{\text{*}}\right),$

$0\ge \underset{k}{\mathrm{lim}}{c}_{{x}_{\text{rec}}^{k}}\ge \underset{k}{\mathrm{lim}}\left(c\left({x}_{\text{rec}}^{k}\right)-{\epsilon }_{c}^{{j}_{k}}\right).$

$\stackrel{¯}{x}$ 是序列 $\left\{{x}_{\text{rec}}^{k}\right\}$ 的一个聚点，对于情形I，由以上两个不等式可以得到 $f\left(\stackrel{¯}{x}\right)\le {f}^{*}+{\epsilon }_{f}$$c\left(\stackrel{¯}{x}\right)\le {\epsilon }_{c}$，因此 $\stackrel{¯}{x}$ 是问题(1)的 $\epsilon$ 最优解。对于情形II，再次利用以上两个不等式可得 $f\left(\stackrel{¯}{x}\right)\le {f}^{\text{*}}$$c\left(\stackrel{¯}{x}\right)\le 0$，故 $\stackrel{¯}{x}$ 是问题(1)的最优解。

3. 收敛性与复杂度分析

$‖{x}^{k+1}-{x}^{k}‖\ge \frac{1-\gamma }{\Lambda }{h}_{\text{rec}}^{k},\text{ }\text{ }\text{ }\text{ }\text{ }k>k\left(l\right),$

$‖{x}^{k+1}-{\stackrel{^}{x}}^{k}‖\ge \frac{1-\gamma }{\Lambda }{h}_{\text{rec}}^{k},\text{ }\text{ }\text{ }\text{ }\text{ }k=k\left(l\right).$

${f}_{{x}^{j}}+〈{\stackrel{˜}{g}}_{f}^{j},{x}^{k+1}-{x}^{j}〉\le {f}_{\text{lev}}^{k},$

${c}_{{x}^{j}}+〈{\stackrel{˜}{g}}_{c}^{j},{x}^{k+1}-{x}^{j}〉\le 0.$

${f}_{{x}^{j}}-{f}_{\text{lev}}^{k}\le 〈{\stackrel{˜}{g}}_{f}^{j},{x}^{k+1}-{x}^{j}〉,$

${c}_{{x}^{j}}\le 〈{\stackrel{˜}{g}}_{c}^{j},{x}^{k+1}-{x}^{j}〉.$

${f}_{{x}^{j}}-{f}_{\text{lev}}^{k}\le 〈{\stackrel{˜}{g}}_{f}^{j},{x}^{k+1}-{x}^{j}〉\le ‖{\stackrel{˜}{g}}_{f}^{j}‖‖{x}^{k+1}-{x}^{j}‖\le \Lambda ‖{x}^{k+1}-{x}^{j}‖.$

${c}_{{x}^{j}}\le 〈{\stackrel{˜}{g}}_{c}^{j},{x}^{k+1}-{x}^{j}〉\le ‖{\stackrel{˜}{g}}_{c}^{j}‖‖{x}^{k+1}-{x}^{j}‖\le \Lambda ‖{x}^{k+1}-{x}^{j}‖.$

$\begin{array}{c}\Lambda ‖{x}^{k+1}-{x}^{j}‖\ge \mathrm{max}\left\{{f}_{{x}^{j}}-{f}_{\text{low}}^{k}-\gamma {h}_{\text{rec}}^{k},{c}_{{x}^{j}}\right\}\\ \ge \mathrm{max}\left\{{f}_{{x}^{j}}-{f}_{\text{low}}^{k}-\gamma {h}_{\text{rec}}^{k},{c}_{{x}^{j}}-\gamma {h}_{\text{rec}}^{k}\right\}\\ =-\gamma {h}_{\text{rec}}^{k}+\mathrm{max}\left\{{f}_{{x}^{j}}-{f}_{\text{low}}^{k},{c}_{{x}^{j}}\right\}\end{array}$

$=-\gamma {h}_{\text{rec}}^{k}+\stackrel{˜}{h}\left({x}^{j};{f}_{\text{low}}^{k}\right)$(7)

$=\left(1-\gamma \right){h}_{\text{rec}}^{k}.$(8)

$k>k\left(l\right)$，则束管理确保 $k\in {J}_{f}^{k}\cap {J}_{c}^{k}$。故令使得 $‖{x}^{k+1}-{x}^{k}‖\ge \frac{1-\gamma }{\Lambda }{h}_{\text{rec}}^{k}$ 成立，当 $k=k\left(l\right)$ 时，选取 ${\stackrel{^}{x}}^{k}$ 为稳定中心，故存在 $j\in {J}_{f}^{k}\cap {J}_{c}^{k}$ 使得 ${x}^{j}={\stackrel{^}{x}}^{k}$，即 $‖{x}^{k+1}-{\stackrel{^}{x}}^{k}‖\ge \frac{1-\gamma }{\Lambda }{h}_{\text{rec}}^{k}$ 成立。

$k-k\left(l\right)+1\le {\Omega }_{\omega ,X}{\left(\frac{\Lambda }{\left(1-\gamma \right){h}_{\text{rec}}^{k}}\right)}^{2}+1.$

$〈\nabla \phi \left({x}^{k};{\stackrel{^}{x}}^{k-1}\right),x-{x}^{k}〉\ge 0,\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\forall x\in {X}^{k-1}.$ (16)

i) 假如在第 $k-1$ 步到第k步没有束压缩机制，那么根据 ${\stackrel{^}{f}}^{k}\left(x\right)$ 的定义(6)可知 ${\stackrel{^}{f}}^{k}\left(x\right)\ge {\stackrel{^}{f}}^{k-1}\left(x\right)$${\stackrel{^}{c}}^{k}\left(x\right)\ge {\stackrel{^}{c}}^{k-1}\left(x\right),\forall x\in {R}^{n}$。根据注1可得 ${f}_{\text{lev}}^{k}\le {f}_{\text{lev}}^{k-1}$，从而 ${X}^{k}\subseteq {X}^{k-1}$。因为 $k\in {K}^{l}$，所以有 ${X}^{k}$ 非空，并且 ${x}^{k+1}\in {X}^{k}$。又因为在每个 $l$ 循环中稳定中心不变，即： ${\stackrel{^}{x}}^{k-1}={\stackrel{^}{x}}^{k}$，从而可以得到 $〈\nabla \phi \left({x}^{k};{\stackrel{^}{x}}^{k}\right),{x}^{k+1}-{x}^{k}〉\ge 0$

ii) 若在第 $k-1$ 步到第k步有束压缩，则聚集指标 ${a}_{k}\in {J}_{f}^{k}$${a}_{k}\in {J}_{c}^{k}$，故 ${\stackrel{^}{f}}^{k}\left(x\right)\ge {\stackrel{¯}{f}}^{{a}_{k}}\left(x\right)$$\text{ }{\stackrel{^}{c}}^{k}\left(x\right)\ge {\stackrel{¯}{c}}^{{a}_{k}}\left(x\right)$$\forall x\in {R}^{n}$，从而 ${X}^{k}\subseteq {X}^{{a}_{k}}$。由(15)可知 ${x}^{k}=\mathrm{arg}\mathrm{min}\left\{\phi \left(x;{\stackrel{^}{x}}^{k-1}\right),x\in {X}^{{a}_{k}}\right\}$，根据一阶最优性条件有：

$〈\nabla \phi \left({x}^{k};{\stackrel{^}{x}}^{k-1}\right),x-{x}^{k}〉\ge 0,\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\forall x\in {X}^{{a}_{k}}.$ (17)

$〈\nabla \phi \left({x}^{k};{\stackrel{^}{x}}^{k\left(l\right)}\right),{x}^{k+1}-{x}^{k}〉\ge 0.$

$\phi \left(x;{\stackrel{^}{x}}^{k\left(l\right)}\right)$ 是强凸函数，有

$\frac{\sigma }{2}{‖{x}^{k+1}-{x}^{k}‖}^{2}\le \phi \left({x}^{k+1};{\stackrel{^}{x}}^{k\left(l\right)}\right)-\phi \left({x}^{k};{\stackrel{^}{x}}^{k\left(l\right)}\right)-〈\nabla \phi \left({x}^{k};{\stackrel{^}{x}}^{k\left(l\right)}\right),{x}^{k+1}-{x}^{k}〉\le \phi \left({x}^{k+1};{\stackrel{^}{x}}^{k\left(l\right)}\right)-\phi \left({x}^{k};{\stackrel{^}{x}}^{k\left(l\right)}\right).$

$\frac{\sigma }{2}{‖{x}^{k+1}-{x}^{k}‖}^{2}\le \phi \left({x}^{k+1};{\stackrel{^}{x}}^{k\left(l\right)}\right)-\phi \left({x}^{k};{\stackrel{^}{x}}^{k\left(l\right)}\right).$

$\frac{\sigma }{2}\underset{{}^{j=k\left(l\right)+1}}{\overset{k}{\sum }}{‖{x}^{j+1}-{x}^{j}‖}^{2}\le \phi \left({x}^{k+1};{\stackrel{^}{x}}^{k\left(l\right)}\right)-\phi \left({x}^{k\left(l\right)+1};{\stackrel{^}{x}}^{k\left(l\right)}\right).$ (18)

$\frac{\sigma }{2}\underset{{}^{j=k\left(l\right)+1}}{\overset{k}{\sum }}{‖{x}^{j+1}-{x}^{j}‖}^{2}\ge \frac{\sigma }{2}\underset{{}^{j=k\left(l\right)+1}}{\overset{k}{\sum }}{\left(\frac{1-\gamma }{\Lambda }{h}_{\text{rec}}^{j}\right)}^{2}\ge \frac{\sigma }{2}\underset{{}^{j=k\left(l\right)+1}}{\overset{k}{\sum }}{\left(\frac{1-\gamma }{\Lambda }{h}_{\text{rec}}^{k}\right)}^{2}.$

$\begin{array}{l}\phi \left({x}^{k+1};{\stackrel{^}{x}}^{k\left(l\right)}\right)-\phi \left({x}^{k\left(l\right)+1};{\stackrel{^}{x}}^{k\left(l\right)}\right)\\ \le \phi \left({x}^{k+1};{\stackrel{^}{x}}^{k\left(l\right)}\right)\le \underset{x\in X}{\mathrm{max}}\left\{\phi \left(x;{\stackrel{^}{x}}^{k\left(l\right)}\right)\right\}\le \underset{x,y\in X}{\mathrm{max}}\left\{\phi \left(x;y\right)\right\}={D}_{\omega ,X}^{2}.\end{array}$

${D}_{\omega ,X}^{2}\ge \frac{\sigma }{2}\underset{{}^{j=k\left(l\right)+1}}{\overset{k}{\sum }}{\left(\frac{1-\gamma }{\Lambda }{h}_{\text{rec}}^{k}\right)}^{2}=\frac{\sigma }{2}\left(k-k\left(l\right)\right){\left(\frac{1-\gamma }{\Lambda }{h}_{\text{rec}}^{k}\right)}^{2},$

$k-k\left(l\right)\le \frac{2{D}_{\omega ,X}^{2}}{\sigma }{\left(\frac{\Lambda }{\left(1-\gamma \right){h}_{\text{rec}}^{k}}\right)}^{2}={\Omega }_{\omega ,X}{\left(\frac{\Lambda }{\left(1-\gamma \right){h}_{\text{rec}}^{k}}\right)}^{2}.$

$\square$

a) 如果 ${\epsilon }_{f}^{k}\equiv {\epsilon }_{f}\ge 0$${\epsilon }_{c}^{k}\equiv {\epsilon }_{c}\ge 0$$\forall k$，则序列 $\left\{{x}_{\text{rec}}^{k}\right\}$ 的任意聚点是问题(1)的 $\epsilon$ 最优解，其中 $\epsilon :=\mathrm{max}\left\{{\epsilon }_{f},{\epsilon }_{c}\right\}$

b) 如果 ${\epsilon }_{f}^{k}\to 0$${\epsilon }_{c}^{k}\to 0$$k\to \infty$，则序列 $\left\{{x}_{\text{rec}}^{k}\right\}$ 的任意聚点是问题(1)的最优解。

$\square$

$\left(1+\frac{{f}^{*}-{f}_{\text{low}}^{0}}{\gamma {\delta }_{\text{Tol}}}\right)\left({\Omega }_{\omega ,X}{\left(\frac{\Lambda }{\left(1-\gamma \right){\delta }_{\text{Tol}}}\right)}^{2}+1\right).$

${f}^{\text{*}}\ge {f}_{\text{low}}^{0}+\gamma {h}_{\text{rec}}^{1}+\cdots +\gamma {h}_{\text{rec}}^{k}\ge {f}_{\text{low}}^{0}+\gamma {\delta }_{\text{Tol}}+\cdots +\gamma {\delta }_{\text{Tol}}.$

$N\le \frac{{f}^{\text{*}}-{f}_{\text{low}}^{0}}{\gamma {\delta }_{\text{Tol}}}.$

${\Omega }_{\omega ,X}{\left(\frac{\Lambda }{\left(1-\gamma \right){h}_{\text{rec}}^{k}}\right)}^{2}+1\le {\Omega }_{\omega ,X}{\left(\frac{\Lambda }{\left(1-\gamma \right){\delta }_{\text{Tol}}}\right)}^{2}+1.$

${k}_{{\delta }_{\text{Tol}}}$ 是使得 ${h}_{\text{rec}}^{k}>{\delta }_{\text{Tol}}\text{ }$ 成立的最大指标集，那么

${k}_{{\delta }_{\text{Tol}}}\le \left(1+\frac{{f}^{*}-{f}_{\text{low}}^{0}}{\gamma {\delta }_{\text{Tol}}}\right)\left({\Omega }_{\omega ,X}{\left(\frac{\Lambda }{\left(1-\gamma \right){\delta }_{\text{Tol}}}\right)}^{2}+1\right).$

$\square$

4. 结束语

NOTES

*通讯作者

 [1] Kiwiel, K.C. (1985) An Exact Penalty Function Algorithm for Non-Smooth Convex Constrained Minimization Prob-lems. IMA Journal of Numerical Analysis, 5, 111-119. https://doi.org/10.1093/imanum/5.1.111 [2] Karas, E., Ribeiro, A., Sagastizábal, C., et al. (2009) A Bundle-Filter Method for Nonsmooth Convex Constrained Optimization. Mathematical Programming, 116, 297-320. https://doi.org/10.1007/s10107-007-0123-7 [3] Lemarechal, C., Nemirovskii, A. and Nesterov, Y. (1995) New Variants of Bundle Methods. Mathematical Programming, 69, 111-147. https://doi.org/10.1007/BF01585555 [4] Fletcher, R. and Leyffer, S. (2002) Nonlinear Programming without a Penalty Function. Mathematical Programming, 91, 239-269. https://doi.org/10.1007/s101070100244 [5] Van Ackooij, W. and De Oliveira, W. (2014) Level Bundle Methods for Constrained Convex Optimization with Various Oracles. Computational Optimization and Applications, 57, 555-597. https://doi.org/10.1007/s10589-013-9610-3 [6] Kiwiel, K.C. (1999) A Bundle Bregman Proximal Method for Convex Nondifferentiable Minimization. Mathematical Programming, 85, 241-258. https://doi.org/10.1007/s101070050056 [7] Ben-Tal, A. and Nemirovski, A. (2005) Non-Euclidean Restricted Memory Level Method for Large-Scale Convex Optimization. Mathematical Programming, 102, 407-456. https://doi.org/10.1007/s10107-004-0553-4 [8] 梁玲. 非光滑优化基于非精确数据的加速水平束方法[D]: [硕士学位论文]. 南宁: 广西大学, 2018. [9] 陈韵梅, 张维. 基于近似一阶信息的加速的bundle level算法[J]. 中国科学, 2017, 10(47): 1119-1142.