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!

  • $\begingroup$ 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)$. $\endgroup$ Apr 4 at 17:31
  • $\begingroup$ 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. $\endgroup$ Apr 5 at 5:46
  • 2
    $\begingroup$ 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. $\endgroup$
    – Zhen Lin
    Apr 5 at 6:43
  • 1
    $\begingroup$ If $y=-1$, the function has no minimum. Take $x_1=0$, for example. Then $f(0,x_2)=-x^2_2 -x_2$. $\endgroup$
    – mjw
    Apr 5 at 13:44
  • 1
    $\begingroup$ If $y \le 0$, the function has no minimum. At what values of $y$ does your algorithm/code converge? $\endgroup$
    – 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.


Your Answer

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