fminunc step size too small

Hello Matlab community,

I am using fminunc to fit a function to a set of datapoints. The optimizer stops due to small step size however I have noticed the steps it is taking are way too small. I don't want to set the minimum step size lower than 1e-3 but if I do so it just stops immediately.

The solution I have found is to provide the function with my own calculated gradient and manually multiplying it by 1e6.

Is there an optimizer option that can rescale the step size to gradient ratio in a similar way?

My optimizer options are:

options = optimoptions('fminunc', ...
    'Display', 'iter', ...
    'Algorithm', 'trust-region', ...
    'HessianFcn','objective', ...
    'SpecifyObjectiveGradient',true, ...
    'StepTolerance', 5e-3, ...,
    "FiniteDifferenceStepSize", 0.1, ...,
    "FunctionTolerance",0.00001, ...
    "OptimalityTolerance",2e-6/factor, ...
    'MaxFunctionEvaluations', 10000, ...
    'MaxIterations', 10000, ...
    'OutputFcn', @saveIterations);
        

Thank you in advance for your help!

Answer 1

[Matt J]

It's not clear to me whether you are are talking about the StepTolerance or the FiniteDifferenceStepSize, both of which you have set to unusally large values. The StepTolerance has no effect on how large a step will be taken by fminunc at each iteration. It only tells fminunc when to stop.

The FiniteDifferenceStepSize affects how the gradient is approximated. If you find that the optimizer stops immediately with large values of FiniteDifferenceStepSize, it probably means that your objective function is piecewise constant. If your objective f(x) is piecwise constant, then stopping immediately is the appropriate thing for fminunc to do, because virtually every point would be a local minimum. A piecewise constant objective can happen if you are doing rounding, nearest-neighbor interpolation, or any other quantization operation in the calcualtion of f(x). These operations are illegal, and violate the theoretical assumptions of fminunc.

[Matilda]

Thank you for your reply!

In the objective function I am also providing a gradient and setting the gradient step size accordingly. Does the FiniteDifferenceStepSize still affect calculations?

I will check for the piecewise constant, my function doesn't have any rounding but there is a random element that could be causing something similar.

[Torsten]

my function doesn't have any rounding but there is a random element that could be causing something similar.

Deterministic solvers (like fminunc) fail if the function to be minimized is influenced by random elements.

[Matt J]

I am also providing a gradient and setting the gradient step size accordingly. Does the FiniteDifferenceStepSize still affect calculations?

No, not in fminunc. In fmincon, it would still be used to calculate derivatives of your constraints, if not provided.

[Matilda]

I see, what would be the best choice of optimizer?

The function has a random threshold but I fix it during the optimization by fixing the random seed meaning that the result is deterministic.

[Matt J]

I see, what would be the best choice of optimizer?

What's wrong with fminunc? If you have no constraints, and the objective is smooth, that is the correct optimizer.

[Torsten]

The function has a random threshold but I fix it during the optimization by fixing the random seed meaning that the result is deterministic.

If you choose some inputs randomly at the start of the computation, but keep them fixed in the course of fminunc's iterations, you can use the optimizer. From what you wrote I got the impression that the objective function is influenced by different values for the random inputs each time your function is called.

[Walter Roberson]

For fmincon() and fminunc() (and most related functions), the objective function has to satisify several properties:

• the function must be consistent. If called with the same parameters, the result must be the same each time
• the function must be continuous within any relevant controlling boundaries.

Functions that incorporate an element of randomness are rarely continuous, with the exception of the case where the random factor is decided before the function is called and thereafter all calls use the same random factor. (Well, you could also implement a persistent variable and set the variable the first time the function was called.)

[Matilda]

The objective function is consistent between runs of fminunc, but it is piecewise constant due to a thresholding operation. The scale at which it is piecewise constant is very small and threfore limiting the step size to a larger number would overcome this issue but then the optimizer stops too early. I suspect this is due to a small gradient.

I am assuming that the gradient magnitude sets the step size of the optimizer and I believe the relationship between the two is not working in my case and I would like the gradient to give a bigger step size.

Alternatively I am looking for a optimizer that is better than fminunc for my particular situation.

Thank you all for your help!

[Matt J]

The scale at which it is piecewise constant is very small and threfore limiting the step size to a larger number would overcome this issue but then the optimizer stops too early. I suspect this is due to a small gradient.

The OptimalityTolerance parameter determines at what gradient magnitude the iterations will stop so you could make it smaller. As I said before, your StepTolerance, and in fact all of your tolerance selections, look unusually large. Remember, there is no connection between the FiniteDifferenceStepSize and any of the tolerance parameters. They are independent things, so making the stepsize large doesn't mean the stopping tolerances should be made large as well. I usually set,

FunctionTolerance=StepTolerance=OptimalityTolerance = 1e-12

....but it is piecewise constant due to a thresholding operation. The scale at which it is piecewise constant is very small and threfore limiting the step size to a larger number would overcome this issue

Perhaps, but I think the better strategy woudl be to find a differentiable alternative for all the discontinuous operations you might be doing in your objective function. The thresholding operation could be approximated by a sigmoid or arctan() function, for example.

Answer 2

[Catalytic]

The solution I have found is to provide the function with my own calculated gradient and manually multiplying it by 1e6.

That might mean your initial point is poorly chosen. In particular, it is chosen in a region where the objective function is almost, but not perfectly flat. This is similar to what is happening in the following example. Notice that the gradient is never exactly zero anywhere except at the global minimum x=0, but for numerical purposes, it may as well be. The optimization cannot move until the initial point is chosen in an area where it has substantial magnitude -

fun=@(x)1-exp(-x.^2/2);
opts=optimoptions('fminunc','Display','none');

x1 = fminunc(fun,3000,opts)

x1 = 3000

x2 = fminunc(fun,30,opts)

x2 = 30

x3 = fminunc(fun,3,opts)

x3 = 3.5861e-09

[Catalytic]

The function has a random threshold but I fix it during the optimization by fixing the random seed meaning that the result is deterministic.

Do you set the random seed inside the objective function? If so, that is one more reason why your initial guess x0 is probably poor. It means you are choosing it without knowing the random threshold that determines your objective function, making x0 essentially an arbitrary guess. An initial guess should not be chosen randomly.

[Matilda]

Thank you for your reply!

The random seed is set inside the function but there is also an averaging process which makes the function smooth and deterministic at the large scale. Meaning that I can choose a x0 which I know is sensible.

What I think the issue might be is the fact that the gradient gets much less steep around the minimum creating a kind of minimum valley. I would really like for it to converge to the minimum point in this valley.

The other issue is that this process makes the function piecewise constant at a very small scale. The size of the constant plateauxs gets smaller with increasing averages. I think that when the optimizer function step gets really small it gets stuck on one of these plateauxs and me artificially increasing the step size by multiplying the gradient by a large factor stops this from happening.

[Sam Chak]

Hi @Matilda

Could you provide the data points or at least a portion of the data that exhibits the piecewise constant behavior? This may enable us to investigate whether your preferred fminunc() optimizer is effective.

[Matt J]

What I think the issue might be is the fact that the gradient gets much less steep around the minimum creating a kind of minimum valley.

If so, you have an ill-conditioned problem (essentially a case of non-unique solutions), and need to regularize it. No algorithm can be guaranteed to reach a particular solution when a problem is ill-conditioned. You can also expect different results for different x0 and on different CPUs.