0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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$$

$\endgroup$
  • $\begingroup$ Brilliant. Any suggestion for the other case? $\endgroup$ – Alen Dec 14 '13 at 17:25
  • $\begingroup$ 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. $\endgroup$ – Macavity Dec 14 '13 at 17:43
  • $\begingroup$ 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) $\endgroup$ – Alen Dec 14 '13 at 17:48
  • $\begingroup$ Oh, hadn't thought about the 2nd function. Will try in a bit and post if I find a solution. $\endgroup$ – Macavity Dec 14 '13 at 17:59
  • $\begingroup$ Somehow I don't think I'll get an answer here, I'll post another question $\endgroup$ – Alen Dec 14 '13 at 22:33

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.