0

I have the formula for calculating the step-size for steepest descent for a given quadratic. However, the formula says that Q is positive definite. My Q is not. Does the same formula apply? Admins, how do I get this question answered. It seems that once someone has commented then the question tends to get ignored as it is not up in the list.

user100503
  • 449
  • Show your formula please? – IAmNoOne May 01 '14 at 01:35
  • If f= 1/2x^TQx - b^Tx. Q is spd. gradient (g) is Qx-b. x^(k+1)=x^(k)-alphag^(k). alpha= (g^Tg)/(g^TQg) – user100503 May 01 '14 at 01:43
  • Sorry, $grad(g) = Qx - b$? What is the role of $f$ here then? – IAmNoOne May 01 '14 at 01:55
  • The function f is represented in given quadratic form. Q = Q^T – user100503 May 01 '14 at 01:56
  • So then what is $g$? Did you mean $grad(f) = Qx - b$? – IAmNoOne May 01 '14 at 02:09
  • Yes. g is the grad(f) – user100503 May 01 '14 at 02:14
  • So in other words, $Q$ is the Hessian of $f$. It looks like if $Q$ is not positive definite, then $Q$ may be singular, so the algorithm is not well-defined (in other words, $f$ is not strictly convex). – IAmNoOne May 01 '14 at 02:24
  • Yes, Q is the Hessian. Q is actually [4 0; 0 -8]. Q is indefinite, I believe. Q is not singular. – user100503 May 01 '14 at 02:32
  • 1
    Your Hessian is indefinite, so the quadratic does not have a bounded minimum, and gradient descent will send you off to infinity while the function value plummets. In your example, let $x_1=0$ and $x_2\to\infty$, then $f\to-\infty$. Why do you want to do this? –  May 02 '14 at 17:39
  • Thank you. If x1 and x2 are both 0, then after two iterations we get a point that is the same as the point after the first iteration. Does that imply that this point is neither a max or a min? – user100503 May 02 '14 at 17:59

0 Answers0