# Maximax optimization over a particular matrix

I have the summation of $$N$$ matrices which are weighted by some weighing factors (parameters):

$$M_\alpha=\sum_{i=1}^N \alpha_i M_i$$

$$d_{\alpha}=\arg\max_{rows} M_\alpha$$

The ideal vector $$d$$ is given as $$d=\{1,...,1,2,...,2,3,...,3,...,n,...,n\}$$ where $$n$$ is the number of columns of the matrix $$M_\alpha$$, the number of 1s, 2s etc. in $$d$$ is equal to $$m/n$$, where $$m$$ is the total number of rows of matrix $$M_\alpha$$.

The problem is the following:

$$\max_{\alpha}\sum_{i=1}^m \delta(d(i)-d_{\alpha}(i)))$$

where $$\delta$$ is the kronecker delta function.

Let $$M_1,M_2,M_3$$, ($$N=3$$ different matrices), be all of size $$m\times n=40\times 4$$ as follows:

M1={0.609955572743010, 0.00170731526668555, 0.000650398480689995, 0.387686713509614, 0.352128847651293, 0.00107332837222463, 0.00383334455135158, 0.642964479425131, 0.994077279324872, 1.25013564041093*10^-05, 1.83150969667110*10^-05, 0.00589190422175699, 0.0541834841056487, 0.00304138308773895, 3.86671456986247*10^-05, 0.942736465660914, 0.999697788212839, 9.55623916740011*10^-08, 6.39890357522832*10^-08, 0.000302052235733568, 0.204343973316372, 0.00221136766252747, 0.0439234933355582, 0.749521165685542, 0.976473913048648, 0.000266115805342264, 0.000205472832931933, 0.0230544983130776, 0.658987200165756, 0.000564938489485245, 0.0129346609515954, 0.327513200393164, 0.993898690171526, 1.90808582766092*10^-05, 1.93454968657929*10^-05, 0.00606288347333146, 0.147358674938040, 0.00179172380408377, 0.0195203233074620, 0.831329277950414, 1.46348315513591*10^-14, 0.999999850064741, 4.99352198389998*10^-08, 1.00000024953831*10^-07, 1.64634157803843*10^-14, 0.999999866666615, 3.33333422046731*10^-08, 1.00000026614020*10^-07, 7.15056020814627*10^-07, 0.998855577466965, 1.39432952241941*10^-06, 0.00114231314749163, 3.03631322330502*10^-05, 0.928119733089346, 3.39383500856185*10^-06, 0.0718465099434118, 3.43825818213316*10^-13, 0.999999187866704, 3.33335184201576*10^-08, 7.78799433878354*10^-07, 1.64803181035325*10^-14, 0.999999866633161, 3.33667955721732*10^-08, 1.00000026610674*10^-07, 1.40028993444907*10^-14, 0.999999849999950, 5.00000111369661*10^-08, 1.00000024947352*10^-07, 1.64771550590879*10^-14, 0.999999851056829, 4.89431289795013*10^-08, 1.00000025053039*10^-07, 1.64634157803843*10^-14, 0.999999866666615, 3.33333422046731*10^-08, 1.00000026614020*10^-07, 4.85269640409878*10^-14, 0.999999705357355, 3.33995555767818*10^-08, 2.61243040675023*10^-07, 9.09970886275449*10^-07, 8.80847451325440*10^-07, 0.998898067468975, 0.00110014171268767, 0.000141156216087768, 0.000103304767788300, 0.801897371774159, 0.197858167241965, 0.000354646236379861, 0.000259229276184516, 0.979077950299900, 0.0203081741875359, 0.00524216456740572, 3.82038758928901*10^-05, 0.933811067627086, 0.0609085639296154, 0.0934557418369791, 0.00201358072840893, 0.181879061959566, 0.722651615475046, 1.75842997635072*10^-06, 1.69242866594236*10^-06, 0.998472701114213, 0.00152384802714525, 0.000122526265236807, 0.0114968681963201, 0.718905726923267, 0.269474878615176, 3.16860720581802*10^-05, 1.62720917104366*10^-05, 0.994528527213605, 0.00542351462262581, 0.00192738945529482, 7.70759733587586*10^-06, 0.966949633373471, 0.0311152695738981, 1.62865705458289*10^-11, 1.47240955795276*10^-11, 0.999995561266735, 4.43870225434399*10^-06, 0.000126921039929180, 0.00441070141492391, 0.386257612728005, 0.609204764817142, 0.450902449976079, 0.000147286721066355, 4.15927459758263*10^-07, 0.548949847375394, 0.898623991867438, 2.75637762942201*10^-05, 6.46357512424893*10^-06, 0.101341980781144, 1.13673339728006*10^-05, 0.00534149297450797, 0.0431760667261930, 0.951471072965326, 2.17946210105090*10^-06, 0.0438464450864378, 0.00191444464716315, 0.954236930804298, 0.104133865070695, 0.00233635732000811, 0.136379322163522, 0.757150455445775, 0.298595450162043, 0.309137610495699, 0.0971665472242380, 0.295100392118019, 2.77743921924301*10^-05, 0.000272757074581966, 0.00461735316655282, 0.995082115366673, 0.398257110769054, 0.00149912836234743, 0.0431012466209110, 0.557142514247688, 0.341854869609261, 0.00113627516668155, 0.0284582791264737, 0.628550576097584}

M2={0.997997690879728, 0.000399238009679442, 3.16999992360244*10^-05, 0.00157137111135670, 0.668594080378788, 0.000186789531392926, 0.000283770266878297, 0.330935359822941, 0.999999286473402, 5.93571435328038*10^-08, 5.26142963266451*10^-08, 6.01555157717163*10^-07, 0.330951619597146, 0.000186222910665124, 5.45437398752072*10^-07, 0.668861612054790, 0.999979147680591, 4.96810286608811*10^-08, 3.91877816253543*10^-08, 2.07634505990934*10^-05, 0.211201317605335, 0.00460600427667896, 0.0737934133042877, 0.710399264813699, 0.996332512113470, 6.04225168178655*10^-06, 6.96384038056380*10^-06, 0.00365448179446815, 0.975503800955962, 0.000259520870359853, 0.000308614204583400, 0.0239280639690948, 0.999469335416755, 1.40398540348861*10^-07, 1.95284879485547*10^-07, 0.000530328899825564, 0.409719303511683, 0.00207618094675648, 0.00238898574355966, 0.585815529798001, 1.65476478644032*10^-14, 0.999999866498967, 3.35009895669847*10^-08, 1.00000026597255*10^-07, 1.64634157803843*10^-14, 0.999999866666615, 3.33333422046731*10^-08, 1.00000026614020*10^-07, 1.50675964375090*10^-09, 0.999950882038016, 2.13978503885356*10^-06, 4.69766701860591*10^-05, 0.000146379417384968, 0.983039995056467, 0.000101958004732298, 0.0167116675214155, 1.64634462009615*10^-14, 0.999999866666555, 3.33334023306566*10^-08, 1.00000026614014*10^-07, 1.88003694055318*10^-14, 0.999999859597872, 4.04020837601738*10^-08, 1.00000025907144*10^-07, 1.63686594466428*10^-14, 0.999999850960123, 4.90398355968660*10^-08, 1.00000025043368*10^-07, 1.40000007835072*10^-14, 0.999999849999949, 5.00000124736750*10^-08, 1.00000024947352*10^-07, 1.64634162951276*10^-14, 0.999999866666614, 3.33333432220560*10^-08, 1.00000026614020*10^-07, 1.77197769335975*10^-14, 0.999999863824475, 3.61754807489410*10^-08, 1.00000026329805*10^-07, 6.24802819657261*10^-08, 6.54206918903079*10^-08, 0.999695805624635, 0.000304066474391365, 4.17629238413074*10^-05, 9.17180023574064*10^-05, 0.941419169889299, 0.0584473491845027, 4.45569337408179*10^-09, 3.09511090552630*10^-09, 0.999930293436625, 6.96990125708923*10^-05, 4.88549459064749*10^-07, 2.51982994299512*10^-07, 0.999330790505086, 0.000668468962460487, 0.0481570811375852, 0.00336430981574971, 0.575753152635769, 0.372725456410896, 2.90593552775306*10^-05, 2.97053505468664*10^-05, 0.993415829090078, 0.00652540620409724, 0.000259682967771992, 0.000275271924348368, 0.979056459214500, 0.0204085858933792, 8.05701380692905*10^-10, 4.92679259518032*10^-10, 0.999969857731615, 3.01409700049762*10^-05, 1.55575333355898*10^-08, 9.46236836499764*10^-09, 0.999868311178764, 0.000131663801334523, 2.05397179809771*10^-14, 2.13593440127015*10^-14, 0.999999900000016, 9.99999424647564*10^-08, 2.27734235440637*10^-12, 2.44167103783077*10^-12, 3.48780511272915*10^-12, 0.999999999991793, 0.00486351254210242, 5.31825160156174*10^-08, 3.34626784870301*10^-08, 0.995136400812703, 0.132452981454285, 0.000178075607065361, 6.95495341114794*10^-05, 0.867299393404539, 6.71378008007283*10^-08, 8.08532794505720*10^-08, 1.07436677324882*10^-07, 0.999999744572242, 2.16271866056670*10^-05, 0.00787511307003729, 0.000241425939162816, 0.991861833804194, 0.249096594065283, 0.00454779747299679, 0.0873186983978455, 0.659036910063874, 0.0287821174289005, 0.0916679032413869, 0.00575134721842477, 0.873798632111288, 1.03497559692374*10^-13, 2.18456032445438*10^-13, 1.58943257903254*10^-13, 0.999999999999519, 0.620115420812621, 0.000248272611226680, 0.00542472006012683, 0.374211586516025, 0.488061381134680, 0.000785818969734454, 0.0221437618269132, 0.489009038068673}

M3={0.997251492885447, 0.000408383896912326, 1.03283238017634*10^-05, 0.00232979489383883, 0.590940666212816, 0.000316920438536308, 0.00127859613580867, 0.407463817212840, 0.999994606897510, 5.17609604886250*10^-08, 5.32386422310068*10^-08, 5.28810288749134*10^-06, 0.206609258866747, 0.000566593094416052, 8.13188557954753*10^-06, 0.792816016153258, 0.999991730916819, 5.00331055251115*10^-08, 3.34063790361804*10^-08, 8.18564369645056*10^-06, 0.220033453596154, 0.00425995690893422, 0.0572180610293155, 0.718488528465596, 0.997865142152363, 2.44550442323017*10^-06, 1.75548505281313*10^-06, 0.00213065685816122, 0.964691971718664, 0.000445487839631676, 0.000563898121560682, 0.0342986423201434, 0.999762118280277, 7.87393486477125*10^-08, 7.18181430171090*10^-08, 0.000237731162230879, 0.369787959012358, 0.00272368289121565, 0.00701780020148296, 0.620470557894943, 1.46489682738296*10^-14, 0.999999850067678, 4.99322826722400*10^-08, 1.00000024954124*10^-07, 1.64634157803843*10^-14, 0.999999866666615, 3.33333422046731*10^-08, 1.00000026614020*10^-07, 6.69630111100113*10^-09, 0.999889315088554, 1.19295372550878*10^-06, 0.000109485261419128, 0.000416102520734849, 0.970478941018101, 0.000247713945703149, 0.0288572425154608, 4.81902432564401*10^-14, 0.999999706256558, 3.33333561287706*10^-08, 2.60410037729724*10^-07, 1.67454422722316*10^-14, 0.999999866095536, 3.39044209981976*10^-08, 1.00000026556912*10^-07, 1.40023264652071*10^-14, 0.999999849999950, 5.00000116132114*10^-08, 1.00000024947352*10^-07, 1.40279942773655*10^-14, 0.999999850000073, 4.99998877195922*10^-08, 1.00000024947364*10^-07, 1.64634157803843*10^-14, 0.999999866666615, 3.33333422046731*10^-08, 1.00000026614020*10^-07, 1.66560431194956*10^-14, 0.999999866279651, 3.37203062780474*10^-08, 1.00000026575323*10^-07, 7.98433049830131*10^-08, 8.18464068354558*10^-08, 0.999660418116080, 0.000339420194208729, 0.000213998388400684, 0.000129607463531244, 0.888588228446370, 0.111068165701698, 2.92930149746425*10^-07, 2.19563135378396*10^-07, 0.999429575062814, 0.000569912443900679, 5.14329644265439*10^-05, 2.64102548339620*10^-05, 0.993032285858703, 0.00688987092203679, 0.0966590189676875, 0.00446360471415665, 0.251756697455539, 0.647120678862617, 2.12926382874521*10^-06, 2.00909724035885*10^-06, 0.998349085871284, 0.00164677576764661, 4.99542237747158*10^-06, 0.00122147371105765, 0.951296367516562, 0.0474771633500026, 1.07824887591619*10^-07, 6.42289936887720*10^-08, 0.999657382096022, 0.000342445850096587, 7.29408226726826*10^-06, 4.26840390664120*10^-06, 0.997200424518294, 0.00278801299553237, 2.53861768024925*10^-14, 2.61462672920238*10^-14, 0.999999870408890, 1.29591058324794*10^-07, 6.31901229654999*10^-07, 9.47856216115471*10^-07, 0.00134396620991236, 0.998654454032642, 0.0169547217278078, 1.77160490546745*10^-06, 7.26383215752101*10^-08, 0.983043434028965, 0.324664938404928, 2.55533558747204*10^-06, 3.09694147734326*10^-07, 0.675332196565337, 1.78958596417082*10^-05, 0.000360176756504485, 0.00199051864692794, 0.997631408736926, 0.000103601123113954, 0.0178837457455346, 0.00187601244713895, 0.980136640684213, 0.171927913386833, 0.00543681786555876, 0.118640826567923, 0.703994442179686, 0.283158491426343, 0.296360698888283, 0.0936555028166216, 0.326825306868753, 6.01141409211649*10^-10, 6.55764405707647*10^-10, 9.27182498541578*10^-10, 0.999999997815912, 0.641140498662775, 0.000796336561012832, 0.0139385905700267, 0.344124574206185, 0.477221152495071, 0.00124641271489302, 0.0218114753372417, 0.499720959452794}


and the ideal matrix is given as:

d={1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4}


How can we find the parameters $$\alpha_1,\alpha_2$$ and $$\alpha_3$$ for this example?

One needs the following code to get the $$40\times 4$$ matrices from the lists:

ArrayReshape[M1, {40, 4}]
ArrayReshape[M2, {40, 4}]
ArrayReshape[M3, {40, 4}]
ArrayReshape[M4, {40, 4}]


I was thinking about using NArgMax but I dont know how to get the column indices of a matrix in mathematica. In Matlab it is easy. I can just use $$[a,b]=\max(M')$$, and use the vector b as my $$d_\alpha$$. Another option would be LinearProgramming but the final objective function seems not to be linear.

Added: The main idea is to find a vector of $$40\times 1$$ from each given matrix $$M_i$$. For example if we consider $$M_1$$, then if we find the indices of all rows which have the maximum element:

this will be

d1={1,4,1,4,1,4,1,1,1,4,2,2,2,2,2,2,2,2,2,2,3,3,3,3,4,3,3,3,3,3,4,4,1,4,4,4,2,4,4,4}


if we do the same thing to $$M_2$$ and $$M_3$$, we get similar vectors like $$d_1$$. Lets name them as $$d_2$$ and $$d_3$$. These three vectors are similar to the ideal vector

d={1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4}


but each $$d_i$$ has a few deviations from the ideal one. The deviations do not always occur at the same indexes. Therefore one can take linear combination of these three matrices $$M_1,M,2,M_3$$ with three parameters $$\alpha_1,\alpha_2,\alpha_3$$ such that the resulting matrix will give us a vector $$d$$, let it be $$d_{final}$$, which has the lowest number of deviations from the ideal vector. I am trying to find these three parameters in an optimum way such that the total number of deviations from the ideal vector will be minimized. The best is of course to be able to obtain the ideal $$d$$.

• A much smaller example, with expected outputs would help greatly Commented Oct 19, 2018 at 2:06
• @CarlWoll I can further explain it. This is actually a small size experiment. I have 400 of these matrices and each matrix has 40000 rows. Please see the edit. Commented Oct 19, 2018 at 8:34
• @CarlWoll okay, I added further information about what is actually wanted. Please let me know if there is something missing or not clear. For smaller size matrices, I dont know any example. The ones that I have are from Matlab. If you want you can use another example. The sum of the elements of each row will be 1. Commented Oct 19, 2018 at 9:23

Update: A faster version of maxColumn

ClearAll[maxColumn, objf]
maxColumn[x_] := Position[x, Max[x], 1, 1][[1, 1]]


used with OP's M1, M2, M3 and d:

d={1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4}
αs = {α1, α2, 1 - α1 - α2};
{m1, m2, m3} = Partition[#, 4] & /@ {M1, M2, M3};
mα = Simplify[αs .{m1, m2, m3}];
objf[α1_?NumericQ, α2_?NumericQ] := Total@Unitize[d - maxColumn /@ mα]
nm = NMinimize[{objf[α1, α2], 0 <= α1 <= 1, 0 <= α2 <= 1,  0 <= α1 + α2 <= 1}, {α1, α2}]


{4., {α1 -> 0.0216585, α2 -> 0.747138}}

Column[{Row[{"dM1        ", Row[maxColumn /@ m1]}],
Row[{"dM2        ", Row[maxColumn /@ m2]}],
Row[{"dM3        ", Row[maxColumn /@ m3]}],
Row[{"d          ", Row@d}],
Row[{"solution   ", Row[maxColumn /@ (mα /. nm[[2]])]}]},
Alignment -> Center, Dividers -> {None, {4 -> Gray}}]


ClearAll[maxColumn]
maxColumn = FullSimplify @ PiecewiseExpand @
Piecewise[Table[{i, #[[i]] >= Max[#]}, {i, Length@#}], Undefined] &;


Examples:

SeedRandom[1]
{m1, m2, m3, m4} = RandomInteger[1000, {4, 8, 4}];

Row[Column[{maxColumn /@ #, MatrixForm[# /. Max[#] -> Style[Max[#], Red] & /@ #]},
Alignment -> Center] & /@ {m1, m2, m3, m4}, Spacer[10]]


Minimize the number of deviations from ideal:

αs = {α1, α2, α3, 1 - α1 - α2 - α3};
mα = Simplify[αs .{m1, m2, m3, m4}];
ideal = {1, 1, 2, 2, 3, 3, 4, 4};
nm = NMinimize[{Total@Unitize[ideal- maxColumn /@ mα],
0 <= α1 <= 1, 0 <= α2 <= 1, 0 <= α3 <= 1, 0 <= α1 + α2 + α3 <= 1}, {α1, α2, α3}]


{5., {α1 -> 0.40838672038371643, α2 -> 0.1763031235070461, α3 -> 0.23903363227708174}}

maxColumn /@ (mα /. nm[[2]])


{1, 1, 4, 1, 1, 4, 4, 3}

• First of all thank you very much for the answer. It is just in the right direction. Just the row sums of three matrices need to be $1$. The parameters and the constraints are quite okay. As long as I understood, we were not able to improve on the result of the third matrix right? So linear combinations from other matrices seem not to help us to imporve the result, at least for this example. Commented Oct 19, 2018 at 12:40
• @Seyhmus, the first, second and third matrices have two matches each. So by mixing we get one more match. Could you post copy/pastable versions of M1 thru M4 with commas replaced by . and spaces by ,?
– kglr
Commented Oct 19, 2018 at 12:52