ALAFF Existence of A-conjugate search directions

Skip to main content

\( \usepackage{array} \setlength{\oddsidemargin}{-0.0in} \setlength{\evensidemargin}{-0.0in} \setlength{\textheight}{8.75in} \setlength{\textwidth}{6.5in} \setlength{\topmargin}{-0.25in} \newcommand{\R}{\mathbb R} \newcommand{\Rm}{\mathbb R^m} \newcommand{\Rn}{\mathbb R^n} \newcommand{\Rnxn}{\mathbb R^{n \times n}} \newcommand{\Rmxn}{\mathbb R^{m \times n}} \newcommand{\Rmxm}{\mathbb R^{m \times m}} \newcommand{\Rmxk}{\mathbb R^{m \times k}} \newcommand{\Rkxn}{\mathbb R^{k \times n}} \newcommand{\C}{\mathbb C} \newcommand{\Cm}{\mathbb C^m} \newcommand{\Cmxm}{\mathbb C^{m \times m}} \newcommand{\Cnxn}{\mathbb C^{n \times n}} \newcommand{\Cmxn}{\mathbb C^{m \times n}} \newcommand{\Ckxk}{\mathbb C^{k \times k}} \newcommand{\Cn}{\mathbb C^n} \newcommand{\Ck}{\mathbb C^k} \newcommand{\Null}{{\cal N}} \newcommand{\Col}{{\cal C}} \newcommand{\Rowspace}{{\cal R}} \newcommand{\Span}{{\rm {Span}}} \newcommand{\rank}{{\rm rank}} \newcommand{\triu}{{\rm triu}} \newcommand{\tril}{{\rm tril}} \newcommand{\sign}{{\rm sign}} \newcommand{\FlaTwoByTwo}[4]{ \left( \begin{array}{c | c} #1 \amp #2 \\ \hline #3 \amp #4 \end{array} \right) } \newcommand{\FlaTwoByTwoSingleLine}[4]{ \left( \begin{array}{c c} #1 \amp #2 \\ #3 \amp #4 \end{array} \right) } \newcommand{\FlaTwoByTwoSingleLineNoPar}[4]{ \begin{array}{c c} #1 \amp #2 \\ #3 \amp #4 \end{array} } \newcommand{\FlaOneByTwo}[2]{ \left( \begin{array}{c | c} #1 \amp #2 \end{array} \right) } \newcommand{\FlaOneByTwoSingleLine}[2]{ \left( \begin{array}{c c} #1 \amp #2 \end{array} \right) } \newcommand{\FlaTwoByOne}[2]{ \left( \begin{array}{c} #1 \\ \hline #2 \end{array} \right) } \newcommand{\FlaTwoByOneSingleLine}[2]{ \left( \begin{array}{c} #1 \\ #2 \end{array} \right) } \newcommand{\FlaThreeByOneB}[3]{ \left( \begin{array}{c} #1 \\ \hline #2 \\ #3 \end{array} \right) } \newcommand{\FlaThreeByOneT}[3]{ \left( \begin{array}{c} #1 \\ #2 \\ \hline #3 \end{array} \right) } \newcommand{\FlaOneByThreeR}[3]{ \left( \begin{array}{c | c c} #1 \amp #2 \amp #3 \end{array} \right) } \newcommand{\FlaOneByThreeL}[3]{ \left( \begin{array}{c c | c} #1 \amp #2 \amp #3 \end{array} \right) } \newcommand{\FlaThreeByThreeBR}[9]{ \left( \begin{array}{c | c c} #1 \amp #2 \amp #3 \\ \hline #4 \amp #5 \amp #6 \\ #7 \amp #8 \amp #9 \end{array} \right) } \newcommand{\FlaThreeByThreeTL}[9]{ \left( \begin{array}{c c | c} #1 \amp #2 \amp #3 \\ #4 \amp #5 \amp #6 \\ \hline #7 \amp #8 \amp #9 \end{array} \right) } \newcommand{\diag}[1]{{\rm diag}( #1 )} \newcommand{\URt}{{\sc HQR}} \newcommand{\FlaAlgorithm}{ \begin{array}{|l|} \hline \routinename \\ \hline \partitionings \\ ~~~ \begin{array}{l} \partitionsizes \end{array} \\ {\bf \color{blue} {while}~} \guard \\ ~~~ \begin{array}{l} \repartitionings \end{array} \\ ~~~ \color{red} { \begin{array}{l} \hline \color{black} {\update} \\ \hline \end{array}} \\ ~~~ \begin{array}{l} \moveboundaries \end{array} \\ {\bf \color{blue} {endwhile}} \\ \hline \end{array} } \newcommand{\FlaAlgorithmWithInit}{ \begin{array}{|l|} \hline \routinename \\ \hline \initialize \\ \partitionings \\ ~~~ \begin{array}{l} \partitionsizes \end{array} \\ {\bf \color{blue} {while}~} \guard \\ ~~~ \begin{array}{l} \repartitionings \end{array} \\ ~~~ \color{red} { \begin{array}{l} \hline \color{black} {\update} \\ \hline \end{array}} \\ ~~~ \begin{array}{l} \moveboundaries \end{array} \\ {\bf \color{blue} {endwhile}} \\ \hline \end{array} } \newcommand{\FlaBlkAlgorithm}{ \begin{array}{|l|} \hline \routinename \\ \hline \partitionings \\ ~~~ \begin{array}{l} \partitionsizes \end{array} \\ {\bf \color{blue} {while}~} \guard \\ ~~~ {\bf choose~block~size~} \blocksize \\ ~~~ \begin{array}{l} \repartitionings \end{array} \\ ~~~ ~~~ \repartitionsizes \\ ~~~ \color{red} { \begin{array}{l} \hline \color{black} {\update} \\ \hline \end{array}} \\ ~~~ \begin{array}{l} \moveboundaries \end{array} \\ {\bf \color{blue} {endwhile}} \\ \hline \end{array} } \newcommand{\complexone}{ \begin{array}{|c|}\hline \!\pm\! \\ \hline \end{array}~ } \newcommand{\HQR}{{\rm HQR}} \newcommand{\QR}{{\rm QR}} \newcommand{\st}{{\rm \ s.t. }} \newcommand{\QRQ}{{\rm {\normalsize \bf Q}{\rm \tiny R}}} \newcommand{\QRR}{{\rm {\rm \tiny Q}{\bf \normalsize R}}} \newcommand{\deltaalpha}{\delta\!\alpha} \newcommand{\deltax}{\delta\!x} \newcommand{\deltay}{\delta\!y} \newcommand{\deltaz}{\delta\!z} \newcommand{\deltaw}{\delta\!w} \newcommand{\DeltaA}{\delta\!\!A} \newcommand{\meps}{\epsilon_{\rm mach}} \newcommand{\fl}[1]{{\rm fl( #1 )}} \newcommand{\becomes}{:=} \newcommand{\defrowvector}[2]{ \left(#1_0, #1_1, \ldots, #1_{#2-1}\right) } \newcommand{\tr}[1]{{#1}^T} \newcommand{\LUpiv}[1]{{\rm LU}(#1)} \newcommand{\maxi}{{\rm maxi}} \newcommand{\Chol}[1]{{\rm Chol}( #1 )} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

Subsection 8.3.2 Existence of A-conjugate search directions

The big question left dangling at the end of the last unit was whether there exists a direction \(p^{(k)} \) that is A-orthogonal to all previous search directions and that is not orthogonal to \(r^{(k)} \text{.}\) Let us examine this:

Assume that all prior search directions \(p^{(0)}, \ldots , p^{(k-1)} \) were A-conjugate.
Consider all vectors \(p \in \Rn \) that are A-conjugate to \(p^{(0)}, \ldots , p^{(k-1)} \text{.}\) A vector \(p \) has this property if and only if \(p \perp \Span( A p^{(0)}, \ldots , A p^{(k-1)} ) \text{.}\)
For \(p \perp \Span( A p^{(0)}, \ldots , A p^{(k-1)} ) \) we notice that

\begin{equation*} p^T r^{(k)} = p^T ( b - A x^{(k)} ) = p^T ( b - A P^{(k-1)} a^{(k-1)} ) % = p^T b - p^T A P^{(k-1)} a^{(k-1)} \end{equation*}

where we recall from (8.3.2) that

\begin{equation*} P^{(k-1)} = \left( \begin{array}{c c c} p^{(0)} \amp \cdots \amp p^{(k-1)} \end{array} \right) \mbox{ and } a^{(k-1)} = \left( \begin{array}{c} \alpha_0 \\ \vdots \\ \alpha_{k-1} \end{array} \right). \end{equation*}
If all vectors \(p \) that are A-conjugate to \(p^{(0)}, \ldots, p^{(k-1)} \) are orthogonal to the current residual, \(p^T r^{(k)} = 0 \) for all \(p \) with \(P^{(k-1)\,T} A p = 0 \text{,}\) then

\begin{equation*} 0 = p^T b - p A P^{(k-1)} a^{(k-1)} = p^T b \mbox{ for all } p \perp \Span( Ap^{(0)}, \ldots , A p^{(p-1)} ). \end{equation*}

Let's think about this: \(b \) is orthogonal to all vectors that are orthogonal to \(\Span( Ap^{(0)}, \ldots , A p^{(p-1)} ) \text{.}\) This means that

\begin{equation*} b \in \Span( Ap^{(0)}, \ldots , A p^{(k-1)} ) . \end{equation*}
Hence \(b = A P^{(k-1)} z \) for some \(z \in \R^k \text{.}\) It also means that \(x = P^{(k-1)} z \) solves \(A x = b \text{.}\)
We conclude that our method must already have found the solution since \(x^{(k)}\) minimizes \(f( x ) \) over all vectors in \(\Span( p^{(0)}, \ldots , p^{(k-1)} ) \text{.}\) Thus \(A x^{(k)} = b \) and \(r^{(k)} = 0 \text{.}\)

We conclude that there exist descent methods that leverage A-conjugate search directions as described in Figure 8.3.1.3. The question now is how to find a new A-conjugate search direction at every step.