Let me start with an example. Let
$$\mathbf{A}=\begin{bmatrix}3&1\\2&3\\1&5\end{bmatrix},$$
and let $Q=\{\mathbf{q}\vert\mathbf{q}\in\Bbb R^3_+ \land \sum_i^n q_i=1\}$ and $\alpha=\bigl(\frac{1}{2},\frac{1}{2},\frac{1}{2}\bigr)$. Abusing notation, let $\mathbf{q}^{\frac{1}{\alpha}}=\bigl(q_1^{\frac{1}{\alpha_1}},q_2^{\frac{1}{\alpha_2}},q_3^{\frac{1}{\alpha_3}}\bigr)=\bigl(q_1^2,q_2^2,q_3^2\bigr).$ Consider the set $K=\{\mathbf{k}\in\Bbb R^2_+\vert \mathbf{k}=\mathbf{A}^{\top}\mathbf{q}^{\frac{1}{\alpha}}\land \mathbf{q}\in Q\}.$ There exist two members of $K$ such that the $j$-th component of $\underline{\mathbf{k}}^j$ is lower than the $j$-th component of any other $\mathbf{k}\in K$. These can be easily identified using calculus. In this case, $\underline{\mathbf{k}}^1=\bigl(\frac{6}{11},\frac{211}{121}\bigr),$ that corresponds to $\mathbf{q}_{\underline{\mathbf{k}}^1}=\bigl(\frac{2}{11},\frac{3}{11},\frac{6}{11}\bigr)$ is the $\mathbf{k}$ with the lowest first component and $\underline{\mathbf{k}}^2=\bigl(\frac{734}{529},\frac{15}{23}\bigr),$ corresponding to $\mathbf{q}_{\underline{\mathbf{k}}^2}=\bigl(\frac{15}{23},\frac{5}{23},\frac{3}{23}\bigr)$, the one with the lowest second component. $K$, (blue) $\underline{\mathbf{k}}^1$ and $\underline{\mathbf{k}}^2$ (red) are shown in the following figure.
I need to pinpoint those $\mathbf{k}$ that are on the convex part of the frontier of $K$ between $\underline{\mathbf{k}}^1$ and $\underline{\mathbf{k}}^2$, i.e., the yellow dots. In order to identify them, I
- Choose $\beta\in[0,1]$ and compute $\hat{\mathbf{k}} =\beta\underline{\mathbf{k}}_1+(1-\beta)\underline{\mathbf{k}}_2.$ This yields a point in the straight segment that connects $\underline{\mathbf{k}}_1$ and $\underline{\mathbf{k}}_2,$ i.e., the green dots.
- Determine the proportion $r=\frac{\hat k_1}{\hat k_2}.$ By construction $\frac{\underline{k}_2^2}{\underline{k}_1^2}\leq r \leq\frac{\underline{k}_2^1}{\underline{k}_1^1}.$
- Minimize $k_1$ subject to $\mathbf{k}\in K$ and $k_2=r k_1.$ Let $k^*_1$ be the solution to this problem and $\mathbf{k}^*=(k^*_1,rk^*_1).$
For every $\beta \in[0,1]$ this procedure should yield a $\mathbf{k}^*$ that is on the frontier. These $\mathbf{k}^*$ have an additional property: the solution to the problem $\max\sum_{i=1}^n q_i, s.t.\mathbf{A}^{\top}\mathbf{q}^{\alpha} \leq \mathbf{k}^* \land \mathbf{q} \geq 0,$ denoted $\mathbf{q}^*$, is such that $\sum_i q_i^*=1.$
However, when I solve this maximization problem, only a handful of the $\mathbf{k}^*$ are actually such that $\sum q^*_i=1$ (purple dots). This is very unfortunate, because what I'm really interested in are the KKT multipliers in this last problem, in particular those associated with the $\mathbf{A}^{\top}\mathbf{q}^{\alpha} \leq \mathbf{k}^*$ constraints.
I'm guessing that the problem can lie in the fact that $\mathbf{k}^*$ identified in the minimization step are just approximations to the true $\mathbf{k}^*$ on the frontier. However, increasing WorkingPrecision to, e.g., 30, only makes matters worse, as fewer $\mathbf{k}^*$ result in $\sum q^*_i=1$.
Edit: Do you believe this can be the case? If so, can you propose a workaround or a way of identifying the true $\mathbf{k}^*$?
Ideally this should work for any ${n\times J}$ matrix $\mathbf{A}$ with $a_{ij}\geq0$ (and $a_{ij}>0$ for most $ij$, there cannot be any rows or columns that consist only of $0$s), $Q=\{\mathbf{q}\vert \mathbf{q}\in\Bbb R^n_+\land\sum_i^n q_i=1\}$ and an $\alpha\in\Bbb R^n_+$ such that $\alpha_i\in]0,1[$ $\forall i=1,\dots,n$.
My code follows:
A = {{3, 1}, {2, 3}, {1, 5}};
t = Dimensions[A][[1]];
f = Dimensions[A][[2]];
qVec = Array[q, t];
αVec = ConstantArray[1/2, t];
onesVec = ConstantArray[1, t];
zerosVec = ConstantArray[0, t];
needs = Transpose[A].qVec^(1/αVec);
kcrit =
Table[
needs /.
Minimize[
{needs[[i]], qVec.onesVec == 1, Thread[0 <= qVec <= 1]},
qVec,
Reals][[2]],
{i, 1, f}];
step = 1/100;
grid = Flatten[Permutations /@ IntegerPartitions[1, {t}, Range[0, 1, step]], 1];
lg = Length[grid];
plotK =
ListPlot[
Table[needs /. Thread[qVec -> grid[[i]]], {i, 1, lg}],
AspectRatio -> 1, PlotRange -> {{0, 3.2}, {0, 5.2}}];
plotkcrit = ListPlot[kcrit, AspectRatio -> 1, PlotStyle -> Red];
grid = Flatten[Permutations /@ IntegerPartitions[1, {f}, Range[0, 1, step]], 1];
lg = Length[grid];
line = Table[Transpose[kcrit].grid[[i]], {i, 1, lg}];
plotline = ListPlot[line, PlotStyle -> Green];
frontier = {};
frontier2 = {};
success = 0;
Do[
r = Table[line[[g, i]]/line[[g, 1]], {i, 1, f}];
k =
needs /.
Minimize[
Flatten[
{needs[[1]],
qVec.onesVec == 1,
Table[needs[[i]] == r[[i]] needs[[1]], {i, 2, f}],
onesVec >= qVec >= zerosVec}],
qVec, Reals][[2]];
AppendTo[frontier, k];
temp =
NMaximize[{qVec.onesVec, onesVec >= qVec >= zerosVec, needs <= k}, qVec, Reals];
If[temp[[1]] == 1,
success++; AppendTo[frontier2, needs /. temp[[2]]];];,
{g, 1, lg}];
plotfrontier = ListPlot[frontier, PlotStyle -> Yellow];
plotfrontier2 = ListPlot[frontier2, PlotStyle -> Purple];
Show[
{plotK, plotline, plotfrontier, plotkcrit, plotfrontier2,
Graphics[{Text["k1", {0.48, 1.75}], Text["k2", {1.4, 0.55}]}]}]
Print["Purple over Yellow: ", success/lg]
Follow-up: I've tried Chris K.'s suggestion. His code is much faster than mine, but, again, is tantamount to identifying the boundary in yellow in my original post. If I check which of his $\mathbf{k}^*$ result in $\sum q^*_i=1$, I obtain a very similar picture as above (orange is $\mathbf{k}^*$ obtained with Chris's method, purple those $\mathbf{k}^*$ that result in $\sum q^*_i=1$). It's striking that the number of purple points in both pictures is the same, 2% of the yellow/orange points, though the specific $\mathbf{k}^*$ for which this happens are different.
Also, I don't see how Chris's method would generalize to $n>3$, e.g., to
$$\mathbf{A}=\begin{bmatrix}3&1\\2&3\\1&5\\5&\frac{1}{2}\end{bmatrix},$$
