# Gradient descent algorithm not terminating

Given the minimization problem

$$\underset{x_1, x_2}{\text{minimize}} \quad f (x_1, x_2) := x_1^2 + y x_2^2 - x_1 x_2 - x_1 - x_2$$

My algorithm is working fine for a specific range of $$y$$ and for some specific range of $$y$$, for example $$y = -1$$, my gradient descent algorithm is not terminating irrespective of the initial step size and initial point chosen.

I am not able to decode that why this is happening.

I tried to evaluate the Hessian matrix and for $$y = -1$$, it comes out to be negative. That means, this function is neither convex nor concave. Can this be the reason why it is not terminating?

I read about this on internet and found that gradient descent algorithm can be applied to functions in general irrespective of them being convex or concave. I also tried to print the values of function at each iteration. It seems that values are not converging rather diverging and overflow happened after millions of iterations. As I said, this is only happening when Hessian is negative. Please help!

• Huh? The RHS $X_1^2-yX_2^2-X_1X_2-X_1-X_2$ is a constant function of $(x_1,x_2)$. Apr 4 at 17:31
• In the same way that $f(x)=X$ (for all $x$) or $f(\omega)=\Omega$ (for all $\omega$) is a constant function, $f(x)=x$ (for all $x$) is the identity function. Apr 5 at 5:46
• If your function has no minimum then why should gradient descent terminate? As it turns out for $y = -1$ your function does indeed take arbitrarily large negative values. Apr 5 at 6:43
• If $y=-1$, the function has no minimum. Take $x_1=0$, for example. Then $f(0,x_2)=-x^2_2 -x_2$.
– mjw
Apr 5 at 13:44
• If $y \le 0$, the function has no minimum. At what values of $y$ does your algorithm/code converge?
– mjw
Apr 5 at 15:03

$$\frac{\partial f }{\partial x_1} =2x_1 - x_2 -1$$ $$\frac{\partial f }{\partial x_2} =-x_1 + 2yx_2 -1$$

So optima or saddle points could occur when both of these are zero:

$$2x_1 - x_2 =1$$ $$-x_1 + 2yx_2 =1$$

Computing the Hessian (the matrix of second derivatives):

$$H= \pmatrix{2 &-1\\-1 &2y},$$

we see that the Hessian is zero when $$y=\frac{1}{4}$$ and positive for $$y>\frac{1}{4}$$.

Thus, for $$y>\frac{1}{4}$$, a minimum will exist. For $$y<\frac{1}{4}$$, the function has a saddle point and no minimum. For $$y=\frac{1}{4}$$, higher order tests are required, so says https://mathworld.wolfram.com/SecondDerivativeTest.html.