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