I want to minimize some multivariable function $\Delta(\alpha, \beta)$. I know that this function has a zero point, $\Delta(5, 5) = 0$.

Starting from some $(\alpha, \beta)$ close to $(5,5)$ (e.g. (4.8, 5.2)), I want to use a gradient descent method to recover the 'correct' values $(5,5)$.

I can plot the surface $\alpha, \beta, \Delta$ and it clearly has a minimum point, but my algorithm fails to converge

My general approach is:

1. Start with some initial $\alpha, \beta$. Compute $\Delta$
2. Calculate $\frac{\partial \Delta}{\partial \alpha}$ and $\frac{\partial \Delta}{\partial \beta}$ by evaluating e.g. $$\frac{\partial \Delta}{\partial \alpha} = \frac{\Delta(\alpha+\epsilon, \beta)-\Delta(\alpha-\epsilon, \beta)}{2 \epsilon}$$

1. Update $\alpha, \beta$ as $$\alpha = \alpha - \gamma \frac{\partial \Delta}{\partial \alpha}$$ and the equivalent for $\beta$

2. Iterate

Is there any reason why this general approach should not work?

• When it fails to converge, how close are you getting? How do you choose $\gamma$? – Tyler Olsen Feb 21 '18 at 14:28

There are a few issues that can cause the problem:

• first, you use gradient computation using finite difference approximations. Is this necessary? Can you compute the partial derivatives of $\Delta$ analytically?

• secondly, the finite difference approximation is only valid for small $\varepsilon$. However, using too small value can cause instabilities if the function $\Delta$ is not very smooth (yours seems smooth enough). When functions are well behaved I use something like $\varepsilon = 10^{-6}$ to test against the analytic gradient.

• let's say that you manage to compute the gradient correctly. Then the choice of the step $\gamma$ is also important. There are different ways of choosing the descent step size, but if you want to keep it simple, then do something like the following:

1. Choose a starting value for $\gamma$ which is not very large, like $\gamma=0.001$ or $\gamma=0.01$.

2. At each iteration, if you manage to decrease the value of the function, increase $\gamma$ using a rule like $\gamma \gets \min (\gamma_{max},1.1\gamma)$ (where $\gamma_{max}$ is an upper limit for the step size, like $\gamma_{max} = 1$ or smaller). If the value of the function does not decrease, then change $\gamma$ by doing something like $\gamma \gets 0.9\gamma$.

3. When $\gamma$ is too small or the decrease in the value of the function is too small, you stop.

For a convex and smooth function, these three should be enough to get you close to the minimum. For more complex examples, using an existing optimized approach like quasi-newton or lbfgs can give very good results.

• Should the updates to $\alpha, \beta$ use the same $\gamma$ ? – user1887919 Feb 22 '18 at 12:40
• Not necessarily. Each step in your algorithm has a step size $\gamma$ and that can change. Don't make it too big, though. – Beni Bogosel Feb 22 '18 at 21:50