An optimization problem with regard to permutation function

Question

So far I only meet optimization problems solved by searching for an optimal point in $\mathbb{R}^n$. But today I met with an optimization problem that asks me to search within a set of functions. My previous knowledge on optimization such as Lagrangian multiplier method and KKT suddenly loses its power. I have no idea about how to handle it.

The question is as follows: Given a pmf, i.e., a finite sequence of positive values $q_1,q_2,\ldots,q_n$ satisfying $\sum\limits_{i=1}^n q_i=1$, try to find

$\mathrm{argmin}\sum\limits_{i=1}^n iq_{P(i)}$ within all permutation $P$ of the given pmf.

I guess the answer is the permutation that sorts the pmf in a nonincreasing order. But how to obtain it? Which brach of mathematics aims at this kind of optimization problems with regard to functions? Thank you for your answer.

Answer 1

If "it" in "how to obtain it" refers to the answer, note that if the $q_i$ aren't sorted, you can reduce the value of the objective function by swapping two that are out of order.

If "it" in "how to obtain it" refers to the permutation, see Wikipedia.

The branch of mathematics and computer science that deals with optimizing functions of combinatorial objects like permutations is called combinatorial optimization.

Answer 2

More generally, given two sets of non-negative numbers with the same cardinality $n$, $0\le a_1\le a_2\le\ldots\le a_n$ and $0\le b_1\le b_2\le\ldots\le b_n$, $$\sum_{i=1}^n a_ib_{n-i+1}\le \sum_{i=1}^n a_ib_{P(i)}\le \sum_{i=1}^n a_ib_i$$, where $P$ is your notation for an element of the set of all permutations of $1$ to $n$. This can be proved by showing swapping two "out of order" $b_i$'s relative to their corresponding $a_i$'s resulting in an increase in the sum.