optimization/step_length_positive_definite.m

   1 function alpha = step_length_positive_definite(g, Q, p)
   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).
  15   %
  16   % INPUT:
  17   %
  18   %   - ``g`` -- The gradient of f at x.
  19   %
  20   %   - ``Q`` -- The positive-definite matrix in the definition of
  21   %     ``f`` above.
  22   %
  23   %   - ``p`` -- The direction in which ``f`` decreases. The line
  24   %     along which we minimize f(x + alpha*p).
  25   %
  26   % OUTPUT:
  27   %
  28   %   - ``alpha`` -- The value which causes ``f`` to decrease the
  29   %     most.
  30   %
  31   % NOTES:
  32   %
  33   % All vectors are assumed to be *column* vectors.
  34   %
  35   denom = (p' * Q * p);
  36
  37   % denom is non-negative, since it's a Q-norm. No need to abs() it.
  38   if (denom < eps)
  39     % Catch divide-by-zeros. If denom is effectively zero, set it to
  40     % something tiny instead. This trick is also used in the PCGM.
  41     denom = eps;
  42   end
  43
  44   alpha = (g' * g)/denom;
  45 end