Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
What are $F, H$? – copper.hat Apr 30 '12 at 23:39
What are unreal meanings? You may want to take a look at this question and my answer to it. Does that clarify some things? – joriki May 1 '12 at 0:52
This looks neither like Fletcher-Reeves nor Polak-Ribiere. Where did you get this thing you've shown us? – J. M. May 1 '12 at 1:19
@J.M. From It is in russian. – Dracontis May 1 '12 at 9:51
@copper.hat F is a function, and I really don't know what H is it. It explained in my source as $(p_k, H*p_{k-1}) = 0$ and nothing else. – Dracontis May 1 '12 at 9:53
up vote 2 down vote accepted

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}

share|cite|improve this answer

If you do have cube power in the last term $(x_3-3)^3$ then you don't have finite solution since when $x_3$ tends to $-\infty$ the function tends to $-\infty$ either. However in general H indeed is a Hessian matrix of your nonlinear function which is constant for the quadratic form but should be updated for a general nonlinear function on each step.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.