How to calculate $a_k$ with Conjugate gradients method?

Question

I have got function like:

$3(x_1-1)^2+2(x_2-2)^2+(x_3-3)^3$ and starting point is $(9; -7; 11)$

I'm using the following algorithm:

1. $p_0 = -f'(x)$
2. $a_k = - (f'(x_k), p_k) / (p_k, H*p_k)$ and calculate $x_{k+1} = x_k + a_k*p_k$
3. if $f'(x_{k+1}) = 0$ or (less epsilon) I found my minimum, otherwise counting new $p$ and repeat step 1: $p_k+1 = -f'(x_{k+1}) + (f'(x_{k+1}), f'(x_{k+1})) / ((f'(x_k), f'(x_k))) * p_k$;

And I can't understand how to calculate $a_k$. I'm using it like:

$a_k = - (f'(x_k) * p_k) / p_k^2$

And it gave me unreal meanings. So how should I calculate this?

Answer 1

Your function can be written as: $$f(x)=(x-x^*)^T H(x-x^*)$$ where: \begin{align} H&=\begin{pmatrix} 3&0&0\\0&2&0\\0&0&1 \end{pmatrix}& x^*&=\begin{pmatrix} 1\\2\\3 \end{pmatrix} \end{align} Note that it is quite obvious from the function that the minimum is achieved for $x=x*$, where the value of the function is 0.

Also, the $H$ you have in your formulas is precisely the one I have written above. The algorithm you have found is the conjugate gradient algorithm applied to a quadratic function for which we know the Hessian matrix $H$.

The gradient $f'(x)$ thus reads $f'(x)=H(x-x^*)$. I rewrite your algorithm hereunder:

1. Let $k=0$ and $p_0 = -f'(x_0)=-H(x_0-x^*)$
2. At iteration $k$, let: \begin{align} a_k &= - \frac{f'(x_k)^T p_k}{p_k^T Hp_k}\\ x_{k+1} &= x_k + a_k p_k \end{align} if $f'(x_{k+1}) = H(x_k-x^*)=0$ or ($<\varepsilon$) I found my minimum, otherwise let: \begin{align} b_k&=\frac{f'(x_{k+1})^T f'(x_{k+1})}{f'(x_k)^T f'(x_k)}\\ p_{k+1} &= -f'(x_{k+1}) + b_k p_k \end{align} and repeat step 2.

I implemented the algorithm starting from $x_0=\begin{pmatrix} 9\\-7\\11 \end{pmatrix}$ and the iterates it produces are: \begin{align} x_0&=\begin{pmatrix} 9\\-7\\11 \end{pmatrix}& x_1&=\begin{pmatrix} -0.482\\0.1115\\7.8393 \end{pmatrix}& x_2&=\begin{pmatrix} 1.2069\\2.8276\\4.8621 \end{pmatrix}& x_3&=\begin{pmatrix} 1\\2\\3 \end{pmatrix} \end{align}