Add step_size_positive_definite().
authorMichael Orlitzky <michael@orlitzky.com>
Mon, 18 Mar 2013 02:21:04 +0000 (22:21 -0400)
committerMichael Orlitzky <michael@orlitzky.com>
Mon, 18 Mar 2013 02:21:04 +0000 (22:21 -0400)
optimization/step_size_positive_definite.m [new file with mode: 0644]

diff --git a/optimization/step_size_positive_definite.m b/optimization/step_size_positive_definite.m
new file mode 100644 (file)
index 0000000..3e991a3
--- /dev/null
@@ -0,0 +1,29 @@
+function alpha = step_size_positive_definite(Q, b, x)
+  % Let,
+  %
+  %   f(x) = (1/2)<Qx,x> - <b,x> + a    (1)
+  %
+  % where Q is symmetric and positive definite.
+  %
+  % If we seek to minimize f; that is, to solve Qx = b, then we can do
+  % so using the method of steepest-descent. This function computes
+  % the optimal step size alpha for the steepest descent method, in
+  % the negative-gradient direction, at x.
+  %
+  % INPUT:
+  %
+  %   - ``Q`` -- the positive-definite matrix in the definition of f(x).
+  %
+  %   - ``b`` -- the known vector in the definition of f(x).
+  %
+  % OUTPUT:
+  %
+  %   - ``alpha`` -- the optimal step size in the negative gradient
+  %     direction.
+  %
+
+  % The gradient of f(x) is Qx - b, and d_k is the negative gradient
+  % direction.
+  d_k = b - Q*x;
+  alpha = (d_k' * d_k) / (d_k' * Q * d_k);
+end