Hi there,
First of all, thanks for implementing this algorithm. I look forward to being able to use it correctly.
In my application, I'm currently using a Gauss-Newton (sometimes called Newton-Raphson) algorithm to solve for a single-shooting problem. A good description of the problem is provided at the start of this video: https://www.youtube.com/watch?v=4qFlaqCsnQA . The mathematical specifications of my implementation is available here: https://nyxspace.com/MathSpec/optimization/targeting/ .
I'm trying to switch from Gauss-Newton to Levenberg, using your library. Although in theory Gauss-Newton is not great with a bad initial guess, in my application it works decently well. Levenberg Marquardt is theoretically more resilient to bad initial guesses. However, your LM library algorithm is always taking tiny steps to guess what the correct solution (\vec{x}) could be. So, I suspect I'm incorrectly configuring it.
It converges on the correct solution in 8 evaluations if I provide it with the exact solution of the Gauss Newton algorithm. Otherwise, it'll try incredibly small changes in the solutions and assume that it has minimized the function... but the residuals are just as large as when it started the problem (and nowhere near zero).
I've provided a detailed example below, but my question straightforward:
Is there a way to tell the LM structure to only converge when the residuals are zero and ignore ftol and xtol entirely?
Thanks
Example
Gauss Newton solution
The correct solution that minimizes the problem is the following Vector3<f64>
:
┌ ┐
│ 0.6887498158650465 │
│ -1.9563017351074758 │
│ -0.560405774185829 │
└ ┘
Full log of the solution:
INFO nyx_space::md::opti::raphson_finite_diff > Targeter -- CONVERGED in 12 iterations
INFO nyx_space::md::opti::raphson_finite_diff > SMA: achieved = 8100.00000 desired = 8100.00000 scaled error = 0.00000
INFO nyx_space::md::opti::raphson_finite_diff > Eccentricity: achieved = 0.40000 desired = 0.40000 scaled error = -0.00000
INFO nyx_space::md::opti::raphson_finite_diff > Inclination: achieved = 28.52611 desired = 28.52611 scaled error = 0.00000
FD: Targeter solution correcting ["VelocityX", "VelocityY", "VelocityZ"] (converged in 0.032 seconds, 12 iterations):
Correction @ 2020-01-01T00:00:00 UTC:
VelocityX = 0.689 m/s
VelocityY = -1.956 m/s
VelocityZ = -0.560 m/s
|Δv| = 2148.383 m/s
Achieved @ 2020-01-01T00:59:20.540817260 UTC:
SMA = 8100.000 (wanted 8100.000 ± 1.0e-3)
Eccentricity = 0.400 (wanted 0.400 ± 1.0e-5)
Inclination = 28.526 (wanted 28.526 ± 1.0e-1)
Corrected state:
total mass = 100.000000kg @ [Earth J2000] 2020-01-01T00:00:00 UTC position = [3835.382907, -7756.921938, -4156.921938] km velocity = [5.345645, 1.118432, -2.001254] km/s
total mass = 100.000000kg @ [Earth J2000] 2020-01-01T00:00:00 UTC sma = 8100.000000 km ecc = 0.400000 inc = 28.526111 deg raan = 54.206044 deg aop = 108.326570 deg ta = 136.729436 deg
Achieved state:
total mass = 100.000000kg @ [Earth J2000] 2020-01-01T00:59:20.540817260 UTC position = [7266.068236, 5249.287121, -1534.719097] km velocity = [-4.534582, 3.021172, 2.959670] km/s
total mass = 100.000000kg @ [Earth J2000] 2020-01-01T00:59:20.540817260 UTC sma = 8100.000000 km ecc = 0.400000 inc = 28.526111 deg raan = 54.206044 deg aop = 108.326570 deg ta = 230.979694 deg
Initial params at zero
If the initial params
is zero, then it'll "converge" claiming that the ftol
solution: MinimizationReport { termination: Converged { ftol: true, xtol: false }, number_of_evaluations: 26, objective_function: 5001.106174351325 }
.
First attempted control (the "achieved, desired, error" message shows the actual targets of the problem):
INFO nyx_space::md::opti::minimize_lm > SMA: achieved = 7903.45074 desired = 8100.00000 scaled error = 196.54926
INFO nyx_space::md::opti::minimize_lm > Eccentricity: achieved = 0.21490 desired = 0.40000 scaled error = 0.18510
INFO nyx_space::md::opti::minimize_lm > Inclination: achieved = 30.44637 desired = 28.52611 scaled error = -1.92026
[src/md/opti/minimize_lm.rs:634] converged = false
ctrl =
┌ ┐
│ -0.007939256315236743 │
│ -0.01202376661064193 │
│ 0.025652932101011633 │
└ ┘
And 22nd attempt: this shows that we're back at the initial error in residuals.
INFO nyx_space::md::opti::minimize_lm > SMA: achieved = 8000.00000 desired = 8100.00000 scaled error = 100.00000
INFO nyx_space::md::opti::minimize_lm > Eccentricity: achieved = 0.20000 desired = 0.40000 scaled error = 0.20000
INFO nyx_space::md::opti::minimize_lm > Inclination: achieved = 30.00000 desired = 28.52611 scaled error = -1.47389
[src/md/opti/minimize_lm.rs:634] converged = false
ctrl =
┌ ┐
│ -0.00000000000000003901171501256353 │
│ -0.00000000000000005908364492440542 │
│ 0.0000000000000001260660433615449 │
└ ┘
INFO nyx_space::md::opti::minimize_lm > Correction VelocityX (element 0): -0.00000000000000003901171501256353
INFO nyx_space::md::opti::minimize_lm > Correction VelocityY (element 1): -0.00000000000000005908364492440542
INFO nyx_space::md::opti::minimize_lm > Correction VelocityZ (element 2): 0.0000000000000001260660433615449
Final attempt:
INFO nyx_space::md::opti::minimize_lm > SMA: achieved = 8000.00000 desired = 8100.00000 scaled error = 100.00000
INFO nyx_space::md::opti::minimize_lm > Eccentricity: achieved = 0.20000 desired = 0.40000 scaled error = 0.20000
INFO nyx_space::md::opti::minimize_lm > Inclination: achieved = 30.00000 desired = 28.52611 scaled error = -1.47389
[src/md/opti/minimize_lm.rs:634] converged = false
MinimizationReport { termination: Converged { ftol: true, xtol: false }, number_of_evaluations: 26, objective_function: 5001.106174351325 }
Result correction:
┌ ┐
│ 0 │
│ 0 │
│ 0 │
└ ┘
0 km/s
Initial params set to some random but wrong solution
24 evaluations, no meaningful progress. Initial parameters set to [1.5, 1.5 ,1.5]
.
First attempt:
INFO nyx_space::md::opti::minimize_lm > SMA: achieved = -14499.72096 desired = 8100.00000 scaled error = 22599.72096
INFO nyx_space::md::opti::minimize_lm > Eccentricity: achieved = 1.57039 desired = 0.40000 scaled error = -1.17039
INFO nyx_space::md::opti::minimize_lm > Inclination: achieved = 27.34254 desired = 28.52611 scaled error = 1.18357
[src/md/opti/minimize_lm.rs:634] converged = false
ctrl =
┌ ┐
│ 2.1167838430947192 │
│ 1.9808284453966405 │
│ 4.069698058817354 │
└ ┘
INFO nyx_space::md::opti::minimize_lm > Correction VelocityX (element 0): 2.1167838430947192
INFO nyx_space::md::opti::minimize_lm > Correction VelocityY (element 1): 1.9808284453966405
INFO nyx_space::md::opti::minimize_lm > Correction VelocityZ (element 2): 4.069698058817354
Some attempt in the middle:
INFO nyx_space::md::opti::minimize_lm > SMA: achieved = 16469.24599 desired = 8100.00000 scaled error = -8369.24599
INFO nyx_space::md::opti::minimize_lm > Eccentricity: achieved = 0.44310 desired = 0.40000 scaled error = -0.04310
INFO nyx_space::md::opti::minimize_lm > Inclination: achieved = 25.96224 desired = 28.52611 scaled error = 2.56387
[src/md/opti/minimize_lm.rs:634] converged = false
ctrl =
┌ ┐
│ 1.5000000000005078 │
│ 1.5000000000006835 │
│ 1.500000000052811 │
└ ┘
INFO nyx_space::md::opti::minimize_lm > Correction VelocityX (element 0): 1.5000000000005078
INFO nyx_space::md::opti::minimize_lm > Correction VelocityY (element 1): 1.5000000000006835
INFO nyx_space::md::opti::minimize_lm > Correction VelocityZ (element 2): 1.500000000052811
Last attempt:
INFO nyx_space::md::opti::minimize_lm > SMA: achieved = 16469.24599 desired = 8100.00000 scaled error = -8369.24599
INFO nyx_space::md::opti::minimize_lm > Eccentricity: achieved = 0.44310 desired = 0.40000 scaled error = -0.04310
INFO nyx_space::md::opti::minimize_lm > Inclination: achieved = 25.96224 desired = 28.52611 scaled error = 2.56387
[src/md/opti/minimize_lm.rs:634] converged = false
MinimizationReport { termination: Converged { ftol: false, xtol: true }, number_of_evaluations: 24, objective_function: 35022142.535638005 }
Result correction:
┌ ┐
│ 1.5 │
│ 1.5 │
│ 1.5 │
└ ┘
2.598076211353316 km/s