Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I encounter the following claim in my research for which I couldn't get a solution for a long time. I asked a more general version of the question at math.stackexchange which did not attract much attention there. Following is a particular version of the question.

Let $p>1$ and let

$$L = \{ \ \textbf{x} \in \mathbb{R}^n:\ \ x _i\ge 0, \sum_i x_i=1, \sum_i a_i x_i =b\ \}$$ for some real numbers $a_i$ and $b$.

Suppose that $\textbf{x}, \textbf{y}\in L$ with the following property: $x_i=0$ wherever $y_i=0$, and $y_j\neq 0$ but $x_j=0$ for some $j$, i.e., $\bf{y}$ has more support than $\bf{x}$. Then $\|\textbf{x}\|_p>\|\textbf{y}\|_p$ or there exists $\textbf{z}\in L$ such that $\textbf{z}$ has more support than $\textbf{x}$, i.e., $x_i=0$ wherever $z_i=0$ and $z_k\neq 0$ but $x_k=0$ for some $k$ and $\|\textbf{x}\|_p>\|\textbf{z}\|_p$.

The claim is roughly that the $\ell_p$-norm of points of $L$ which are more closer to the boundary of the probability simplex is larger than the ones which are interior enough. In 2-dimension, the claim is very obvious. The only possibility of $L$ there is $\{ \(x_1,x_2):\ x_i\ge 0, x_1+x_2=1\ \}$ and the boundary points $(1,0),(0,1)$ have the maximum $\ell_p$-norm and as we go deeper interior the norm is lesser and lesser. I am wondering whether the same would be the case even in the higher dimensions.

share|improve this question
    
What is $a_i$ (in the definition of $L$)? –  Sergei Ivanov May 29 '12 at 11:55
    
$a_i$ and $b$ are some real numbers. –  Ashok May 29 '12 at 12:20
    
The logic of the question looks strange as the inequality $\|x\|_p>\|y\|_p$ implies the property "there exists $z$ ..." (because you can take $y$ for $z$). So you are asking for "A or B" when A in fact implies B and hence "A or B" is equivalent to just B. Is this indeed what you intend to ask? –  Sergei Ivanov May 29 '12 at 12:45
    
Yes Sergei Ivanov, you are right. Actually I want to prove B: There exists $\textbf{z}$ such that... I know for sure that $\textbf{x}, \textbf{y}\in L$ with the mentioned properties. If $\textbf{y}$ itself works as $\textbf{z}$ its fine. I am claiming, otherwise, there exists $\textbf{z}$... –  Ashok May 29 '12 at 13:00
add comment

2 Answers

up vote 3 down vote accepted

The answer is no, for any $n\ge 3$ and any $C^1$-smooth strictly convex norm on $\mathbb R^n$. (Here "strictly convex" means that the triangle inequality is strict for any two non-collinear vectors. This is equivalent to the following: the norm restricted to any affine subspace not containing 0 is a strictly convex function on that subspace.)

The claim you are asking for is equivalent to the following: if $L$ is the intersection of the probability simplex and a hyperplane, then the norm restricted to $L$ cannot attain its minimum at a point of the relative boundary of $L$.

To construct a counter-example, consider the set $F$ of points in the simplex where the coordinate $x_1$ is zero and all other coordinates are positive. (Thus $F$ is the relative interior of one of the $(n-2)$-dimensional faces of the simplex.) Consider the norm as a function on this $(n-2)$-dimensional convex set. Since this function is strictly convex, there is at most one point where its derivative vanishes. Choose $\mathbf x=(x_i)\in F$ so that this restricted derivative does not vanish at $\mathbf x$ (here I use the assumption that $n\ge 3$). Let $(a_i)$ be the vector of partial derivatives of the norm at $\mathbf x$ and let $b=\sum a_ix_i$. It is easy to see that $b\ne 0$.

Consider the hyperplane $Y=\{\mathbf y=(y_i):\sum a_iy_i=b\}$ and let $L$ be the intersection of $Y$ and the simplex. By the choice of $\mathbf x$, this hyperplane intersects the relative interior of the simplex, so $L$ contains vectors all whose coordinates are nonzero and $\mathbf x$ belongs to the relative boundary of $L$. On the other hand, the norm restricted on $Y$ is a strictly convex function and by construction it has a critical point at $\mathbf x$. Therefore $\mathbf x$ is the minimum point of the norm on $Y$ and hence on $L$.

share|improve this answer
    
Thank you very much for the clear explanation. It would be helpful to me if you can explain what made you to think that the result was false and how did you come up with this counterexample. –  Ashok May 29 '12 at 17:08
add comment

The way it currently stands, $L$ is the intersection of the "positive" part of the unit sphere w.r.t. the $\ell^1$-norm and an affine hyperspace. If $a_i$ and $b$ are allowed to be arbitrary, $L$ will in general not be non-empty; it could also contain just a single element.

share|improve this answer
    
I have said in the question that $\textbf{x},\textbf{y}\in L$ for sure. –  Ashok May 29 '12 at 13:25
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.