Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers

up vote 1 down vote accepted

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.

share|improve this answer
    
I got it. Thank you! (I mean the former) –  Zhou Heng Feb 21 '13 at 11:28
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.