Let us consider a function $f\in C^2$, and convex such that the Hessian $H\le LI$. We consider following minimization problem: $$\min_{x\in \mathbb{R}^n }f(x)$$ Let us consider the following iterative process for estimating the minimizer, $$x^{k+1}=x^k-A \nabla f(x^k)$$ where the matrix $A$ can be singular. It is well known, that if $A=\mu I$, a suitable Lyapunov function to use for checking convergence, is the function $f$ itself, as in that setting we have $$f(x^{k+1})\le f(x^k)-(\mu-\mu^2L/2)\|\nabla f(x^k)\|_2^2 $$ which shows descent property for $0<\mu <2/L$.
My question is,
Is it possible to choose such a suitable Lyapunov function for the general case when $A$ might be singular. Of course, we could choose $f$, but then to have descent property we need to have $A-L/2 A^tA$ positive definite. I just want to know if there are better functions that might impose weaker restrictions on $A$ and still have a descent property.
Any reference to literature and existing techniques will be highly appreciated. Thanks in advance.
Edit: Another observation that I have made is that, if we have some $x^\star$ such that $\nabla f(x^\star)=0$, we can write the following $${x}^{n+1}-{x}^\star=({I-AG}({x}^\star,\ {x}^n))({x}^n-{x}^\star)$$ where $$G({x}^\star,\ {x}^n)=\int_0^1 \nabla^2f(x^\star+\tau(x^n-x^\star))d\tau$$ Then, analyzing convergence of the sequence $\{x^n\}$ is equivalent to finding suitable conditions on the minimum and maximum eigenvalues of $AG({x}^\star,\ {x}^n)$. Does the function $\|x-x^\star\|_2$ then qualify as a Lyapunov function? Even if it is true, I can not find an analog of $f(\cdot)$ which acts a Lyapunov function for the general case. I have read a few sections of the paper that @dohmatob referred in the comments, but I think I cannot find a Lyapunov function for this problem using the techniques introduced in that paper. The matrix $A$ is creating the problem.
