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$
11
  • 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
    Commented Nov 8, 2018 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
    Commented Nov 8, 2018 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
    Commented Nov 8, 2018 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
    Commented Nov 8, 2018 at 14:31
  • 2
    $\begingroup$ Try changing the inequality constraint to Thread[1 + zerosVec >= varVec >= zerosVec]. $\endgroup$
    – Michael E2
    Commented Nov 8, 2018 at 14:35

2 Answers 2

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$
3
  • $\begingroup$ Thank you so much @Michael E2 $\endgroup$
    – Patricio
    Commented Nov 9, 2018 at 12:24
  • $\begingroup$ @Patricio You're welcome. $\endgroup$
    – Michael E2
    Commented Nov 9, 2018 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
    Commented Nov 9, 2018 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 and acknowledge you have read our privacy policy.

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