next up previous contents index
Next: The Procrustes Problem Up: Nonlinear Eigenvalue Problems with Previous: MATLAB Templates   Contents   Index


Sample Problems and Their Differentials

This section serves as a sample guide on the manipulation of objective functions of matrices with orthonormal columns. We have found a few common tricks worth emphasizing.

Once one has a formula for the objective function $F(Y)$, we define the formula for $dF(Y)$ implicitly by $\tr(V^*dF(Y)) =
\frac{d}{dt} F(Y(t)) \vert _{t=0}$, where $Y(t) = Y+tV$ (or any curve $Y(t)$ for which $\dot{Y}(0)=V$). The reader may recall that $\tr(A^* B)
= \sum_{i,j} A_{ij} B_{ij}$, so it functions just like the real inner product for vectors,[*] and the implicit definition of $dF(Y)$ is actually the directional derivative interpretation of the gradient of $F(Y)$ as an unconstrained function in a Euclidean space.

For most of the functions we have used in our examples, the easiest way to obtain the formula for $dF$ is to actually use the implicit definition.

For example, if $F(Y) = \tr(A Y^* B Y)$ one then has

\begin{displaymath}\tr(V^*dF(Y))= \tr (AV^*BY + AY^*BV).\end{displaymath}

Since the value of the trace is invariant under cyclic permutations of products and transposes, we may rewrite this equation as

\begin{displaymath}\tr(V^*dF(Y)) = \tr (V^*BYA + V^*B^*YA^*),\end{displaymath}

and, since $V$ is unrestricted, this implies that $dF(Y) = BYA+B^*Y^*A^*$.

The process we recommend is:

As a check, we recommend using the finite difference dF.m code supplied in the subdirectory finitediff to check derivations before proceeding.

The software needs a function called ddF.m, which returns $\frac{d}{dt} dF(Y(t))\vert _{t=0}$ for $\dot{Y}(0) = H$. The sort of second derivative information required by the software is easier to derive than the first. If one has an analytic expression for $dF(Y)$, then one need only differentiate.

If, for some reason, the computation for ddF.m costs much more than two evaluations of $dF(Y)$ with dF.m, the reader may just consider employing the finite difference function for ddF.m found in finitediff (or simply use ddF.m as a check).

It is, however, strongly suggested that one use an analytic expression for computing $dF(Y)$, as the finite difference code for it requires a large number of function evaluations ($2np$).



Subsections
next up previous contents index
Next: The Procrustes Problem Up: Nonlinear Eigenvalue Problems with Previous: MATLAB Templates   Contents   Index
Susan Blackford 2000-11-20