How to maximize $\min_k a_k$ under constraints $\sum_k a_k=A$ and $\sum_k a_k^2=B$?

Question

Suppose I want to find the tuple of positive real numbers $a_k>0$ that maximize the cost $\min_k a_k$, under the constraints $\sum_k a_k=A$ and $\sum_k a_k^2=B$, for some given $A,B>0$. Assume $k=1,...,n$ for some $n$.

Normally, for this kind of problem, I'd use Lagrange multipliers, defining the Lagrangian $$L = \min_k a_k + \alpha \left(\sum_k a_k-A\right) + \beta \left(\sum_k a_k^2-B\right),$$ and working out the conditions that come out imposing $\nabla L=0$. However, in this case, the $\min$ function defining the cost has a discontinuous derivative, which makes me unsure as to how to proceed.

---

For concreteness and better clarity, let's work out the $n=2$ case. The problem is here to find the max of $\min(a_1,a_2)$ under the given constraints. I'd then write the Lagrangian function $$L = \min(a_1,a_2) + \alpha \left(\sum_{k=1}^2 a_k-A\right) + \beta \left(\sum_{k=1}^2 a_k^2-B\right) .$$ From this, imposing $\partial_{a_k}L=0$, we'd get the conditions $1+\alpha+2\beta a_1=0$ and $\alpha+2\beta a_2=0$, which can be solved for $\alpha,\beta$. But in this simple case, the constraints also directly impose the conditions $a_1+a_2=A$ and $a_1^2+a_2^2=B$, which can be directly solved to give $$a_1^\pm = \frac{A}{2} \pm \frac12\sqrt{2B-A^2}, \qquad a_2 = A- a_1.$$ It's not hard to see from basic arithmetic considerations that $2B-A^2\ge0$, and thus $0\le a_1^-,a_2^- \le A/2$. Thus we can always write $\min(a_1,a_2) = \frac A2 - \frac12\sqrt{2B-A^2}$, and that's the final answer, as here there's no room for further optimisation (and introducing the Lagrangian is effectively useless).

---

Let's try to tackle the slightly less boring case with $n=3$. Now the constraints don't automatically determine $a_1,a_2,a_3$. If I try to work out the problem with the simplified Lagrangian $$L=a_1 + \alpha \left(\sum_{k=1}^3 a_k-A\right) + \beta \left(\sum_{k=1}^3 a_k^2-B\right),$$ imposing vanishing gradient I get the three conditions $$\begin{cases}1+ \alpha + 2\beta a_1=0, \\ \alpha + 2\beta a_2 =0, \\ \alpha + 2\beta a_3 =0,\end{cases}$$ which imply $\beta(a_2-a_3)=0$ and $2\beta(a_3-a_1)=2\beta(a_2-a_1)=0$. Thus we must have $\beta\neq0$, which in turn implies $a_2=a_3$, and we go back to a situation where the constraints determine $a_1$, now via $a_1+2a_2=A$ and $a_1^2+2a_2^2=B$, which give $$a_1^\pm = \frac{A}{3} \pm \frac{\sqrt2}{3}\sqrt{3B-A^2}.$$ This is more or less where I hit the problem: I'm tempted to say that, by symmetry, this tells me the stationary points for each individual variable $a_1,a_2,a_3$. But what I actually want is the stationary points (and in particular the max) for their min, and I'm not sure how to convert from one problem into the other using a relatively "elegant" argument (that is to say, possibly without having to work out a plethora of subcases to get there). Furthermore, I think the solutions obtained imposing $\nabla L=0$ (with the $L$ using $\min a_k$ as cost function) only tell me the local stationary points in regions where the cost is smooth (or at least is differentiable), so all regions corresponding to some $a_j=a_k$ are probably left out.

Answer 1

In the case $n=3$ the command of Mathematica 13.3 (Capital letters as parameters and subscripts are not welcome in MMA.)

Maximize[{Min[a1, a2, a3],  a1 + a2 + a3 == a && 
a1^2 + a2^2 + a3^2 == b && {a1, a2, a3} >= 0 && a > 0 &&  b > 0}, {a1, a2, a3}]

answers $$ \left\{ \begin{array}{cc} \{ & \begin{array}{cc} \frac{1}{6} \left(2 a-\sqrt{2} \sqrt{3 b-a^2}\right) & a>0\land \frac{a^2}{3}<b\leq a^2 \\ \frac{1}{6} \left(2 a+\sqrt{2} \sqrt{3 b-a^2}\right) & a>0\land b=\frac{a^2}{3} \\ -\infty & \text{True} \\ \end{array} \\ \end{array} ,\left\{\text{a1}\to \begin{array}{cc} \{ & \begin{array}{cc} \frac{1}{6} \left(2 a-\sqrt{2} \sqrt{3 b-a^2}\right) & a>0\land \frac{a^2}{3}<b\leq a^2 \\ \frac{1}{6} \left(2 a+\sqrt{2} \sqrt{3 b-a^2}\right) & a>0\land b=\frac{a^2}{3} \\ \text{Indeterminate} & \text{True} \\ \end{array} \\ \end{array} ,\text{a2}\to \begin{array}{cc} \{ & \begin{array}{cc} \frac{1}{3} \left(a-\sqrt{2} \sqrt{3 b-a^2}\right) & a>0\land b=\frac{a^2}{3} \\ \frac{1}{6} \left(2 a-\sqrt{2} \sqrt{3 b-a^2}\right) & a>0\land \frac{a^2}{3}<b\leq a^2 \\ \text{Indeterminate} & \text{True} \\ \end{array} \\ \end{array} ,\text{a3}\to \begin{array}{cc} \{ & \begin{array}{cc} \frac{1}{3} \left(a+\sqrt{2} \sqrt{3 b-a^2}\right) & a>0\land \frac{a^2}{3}<b\leq a^2 \\ \frac{1}{6} \left(2 a+\sqrt{2} \sqrt{3 b-a^2}\right) & a>0\land b=\frac{a^2}{3} \\ \text{Indeterminate} & \text{True} \\ \end{array} \\ \end{array} \right\}\right\}$$

Answer 2

Since the problem is fully symmetric, for any solution $a_{k}$ also any permutation of the tuple is also a solution of the minimizing problem. Therefore we can without loss of generalizazion transform the optimization problem doing the following:

$$ \begin{cases} \max \min_{1\leq k\leq N} a_k\\ \sum_{k=1}^N a_k=A\\ \sum_{k=1}^N a_k^2=B \\ a_k>0 \quad 1\leq k\leq N \end{cases} \Rightarrow \begin{cases} \max a_1\\ \sum_{k=1}^N a_k=A\\ \sum_{k=1}^N a_k^2=B \\ a_1\leq a_k \quad 2\leq k\leq N\\ a_1>0 \end{cases}\\ $$

If we search for solutions of the latter problem we can tackle the first two constraints via lagrange multipliers and end up with: $$L = a_1 + \alpha \left(\sum_{k=1}^N a_k-A\right) + \beta \left(\sum_{k=1}^N a_k^2-B\right)$$ Now we check for critical points and see that $$ 0=\partial_{a_1}L=1+\alpha+2\beta a_1\\ 0=\partial_{a_i}L=\alpha+2\beta a_i \quad 2\leq i \leq N\\ $$

Therefore we immediatly see that for a critical point $a_i=a_j$ for all $2\leq i,j \leq N$. Side note: we have not yet checked if the found critical points are actually within the admissible domain $0<a_1\leq a_i$ for $2\leq i\leq N$, but if there exists a critical point we now know it is of that form. Evaluation of the contraints yields (similar to your $N=2$ case above) $$ a_1=\frac{A \pm \sqrt{(N-1) (B N-A^2)}}{N}\\ a_i=\frac{A (N-1) \mp \sqrt{(N-1) (B N-A^2)}}{(N-1) N}\quad 2\leq i\leq N $$ If we now demand that $a_1\leq a_i$ we easily see that only the lower solution remains, namely $$ a_1=\frac{A - \sqrt{(N-1) (B N-A^2)}}{N}\\ a_i=\frac{A (N-1) + \sqrt{(N-1) (B N-A^2)}}{(N-1) N}\quad 2\leq i\leq N $$ Additionaly restrictions for admissible critical points are $$ BN\geq A^2 \text{ from the square root.}\\ A^2>B(N-1) \mbox{ from } a_1>0. $$ These two conditions are to be expected, since the sphere and the hyperplane do only intersect for $a_i>0$ for specific $A$ and $B$.

Unfortunately, as commenters pointed out, this does not yield the desired maximum. Therefore we need to investigate the boundaries of the domain, especially $a_1\leq a_k$. Since we do not know how many of the $a_k$ are equal to $a_1$ we can either do it step by step or we formulate it by introducing a new unkown $1\leq m\leq N$ and solve the following optimisation problem

$$ \begin{cases} \max_{1\leq m\leq N}\max a_1\\ m\cdot a_1 + \sum_{k=m+1}^N a_k=A\\ m\cdot a_1^2 + \sum_{k=m+1}^N a_k^2=B \\ a_1< a_k \quad m+1\leq k\leq N\\ a_1>0 \end{cases} $$

This yields (similar as above) $$ a_1=\frac{A m - \sqrt{m (N-m) (B N-A^2)}}{m N}=\frac{A - \sqrt{\tfrac{N-m}{m} (B N-A^2)}}{N}\\ a_k = \frac{A(N-m) + \sqrt{m (N-m) (B N-A^2)}}{N(N-m)} $$

now if we investigate the $a_1$ we can easily see that it is maximized for $m$ as large as possible, but the constraints can no longer be fulfilled for $m=N$ so we achieve the maximum for$m=N-1$.

This yields finally $$ \max\min a_k = a_1=\frac{A (N-1) - \sqrt{(N-1) (B N-A^2)}}{(N-1) N} $$

Answer 3

Taking a lagrangian as

$$ L(a,\lambda,s) = a_1+\lambda_0\left(\sum_{k=1}^na_k - A\right)+\lambda_1\left(\sum_{k=1}^n a_k^2-B\right)+\sum_{k=1}^n\lambda_{k+1}(a_k-s_k^2)\ \ \ \ (1) $$

we arrive to a solution which agrees with the numerical solution for

$$ \max(\min a_k)\ \ \ \ \text{s. t.}\ \ \ \ \cases{\sum_{k=1}^na_k = A\\ \sum_{k=1}^n a_k^2=B\\ a_k \ge 0}\ \ \ \ \ (2) $$

Follows a MATHEMATICA script which calculates the stationary points to the problem $(1)$ and verifies that between those stationary points, we can find the solution obtained thru the minimization of the problem $(2)$. The tests were realized using $A = 1, B = \frac 13$ such that $\frac{A^2}{n}\lt B\lt A^2$.

n = 7;
A = 1;
B = 1/3;
tA = Table[a[k], {k, 1, n}];
tL = Table[lambda[k], {k, 0, n + 1}];
tS = Table[s[k], {k, 1, n}];
L = a[1] + lambda[0] (Sum[a[k], {k, 1, n}] - A) + lambda[1] (Sum[a[k]^2, {k, 1, n}] - B) + Sum[lambda[k + 1] (a[k] - s[k]^2), {k, 1, n}];
vars = Join[Join[tA, tL], tS];
equs = Grad[L, vars];
sols = Quiet@Solve[equs == 0, vars];
vars2 = Join[Join[tA, tL], Table[s[k]^2, {k, 1, n}]];
res = Union[vars2 /. sols] // FullSimplify;
GOODS = {};
For[k = 1, k <= Length[res], k++, real = True; For[j = 1, j <= 3 n + 2, j++, If[NotElement[res[[k, j]], Reals] || ! NumericQ[res[[k,j]]], real = False]]; If[real, AppendTo[GOODS, res[[k]]]]]
res0 = Union[tA /. sols] // FullSimplify;
ineqA = Table[a[k] >= 0, {k, 1, n}];
NMaximize[Join[{Min[tA], Sum[a[k], {k, 1, n}] == A, Sum[a[k]^2, {k, 1, n}] == B}, ineqA], tA, Method -> "DifferentialEvolution"]
For[k = 1; best = -10^10, k <= Length[GOODS], k++, 
 If[GOODS[[k, 1]] > best, kbest = k; best = GOODS[[k, 1]]]]
GOODS[[kbest]]

As we can verify in the last code line, $s_k^2=0\forall k$ as well as $\lambda_k=0,\ k= 2,\cdots, n$.

From $(1)$

$$ \left( \begin{array}{ccccccccccccccccccccccc} a(1) & a(2) & a(3) & a(4) & a(5) & a(6) & a(7) & \lambda (0) & \lambda (1) & \lambda (2) & \lambda (3) & \lambda (4) & \lambda (5) & \lambda (6) & \lambda (7) & \lambda (8) & s(1)^2 & s(2)^2 & s(3)^2 & s(4)^2 & s(5)^2 & s(6)^2 & s(7)^2 \\ \frac{1}{7} \left(1+2 \sqrt{2}\right) & \frac{1}{21} \left(3-\sqrt{2}\right) & \frac{1}{21} \left(3-\sqrt{2}\right) & \frac{1}{21} \left(3-\sqrt{2}\right) & \frac{1}{21} \left(3-\sqrt{2}\right) & \frac{1}{21} \left(3-\sqrt{2}\right) & \frac{1}{21} \left(3-\sqrt{2}\right) & \frac{1}{14} \left(3 \sqrt{2}-2\right) & -\frac{3}{2 \sqrt{2}} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \frac{1}{7} \left(1+2 \sqrt{2}\right) & \frac{1}{21} \left(3-\sqrt{2}\right) & \frac{1}{21} \left(3-\sqrt{2}\right) & \frac{1}{21} \left(3-\sqrt{2}\right) & \frac{1}{21} \left(3-\sqrt{2}\right) & \frac{1}{21} \left(3-\sqrt{2}\right) & \frac{1}{21} \left(3-\sqrt{2}\right) \\ \end{array} \right) $$

From $(2)$

$$ \{0.0755136,\{a(1)\to 0.0755136,a(2)\to 0.0755136,a(3)\to 0.0755136,a(4)\to 0.0755136,a(5)\to 0.0755136,a(6)\to 0.0755136,a(7)\to 0.546918\}\} $$

Answer 4

Here's the full "straightforward" way to solve the problem, using the idea from some of the other answers to introduce slack variables (which of course, a posteriori, is the standard approach in this context).

To avoid dealing with the non-smooth cost function, we instead consider $a_1$ as cost function, introducing the inequality constraints $a_1 \le a_k$ for all $k>1$. These inequality constraints are then converted into equality constraints introducing additional slack variables $s_k$. The Lagrangian thus becomes: $$L = a_1 + \alpha\left(\sum_{k=1}^n a_k-a\right) + \beta\left(\sum_{k=1}^n a_k^2 -b\right) + \sum_{k=2}^n \gamma_k (a_k - a_1 - s_k^2),$$ where we have to remember that the task is now to minimise $a_1$ with respect to the variables $(a_1,...,a_n,s_2,...,s_n)$.

The gradient $\nabla L=0$ gives the conditions: $$ 1 + \alpha + 2\beta a_1 - \sum_{k=2}^n \gamma_k = 0, \\ \alpha + 2\beta a_k + \gamma_k = 0, \qquad \forall k=2,..., n, \\ \gamma_k s_k=0, \qquad \forall k=2,..., n. $$

---

Consider first the simplest case with $n=3$. We have several possibilities:

1. If $s_2,s_3\neq0$, then $\gamma_2=\gamma_3=0$. The conditions above then simplify to $$1+\alpha + 2\beta a_1=0, \quad \alpha + 2\beta a_2 = \alpha+ 2\beta a_3=0.$$ This implies $a_2=a_3\neq a_1$. Using the constraints, we then find two possible solutions for $a_1$. One of these is larger than $a_2$, and is therefore excluded, and the remaining solution is $$a_1=\frac a3-\frac{\sqrt2}{3} \sqrt{3b-a^2}.$$

2. Suppose now $s_2=0$ and $s_3\neq0$. This means $a_1=a_2<a_3$. Then we can again directly use the constraints, finding two possible solutions for $a_1$, the smallest of which satisfies the constraints and equals $$a_1 = \frac{a}{3} - \frac{\sqrt2}{6}\sqrt{3b-a^2}.$$ The case $s_2\neq0, s_3=0$ gives an identical solution.

3. The last possibility is having $s_2=s_3=0$. This implies $a_1=a_2=a_3$ and thus $a_1=a/3$. Due to the quadratic constraint, this is possible only if $3b=a^2$.

By direct inspection of the above three cases, the largest $a_1$ is clearly achieved (2) (which is identical to (3) when $3b=a^2$. We conclude that the max of $\min\{a_1,a_2,a_3\}$ is $$a_1 = \frac a3-\frac{\sqrt2}{6}\sqrt{3b-a^2}.$$

---

Strong of the intuition provided by the above, let's tackle the general case $n>3$. Let's explore the possible scenarios as follows:

1. Suppose $s_k=0$ for all $k=2,...,n$. Then $a_1=a_2=...=a_n$, hence $a_1=a/n$. This is only possible if $nb=a^2$.

2. Suppose $s_2=...=s_{n-1}=0$ and $s_n\neq0$. Then $a_1=a_2=...=a_{n-1}<a_n$. The constraints then read $(n-1) a_1 + a_n=a$ and $(n-1)a_1^2+a_n^2=b$, which give two solutions, one of which corresponds to $a_1>a_n$ and is thus not feasible, and the other one is $$a_1 = \frac an - \frac{\sqrt{(n-1)(bn-a^2)}}{n(n-1)}.$$

3. Suppose more generally $s_1=...=s_m=0$, and $s_{m+1},...,s_n\neq0$, for some $1<m<n$. This implies $\gamma_{m+1}=...=\gamma_n=0$, and thus the corresponding conditions from $\nabla L=0$ become $\alpha+2\beta a_{m+1}=...=\alpha+2\beta a_n=0$. This implies $a_{m+1}=...=a_n$, and we yet again reach a situation with only two possible values for the $a_k$, namely, $a_1=...=a_m$ and $a_{m+1}=...=a_n$, but $a_1\neq a_n$. Using the constraints as always then gives the conditions $m a_1 + (n-m) a_n=a$ and $m a_1^2+(n-m)a_n^2=b$, which gives two solutions for $a_1$, the smallest of which is feasible and reads $$a_1 = \frac an - \frac{\sqrt{m(n-m)(bn-a^2)}}{nm}.$$

The above covers all possible situations. We now simply observes that $\sqrt{m(n-m)}/m$ decreases with $1< m <n$, to conclude that the largest $a_1$ corresponds to case (2) above, and thus the final solution is $$ a_1 = \frac an - \frac{\sqrt{(n-1)(bn-a^2)}}{n(n-1)}.$$

Answer 5

Here is a simple solution:

Assume that $n \ge 3$. The problem is feasible if and only if $nB \ge A^2 > B$ and $A, B > 0$.

The maximum of $\min\limits_{1\le k\le n} a_k$ is given by $$\frac{A}{n} - \frac{\sqrt{(n - 1)(nB - A^2)}}{n(n - 1)}.$$ (Note: $\frac{A}{n} - \frac{\sqrt{(n - 1)(nB - A^2)}}{n(n - 1)} > 0$.)

Proof.

WLOG, assume that $a_1 = \min(a_1, a_2, \cdots, a_n)$.

First, we have $\frac{A}{n} - a_1 \ge 0$ and \begin{align*} &\left(\frac{A}{n} - a_1\right)^2 - \left(\frac{\sqrt{(n - 1)(nB - A^2)}}{n(n - 1)}\right)^2\\[6pt] ={}& \frac{n(n-1)a_1^2 - 2(n-1)Aa_1 + A^2 - B}{n(n - 1)}\\[6pt] ={}& \frac{2}{n(n - 1)}\sum_{2 \le i < j \le n} (a_i - a_1)(a_j - a_1)\\[6pt] \ge{}& 0 \end{align*} which results in $$\frac{A}{n} - \frac{\sqrt{(n - 1)(nB - A^2)}}{n(n - 1)} \ge a_1.$$

Second, when $$a_1 = a_2 = \cdots = a_{n-1} = \frac{A}{n} - \frac{\sqrt{(n - 1)(nB - A^2)}}{n(n - 1)}$$ and $$a_n = \frac{A}{n} + \frac{\sqrt{(n - 1)(nB - A^2)}}{n},$$ we have $a_k > 0, \forall k$ and $\sum_{k=1}^n a_k = A$ and $\sum_{k=1}^n a_k^2 = B$.

Thus, the maximum of $\min\limits_{1\le k\le n} a_k$ is given by $$\frac{A}{n} - \frac{\sqrt{(n - 1)(nB - A^2)}}{n(n - 1)}.$$

We are done.