5d3e8a0b2e92a1d4d4b54606ab9453b5a96be215
[octave.git] / optimization / step_length_positive_definite.m
1 function alpha = step_length_positive_definite(g, Q)
2 %
3 % Find the minimizer alpha of,
4 %
5 % phi(alpha) = f(x + alpha*p)
6 %
7 % where ``p`` is a descent direction,
8 %
9 % f(x) = (1/2)<Qx,x> - <b,x>
10 %
11 % and ``Q`` is positive-definite.
12 %
13 % The closed-form solution to this problem is given in Nocedal and
14 % Wright, (3.55). The direction of steepest descent will always be
15 % the negative gradient direction; this simplified form is given in
16 % Guler.
17 %
18 % INPUT:
19 %
20 % - ``g`` -- The gradient of f at x.
21 %
22 % - ``Q`` -- The positive-definite matrix in the definition of
23 % ``f`` above.
24 %
25 % OUTPUT:
26 %
27 % - ``alpha`` -- The value which decreases ``f`` the most.
28 %
29 % NOTES:
30 %
31 % All vectors are assumed to be *column* vectors.
32 %
33 denom = (g' * Q * g);
34
35 % denom is non-negative, since it's a Q-norm. No need to abs() it.
36 if (denom < eps)
37 % Catch divide-by-zeros. If denom is effectively zero, set it to
38 % something tiny instead. This trick is also used in the PCGM.
39 denom = eps;
40 end
41
42 alpha = (g' * g)/denom;
43 end