# Proving an inequality involving multiple constraints

Let $R$ be a discrete set and let $f:{\left[ {0,1} \right]^{\left| R \right|}} \times {\left[ {0,1} \right]^{\left| R \right|}} \to \mathbb{R}$ be defined as $f\left( {{\mathbf{x}},{\mathbf{y}}} \right) = \sum\limits_r {\frac{{x_r^2}}{{{x_r} + {y_r}}}}$

I want to show that given the constraints $1 \geqslant {x_r} > 0,\forall {x_r} \in R$, $1 \geqslant {y_r} \geqslant 0,\forall {y_r} \in R$, $\sum\limits_r {{x_r}} = 1$ and $\sum\limits_r {{y_r}} = n - 1$, where $n \in \mathbb{N},n \geqslant 2$, it follows that $f\left( {{\mathbf{x}},{\mathbf{y}}} \right) \geqslant \frac{1}{n}$ for each ${\mathbf{x}},{\mathbf{y}} \in {\left[ {0,1} \right]^{\left| R \right|}}$ satisfying the constraints above.

My attempt: Let us define Lagrange function $L\left( {{\mathbf{x}},{\mathbf{y}}} \right): = \sum\limits_r {\frac{{x_r^2}}{{{x_r} + {y_r}}}} + {\lambda _1}\left( {1 - \sum\limits_r {{x_r}} } \right) + {\lambda _2}\left( {n - 1 - \sum\limits_r {{y_r}} } \right)$. Setting $0 = \nabla L\left( {{{\mathbf{x}}_0},{{\mathbf{y}}_0}} \right)$ yields $\Rightarrow \frac{{{y_r}}}{{{x_r} + {y_r}}} = \frac{{n - 1}}{n},\frac{{{x_r}}}{{{x_r} + {y_r}}} = \frac{1}{n},\forall r \Rightarrow L\left( {{{\mathbf{x}}_0},{{\mathbf{y}}_0}} \right) = f\left( {{{\mathbf{x}}_0},{{\mathbf{y}}_0}} \right) = \sum\limits_r {\frac{{{x_r}}}{{{x_r} + {y_r}}}{x_r}} = \frac{1}{n}\sum\limits_r {{x_r}} = \frac{1}{n}$.

However, for bordered Hessian matrix we have $H\left( {{{\mathbf{x}}_0},{{\mathbf{y}}_0}} \right) = \left[ {\begin{array}{*{20}{c}} 0&0&1& \cdots &1&0& \cdots &0 \\ 0&0&0& \cdots &0&1& \cdots &1 \\ 1&0&{\frac{2}{{{x_1} + {y_1}}}{{\left( {\frac{{n - 1}}{n}} \right)}^2}}&0&0&{\frac{{ - 2}}{{{x_1} + {y_1}}}\frac{{n - 1}}{{{n^2}}}}&0&0 \\ \vdots & \vdots &0& \ddots &0&0& \ddots &0 \\ 1&0&0&0&{\frac{2}{{{x_{\left| R \right|}} + {y_{\left| R \right|}}}}{{\left( {\frac{{n - 1}}{n}} \right)}^2}}&0&0&{\frac{{ - 2}}{{{x_{\left| R \right|}} + {y_{\left| R \right|}}}}\frac{{n - 1}}{{{n^2}}}} \\ 0&1&{\frac{{ - 2}}{{{x_1} + {y_1}}}\frac{{n - 1}}{{{n^2}}}}&0&0&{\frac{2}{{{x_1} + {y_1}}}\frac{1}{{{n^2}}}}&0&0 \\ \vdots & \vdots &0& \ddots &0&0& \ddots &0 \\ 0&1&0&0&{\frac{{ - 2}}{{{x_{\left| R \right|}} + {y_{\left| R \right|}}}}\frac{{n - 1}}{{{n^2}}}}&0&0&{\frac{2}{{{x_{\left| R \right|}} + {y_{\left| R \right|}}}}\frac{1}{{{n^2}}}} \end{array}} \right]$

We know that a sufficient condition for $\left( {{{\mathbf{x}}_0},{{\mathbf{y}}_0}} \right)$ to be a minimum of $f$ is that all of its principal minors must satisfy $\left| {{H_3}} \right|,\left| {{H_4}} \right|, \ldots ,\left| {{H_{2\left| r \right| + 2}}} \right| > 0$. However $\left| {{H_3}} \right| = \left| {\begin{array}{*{20}{c}} 0&0&1 \\ 0&0&0 \\ 1&0&{\frac{2}{{{x_1} + {y_1}}}{{\left( {\frac{{n - 1}}{n}} \right)}^2}} \end{array}} \right| = 0$.

Is there another way to tackle this problem/show that $\frac{1}{n}$ is the minimal value?

I'd also like to show that for $g:{\left[ {0,1} \right]^{\left| R \right|}} \times {\left[ {0,1} \right]^{\left| R \right|}} \times {\left[ {0,1} \right]^{\left| R \right|}} \to \mathbb{R},g\left( {{\mathbf{x}},{\mathbf{y}},{\mathbf{z}}} \right) = \sum\limits_r {\frac{{{x_r}{y_r}}}{{{x_r} + {y_r} + {z_r}}}}$ and constraints $1 \geqslant {x_r} > 0,\forall {x_r} \in R,1 \geqslant {y_r} \geqslant 0,\forall {y_r} \in R,1 \geqslant {z_r} \geqslant 0,\forall {z_r} \in R$, $\sum\limits_r {{x_r}} = 1$, $\sum\limits_r {{y_r}} = 1$ and $\sum\limits_r {{z_r}} = n - 2$, where $n \in \mathbb{N},n \geqslant 3$, it follows that $g\left( {{\mathbf{x}},{\mathbf{y}},{\mathbf{z}}} \right) \leqslant \frac{1}{n}$ for all ${\mathbf{x}},{\mathbf{y}},{\mathbf{z}} \in {\left[ {0,1} \right]^{\left| R \right|}}$ satisfying the constraints above.

## 1 Answer

Another way is to use Cauchy Schwarz inequality which implies: $$\left(\sum\limits_r {\frac{{x_r^2}}{{{x_r} + {y_r}}}}\right)\left(\sum_r (x_r + y_r\right)\ge \left(\sum_r x_r \right)^2$$

$$\implies f\left( {{\mathbf{x}},{\mathbf{y}}} \right)(1+ n-1) \ge 1$$

$$\implies f\left( {{\mathbf{x}},{\mathbf{y}}} \right) \ge \frac1n$$

• Brilliant. Any suggestion for the other case? – Alen Dec 14 '13 at 17:25
• You have found the critical point and its value well. However I don't see any easy way to confirm it is a minimum using your bordered Hessian. – Macavity Dec 14 '13 at 17:43
• It's really irrelevant how I prove it, and your proof is very elegant. I am interested in how would I go about proving that $g$ defined above has the maximum equal to $\frac{1}{n}$ (there is the same problem with the Hessian matrix when using Lagrange function) – Alen Dec 14 '13 at 17:48
• Oh, hadn't thought about the 2nd function. Will try in a bit and post if I find a solution. – Macavity Dec 14 '13 at 17:59
• Somehow I don't think I'll get an answer here, I'll post another question – Alen Dec 14 '13 at 22:33