# Minimization of a function

Let $$T$$ be a $$n\times m$$ matrix. I'm trying to solve

$$\min \sum_i T_{ij}{\lambda_i}^{\frac{1}{\alpha_i}}$$ $$s.t. \sum_i \lambda_i =1, \lambda_i \geq 0$$ for $$j=1,2,...,m$$. When $$\alpha_i=\alpha$$ for all $$i$$, this can be readily done by hand. The code I've written is

ClearAll["Global*"]
T = {{2, 3}, {3, 2}, {1, 4}};
techniques = Dimensions[T][[1]];
factors = Dimensions[T][[2]];
αVec = ConstantArray[3/6, techniques];
λVec = Array[λ, techniques];
onesVec = ConstantArray[1, techniques];
FactorNeeds = Transpose[T].λVec^(1/αVec);

varVec = λVec;
zerosVec = ConstantArray[0, Length[varVec]];
temp = Table[FactorNeeds /.
Flatten[
Minimize[{FactorNeeds[[j]], onesVec.λVec == 1,
varVec >= zerosVec}, varVec, Reals]][[2 ;; 4]], {j, 1,
factors}];
minmax = Table[temp[[j, 2]]/temp[[j, 1]], {j, 1, factors}]
minKL = Min[minmax]
maxKL = Max[minmax]


and it works fine when $$\alpha=0.5$$ (in the code αVec = ConstantArray[3/6, techniques]). However, if I try to set $$\alpha=\frac{4}{6}$$ or $$\alpha=\frac{5}{6}$$ it just keeps running and does not return an answer. The solution, in both cases is easy to compute; for instance, for $$j=1$$ (just plug the appropriate value for $$\alpha$$):

$$\lambda_1=\frac{1}{1+\left(\frac{2}{3}\right)^{\frac{\alpha}{1-\alpha}}+2^{\frac{\alpha}{1-\alpha}}}$$

$$\lambda_2 =\left(\frac{2}{3}\right)^{\frac{\alpha}{1-\alpha}} \lambda_1$$

$$\lambda_3 =2^{\frac{\alpha}{1-\alpha}} \lambda_1,$$

which, of course, add up to one.

• Your objective function is not a polynomial for $a=4/6$ or $a=5/6$, but it is for $a=3/6$. I suspect that is the reason. – Michael E2 Nov 8 '18 at 11:47
• Can this be done analytically if the function is not an polynomial? It might be very tough to solve it. Have you tried it for a finite series? The infinite might be troublesome. – Gladaed Nov 8 '18 at 12:06
• @Michael E2 Perhaps I should not call it a polynomial, but I don't think this can be the cause. I've edited the question to indicate the exact values of the solution for $\alpha=\frac{4}{6}$ and $\alpha=\frac{5}{6}$ – Patricio Nov 8 '18 at 13:10
• OK, it seems using Solve on the Lagrange multiplier system seems to work quickly. (I thought Minimize was getting stuck because the effective degree of the system for $a=5/6$ is something like $6^3$, but the crit.pt equations form a simple system. Minimize must be checking that the crit.pt. is a minimum, which perhaps turns out to be complicated.) – Michael E2 Nov 8 '18 at 14:31
• Try changing the inequality constraint to Thread[1 + zerosVec >= varVec >= zerosVec]. – Michael E2 Nov 8 '18 at 14:35

Analysis over compact domains is generally easier than over open and unbounded domains. (For instance a continuous function on a closed, bounded domain is guaranteed to have a minimum.) While the boundedness of onesVec.λVec == 1, varVec >= zerosVec can be inferred, apparently it is not; so adding explicitly an upper bound onesVec >= varVec helps Minimize.

temp = Table[
FactorNeeds /.
Flatten[Minimize[{FactorNeeds[[j]], onesVec.λVec == 1,
onesVec >= varVec >= zerosVec}, varVec, Reals]][[2 ;; 4]], {j,
1, factors}];
minmax = Table[temp[[j, 2]]/temp[[j, 1]], {j, 1, factors}]
minKL = Min[minmax]
maxKL = Max[minmax]


The output for αVec = ConstantArray[4/6, techniques] is

{961/294, 732/803}
732/803
961/294


My guess is that without the extra bound, Minimize is having a difficult time proving it has found the global minimum.

• Thank you so much @Michael E2 – Patricio Nov 9 '18 at 12:24
• @Patricio You're welcome. – Michael E2 Nov 9 '18 at 12:24
• Code is slightly neater as minmax = 1/ Apply[Divide, FactorNeeds /. Last /@ (Minimize[{#, onesVec.λVec == 1, onesVec >= varVec >= zerosVec}, varVec, Reals] &) /@ FactorNeeds, 1] – TheDoctor Nov 9 '18 at 15:50

We can use the Weierstrass parametrization of a superellipsoid (similar to what I did in your other question) to ease the task of minimization; an additional advantage of this approach is that the positivity constraints are quite easy to impose:

vec[u_, v_] := {((2 u)/(1 + u^2) (1 - v^2)/(1 + v^2))^2,
((2 u)/(1 + u^2) (2 v)/(1 + v^2))^2, ((1 - u^2)/(1 + u^2))^2}

With[{mat = {{2, 3}, {3, 2}, {1, 4}}, α = 2/3},
ArgMin[{#, 0 < u < 1 && 0 < v < 1}, {u, v}] & /@ ((vec[u, v]^(1/α)).mat)]
{{1/Sqrt[13], 1/2 (-3 + Sqrt[13])},
{Root[13 - 35 #1^2 + 13 #1^4 &, 3], 1/3 (-2 + Sqrt[13])}}

FullSimplify[vec @@@ %]
{{9/49, 4/49, 36/49}, {16/61, 36/61, 9/61}}
`