I have a function, $$f(\mathbf{x})=x_1^2+4x_2^2-4x_1-8x_2,$$

which can also be expressed as $$f(\mathbf{x})=(x_1-2)^2+4(x_2-1)^2-8.$$ I've deduced the minimizer $\mathbf{x^*}$ as $(2,1)$ with $f^*=-8$ by finding the gradient $$\nabla f(\mathbf{x})=(2x_1-4,8x_2-8).$$

I understand that method of steepest descent is defining $$z(t)=\mathbf{x}-t\nabla f(\mathbf{x})$$ $$g(t)=f(z(t))$$ and then setting $g'(t)=0$ and solving for $t$ in terms of $x_1$ and $x_2$. I am asked to start from $\mathbf{x_0}=(0,0)^T$. I can iterate multiple times and I am assuming $f$ will not reach $f^*$. However I am lost in how to prove that this method diverges with a succinct proof.

enter image description here


I tried your example and found the following convergence:

0:  x1=0        x2=0        t=0        f(x)=0
1:  x1=0.588255 x2=1.17651  t=0.147064 f(x)=-5.88235
2:  x1=1.47049  x2=0.735289 t=0.312461 f(x)=-7.43933
3:  x1=1.62623  x2=1.04672  t=0.147064 f(x)=-7.85156
4:  x1=1.85982  x2=0.929922 t=0.312477 f(x)=-7.96071
5:  x1=1.90105  x2=1.01237  t=0.147064 f(x)=-7.9896
6:  x1=1.96289  x2=0.981448 t=0.312477 f(x)=-7.99725
7:  x1=1.9738   x2=1.00327  t=0.147064 f(x)=-7.99927
8:  x1=1.99018  x2=0.995088 t=0.312502 f(x)=-7.99981
9:  x1=1.99307  x2=1.00087  t=0.147064 f(x)=-7.99995
10: x1=1.9974   x2=0.9987   t=0.312436 f(x)=-7.99999
11: x1=1.99816  x2=1.00023  t=0.147079 f(x)=-8

I can't see any reason why the stepest-descent method should not converge in your case. The starting point is near enough to the global minimum.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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