Skip to main content

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$.



Answer



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}}]

enter image description here


Original answer:


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]]

enter image description here


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}



Comments

Post a Comment

Popular posts from this blog

mathematical optimization - Minimizing using indices, error: Part::pkspec1: The expression cannot be used as a part specification

I want to use Minimize where the variables to minimize are indices pointing into an array. Here a MWE that hopefully shows what my problem is. vars = u@# & /@ Range[3]; cons = Flatten@ { Table[(u[j] != #) & /@ vars[[j + 1 ;; -1]], {j, 1, 3 - 1}], 1 vec1 = {1, 2, 3}; vec2 = {1, 2, 3}; Minimize[{Total@((vec1[[#]] - vec2[[u[#]]])^2 & /@ Range[1, 3]), cons}, vars, Integers] The error I get: Part::pkspec1: The expression u[1] cannot be used as a part specification. >> Answer Ok, it seems that one can get around Mathematica trying to evaluate vec2[[u[1]]] too early by using the function Indexed[vec2,u[1]] . The working MWE would then look like the following: vars = u@# & /@ Range[3]; cons = Flatten@{ Table[(u[j] != #) & /@ vars[[j + 1 ;; -1]], {j, 1, 3 - 1}], 1 vec1 = {1, 2, 3}; vec2 = {1, 2, 3}; NMinimize[ {Total@((vec1[[#]] - Indexed[vec2, u[#]])^2 & /@ R...
Post a Comment
Read more

functions - Get leading series expansion term?

Given a function f[x] , I would like to have a function leadingSeries that returns just the leading term in the series around x=0 . For example: leadingSeries[(1/x + 2)/(4 + 1/x^2 + x)] x and leadingSeries[(1/x + 2 + (1 - 1/x^3)/4)/(4 + x)] -(1/(16 x^3)) Is there such a function in Mathematica? Or maybe one can implement it efficiently? EDIT I finally went with the following implementation, based on Carl Woll 's answer: lds[ex_,x_]:=( (ex/.x->(x+O[x]^2))/.SeriesData[U_,Z_,L_List,Mi_,Ma_,De_]:>SeriesData[U,Z,{L[[1]]},Mi,Mi+1,De]//Quiet//Normal) The advantage is, that this one also properly works with functions whose leading term is a constant: lds[Exp[x],x] 1 Answer Update 1 Updated to eliminate SeriesData and to not return additional terms Perhaps you could use: leadingSeries[expr_, x_] := Normal[expr /. x->(x+O[x]^2) /. a_List :> Take[a, 1]] Then for your examples: leadingSeries[(1/x + 2)/(4 + 1/x^2 + x), x] leadingSeries[Exp[x], x] leadingSeries[(1/x + 2 + (1 - 1/x...
Post a Comment
Read more

What is and isn't a valid variable specification for Manipulate?

I have an expression whose terms have arguments (representing subscripts), like this: myExpr = A[0] + V[1,T] I would like to put it inside a Manipulate to see its value as I move around the parameters. (The goal is eventually to plot it wrt one of the variables inside.) However, Mathematica complains when I set V[1,T] as a manipulated variable: Manipulate[Evaluate[myExpr], {A[0], 0, 1}, {V[1, T], 0, 1}] (*Manipulate::vsform: Manipulate argument {V[1,T],0,1} does not have the correct form for a variable specification. >> *) As a workaround, if I get rid of the symbol T inside the argument, it works fine: Manipulate[ Evaluate[myExpr /. T -> 15], {A[0], 0, 1}, {V[1, 15], 0, 1}] Why this behavior? Can anyone point me to the documentation that says what counts as a valid variable? And is there a way to get Manpiulate to accept an expression with a symbolic argument as a variable? Investigations I've done so far: I tried using variableQ from this answer , but it says V[1...
Post a Comment
Read more