From: Michael Orlitzky Date: Sat, 9 Mar 2013 01:51:40 +0000 (-0500) Subject: Add some step length functions, untested. X-Git-Url: http://gitweb.michael.orlitzky.com/?p=octave.git;a=commitdiff_plain;h=69d4adf22828f26858e89de560078e1b5ed1714a Add some step length functions, untested. --- diff --git a/optimization/step_length_cgm.m b/optimization/step_length_cgm.m new file mode 100644 index 0000000..60f7cd4 --- /dev/null +++ b/optimization/step_length_cgm.m @@ -0,0 +1,40 @@ +function alpha = step_length_cgm(r, A, p) + ## + ## Compute the step length for the conjugate gradient method (CGM). + ## The CGM attempts to solve, + ## + ## Ax = b + ## + ## or equivalently, + ## + ## min[phi(x) = (1/2) - ] + ## + ## where ``A`` is positive-definite. In the process, we need to + ## compute a number of search directions ``p`` and optimal step + ## lengths ``alpha``; i.e., + ## + ## x_{k+1} = x_{k} + alpha_{k}*p_{k} + ## + ## This function computes alpha_{k} in the formula above. + ## + ## INPUT: + ## + ## - ``r`` -- The residual, Ax - b, at the current step. + ## + ## - ``A`` -- The matrix ``A`` in the formulation above. + ## + ## - ``p`` -- The current search direction. + ## + ## OUTPUT: + ## + ## - ``alpha`` -- The minimizer of ``f(x) = x + alpha*p`` along ``p`. + ## + ## NOTES: + ## + ## All vectors are assumed to be *column* vectors. + ## + + ## A simple calculation should convince you that the gradient of + ## phi(x) above is Ax - b == r. + alpha = step_length_positive_definite(r, A, p); +end diff --git a/optimization/step_length_positive_definite.m b/optimization/step_length_positive_definite.m new file mode 100644 index 0000000..b1e5c48 --- /dev/null +++ b/optimization/step_length_positive_definite.m @@ -0,0 +1,36 @@ +function alpha = step_length_positive_definite(g, Q, p) + ## + ## Find the minimizer alpha of, + ## + ## phi(alpha) = f(x + alpha*p) + ## + ## where ``p`` is a descent direction, + ## + ## f(x) = (1/2) - + ## + ## and ``Q`` is positive-definite. + ## + ## The closed-form solution to this problem is given in Nocedal and + ## Wright, (3.55). + ## + ## INPUT: + ## + ## - ``g`` -- The gradient of f. + ## + ## - ``Q`` -- The positive-definite matrix in the definition of + ## ``f`` above. + ## + ## - ``p`` -- The direction in which ``f`` decreases. The line + ## along which we minimize f(x + alpha*p). + ## + ## OUTPUT: + ## + ## - ``alpha`` -- The value which causes ``f`` to decrease the + ## most. + ## + ## NOTES: + ## + ## All vectors are assumed to be *column* vectors. + ## + alpha = -(g' * p)/(p' * Q * p) +end