1
$\begingroup$

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?

  • 0
    What are $F, H$?2012-04-30
  • 0
    What are unreal meanings? You may want to take a look at [this question](http://math.stackexchange.com/questions/109983/beta-k-for-conjugate-gradient-method) and my answer to it. Does that clarify some things?2012-05-01
  • 0
    This looks neither like Fletcher-Reeves nor Polak-Ribiere. Where did you get this thing you've shown us?2012-05-01
  • 0
    @J.M. From http://knigechka.blogspot.com/2010/04/blog-post_7372.html It is in russian.2012-05-01
  • 0
    @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.2012-05-01
  • 0
    @J.M. Your question didn't help me, because it's for matrix. I just can't figure out how to implement it on equation.2012-05-01
  • 0
    No, the CG variants I mentioned are precisely the ones used for optimization. Look it up yourself if you don't want to take my word for it. (Also, a textbook has better chances of displaying the proper code as opposed to a website from some random pocket of the web.)2012-05-01
  • 0
    @J.M. Here is it http://people.equars.com/marco/poli/phd/node54.html , but still how should I calculate lambda?2012-05-01
  • 0
    My research advisor was Polak.2012-05-01

2 Answers 2

2

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}

0

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.