A variant of the constrained gradient method (Q911461)

The authors consider the method of conditional gradients applied to a mathematical program of minimizing a convex differentiable functional \(\phi\) (x) over a convex set \(D\subset {\mathbb{R}}^ n\). The corresponding iterative algorithm can be described as follows. Let \(x_ k\) be a current guess. Find \(y_ k\in S_ k=\{x_ k+S\}\cap D\) such that: \[ (1)\quad (y_ k-x_ k)^ T\nabla \phi (x_ k)\leq t_ k\quad \min \{(y-x_ k)^ T\nabla \phi (x_ k):\quad y\in S_ k\}, \] where S is a convex compact neighborhood of zero and \(t_ k\in (0,1]\). Then put \(x_{k+1}=x_ k+\lambda_ k(y_ k-x_ k)\) for some \(\lambda_ k\in [0,1].\) Some simple procedures for choosing parameters \(t_ k\) and \(\lambda_ k\), ensuring convergence of the algorithm, are given. A method for solving problem (1), when the sets D and S are defined by inequality constraints, is proposed.