3
$\begingroup$

I am solving some quadratic optimization problems in Mathematica 12.2 using NMinimize. Mathematica incorrectly gives the error NMinimize::ubnd, saying "The problem is unbounded.".

This should not be the case, however: I am minimizing a sum of squares over a simplex.

Does anyone know why Mathematica might be doing this?

Unfortunately the instances which exhibit this problem are quite large, but see an example here. (This should take ~30s to run.) Many similar problems work fine.

$\endgroup$
5
  • $\begingroup$ As a workaround, I can add additional linear inequalities to the constraints that are implied by the ones I already have, after which NMinimize gives good answers. $\endgroup$ Oct 12, 2021 at 0:57
  • 1
    $\begingroup$ Maybe it's round-off error? I doubt anyone is going to be able to analyze the example (188 variables, 3MB expression) $\endgroup$
    – Michael E2
    Oct 12, 2021 at 0:59
  • $\begingroup$ @MichaelE2, I've updated the gist with a problem with the constraints specified with exact numbers (the quantity to minimize still contains approximate real numbers, but is still a positive integer combination of squares). $\endgroup$ Oct 12, 2021 at 1:20
  • $\begingroup$ Why do you have the following 2 constraints: P[0] >= 0 and P[0] == 0. Then why consider P[0] at all as a variable to be included in the minimization? $\endgroup$
    – JimB
    Oct 12, 2021 at 4:47
  • $\begingroup$ @JimB, just for convenience in the larger problem. I presumed it would have negligible effect here. $\endgroup$ Oct 12, 2021 at 9:10

4 Answers 4

3
$\begingroup$

Using

QuadraticOptimization[error, constraints, vars, Method -> "COIN", 
 Tolerance -> 0.000001]

(possibly tweaking the Tolerance) instead gives good answers.

$\endgroup$
2
$\begingroup$

I wonder if the issue is just that of lack of numerical precision and/or there are multiple solutions that give the same minimum. Consider the pieces of your code as error (the function being minimized), constraints, and vars.

Using NMinimize:

results = Table[10^i NMinimize[{error/10^i, constraints}, vars][[1]], {i, 6, 10}]
[![Unbounded error message][1]][1]
(* {-∞, 5616.11, 5616.45, 5617.94, 5648.9} *)

(The "unbounded" error message is just for when the error is divided by 10^6).

Using QuadraticOptimization:

qo = Table[error /. QuadraticOptimization[error/10^i, constraints, vars, Method -> "COIN",
  Tolerance -> 0.000001], {i, 6, 10}]
(* {5616.45, 5617.94, 5648.9, 5702.51, 5978.63} *)

The resulting values for the parameters can vary a great deal which is why I say there might be multiple solutions meaning there might be some linear combinations of some of the parameters that give the same minimum.

$\endgroup$
0
$\begingroup$

I encountered this issue in Mathematica 13.1, also using NMinimize. The key change that resolved the issue for me was to use Method -> "Xpress" as an option for NMinimize. I recommend trying some of the other solvers when you encounter NMinimize::ubnd.

$\endgroup$
2
  • $\begingroup$ As a side note, perhaps Mathematica should try different Method options when encountering the NMinimize::ubnd error. $\endgroup$
    – ocelto
    Mar 23, 2023 at 16:46
  • $\begingroup$ I did not succeed with Method -> "Xpress" , obtaining an error message "NMinimize::nconv: The problem contains quadratic data, which is not convex'. $\endgroup$
    – user64494
    Mar 26, 2023 at 18:20
0
$\begingroup$

This is a huge optimization problem with 187 variables (P[0]==0). Because of this reason Mathematica 13.2 has problems with it. I succeeded in such a way.

NMinimize[Rationalize[Objective function,Constraints,0]/.P[0]->0, Variables, 
Method -> "NelderMead", AccuracyGoal -> 2, PrecisionGoal -> 2]

{2.07704*10^7, {P[2900] -> -2.09654*10^-7, P[3000] -> 0., P[3100] -> 0., P[3200] -> 0., P[3300] -> 0., P[3350] -> 0., P[3400] -> 0., P[3450] -> 0., P[3500] -> 0., P[3550] -> 0., P[3575] -> 0., P[3600] -> 0., P[3625] -> 0., P[3650] -> 0., P[3675] -> 0., P[3700] -> 0., P[3725] -> 0., P[3750] -> 0., P[3770] -> 0., P[3775] -> 1.79483*10^-8, P[3780] -> 1.65792*10^-9, P[3790] -> 0., P[3800] -> 0., P[3810] -> 0., P[3820] -> 9.18939*10^-8, P[3825] -> 1.98913*10^-8, P[3830] -> 0., P[3840] -> 3.99867*10^-8, P[3850] -> 0., P[3860] -> 0., P[3870] -> 0., P[3875] -> 2.01356*10^-9, P[3880] -> 8.72481*10^-8, P[3890] -> 0., P[3900] -> 0.0000142122, P[3910] -> 0., P[3920] -> 0., P[3925] -> 0., P[3930] -> 6.61508*10^-6, P[3940] -> 0., P[3950] -> 0., P[3960] -> 0., P[3970] -> 0., P[3975] -> 0., P[3980] -> 7.06461*10^-6, P[3990] -> 0., P[3995] -> 0., P[4000] -> 1.15519*10^-8, P[4005] -> 2.21955*10^-9, P[4010] -> 0., P[4015] -> 4.47147*10^-10, P[4020] -> 0.000136336, P[4025] -> 0.0000328433, P[4030] -> 0.00602316, P[4035] -> 6.72181*10^-8, P[4040] -> 5.50496*10^-9, P[4045] -> 0., P[4050] -> 0., P[4055] -> 5.19415*10^-8, P[4060] -> 1.1761*10^-8, P[4065] -> 6.72601*10^-6, P[4070] -> 3.81953*10^-8, P[4075] -> 0.0000147758, P[4080] -> 2.18652*10^-8, P[4085] -> 2.32689*10^-6, P[4090] -> 0., P[4095] -> 2.75499*10^-8, P[4100] -> 0.0000116484, P[4105] -> 1.44813*10^-7, P[4110] -> 0.00412757, P[4115] -> 0.000015634, P[4120] -> 2.24513*10^-6, P[4125] -> 0.0000487553, P[4130] -> 0.0000250081, P[4135] -> 6.02483*10^-9, P[4140] -> 6.5742*10^-6, P[4145] -> 0., P[4150] -> 2.76373*10^-6, P[4155] -> 0.00218362, P[4160] -> 5.62025*10^-7, P[4165] -> 0.0000205955, P[4170] -> 3.39418*10^-6, P[4175] -> 0.000155625, P[4180] -> 0.0000987216, P[4185] -> 0.000159778, P[4190] -> 2.46234*10^-6, P[4195] -> 0.000340439, P[4200] -> 0.000341366, P[4205] -> 0.00029813, P[4210] -> 0.000456094, P[4215] -> 0.000512788, P[4220] -> 0.000641705, P[4225] -> 0.00166537, P[4230] -> 0.0000928972, P[4235] -> 0.00028819, P[4240] -> 0.00056863, P[4245] -> 0.00418505, P[4250] -> 0.00110823, P[4255] -> 0.00136352, P[4260] -> 0.00161262, P[4265] -> 0.0064793, P[4270] -> 0.00209775, P[4275] -> 0.0220397, P[4280] -> 0.00256024, P[4285] -> 0.00277469, P[4290] -> 0.00413998, P[4295] -> 0.00317846, P[4300] -> 0.00334882, P[4305] -> 0.00344915, P[4310] -> 0.00351425, P[4315] -> 0.00351751, P[4320] -> 0.00348308, P[4325] -> 0.00341998, P[4330] -> 0.0175527, P[4335] -> 0.00322862, P[4340] -> 0.00309805, P[4345] -> 0.00293599, P[4350] -> 0.00273779, P[4355] -> 0.0225724, P[4360] -> 0.00214833, P[4365] -> 0.00179855, P[4370] -> 0.00141017, P[4375] -> 0.000989192, P[4380] -> 0.00100061, P[4385] -> 0.000854034, P[4390] -> 0.000614846, P[4395] -> 0.0117653, P[4400] -> 0.000134367, P[4405] -> 0.0000848635, P[4410] -> 0.0000645971, P[4415] -> 0.000161368, P[4420] -> 0.000147725, P[4425] -> 0.000136553, P[4430] -> 0.0000895956, P[4435] -> 0.00161088, P[4440] -> 0.0000203841, P[4445] -> 0.000166314, P[4450] -> 0.0000540109, P[4455] -> 3.37585*10^-6, P[4460] -> 9.92269*10^-7, P[4465] -> 0.00410407, P[4470] -> 0.0000199753, P[4475] -> 3.12725*10^-8, P[4480] -> 6.01605*10^-6, P[4485] -> 0.0000191758, P[4490] -> 0.0000340569, P[4495] -> 0., P[4500] -> 1.52983*10^-8, P[4505] -> 0.000059813, P[4510] -> 5.75173*10^-9, P[4515] -> 0.00168845, P[4520] -> 0., P[4525] -> 4.94183*10^-9, P[4530] -> 0., P[4535] -> 0.0000649872, P[4540] -> 1.50277*10^-9, P[4545] -> 1.20706*10^-7, P[4550] -> 0.00775557, P[4555] -> 0., P[4560] -> 0., P[4565] -> 0., P[4570] -> 0., P[4575] -> 0., P[4580] -> 9.7536*10^-11, P[4585] -> 0., P[4590] -> 0., P[4595] -> 0., P[4600] -> 0., P[4605] -> 0., P[4610] -> 0., P[4615] -> 0., P[4620] -> 0.0196939, P[4625] -> 0.000167266, P[4630] -> 0., P[4635] -> 0., P[4640] -> 0., P[4645] -> 0., P[4650] -> 0.000459051, P[4655] -> 0., P[4660] -> 0., P[4665] -> 0., P[4670] -> 0., P[4680] -> 0., P[4700] -> 0., P[4720] -> 0., P[4800] -> 0., P[5000] -> 0.}}

Its execution on my comp took several hours .

Addition.

..., Method -> "NelderMead", AccuracyGoal -> 3, PrecisionGoal -> 4] // Timing

produces

{16159.4, {2.07869*10^7, {P[2900] -> -1.91594*10^-7, P[3000] -> 0., P[3100] -> 0., P[3200] -> 0., P[3300] -> 0., P[3350] -> 0., P[3400] -> 0., P[3450] -> 0., P[3500] -> 0., P[3550] -> 0., P[3575] -> 0., P[3600] -> 0., P[3625] -> 0., P[3650] -> 0., P[3675] -> 0., P[3700] -> 0., P[3725] -> 0., P[3750] -> 0., P[3770] -> 0., P[3775] -> 0., P[3780] -> 0., P[3790] -> 0., P[3800] -> 0., P[3810] -> 0., P[3820] -> 1.88455*10^-8, P[3825] -> 0., P[3830] -> 0., P[3840] -> 0., P[3850] -> 0., P[3860] -> 0., P[3870] -> 0., P[3875] -> 0., P[3880] -> 1.42029*10^-8, P[3890] -> 0., P[3900] -> 0.0000141148, P[3910] -> 0., P[3920] -> 0., P[3925] -> 0., P[3930] -> 6.54204*10^-6, P[3940] -> 0., P[3950] -> 0., P[3960] -> 0., P[3970] -> 0., P[3975] -> 0., P[3980] -> 6.99157*10^-6, P[3990] -> 0., P[3995] -> 0., P[4000] -> 0., P[4005] -> 0., P[4010] -> 0., P[4015] -> 0., P[4020] -> 0.000136287, P[4025] -> 0.0000327946, P[4030] -> 0.00602311, P[4035] -> 1.853*10^-8, P[4040] -> 0., P[4045] -> 0., P[4050] -> 0., P[4055] -> 3.25431*10^-9, P[4060] -> 0., P[4065] -> 6.67733*10^-6, P[4070] -> 0., P[4075] -> 0.0000147271, P[4080] -> 0., P[4085] -> 2.27821*10^-6, P[4090] -> 0., P[4095] -> 0., P[4100] -> 0.0000115997, P[4105] -> 9.61286*10^-8, P[4110] -> 0.00412752, P[4115] -> 0.0000155853, P[4120] -> 2.19645*10^-6, P[4125] -> 0.0000487066, P[4130] -> 0.0000249594, P[4135] -> 0., P[4140] -> 6.52552*10^-6, P[4145] -> 0., P[4150] -> 2.71504*10^-6, P[4155] -> 0.00218357, P[4160] -> 5.13343*10^-7, P[4165] -> 0.0000205468, P[4170] -> 3.3455*10^-6, P[4175] -> 0.000155576, P[4180] -> 0.0000986729, P[4185] -> 0.00015973, P[4190] -> 2.41366*10^-6, P[4195] -> 0.00034039, P[4200] -> 0.000341317, P[4205] -> 0.000298081, P[4210] -> 0.000456045, P[4215] -> 0.00051274, P[4220] -> 0.000641656, P[4225] -> 0.00166533, P[4230] -> 0.0000928485, P[4235] -> 0.000288141, P[4240] -> 0.000568581, P[4245] -> 0.00418501, P[4250] -> 0.00110818, P[4255] -> 0.00136347, P[4260] -> 0.00161257, P[4265] -> 0.00647925, P[4270] -> 0.00209771, P[4275] -> 0.0220396, P[4280] -> 0.00256019, P[4285] -> 0.00277464, P[4290] -> 0.00413993, P[4295] -> 0.00317841, P[4300] -> 0.00334878, P[4305] -> 0.0034491, P[4310] -> 0.0035142, P[4315] -> 0.00351746, P[4320] -> 0.00348303, P[4325] -> 0.00341993, P[4330] -> 0.0175527, P[4335] -> 0.00322857, P[4340] -> 0.003098, P[4345] -> 0.00293594, P[4350] -> 0.00273774, P[4355] -> 0.0225723, P[4360] -> 0.00214828, P[4365] -> 0.0017985, P[4370] -> 0.00141012, P[4375] -> 0.000989144, P[4380] -> 0.00100057, P[4385] -> 0.000853985, P[4390] -> 0.000614798, P[4395] -> 0.0117652, P[4400] -> 0.000134319, P[4405] -> 0.0000848148, P[4410] -> 0.0000645484, P[4415] -> 0.000161319, P[4420] -> 0.000147676, P[4425] -> 0.000136505, P[4430] -> 0.0000895469, P[4435] -> 0.00161084, P[4440] -> 0.0000203354, P[4445] -> 0.000166265, P[4450] -> 0.0000539623, P[4455] -> 3.32717*10^-6, P[4460] -> 9.43589*10^-7, P[4465] -> 0.00410402, P[4470] -> 0.0000199266, P[4475] -> 0., P[4480] -> 5.96737*10^-6, P[4485] -> 0.0000191271, P[4490] -> 0.0000340082, P[4495] -> 0., P[4500] -> 0., P[4505] -> 0.0000597643, P[4510] -> 0., P[4515] -> 0.00168841, P[4520] -> 0., P[4525] -> 0., P[4530] -> 0., P[4535] -> 0.0000649385, P[4540] -> 0., P[4545] -> 7.20113*10^-8, P[4550] -> 0.00775553, P[4555] -> 0., P[4560] -> 0., P[4565] -> 0., P[4570] -> 0., P[4575] -> 0., P[4580] -> 0., P[4585] -> 0., P[4590] -> 0., P[4595] -> 0., P[4600] -> 0., P[4605] -> 0., P[4610] -> 0., P[4615] -> 0., P[4620] -> 0.0196939, P[4625] -> 0.000167217, P[4630] -> 0., P[4635] -> 0., P[4640] -> 0., P[4645] -> 0., P[4650] -> 0.000459002, P[4655] -> 0., P[4660] -> 0., P[4665] -> 0., P[4670] -> 0., P[4680] -> 0., P[4700] -> 0., P[4720] -> 0., P[4800] -> 0., P[5000] -> 0.}}}

and two warnings.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.