Examples: Conjugate Directions and Conjugate Gradients

Example 1

Claim. \(k=2\)

proof. First, consider some eigenvalues \(\lambda\) and corresponding eigenvector \(x\), by definition, we have

If \(\lambda - 1 = 0\), we must have \(c^Tx = 0\), so that \(\lambda = 1\) is a eigenvalue,
If \(\lambda - 1 \neq 0\), then \(x\) and \(c\) are linearly dependent, hence the eigenvector is \(c\) and we have

Therefore, there are only 2 distinct eigenvalues for \(Q = I + cc^T\).

Then, we can take \(P_1(\lambda) = a + b\lambda\) be a polynomial of degree 1 s.t.

so that \(1+P(1) = 0\) and \(1+(1+cc^T)P(1+cc^T) =0\). Therefore, we have

Therefore, \(k = 2\) guarantees \(x_2\) is the minimizer of \(f\).

Example 2

First, find its characteristic polynomial as

set the equation to \(0\) and solve to get

Then,

Example 3

proof. Note that this statement is equal to say that \(\forall k\in\{0,...,n-1\}. \forall j < k. d_k^TQd_j = 0\), and I'll prove this statement by strong induction.

First, since \(Q\) is symmetric \(d_k^TQd_j = d_j^TQd_k\) for any \(d_j,d_k\). Also note that since \(d_k\)'s are linear combinations of \(p_0, ..., p_{n-1}\), \(d_k\neq 0, \forall k\in\{0,...,n-1\}\), and since \(Q\) is positive definite \(d_K^TQd_k > 0\).

Then, note that for \(k = 0\), the statement is vacuously true.
Fir \(k \in \{1, ..., n-1\}\), assume that \(\forall m < k. \forall j < m. d_m^TQd_j = d_j^TQd_m = 0\), i.e. \(\forall j,m < k, j\neq m. d^T_mQd_j = 0\) Then, for some \(i < k\), we have

Example 4

proof. Since \(x_1\) is a minimizer of \(S_1\), we must have \(\nabla f(x_1)^T = 0\), otherwise we can have some \(\epsilon > 0, f(x_1 - \epsilon d) < f(x_1)\) and \(x_1-\epsilon d \in S_1\) since \(x_1\in S_1, d\in S_1\). Note that the equation is expanded as

and similarly we have \(\nabla f(x_2)^T d = x_2^TQd - b^Td= 0\).

Therefore, we have

Example 5

proof. Let \(i, j \in\{1, ...,n\}, i\neq j\).
Denote \(e_{mk}\) be the \(k\)th entry of \(e_m\), \(Q_{ij}\) be the entry on \(i\)th row and \(j\)th column of \(Q\)

Note that
\(Q_{pp} = \lambda_i, Q_{pq}=0\), for any \(p,q\in\{1,...,n\}, p\neq q\).
\(e_{ii}=1, e_{ip}=0\) for \(p\in\{1,...,n\}-\{i\}\)
\(e_{jj}=1, e_{jq}=0\) for \(q\in\{1,...,n\}-\{j\}\)
Therefore, consider each term of the summation, when \(p\neq q, Q_{pq}=0\), when \(p=q\), at least one of \(e_{ip},e_{jq}\) equals 0. Therefore, all terms in the summation are 0, \(e_i^TQe_j = 0\), hence \(\{d_0,...,d_{n-1}\} = \{e_1,...,e_n\}\) forms a Q-orthogonal set.

proof. I'll prove by induction.
Let \(k\in \{1,...,n-2\}\), assume \(x_{k} = (\frac{b_1}{\lambda_1},...,\frac{b_k}{\lambda_k}, a_{k+1},...,a_n)\). Consider the \((k+1)\)th step of conjugate direction method.

proof. Let

Therefore, the problem is equivalent to minimize \(\phi\) on \(\in\mathbb R^k\).
Note that

for \(i=1,2,..,k\),
Therefore, set the derivative to \(0\) to satisfy the FONC, we have \(k\) equations

Then, note that \(\frac{\partial^{2}\phi}{\partial y_i^2} = \lambda_i, \frac{\partial^{2}\phi}{\partial y_i y_j} = 0\) for \(i,j\in\{1,...,k\}, i\neq j\), we have \(\nabla^2\phi = diag(\lambda_1,...,\lambda_k)\), i.e. the top-left \(k\times k\) submatrix of \(Q\), since \(Q\) is positive definite, \(\nabla^2\phi\) is also positive definite, SOC also holds and

is the minimizer of \(\phi\).

Example 6

proof. Let \(x,y\in\mathbb R^n\).

positive definite
Since \(Q\) is positive definite,

Therefore,

symmetric

triangular inequality

Define

therefore minimizing \(d((x,y), (x^*, y^*))\) on \(L\) is equivalent to

Note that \(\nabla f = Q\begin{bmatrix}x-x^*\\y-y^*\end{bmatrix}, \nabla l = \begin{bmatrix}a\\-1\end{bmatrix}\) using Lagrange multiplier, we have equations

Therefore, since \(Q\) is symmetric, write \(Q = \begin{bmatrix}p&m\\m&q\end{bmatrix}\)we can solve for

Since \(Q\) is positive definite, this solution is the minimum.