Exercise 2.15 from Boyd & Vandenberghe's Convex Optimization:

Let $x$ be a real random variable with $\textbf{prob}(x=a_i) = p_i$, where $a_1 < a_2 < \cdots < a_n$. In this case, show whether $$\textbf{quart}(x)\leq \alpha$$ is convex in $p$ or not. (where $\textbf{quart}(x)=\inf\{\beta~ |~\textbf{prob}(x\leq\beta)\geq.25\}$).

The answer to this question in the solution manual is as follows:

The constraint $\textbf{quart}(x)\leq \alpha$ is equivalent to $$\textbf{prob}(x\leq \beta)\geq .25~\text{for all }\beta\geq \alpha.~~~~~(1)$$ This can be expressed as a linear inequality $$\sum_{i=k+1}^np_i\geq.25,~~~~~(2)$$ where $k=\max\{i~|~a_i<\alpha\}$.

My question:

In my view equation (1) should mean that, assuming that $a_m$ is the smallest value which is $\geq \alpha$ that random variable $x$ can take, $$p_1+p_2+\cdots p_m\geq .25\\p_1+p_2+\cdots p_m+p_{m+1}\geq .25\\ \vdots \\ p_1+p_2\cdots+p_n\geq.25.$$(please check if this is a right set of inequalities for equation (1).) And I think these set of inequalities can be replaced by following inequality $$p_1+p_2+\cdots p_m\geq .25$$ which is $$\sum_{i=1}^{k+1}p_i\geq .25.$$ But this does not matches with equation (2) above. Where is my thinking wrong? Any help in this regard will be much appreciated. Thanks in advance.

  • 1
    $\begingroup$ I have told you at least twice that Lieven Vandenberghe is a co-author and, yet, you insist on not mentioning him. $\endgroup$ Jul 11 '18 at 14:13
  • 2
    $\begingroup$ The solution manual is not written for students. It seems like you read the answer to a different question. $\endgroup$
    – LinAlg
    Jul 11 '18 at 14:17
  • $\begingroup$ @RodrigodeAzevedo thank you for reminding me. I am sorry. I do not have any prejudice. The only reason I do not mention his name is that I can not remember the correct spelling of his name (maybe not a very good reason but there is no other reason at all) and I will have to verify his name spellings before posting the question. Nevertheless, I will memorize his spellings. $\endgroup$ Jul 11 '18 at 22:58
  • $\begingroup$ @LinAlg No, I have not read the answer to other question. You may check it on the internet (the solution is available online). This is the final part of the question. Anyways, don't you think that the correct set of inequalities that represent equation (1) are the ones I wrote and they all are equivalent to the final inequality that I wrote? Or you think that are not for equation (1)? $\endgroup$ Jul 11 '18 at 23:02
  • 1
    $\begingroup$ @FrankMoses yes you have; subquestion (h) and (i) are two different questions with different answers. $\endgroup$
    – LinAlg
    Jul 12 '18 at 1:21

Your new sum should be up to $k$, but yes, otherwise, the linear inequality for $p$ to show that it belongs into this set is:

$\sum_{i=1}^k p_i \geq 0.25$ where $k = \max \{ i \mid a_i \leq \alpha\}$ (pick $k$ to be $0$ if $a_1 < \alpha$; the inequality is definitely violated in that case anyway).

To see this, note that if the inequality is violated, then we have that sum of the probabilities of $a_i$s below $\alpha$ is strictly less than $0.25$, and thus the quartile is bigger than $\alpha$. The converse proof is exactly the same.

  • $\begingroup$ thank you for your answer. Actually, the definition of $k$ I used is $k=\max\{i~|~a_i<\alpha \}$. I think with this definition the sum should be upto $k+1$. Right? $\endgroup$ Jul 13 '18 at 4:23
  • $\begingroup$ That won't work since then you can satisfy this inequality while having some of that 0.25 probability above $\alpha$. You should probably redefine your $k$. $\endgroup$
    – E-A
    Jul 13 '18 at 5:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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