This project has moved and is read-only. For the latest updates, please go here.

Why does FindMinimum not converge? What can I do about it?

Jan 16, 2013 at 8:34 PM

Ok, so I have been using the FunctionMath.FindMinimum(Func<double, double>, double) method, and it is throwing a "NonconverganceException" on me.  I'm not sure why this is showing up.  Pasted below is a list of the iterations that it is going through.  The first column holds the numbers that FindMinimum tried in my cost function.  The second column holds the costs returned by the cost function for each input number. 

I can see that the FindMinimum method is getting closer and closer, but never getting to "0" as such, which is the actual minimum.  The cost function is a sum-of-squared differences kind of method, so the value will never be negative.  I can kind of understand why this is a problem, but I have no idea how to fix it.  Other minimization algorithms I used in the past had a tolerance value that you could change to prevent this problem.  How can I fix this problem?

 

0 0
0.01 0.000544
-0.01 0.000544
0.00381966 7.94E-05
2.88E-19 4.51E-37
-2.79E-35 4.23E-69
1.10E-19 6.58E-38
1.65E-51 1.48E-101
2.64E-67 3.78E-133
-1.06E-35 6.17E-70
-4.07E-36 9.00E-71
-1.55E-36 1.31E-71
-5.93E-37 1.92E-72
-2.27E-37 2.80E-73
-8.66E-38 4.08E-74
-3.31E-38 5.95E-75
-1.26E-38 8.68E-76
-4.82E-39 1.27E-76
-1.84E-39 1.85E-77
-7.04E-40 2.70E-78
-2.69E-40 3.93E-79
-1.03E-40 5.74E-80
-3.92E-41 8.38E-81
-1.50E-41 1.22E-81
-5.72E-42 1.78E-82
-2.19E-42 2.60E-83
-8.35E-43 3.79E-84
-3.19E-43 5.54E-85
-1.22E-43 8.08E-86
-4.65E-44 1.18E-86
-1.78E-44 1.72E-87
-6.79E-45 2.51E-88
-2.59E-45 3.66E-89
-9.90E-46 5.34E-90
-3.78E-46 7.79E-91
-1.44E-46 1.14E-91
-5.52E-47 1.66E-92
-2.11E-47 2.42E-93
-8.05E-48 3.53E-94
-3.08E-48 5.15E-95
-1.17E-48 7.51E-96
-4.49E-49 1.10E-96
-1.71E-49 1.60E-97
-6.55E-50 2.33E-98
-2.50E-50 3.40E-99
-9.55E-51 4.97E-100
-3.65E-51 7.25E-101
-1.39E-51 1.06E-101
5.01E-83 1.37E-164
-4.48E-99 1.09E-196
1.91E-83 2.00E-165
7.31E-84 2.91E-166
2.79E-84 4.25E-167
1.07E-84 6.20E-168
4.08E-85 9.04E-169
1.56E-85 1.32E-169
5.95E-86 1.92E-170
2.27E-86 2.81E-171
8.68E-87 4.10E-172
3.31E-87 5.98E-173
1.27E-87 8.72E-174
4.83E-88 1.27E-174
1.85E-88 1.86E-175
7.05E-89 2.71E-176
2.69E-89 3.95E-177
1.03E-89 5.77E-178
3.93E-90 8.41E-179
1.50E-90 1.23E-179
5.73E-91 1.79E-180
2.19E-91 2.61E-181
8.37E-92 3.81E-182
3.20E-92 5.56E-183
1.22E-92 8.11E-184
4.66E-93 1.18E-184
1.78E-93 1.73E-185
6.80E-94 2.52E-186
2.60E-94 3.68E-187
9.93E-95 5.36E-188
3.79E-95 7.83E-189
1.45E-95 1.14E-189
5.53E-96 1.67E-190
2.11E-96 2.43E-191
8.07E-97 3.55E-192
3.08E-97 5.17E-193
1.18E-97 7.55E-194
4.50E-98 1.10E-194
1.72E-98 1.61E-195
6.56E-99 2.34E-196
2.51E-99 3.42E-197
-1.71E-99 1.59E-197
9.57E-100 4.99E-198
-6.53E-100 2.32E-198
3.66E-100 7.28E-199
-2.50E-100 3.39E-199
1.40E-100 1.06E-199
-9.53E-101 4.95E-200
5.33E-101 1.55E-200
-3.64E-101 7.22E-201
2.04E-101 2.26E-201
-1.39E-101 1.05E-201
7.78E-102 3.30E-202
-5.31E-102 1.54E-202
2.97E-102 4.81E-203
-2.03E-102 2.24E-203
1.14E-102 7.02E-204
-7.75E-103 3.27E-204
4.34E-103 1.02E-204
-2.96E-103 4.77E-205
1.66E-103 1.49E-205
-1.13E-103 6.96E-206
6.33E-104 2.18E-206
-4.32E-104 1.02E-206
2.42E-104 3.18E-207
-1.65E-104 1.48E-207
9.23E-105 4.64E-208
-6.30E-105 2.16E-208
3.53E-105 6.77E-209
-2.41E-105 3.15E-209
1.35E-105 9.88E-210
-9.19E-106 4.60E-210
5.15E-106 1.44E-210
-3.51E-106 6.72E-211
1.97E-106 2.10E-211
-1.34E-106 9.80E-212
7.51E-107 3.07E-212
-5.12E-107 1.43E-212
2.87E-107 4.48E-213
-1.96E-107 2.09E-213
1.10E-107 6.53E-214
-7.48E-108 3.04E-214
4.18E-108 9.53E-215
-2.86E-108 4.44E-215
1.60E-108 1.39E-215
-1.09E-108 6.48E-216
6.10E-109 2.03E-216
-4.17E-109 9.45E-217
2.33E-109 2.96E-217
-1.59E-109 1.38E-217
8.90E-110 4.32E-218
-6.08E-110 2.01E-218
3.40E-110 6.30E-219
-2.32E-110 2.93E-219
1.30E-110 9.19E-220
-8.87E-111 4.28E-220
4.96E-111 1.34E-220
-3.39E-111 6.25E-221
1.90E-111 1.96E-221
-1.29E-111 9.11E-222
7.24E-112 2.85E-222
-4.94E-112 1.33E-222
2.77E-112 4.16E-223
-1.89E-112 1.94E-223
1.06E-112 6.08E-224
-7.21E-113 2.83E-224
4.03E-113 8.86E-225
-2.75E-113 4.13E-225
1.54E-113 1.29E-225
-1.05E-113 6.03E-226
5.89E-114 1.89E-226
-4.02E-114 8.79E-227
2.25E-114 2.75E-227
-1.53E-114 1.28E-227
8.59E-115 4.02E-228
-5.86E-115 1.87E-228
3.28E-115 5.86E-229
-2.24E-115 2.73E-229
1.25E-115 8.55E-230
-8.55E-116 3.98E-230
4.79E-116 1.25E-230
-3.27E-116 5.81E-231
1.83E-116 1.82E-231
-1.25E-116 8.48E-232
6.98E-117 2.65E-232
-4.77E-117 1.24E-232
2.67E-117 3.87E-233
-1.82E-117 1.80E-233
1.02E-117 5.65E-234
-6.95E-118 2.63E-234
3.89E-118 8.25E-235
-2.66E-118 3.84E-235
1.49E-118 1.20E-235
-1.01E-118 5.60E-236
5.68E-119 1.76E-236
-3.88E-119 8.18E-237
2.17E-119 2.56E-237
-1.48E-119 1.19E-237
8.28E-120 3.74E-238
-5.65E-120 1.74E-238
3.16E-120 5.45E-239
-2.16E-120 2.54E-239
1.21E-120 7.95E-240
-8.25E-121 3.71E-240
4.62E-121 1.16E-240
-3.15E-121 5.41E-241
1.76E-121 1.69E-241
-1.20E-121 7.89E-242
6.74E-122 2.47E-242
-4.60E-122 1.15E-242
2.57E-122 3.60E-243
-1.76E-122 1.68E-243
9.83E-123 5.26E-244
-6.71E-123 2.45E-244
3.75E-123 7.67E-245
-2.56E-123 3.57E-245
1.43E-123 1.12E-245
-9.79E-124 5.21E-246
5.48E-124 1.63E-246
-3.74E-124 7.61E-247
2.09E-124 2.38E-247
-1.43E-124 1.11E-247
7.99E-125 3.48E-248
-5.45E-125 1.62E-248
3.05E-125 5.07E-249
-2.08E-125 2.36E-249
1.17E-125 7.40E-250
-7.96E-126 3.45E-250
4.45E-126 1.08E-250
-3.04E-126 5.03E-251
1.70E-126 1.57E-251
-1.16E-126 7.34E-252
6.50E-127 2.30E-252
-4.43E-127 1.07E-252
2.48E-127 3.35E-253
-1.69E-127 1.56E-253
9.48E-128 4.89E-254
-6.47E-128 2.28E-254
3.62E-128 7.13E-255
-2.47E-128 3.32E-255
1.38E-128 1.04E-255
-9.44E-129 4.85E-256
5.28E-129 1.52E-256
-3.61E-129 7.08E-257
2.02E-129 2.22E-257
-1.38E-129 1.03E-257
7.71E-130 3.23E-258
-5.26E-130 1.51E-258
2.94E-130 4.72E-259
-2.01E-130 2.20E-259
1.12E-130 6.88E-260
-7.67E-131 3.21E-260
4.29E-131 1.00E-260
-2.93E-131 4.68E-261
1.64E-131 1.46E-261
-1.12E-131 6.83E-262
6.27E-132 2.14E-262
-4.28E-132 9.96E-263
2.39E-132 3.12E-263
-1.63E-132 1.45E-263
9.14E-133 4.55E-264
-6.24E-133 2.12E-264
3.49E-133 6.64E-265
-2.38E-133 3.09E-265
1.33E-133 9.68E-266
Feb 11, 2013 at 11:28 AM
I have filed a bug on FindMinimum's convergence criterion related to this issue (http://metanumerics.codeplex.com/workitem/7306). It looks like the minimization algorithm keeps moving the minimum a tiny bit and believing that it still has some minimization to do.

For the moment your best bet is probably to minimize g(x) = f(x) + 1 so the minimum value is 1 rather than zero. It will then see changes in f(x) less than ~10^{-16} as negligible and conclude that it is has converged.
Feb 11, 2013 at 4:51 PM
Thanks for your response. I will take that into consideration for now and look forward to the bug fix.