Let $f(x,y) = (x-y)^4+2x^2+y^2-x+2y$. I am trying to numerically find the miniumum of $f$. We define a fixed-point iteration scheme \begin{align*} g(x, y) = \vec{x}_{n+1} = \vec{x}_{n} - a\nabla f \end{align*} for $\vec{x}_n, \nabla f \in \mathbb{R}^2$ and $a \in \mathbb{R}.$ We know that a fixed point scheme $g(x)$ converges if $||\nabla g || < 1$ in the considered domain (from Numerical Analysis). Hence, \begin{align*} ||\nabla g || < 1 \\ ||\nabla \vec{x}_{n} - a\nabla^2 f || < 1\\ ||\nabla \vec{x}_{n} - a H(f) || < 1 \end{align*} where $H(f)$ denotes the Hessian matrix of $f$. Is there a way to explicitly solve for $a$ or at least approximate its upper bound? Is $\nabla^2 f = H(f)$ or am I wrong? The last equation doesn't really work because the dimensions of $\vec{x}_{n}$ and $H(f)$ don't match so I don't know how to manipulate it. The final objective here is to find an biggest $a$ such that $g$ still converge because I already know how to find the minimum of $f$ with a random $a$. It's a poorly posed question so any help is appreciated! No need for exact answers. The 1 dimensional case is much simpler because if you consider for $g(x) = x_n - af'(x)$ \begin{align*} |g'(x)| < \lambda < 1 \\ |1 - af''(x)| < \lambda \\ -\lambda < 1 - af''(x) < \lambda \\ \frac{\lambda + 1}{f''(x)} < a < \frac{\lambda + 1}{f''(x)}\\ \end{align*} so that at least we know an upper bound for $a$.

  • $\begingroup$ Everything seems fine. Now notice that $\nabla x = I$, the identity matrix, similar to how you get the $1$ in the one-dimensional case. $\endgroup$ – Rahul Mar 9 at 2:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.