1
$\begingroup$

Let $f:\mathbb{R}^n\to\mathbb{R}$ be a given function and let us consider the unconstrained problem, $$\min_{x\in\mathbb{R}^n}f(x)$$ The standard iterative method for this is the gradient descent technique, where one iteratively generates the following sequence of points, $$x^{n+1}=x^n-\mu_ng(x^n)$$ where $\mu_n,n\ge 0$ is a sequence of positive stepsizes, and $g(x)=\nabla f(x)$ is the gradient operator. My question is the following:

Is the gradient evaluation method optimal? In other words, if we adopt the following alternative method: $$x^{n+1}=x^n-\mu_ng(h(x^n))$$ where $h:\mathbb{R}^n\to\mathbb{R}^n $ is a transformation (possible nonlinear), then is it the best way to take $h$ as the identity operator (where the qualifier best is described in some sense, for example, convergence rate)?

So basically I am asking, is it always best to evaluate the gradient at the point $x^n$ itself, or there can be transformations $h$ which might depend on the structure of the function $f$, that may help in faster convergence of the method? Can anybody refer me to any result in the literature that might have a link with this question? Any help is appreciated. Thanks in advance.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ It would be better to take an $h$ such that we can get from the initial point to the exact minimum in a single step. Of course we don't know what that $h$ would be. $\endgroup$
    – Robert Israel
    Jul 18, 2017 at 15:59
  • $\begingroup$ Yes, we don't know how to find such a $h$, however, I wonder how can we proceed to analyze such an algorithm if some form of $h$ is given? Any ideas? $\endgroup$
    – Samrat Mukhopadhyay
    Jul 18, 2017 at 17:32

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.