Minimizing Appreciating Quantities vs. Maximizing Depreciating Quantities Suppose you have a set $S = \{r_1, ..., r_n :\, r_k \in (1, \infty)\, \forall \,k \in \{1,...,n\}\}$. Find a bijective mapping $f: \{0,...,n-1\}\rightarrow \{1,...,n\}$ that minimizes
\begin{align*}
\sum_{k=0}^{n-1}r_{f(k)}^{k}
\end{align*}
Solution: Let $f$ be a mapping that satisfies $k< j \, \rightarrow \, r_{f(k)} \ge r_{f(j)}$. In other words, $f$ sorts $S$ in non-increasing order. To prove optimality, consider a bijective mapping $g$ defined on the same domain and range, and suppose $g$ minimizes the sum. Further, suppose $g$ differs from $f$. Therefore, there must be some inversion: an index $i$ such that $r_{g(i)} < r_{g(i+1)}$. We will show that swapping these two images decreases the total sum, contradicting the optimality of $g$. Notice that if we only swap these two, then the remaining terms of the sum are unchanged. To show that the swap decreases the total sum, we must verify
\begin{align*}
r_{g(i+1)}^{i}+r_{g(i)}^{i+1} &< r_{g(i)}^{i}+r_{g(i+1)}^{i+1}\\
r_{g(i)}^{i+1} -r_{g(i)}^{i}&< r_{g(i+1)}^{i+1}-r_{g(i+1)}^{i}&\iff \\
r_{g(i)}^i(r_{g(i)} - 1)&<r_{g(i+1)}^i(r_{g(i+1)}-1)&\iff 
\end{align*}
But this final inequality holds because each rate exceeds one and by assumption $r_{g(i)} < r_{g(i+1)}$. This contradicts the optimality of $g$, hence any mapping that deviates from sorting the rates in descending order is not optimal.

Now suppose you have a set $S = \{r_1, ..., r_n :\, r_k \in (0, 1)\, \forall \,k \in \{1,...,n\}\}$. Find a bijective mapping $f: \{0,...,n-1\}\rightarrow \{1,...,n\}$ that maxmizes
\begin{align*}
\sum_{k=0}^{n-1}r_{f(k)}^{k}
\end{align*}
Note: It is interesting to point out that the naïve attempt of sorting $S$ in ascending order fails to maximize the sum in certain cases. Take for example the set
\begin{align*}
\biggr\{\frac{1}{10}, \frac{1}{2}, \frac{4}{7}, \frac{3}{5}, \frac{2}{3}\biggr\}&\\
\biggr(\frac{1}{10}\biggr)^0 + \biggr(\frac{1}{2}\biggr)^1 + \biggr(\frac{4}{7}\biggr)^2 + \biggr(\frac{3}{5}\biggr)^3 + \biggr(\frac{2}{3}\biggr)^4&\approx 2.240061476\\
\biggr(\frac{1}{10}\biggr)^0 + \biggr(\frac{4}{7}\biggr)^1 + \biggr(\frac{2}{3}\biggr)^2 + \biggr(\frac{3}{5}\biggr)^3 + \biggr(\frac{1}{2}\biggr)^4&\approx 2.294373016
\end{align*}
You can verify that this second sum is optimal in Mathematica, using the following code

S = {1/10, 1/2, 4/7, 3/5, 2/3};
  p = Range[0, 4];
  perm = Permutations[S];
  totals = Total[#^p] & /@ perm;
  maxPos = First[Flatten[Position[totals, Max[totals]]]]
  perm[[maxPos]]


So my question is: can you think of an efficient rule to maximize the second sum? Currently my best solution is to literally enumerate all $n!$ possible ways to order the terms. Also, why is this problem so much harder? I feel it has something to do with the unboundness of the first problem. A colleague of mine suggested that the solution space of first problem is convex while the second is not, though I do not have a good grasp on why that is. (I know the definition of convexity, but what part of the problem formulation makes the solution space second problem not convex?)
Any help / input would be greatly appreciated.
 A: Even though this won't answer your question here is some first input. 
Vincent Tjeng made and I made some numerics with Mathematica, this was his code (which I used too) 
data = Table[someList = RandomReal[{0, 1}, 5];
    Ordering@
      Ordering@
        (Last@SortBy[{N[Total[#^(Range[Length@someList] - 1)]], #} & /@ 
      Permutations[someList], First])[[2]], {i, 1, 300000}];

If you want to try yourself take something smaller than 300000 because that takes several minutes.
And afterwards with Tally we counted which permutation was the best how often. 
The result ist the following one 
\[ 
\begin{array}{cc}
\text{Permutation} & \text{Count}\\
 \{1,5,4,3,2\} & 18495 \\
 \{1,3,4,5,2\} & 106342 \\
 \{1,4,5,3,2\} & 81069 \\
 \{1,2,3,4,5\} & 56819 \\
 \{1,3,4,2,5\} & 14042 \\
 \{1,4,3,5,2\} & 13085 \\
 \{1,3,5,4,2\} & 2808 \\
 \{1,2,4,5,3\} & 691 \\
 \{1,2,3,5,4\} & 206 \\
 \{1,3,2,4,5\} & 3136 \\
 \{1,2,4,3,5\} & 1305 \\
 \{1,4,3,2,5\} & 1994 \\
 \{1,2,5,4,3\} & 8 \\
\end{array}
\]
Here 1 stands for the smalles and 5 for the biggest.
We see here that only in 905 Cases the last number wasn't the largest or the second smallest. This has a reason.

In the plot you see how much the decrease if you put a number on another position. For example if you look at $x-x^2$ this says you how much the sum decreas if you put the number on the third position insteadt of the second position. 
As you see that for smaller numbers it is not that much of a problem if they are in the ende or only near the end. 
So a better heuristic is the following: Put on position 1 the smallest value. 
Now it is much more difficult how to chose the next one. Should surely take one of the values which are around $0.5$ but you have to be carefull to take one which is in the middle of the values greater than $0.5$, because those values will decrease later more than small values do.
In the plot we see that very big and very small values don't change a lot when raising their powers. So in the last position there will be the largest, or the second smallest value. this is some heuristic I will think more about it.
A: Some additional input as a follow-up to Dominic Michaelis': I've modified the code slightly so that you can actually check the values of the "outlier" data.
The code now runs as follows:
n = 5;
(actualValues[#] = {}) & /@ Permutations[Range[n]];
rankingList = Table[sample = RandomReal[{0, 1}, n];
   sortedSample = (Last@
       SortBy[{N[Total[#^(Range[Length@sample] - 1)]], #} & /@ 
         Permutations[sample], First])[[2]];
   sortedSampleRanking = Ordering@Ordering@sortedSample;
   actualValues[sortedSampleRanking] = 
   Append[actualValues[sortedSampleRanking], sortedSample];
   sortedSampleRanking
   , {i, 1, 1000}];
Tally@rankingList

(*{{{1, 3, 4, 5, 2}, 367}, {{1, 4, 5, 3, 2}, 283}, {{1, 4, 3, 2, 5}, 6}, {{1, 3, 4, 2, 5}, 41}, {{1, 2, 3, 4, 5}, 173}, {{1, 5, 4, 3, 2}, 53}, {{1, 3, 5, 4, 2}, 10}, {{1, 4, 3, 5, 2}, 46}, {{1, 3, 2, 4, 5}, 16}, {{1, 2, 4, 5, 3}, 2}, {{1, 2, 4, 3, 5}, 3}}*)

You can now extract the actual values of certain rankings that you are interested in by running the following code
actualValues[{1, 2, 3, 5, 4}] (*or whatever other ranking*)

Which in the above case gives the following results.
(*{{0.150845, 0.579054, 0.693527, 0.636326, 0.8711}, {0.50505, 0.620839, 0.632839, 0.624155, 0.98465}, {0.342148, 0.555461, 0.630722, 0.604628, 0.927428}}*)

From the small sample size that we have, it does appear that "unexpected" rankings occur mostly when the two or more numbers that occur in unexpected positions are very close to each other in value.
A: In both cases, because of associativity of addition, the solutions have to be "swap-immune," meaning that the optimal order can't be improved by a position swap. In the first case, this is sufficient to show that the solution is unique and ordered.
So in the second case, on on (0,1), is swap-immunity sufficient to show uniqueness? If so, then a program like the one below (in perl) should reliably find the solution in polynomial time. I don't claim this to be a proof. I just tried it out on a few cases and the solution was invariant to the starting permutation.
use List::Util qw(shuffle);
@x= (.1,.5, 0.571428571,.6,.6666666667);
@s = shuffle(@x);
for ($i=0; $i<scalar(@x); $i++){
     for ($j=0; $j<scalar(@x); $j++){
      if ( $s[$i]**$i + $s[$j]**$j < $s[$i]**$j + $s[$j]**$i){
       swap($i,$j);
       $j=0; #restart the search
      }
     }
}
    print join(',',@s);
    sub swap {
     my ($i,$j) = @_;
     my $t = $s[$i];
     $s[$i] = $s[$j];
     $s[$j] = $t;
    }  

