2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Michael E2 Nov 8 '18 at 11:47
  • $\begingroup$ 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. $\endgroup$ – Gladaed Nov 8 '18 at 12:06
  • $\begingroup$ @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}$ $\endgroup$ – Patricio Nov 8 '18 at 13:10
  • 1
    $\begingroup$ 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.) $\endgroup$ – Michael E2 Nov 8 '18 at 14:31
  • 2
    $\begingroup$ Try changing the inequality constraint to Thread[1 + zerosVec >= varVec >= zerosVec]. $\endgroup$ – Michael E2 Nov 8 '18 at 14:35
6
$\begingroup$

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.

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

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}}
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.