RTR

[Hamide Zebardast]

Hi,

I am using 'trustregions' solver to solve my problem, unfortunately it doesn't converge and continue until maximum iteration. Its warning is : "exceeded trust region" !

I will be so grateful if you help me

[Nicolas Boumal]

Hello,

Did you use the tools checkgradient and checkhessian to make sure your cost function and derivatives work out?

Best,

Nicolas

[Nicolas Boumal]

Hello again,

I received a reply from you that appears not to have been posted to the forum.

In your reply, you showed the text output of the checkgradient and checkhessian tools.

In there, we can read the following message:

# The cost function appears to return complex values.
# Please ensure real outputs.

It appears that your cost function sometimes returns complex numbers, but for optimization we normally only consider real-valued cost functions.

It is possible that some numerical issue lead to tiny imaginary parts in the value of $f$; if that is the case, you might be able to resolve the issue simply by returning the real part of the value of f only.

[Hamide Zebardast]

Hi again

Thanks a lot,

I changed cost function to real value, still I see "exceeded trust region", and bellow warnings :

1 . checkgradient :

The slope should be 2. It appears to be: 2.00021.

If it is far from 2, then directional derivatives might be erroneous.

The residual should be 0, or very close. Residual: 2.58133e-12.

If it is far from 0, then the gradient is not in the tangent space.

In certain cases (e.g., hyperbolicfactory), the tangency test is inconclusive.

2 . Checkhessian : 

The slope should be 3. It appears to be: 2.99952.

If it is far from 3, then directional derivatives,

the gradient or the Hessian might be erroneous.

Tangency residual should be zero, or very close; residual: 1.64526e-12.

If it is far from 0, then the Hessian is not in the tangent space.

||a*H[d1] + b*H[d2] - H[a*d1+b*d2]|| should be zero, or very close.

Value: 1.02642e-11 (norm of H[a*d1+b*d2]: 8318.21)

If it is far from 0, then the Hessian is not linear.

<d1, H[d2]> - <H[d1], d2> should be zero, or very close.

Value: 554.927 - 554.927 = 6.82121e-13.

If it is far from 0, then the Hessian is not symmetric.

[Nicolas Boumal]

Hello,

Based on the text output, all tests in checkgradient and checkhessian appear to have passed.

"Exceeded trust region" is not necessarily a warning of something bad. In solving the trust-region subproblem, the algorithm (tCG) must minimize a quadratic function inside a ball. If it is ever about to leave the ball, it terminates and outputs that message to inform the user, but there is nothing abnormal about this event.

What can happen as a result of "exceeded trust region" is that the trust-region radius would need to be increased. Whether or not that's effectively possible is controlled by two parameters (the "options" input to trustregions): options.Delta_bar and options.Delta0. It may be necessary to tweak those parameters. You always need Delta_bar (the maximum allowed radius) to be larger that Delta0 (the initial radius). Notice that trustregions also outputs "options" as a fourth output, so you can get access to the current value of the options there; or you can set options.verbosity = 3 so that option values are displayed at the beginning of optimization.

Best,

Nicolas

[Hamide Zebardast]

Thanks  a lot for your description of algorithm. Actually RTR warns "exceeded trust region" from k=8 and goes until k=1000 (maximum iteration), I think it doesn't converge however gradient and hessian are correct, so what parameter should I check? 

Best,

[Nicolas Boumal]

Can you copy-paste the output of RTR for the first 50 iterations or so?

[Hamide Zebardast]

I have attached the first 50 iterations,

Best

[Nicolas Boumal]

It looks like the method is working well, but that the stopping criterion should be changed.

Specifically, after 10 iterations the value of $f$ has been decreased by ~15 orders of magnitude and the norm of the gradient has been decreased by ~10 orders of magnitude. It's hard to do more than that, because we're getting into machine precision issues at that point (~16 orders of magnitude).

My recommendation is to do either of the following:

 - Either scale the cost function down (by a scalar); for example, if the cost function is a sum of M terms, then divide the sum by M.

 - Or change options.tolgradnorm to be roughly 8 orders of magnitude below the norm of the gradient at a typical starting point. Here, I see that the gradient norm at x0 was ~1e4, so I'd set options.tolgradnorm = 1e-4.

Doing so, the algorithm will happily stop after 10 iterations, and it looks like the solution it has found will be quite good.

Best,

Nicolas

[Hamide Zebardast]

I have normalized the cost function to the size of problem (n) and it works properly , 

Thanks a lot 

[Nicolas Boumal]

Great to read!