Coordinate-wise Armijo's condition: General case

Abstract

Let $z=(x,y)$ be coordinates for the product space ${\mathbb{R}}^{m_1}\times {\mathbb{R}}^{m_2}$. Let $f:{\mathbb{R}}^{m_1}\times {\mathbb{R}}^{m_2}\to \mathbb{R}$ be a $C^1$ function, and $\nabla f=({\partial }_{x}f,{\partial }_{y}f)$ its gradient. Fix $0<\alpha <1$. For a point $(x,y)\in {\mathbb{R}}^{m_1}\times {\mathbb{R}}^{m_2}$, a number $\delta >0$ satisfies Armijo's condition at $(x,y)$ if the following inequality holds: \begin{eqnarray*} f(x-δ\partial _xf,y-δ\partial _yf)-f(x,y)\leq -αδ(||\partial _xf||^2+||\partial _yf||^2). \end{eqnarray*} In one previous paper, we proposed the following {\bf coordinate-wise} Armijo's condition. Fix again $0<\alpha <1$. A pair of positive numbers ${\delta }_1,{\delta }_2>0$ satisfies the coordinate-wise variant of Armijo's condition at $(x,y)$ if the following inequality holds: \begin{eqnarray*} [f(x-δ_1\partial _xf(x,y), y-δ_2\partial _y f(x,y))]-[f(x,y)]\leq -α(δ_1||\partial _xf(x,y)||^2+δ_2||\partial _yf(x,y)||^2). \end{eqnarray*} Previously we applied this condition for functions of the form $f(x,y)=f(x)+g(y)$, and proved various convergent results for them. For a general function, it is crucial - for being able to do real computations - to have a systematic algorithm for obtaining ${\delta }_1$ and ${\delta }_2$ satisfying the coordinate-wise version of Armijo's condition, much like Backtracking for the usual Armijo's condition. In this paper we propose such an algorithm, and prove according convergent results. We then analyse and present experimental results for some functions such as $f(x,y)=a|x|+y$ (given by Asl and Overton in connection to Wolfe's method), $f(x,y)=x^{3}sin(1/x)+y^{3}sin(1/y)$ and Rosenbrock's function.

arXiv comment6 pages. Preprint arXiv:1911.07820 is incorporated as a very special case