Optimization over min function 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?  
 A: 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.
$$
A: 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))$.
