Consider the problem of minimizing $\sum_{i=1}^{n}{x_{i}}$ under the constraints $\sum_{i=1}^{n}{x_{i}^{2}}=1$ and $x_{i} \geq 0$. Obviously the solution is given by the vector $(1,0,\ldots,0)$.

Now consider the variant where we add the constraint $x_{i} \leq a$. I am quite sure that the smallest sum is attained by the vector $(a,a,\ldots,a,b,0,\ldots,0)$ with $a$ repeated $\lfloor \frac{1}{a^2} \rfloor$ times and $b=\sqrt{1-a^2\lfloor \frac{1}{a^2} \rfloor}$.

QUESTION 1: Is there a standard reference for facts like this?

QUESTION 2: What happes when we add the constraint $x_{i} \geq b>0$?

  • 5
    $\begingroup$ This is an easy consequence of Karamata's inequality (aka Hardy-Littlewood-Polya, aka Majorization) applied to the function $\sqrt{x}$. $\endgroup$
    – zeb
    Commented Feb 8, 2014 at 1:15
  • 1
    $\begingroup$ @zeb Thanks! This is just what I was looking for. Perhaps you should turn the comment into an answer, so that I can accept it. $\endgroup$ Commented Feb 8, 2014 at 1:38

1 Answer 1


Karamata's paper: http://elib.mi.sanu.ac.rs/files/journals/publ/1/11.pdf

A few related papers are listed out in this AoPS forum post: http://www.artofproblemsolving.com/Forum/viewtopic.php?p=123878&#p123878


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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