Optimization over min function

Question

We want to maximize $\sum_{i=1}^N \sum_{j=1}^N \min(a_i,b_j)$ such that $\sum_{i=1}^N a_i =1$ and $\sum_{j=1}^N b_j =1$. I think the optimal solution is $a_i = 1/N$ and $b_j = 1/N$ for $i,j = {1,2, ...,N}$. Is it correct? Any suggestion for proving this?

Answer 1

This problem can be solved by using symmetry and convexity.

I prefer to minimise the sum of the $\max$ as the resulting function is convex.

Let $f(a,b) = \sum_i \sum_j \max(a_i,b_j)$. Then the problem is equivalent to $\min \{ f(a,b) | a,b \in A \}$, where $A$ is the affine set $A = \{ x | \sum_k x_k =-1 \}$ (note the $-1$ since I have changed the signs on $a,b$). In particular, $A$ is convex.

We see that $f$ is convex and $f(a,b)=f(b,a)$. Then $f({1 \over 2} (a+b), {1 \over 2} (a+b)) \le {1 \over 2} (f(a,b)+f(b,a))$, hence we need only consider the function $g(x) = f(x,x)$. If $P$ is a permutation matrix, we see that $g(Px) = g(x)$, hence by similar considerations we have $g({1 \over n!} \sum_{P \in {\cal P}} Px) \le {1 \over n!} \sum_{P \in {\cal P}} g(Px)) = g(x)$, where ${\cal P}$ is the set of permutation matrices.

Since $\bar{x} = {1 \over n!} \sum_{P \in {\cal P}} Px = {1 \over n} (x_1+\cdots +x_n)(1,\cdots,1 ) $, we see that we need only consider $h(t) = g(t(1,\cdots,1))$.

However, there is exactly one $t$ such that $t(1,\cdots,1) \in A$ and that is $t= -{1 \over n}$. Hence a minimiser is $-{1 \over n} (1,\cdots,1)$.

Converting back to the original problem, we see that $(a^*,b^*)=+{1 \over n} ((1,\cdots,1),(1,\cdots,1))$ is a maximiser.

To see that the maximiser is unique (or in this case, that the minimiser is unique), note that $-n=f(a^*,b^*) = \sum_i \sum_j \max(a^*_i,b^*_j) \ge \sum_i \sum_j a^*_i = -n$, and $\max(a^*_i,b^*_j) \ge a^*_i$ for all $i,j$ we must have $\max(a^*_i,b^*_j) = a^*_i$ for all $i,j$. Hence $a^*_i \ge b^*_j$ for all $i,j$ and since $\sum_i a^*_i = \sum_j b^*_j = -1$, we must have $a^*_i = b^*_j$ for all $i,j$ and hence $a^* = b^* = +{1 \over n} (1,\cdots,1)$.

Addendum: Answers to some questions in comments below:

The significant property of $f$ is convexity. In particular, if $f$ is convex, then if $\lambda_k \ge 0$ and $ \sum_{k=1}^m \lambda_k = 1$, we have $f(\sum_{k=1}^m \lambda_k p_k ) \le \sum_{k=1}^m \lambda_k f(p_k)$. (In this particular case, we have each $p_k = (a_k, b_k)$.)

This gives the property $f({1 \over 2} (a+b), {1 \over 2} (a+b)) \le {1 \over 2} (f(a,b)+f(b,a))$, from which we see that, in terms of minimising $f$, we can reduce our search to the 'diagonal'.

Note that the $g$ above has the form $g(x) = \sum_i \sum_j \max(x_i,x_j)$, so $g$ is invariant over permutations of $x$, that is, $g((x_1,....,x_n)) = g((x_{\sigma(1)},...,x_{\sigma(n)})$ for any permutation $\sigma$.

Instead of taking all permutations, just note that $g((x_1,....,x_n)) = g((x_2,....,x_n, x_1)) = \cdots = g((x_n,x_1,....,x_{n-1}))$. Note that if we let $\bar{x} = {1 \over n} ((x_1,....,x_n)) +(x_2,....,x_n, x_1)+ \cdots + (x_n,x_1,....,x_{n-1}))$, then $\bar{x}$ has the form $\bar{x} ={1 \over n} (x_1+\cdots +x_n)(1,\cdots,1 ) $.

By convexity, we have $g(\bar{x}) \le {1 \over n} (g((x_1,....,x_n)) + g((x_2,....,x_n, x_1)) + \cdots + g((x_n,x_1,....,x_{n-1}))) = g((x_1,....,x_n))$, so again, since we are minimising, we need only consider $x$ of the form $(t,t,...,t)$, or $t (1,1,....,1)$.

So, to find the minimising values, we need only consider $h(t) = g((t,t,...,t))$.

Answer 2

First, write your problem as a linear problem: $$ \mbox{Maximize }\sum_{i=1}^N \sum_{j=1}^N z_{ij} $$ subject to: \begin{align*} &\sum_{i=1}^N a_i=1\\ &\sum_{j=1}^N b_j=1\\ &z_{ij}\le a_i\quad \forall i,j=1,\cdots,N\\ &z_{ij}\le b_j\quad \forall i,j=1,\cdots,N\\ \end{align*}

Second, find an upper bound for this problem: $$ \sum_{i,j=1}^N z_{ij}\le \sum_{i,j=1}^N a_i = N $$

Finally, find a feasible solution for which this bound is reached (yours is fine): $$ z_{ij}=a_i=b_j=\frac{1}{N}\quad \forall i,j=1,\cdots,N. $$