I have the following code which is working well but for matrices $M_i$ of size $40000\times 4$ the optimization problem takes extremely long.
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}
ClearAll[maxColumn, objf]
maxColumn[x_] := Position[x, Max[x], 1, 1][[1, 1]]
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, α3};
{m1, m2, m3} = Partition[#, 4] & /@ {M1, M2, M3};
mα = Simplify[αs .{m1, m2, m3}];
objf[α1_?NumericQ, α2_?NumericQ, α3_?NumericQ] := Total@Unitize[d - maxColumn /@ mα]
nm = NMinimize[{objf[α1, α2, α3],
-1 <= α1 <= 1, -1 <= α2 <= 1, -1 <= α3 <= 1}, {α1, α2, α3}]
{2., {[Alpha]1 -> 0.166537, [Alpha]2 -> 0.998681, [Alpha]3 -> -0.846158}}
Is there any way to speed up the optimization process via either other type of optimization method or reformulation of the problem? You can reach the original problem from here.
ADDED: I am looking for matrices $M_i$ of size $40000\times 4$ and I have some hundreds of them. The algorithm may also be approximate and/or iterative. It will also be great to have a step monitor to see how the mismatch rate decreases.
ADDED (31.10.2018): I did some experiments about the codes given above. I just created a random matrix of size $40000×4$ and total@unitize[d-maxcolumn@malpha] takes only $0.299$ seconds! In my matrix every element is obtained by the multiplication of $500$ parameters by $500$ real numbers. So for every element of my matrix there are $500$ multiplications and in total $500∗40000∗4=80.000.000$ multiplications. I created 2 random vectors each having $80.000.000$ elements. The inner product of these two vectors a.b takes only $0.048$ seconds!
I just assume that an optimization method evaluates about $1000$ different values of parameters before it iterates its algorithm one step forward. This is what I can see with StepMonitor->. So in total one needs about 305 seconds and roughly about 5 minutes just for one iteration. What I in reality observe is something completely different. Just for one iteration it takes from 15 minutes to 30 minutes and in some cases much more. It seems to me that everything is great for an optimization method.
I do not understand why this program takes too much time. Do you have any idea?
LinearProgramming. That would provide a substantial speed-up. (Here is an example.) $\endgroup$