I am trying to minimize an unconstrained nonlinear optimization problem using conjugate gradient. I don't have exact gradient ($\nabla f(x)$) information, but I do have an approximate gradient ($\nabla f_a(x)$) such that $\| \nabla f(x) - \nabla f_a(x)\| \leq \delta$ for some constant $\delta >0$ for all $x \in \mathbb{R}^n$. Given the fact that $-\nabla f_a$ is a descent direction, will the conjugate gradient with this approx. gradient converge to some local minima ? If not true in general, can we say something for strictly convex quadratic functions ?

  • 1
    $\begingroup$ No such luck; even for strictly convex functions, all you can say is that the algorithm will eventually find itself in a region where $\|\nabla f(x)\|\le\delta$. It may then converge to a point that may or may not be a local minimum, or it may wander endlessly in that region without converging. $\endgroup$ – Rahul May 9 '17 at 6:51
  • $\begingroup$ Can you please elaborate your answer a bit more. What I follow from your reply is that $\nabla f_a$ is driven to 0 using the simple conjugate gradient. Does every algorithm which uses descent direction at each iteration always converge to local min. ? If this fact is true, then steepest descent should work with approx gradient. If we somehow make sure that conjugate gradient creates descent direction at each iteration, can we comment on convergence. If that is true, then we can ask about how to make sure conjugate directions are descent. $\endgroup$ – user402940 May 9 '17 at 15:13
  • $\begingroup$ As long as we use an appropriate globalization method, such as line searches or trust-regions, all gradient based algorithms have this issue. Simply, how do we check whether a function is stationary beyond the accuracy of our gradient, which tells us precisely that? That said, there are inexact gradient methods. However, these methods generally operate under the principle that we may not need an accurate gradient at some particular iteration, but we will need it eventually. As such, the algorithm generally demands more accurate gradients as we get closer to optimality. $\endgroup$ – wyer33 May 10 '17 at 1:28

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.