Message Boards Message Boards

Maximize violating constraints?

Posted 8 years ago

I have the following code, which is a bunch of linear constraints and tries to maximize a nonlinear objective using Maximize.

bounds=Table[b[i], {i, 128}];
boundCond=And@@Map[GreaterEqual[#,0]&, bounds];
upperCond=0.100897647440433502 + 0.0435742177069187164 b[2] + 0.110877290368080139 b[3] + 0.0627215802669525147 b[6] + 0.0303984060883522034 b[11] + 0.195413455367088318 b[12] + 0.00218466715887188911 b[13] + 0.178133592009544373 b[14] + 0.114736616611480713 b[16] + 0.0892148315906524658 b[19] + 0.0430798530578613281 b[20] + 0.127856075763702393 b[22] + 0.235492616891860962 b[24] + 0.100893214344978332 b[26] + 0.0550539642572402954 b[29] + 0.0691445842385292053 b[30] + 0.220859974622726440 b[33] + 0.0824572741985321045 b[34] + 0.111420944333076477 b[35] + 0.119025722146034241 b[36] + 0.0626275166869163513 b[37] + 0.0163705591112375259 b[38] + 0.163605749607086182 b[39] + 0.0159755386412143707 b[40] + 0.222821488976478577 b[41] + 0.0262936670333147049 b[42] + 0.176039412617683411 b[44] + 0.119316443800926209 b[46] + 0.00839051231741905212 b[48] + 0.0780717059969902039 b[49] + 0.0129324616864323616 b[51] + 0.160396441817283630 b[54] + 0.122262813150882721 b[55] + 0.225195974111557007 b[58] + 0.00371941062621772289 b[61] + 0.0782109126448631287 b[66] + 0.163961067795753479 b[67] + 0.0488019287586212158 b[68] + 0.0772711709141731262 b[70] + 0.0967618897557258606 b[72] + 0.0753138065338134766 b[74] + 0.138780370354652405 b[75] + 0.0779474973678588867 b[77] + 0.143815591931343079 b[78] + 0.216688260436058044 b[79] + 0.192488059401512146 b[82] + 0.0594606176018714905 b[83] + 0.0763093978166580200 b[84] + 0.197820603847503662 b[86] + 0.0981343537569046020 b[88] + 0.177558749914169312 b[89] + 0.0137362014502286911 b[91] + 0.0624699629843235016 b[93] + 0.172200247645378113 b[94] + 0.0640604123473167419 b[97] + 0.253324717283248901 b[99] + 0.0138462502509355545 b[102] + 0.00301329372450709343 b[103] + 0.102329082787036896 b[105] + 0.0432044677436351776 b[107] + 0.0967931896448135376 b[109] + 0.00924742128700017929 b[110] + 0.194597169756889343 b[112] + 0.0199854951351881027 b[115] + 0.00540251936763525009 b[117] + 0.0856299698352813721 b[118] + 0.00201270543038845062 b[119] + 0.0697343200445175171 b[120] + 0.0598938837647438049 b[121] + 0.115721419453620911 b[123] + 0.134053930640220642 b[126] + 0.0757555514574050903 b[128] <= 1.4
product:=Apply[Times, bounds];
Maximize[{product, upperCond && boundCond}, bounds];

Basically, bounds is a list of positive variables, and there is a linear constraint upperCond that involves some of the bounds variables, but not all. And I want to maximize the product of all bounds variables.

Now intuitively the maximal value of product should be unbounded because b[1], for example, could just be infinity as it does not appear in the linear constraint. But Mathematica gave me the following results:

Out[119]= {1.0149 10^-53, {b[1] -> 0.631844, b[2] -> 0.366275, b[3] -> 0.536577, b[4] -> 1.06186, b[5] -> 1.14916, b[6] -> 0.307205, b[7] -> 1.02957, b[8] -> 0.590336, b[9] -> 1.02625, b[10] -> 0.781978, 
b[11] -> 0.49093, b[12] -> 0.0258683, b[13] -> 0.585934, b[14] -> 0.0313637, b[15] -> 1.22059, b[16] -> 0.0865507, b[17] -> 0.744385, b[18] -> 0.652376, b[19] -> 0.191569, b[20] -> 0.401325, 
b[21] -> 0.591891, b[22] -> 0.0787587, b[23] -> 1.1079, b[24] -> 0.0211321, b[25] -> 0.673995, b[26] -> 0.270791, b[27] -> 1.09818, b[28] -> 1.15599, b[29] -> 0.847054, b[30] -> 0.286807, 
b[31] -> 1.12585, b[32] -> 1.12369, b[33] -> 0.0213811, b[34] -> 0.214411, b[35] -> 0.156409, b[36] -> 0.103377, b[37] -> 0.748765, b[38] -> 0.910576, b[39] -> 0.0460899, b[40] -> 0.943243, 
b[41] -> 0.0209113, b[42] -> 0.825903, b[43] -> 0.987693, b[44] -> 0.026583, b[45] -> 1.10995, b[46] -> 0.155892, b[47] -> 0.687417, b[48] -> 0.987659, b[49] -> 0.36043, b[50] -> 0.722281, 
b[51] -> 0.551261, b[52] -> 0.733565, b[53] -> 1.09543, b[54] -> 0.0416588, b[55] -> 0.596005, b[56] -> 0.599603, b[57] -> 1.16556, b[58] -> 0.0485591, b[59] -> 1.03535, b[60] -> 1.03462, 
b[61] -> 0.631659, b[62] -> 1.05244, b[63] -> 1.15654, b[64] -> 0.734218, b[65] -> 0.951136, b[66] -> 0.650616, b[67] -> 0.0792143, b[68] -> 0.354095, b[69] -> 0.559035, b[70] -> 0.295494, 
b[71] -> 0.627549, b[72] -> 0.153516, b[73] -> 0.578213, b[74] -> 0.375231, b[75] -> 0.0722742, b[76] -> 0.980545, b[77] -> 0.293393, b[78] -> 0.0657513, b[79] -> 0.028435, b[80] -> 1.06805, 
b[81] -> 1.03576, b[82] -> 0.0495011, b[83] -> 0.797685, b[84] -> 0.262131, b[85] -> 0.704682, b[86] -> 0.0488136, b[87] -> 0.730814, b[88] -> 0.129551, b[89] -> 0.0569268, b[90] -> 0.568371, 
b[91] -> 0.954501, b[92] -> 0.597521, b[93] -> 0.294341, b[94] -> 0.0337064, b[95] -> 1.1071, b[96] -> 0.97234, b[97] -> 0.254995, b[98] -> 0.71303, b[99] -> 0.0327845, b[100] -> 1.10424, 
b[101] -> 1.17713, b[102] -> 0.931491, b[103] -> 0.604491, b[104] -> 0.69352, b[105] -> 0.146641, b[106] -> 0.719575, b[107] -> 0.471206, b[108] -> 1.15883, b[109] -> 0.203697, b[110] -> 0.560459, 
b[111] -> 0.702077, b[112] -> 0.0634536, b[113] -> 1.11802, b[114] -> 1.08117, b[115] -> 0.583974, b[116] -> 0.987578, b[117] -> 0.655513, b[118] -> 0.214568, b[119] -> 0.652192, 
b[120] -> 0.426065, b[121] -> 0.307841, b[122] -> 0.996165, b[123] -> 0.130277, b[124] -> 1.02606, b[125] -> 1.17633, b[126] -> 0.0679813, b[127] -> 1.09422, b[128] -> 0.612329}}

Clearly Mathematica assigned a value to b[1], among other bounds variables that should have been unbounded, which leads to a "maximal" solution which should not exist.

But if I change the optimize objective from the product of all the bounds variables to the sum of all the bounds variables, it returned: NMaximize::ubnd: The problem is unbounded., which makes sense.

And also if I limit the number of bounds variables to say 5, it returned NMaximize::cvdiv: Failed to converge to a solution. The function may be unbounded., which again makes sense.

So seems like Maximize automatically uses NMaximize if constraints involve approximate real numbers, which clearly is the case here. So is the rounding error in NMaximize causing the problem when trying to find a numerical solution? And why is the rounding error not showing up in optimize for the sum of all the variables, and not showing up when the number of variables is small?

POSTED BY: Yuhao Zhu
3 Replies

As you suspected, NMaximize was used since your inputs were not infinite precision. NMaximize is not guaranteed to return the global maximum.

POSTED BY: Frank Kampas
Posted 8 years ago

Thanks for the answer. It did work, but I am still confused. I thought Mathematica would try to maintain as much precision as what the inputs are specified and all the digits in the returned results are correct. In my case, the inputs precisions are about 18, which is higher than the machine precision. So I was confused why I needed to explicitly convert them to a rational number and thereby force Mathematica to work with accurate numbers? Maybe precision of 18 is not enough for Mathematica to generate a correct answer in this case? But why not enough? I am confused by what exactly went wrong in the original calculation...

POSTED BY: Yuhao Zhu
Maximize[{product, 
  Rationalize[upperCond && boundCond, 10^-16]}, bounds]

{\[Infinity], {b[1] -> \[Infinity], 
  b[2] -> 24182746323306567/1622265175591130, 
  b[3] -> 11240398454259712/3837434119983945, b[4] -> 1, b[5] -> 1, 
  b[6] -> 2810099613564928/1085388772474035, b[7] -> 1, b[8] -> 1, 
  b[9] -> 1, b[10] -> 1, b[11] -> 5620199227129856/2104161823026525, 
  b[12] -> 1405049806782464/6763208756637375, 
  b[13] -> 70061753075184913/7540547584280640, 
  b[14] -> 351262451695616/6165157189749615, b[15] -> 1, 
  b[16] -> 43907806461952/992751098838105, b[17] -> 1, b[18] -> 1, 
  b[19] -> 43907806461952/1543851033958665, 
  b[20] -> 72216786944/2452273825275, b[21] -> 1, 
  b[22] -> 5488475807744/1106266364271045, b[23] -> 1, 
  b[24] -> 5488475807744/4075169045280405, b[25] -> 1, 
  b[26] -> 5488475807744/3491887851127845, b[27] -> 1, b[28] -> 1, 
  b[29] -> 2744237903872/1905403353380745, 
  b[30] -> 2744237903872/4786152076555845, b[31] -> 1, b[32] -> 1, 
  b[33] -> 343029737984/3821953077778455, 
  b[34] -> 171514868992/1426912383951135, 
  b[35] -> 171514868992/3856249842011565, 
  b[36] -> 85757434496/4119449219967705, 
  b[37] -> 85757434496/4335044057920515, 
  b[38] -> 58600330913030729/1548638744726250455040, 
  b[39] -> 2679919828/1415588087703945, 
  b[40] -> 19014906843463799/1961535819371616665600, 
  b[41] -> 2679919828/7711793656080585, 
  b[42] -> 5723747979383991/3887211622554444759040, b[43] -> 1, 
  b[44] -> 669979957/6092678186835525, b[45] -> 1, 
  b[46] -> 669979957/8259022041336510, b[47] -> 1, 
  b[48] -> 35357849870916973/61301462539660846694400, 
  b[49] -> 669979957/21616331164200540, b[50] -> 1, 
  b[51] -> 21395058879263203/228692112976668723773440, b[52] -> 1, 
  b[53] -> 1, b[54] -> 669979957/177640929430464480, 
  b[55] -> 16688503279734763/6745719286671368395948032, b[56] -> 1, 
  b[57] -> 1, b[58] -> 669979957/997628667866499840, b[59] -> 1, 
  b[60] -> 1, b[61] -> 60906865551154973/2995827898627755469701120, 
  b[62] -> 1, b[63] -> 1, b[64] -> 1, b[65] -> 1, 
  b[66] -> 35262103/72942734856741120, 
  b[67] -> 669979957/5810841416410629120, 
  b[68] -> 669979957/3459117126323834880, b[69] -> 1, 
  b[70] -> 81362522083409981/1330265603433143478182215680, b[71] -> 1,
   b[72] -> 669979957/27434219797746094080, b[73] -> 1, 
  b[74] -> 669979957/42706390449165434880, 
  b[75] -> 669979957/157389699334467256320, b[76] -> 1, 
  b[77] -> 669979957/176799256886984048640, 
  b[78] -> 669979957/652400414146141224960, 
  b[79] -> 669979957/1965955275789281525760, b[80] -> 1, b[81] -> 1, 
  b[82] -> 669979957/3492786504864772915200, 
  b[83] -> 669979957/2157881827854408744960, 
  b[84] -> 669979957/5538679868602523320320, b[85] -> 1, 
  b[86] -> 669979957/28716384284866793963520, b[87] -> 1, 
  b[88] -> 35262103/1499531850799487385600, 
  b[89] -> 669979957/103100388867611641774080, b[90] -> 1, 
  b[91] -> 41046108341998717/977293585262863836319485788160, 
  b[92] -> 1, 
  b[93] -> 11799142308978959/2555277630539489223086079737856, 
  b[94] -> 669979957/799911578738626154987520, b[95] -> 1, b[96] -> 1,
   b[97] -> 87040378445679343/77319119034335255360270751498240, 
  b[98] -> 1, b[99] -> 669979957/4707017029449634220605440, 
  b[100] -> 1, b[101] -> 1, 
  b[102] -> 14002663508834711/10754227441619805911778748006400, 
  b[103] -> 15579313942043671/5207822573008624307829011906560, 
  b[104] -> 1, 
  b[105] -> 54782132557566611/1243753726928438860167629588398080, 
  b[106] -> 1, 
  b[107] -> 13751392885801517/263634185401748977525114187808768, 
  b[108] -> 1, b[109] -> 669979957/57552339543206488933662720, 
  b[110] -> 87801629772221453/1441151330238367332004877932953600, 
  b[111] -> 1, b[112] -> 669979957/462822743174084111735193600, 
  b[113] -> 1, b[114] -> 1, 
  b[115] -> 38368199793829631/5444182720104323079923322448773120, 
  b[116] -> 1, 
  b[117] -> 7327005996605249/562081423991269200647769726910464, 
  b[118] -> 669979957/1629273337802012801315635200, 
  b[119] -> 55804882421165477/6379531120733365726918518138470400, 
  b[120] -> 669979957/5307313250108026436462837760, 
  b[121] -> 669979957/9116762096543767699453378560, b[122] -> 1, 
  b[123] -> 669979957/35229128061788379923632619520, b[124] -> 1, 
  b[125] -> 1, b[126] -> 669979957/81620206734556441830657884160, 
  b[127] -> 1, b[128] -> 669979957/92249197643274042798967357440}}
POSTED BY: Frank Kampas
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract