An approach to designing numerically implementable algorithms of the \(\epsilon\)-subgradient method (Q1120812)

\textit{C. Lemaréchal} [Inform. Processing 74, Proc. IFIP Congr. 74, Stockholm, 552-556 (1974; Zbl 0297.65041)] and the second author [Issled. Prikl. Mat. 7, 3-11 (1979); English translation in J. Sov. Math. 43, No.3, 2419-2425 (1988; Zbl 0664.90079)] proposed an \(\epsilon\)- subgradient method for finding an \(\epsilon\)-optimal point of a function f. Let f be defined on an open set G of an n-dimensional space \(E^ n\), \(x_ 0\in G\) and \(\epsilon\geq 0\), and let \(T_{\epsilon}(x_ 0)=\{g: g\in E^ n\), \(<g,x><<g,x_ 0>\) for all \(x\in E_{\epsilon}(x_ 0)\}\) be the cone of \(\epsilon\)-generalized support vectors for f at the point \(x_ 0\) with respect to the set G, where \(E_{\epsilon}(x_ 0)=\{x: x\in G\), \(f(x)<f(x_ 0)-\epsilon \}\). The \(\epsilon\)-subgradient minimization method makes it possible to construct a sequence \(\{x_ k\}\), \(x_ k\in G\), \(k=0,1,...\), according to the following rules. If \(0\not\in T_{\epsilon}(x_ k)\), then we seek a vector \(s_ k\), satisfying the condition \(<g,s_ k><0\) for all \(g\in T_{\epsilon}(x_ k)\). Further we seek \(t_ k>0\) such that \(x_{k+1}=x_ k+t_ ks_ k\in G\) and \(f(x_ k)-f(x_{k+1})\geq \epsilon\). But if \(0\in T_{\epsilon}(x_ k)\), then \(x_ k\) is an \(\epsilon\)-optimal point of f on G, i.e., \(f(x_ k)-\epsilon \leq f^*=\inf_{x\in G}f(x).\) In this form the method cannot be realized numerically, above all due to the impossibility of calculating the cone \(T_{\epsilon}(x)\). Lemaréchal [op. cit.], the second author [op. cit.], and the second author and \textit{O. V. Mironov} [Issled. Prikl. Mat. 7, 12-18 (1979); English translation in J. Sov. Math. 43, No.3, 2426-2430 (1988; Zbl 0664.90081)] introduced some schemes for constructing numerically realizable algorithms of the \(\epsilon\)-subgradient method. In this paper we propose yet another approach to obtaining realizable algorithms of this method and prove estimates for convergence.