0
$\begingroup$

Using method of Lagrange multipliers, I am looking to minimise the function

$f(x_1,...,x_n)=\prod_{i=1}^n(1+x_i)$ with the side condition $g(x_1,...,x_n)=\prod_{i=1}^nx_i-q^n=0$.

My goal is to show that $f$ is minimal when $x_i=q$ for all $i$.

I have $$\nabla g=(\prod_{i=1, i \neq j}^nx_i)_{1\leq j \leq n}$$ $$\nabla f=(\prod_{i=1, i \neq j}^n(1+x_i))_{1\leq j \leq n}$$

Now I know that $\nabla f = \lambda \nabla g$, so for all $j$:

$$\prod_{i=1, i \neq j}^n(1+x_i)=\lambda\prod_{i=1, i \neq j}^nx_i$$

and since all $x_i>0$

$$\prod_{i=1, i \neq j}^n(1+\frac{1}{x_i})=\lambda$$

Since the products are equal for all $j$, it follows that the $x_1=x_2=...=x_n$ and thus $x_1...x_n=x_1^n=q^n \iff x_i=q$ for all $i$. So far so good.

My problem is to show that it is a minimum: The entries of the Hessian are

$$\partial_{x_i} ^2f=0$$

$$\partial_{x_j} \partial_{x_k}f=\prod_{i=1, i \neq j,i \neq k}^n(1+x_i)>0$$

So I have a matrix with zero diagonal and positive entries everywhere else. This matrix is not positive definite, as is easily seen in the $2 \times 2$ case.

Did I do any mistakes? How do I argue that it is a minimum?

$\endgroup$
  • 4
    $\begingroup$ You could also try HUYGEN’S INEQUALITY, stating that for $x_i\geq0$ $$(1+x_1)(1+x_2)...(1+x_n)\geq\left(1+\left(x_1x_2...x_n\right)^{\frac{1}{n}}\right)^n$$ $\endgroup$ – rtybase Jul 23 '18 at 21:49
  • $\begingroup$ Even if the Hessian would signalize a local minimum at $x_i=q$ $(i\in[n])$ you could not be sure that it is actually the global minimum. $\endgroup$ – Christian Blatter Jul 24 '18 at 9:09
2
$\begingroup$

The associated Bordered Hessian matrix is $$ \left[ \begin{array}{c|ccc} 0 & (1+q)^{n-1} & (1+q)^{n-1} & (1+q)^{n-1} &\dots \\\hline (1+q)^{n-1} & 0 & (1+q)^{n-2} & (1+q)^{n-2} &\dots \\ (1+q)^{n-1} & (1+q)^{n-2} & 0 & (1+q)^{n-2} &\dots \\ (1+q)^{n-1} & (1+q)^{n-2} & (1+q)^{n-2} & 0 &\dots \\ \vdots & \vdots & \vdots & \vdots & \ddots \end{array} \right] $$ Up to a multiplicative constant, the above has the shape $$ A = \left[ \begin{array}{c|cccc} 0 & a & a & a &\dots & a \\\hline a & 0 & 1 & 1 &\dots & 1\\ a & 1 & 0 & 1 &\dots & 1\\ a & 1 & 1 & 0 &\dots & 1\\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots\\ a &1 & 1 & 1 & \dots & 0 \end{array} \right]\ . $$ It is an $(n+1)\times(n+1)$ matrix, and its characteristic polynomial is $$ P_A(x) = (x+1)^{n-1}(x^2-(n-1)x-na^2)\ . $$ So exactly one eigenvalue is positive. Let $C$ be the matrix: $$ C= \left[\begin{array}{c|cccc} 1 & 0 & 0 & 0 & \dots & 0 \\\hline 0 & 1 & 0 & 0 & \ddots & 0 \\ 0 & -1 & 1 & 0 & \ddots & 0 \\ 0 & 0 & -1 & 1 & \ddots & 0 \\ \vdots & \ddots & \ddots & \ddots & \ddots & \vdots \\ 0 & 0 & 0 & 0 & -1 & 1 \end{array}\right]\ . $$ ($C$ has ones on the diagonal, in the $n\times n$ block "minus ones" immediately under the diagonal, else zeros.) Then conjugation with $C$ gives: $$ CAC^{-1} = \left[\begin{array}{c|c|ccc} 0 & na & (n-1)a & (n-2)a & \dots & a \\\hline a & n-1 & (n-1) & (n-2) & \dots & 1 \\\hline 0 & 0 & -1 & 0 & \dots & 0 \\ 0 & 0 & 0 & -1 & \dots & 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & 0 & \dots & -1 \end{array}\right]\ . $$ As as a quadratic form, $A$ changes by the base change action of $C$ into $$ CAC^t = \left[ \begin{array}{cc|cccc} 0 & a & 0 & 0 & 0 &\dots & 0\\ a & 0 & 1 & 0 & 0 &\ddots & 0\\\hline 0 & 1 & -2 & 1 & 0 &\ddots & 0\\ 0 & 0 & 1 & -2 & 1 &\ddots & 0\\ 0 & 0 & 0 & 1 & -2 &\ddots & 0\\ \vdots & \ddots & \ddots & \ddots & \ddots & \ddots & \vdots\\ 0 & 0 & 0 & 0 & 0 & \dots & -2 \end{array} \right]\ . $$


If Lagrange multiplicators are used, the optimization problem is not regarging the "full function $f+\lambda g$", and the Hessian matrix of $f+\lambda g$ may fulfill sufficient positivity / negativity conditions for only a "tangential null space". The idea is roughly to have a "conditional Taylor polynomial of order two in the $x$-variables", that still allows to deduce a local extremal value.

In our case, the condition is $x_1x_2\dots x_n=q^n$. Formally, writing $x_1=q+h_1+O(h_1^2)$ and analogously for the other variables, we get the relation $$ \prod_{1\le k\le n}(q+h_k+O(h_k^2))=q^n\ , $$ so formally $q^{n-1}(h_1+h_2+\dots+h_n)+O(|h|^2)=0$.

In the given sitation, the matrix $C$ provides an $(n-1)\times (n-1)$ block which is built with vectors from the null space. Eventually, one can work to convert this beginning into a proof.


The most simple solution to the minimum problem is to observe that if two component values in $x=(x_1,x_2,x_3,\dots)$ are not equal, say $x_1\ne x_2$ without loss of generality, then we can redistribute $x_1x_2=c^2$ in a new point $x_c:=(c,c,x_3,\dots)$ and we get a smaller value because $$ (1+x_1)(1+x_2)-(1+c)^2=x_1+x_2-2c=(\sqrt x_1-\sqrt x_2)^2>0\ . $$ (Because of this simpler argument i did not insist to complete the proof using Lagrange multiplicators. Search please the net for the bordered matrix to see many explicit examples.)

$\endgroup$
1
$\begingroup$

Considering the Lagrangian

$$ L(x,\lambda) = \prod_k^n(x_k+1)-(q+1)^n+\lambda\left(\prod_k^n x_k - q^n\right) $$

we have the stationary conditions

$$ L_{x_k} = \prod_{j\ne k}^n(x_j+1)+\lambda\prod_{j\ne k}^n x_j = 0 $$

or

$$ \lambda = -\frac{\prod_{j\ne k}^n(x_j+1)}{\prod_{j\ne k}^n x_j} $$

hence

$$ \lambda = -\frac{\prod_{j\ne k}^n(x_j+1)}{\prod_{j\ne k}^n x_j} = -\frac{\prod_{i\ne k}^n(x_i+1)}{\prod_{i\ne k}^n x_i}\Rightarrow \frac{x_j}{x_j+1} = \frac{x_i}{x_i+1}\Rightarrow x_1=x_2=\cdots=x_n = q $$

This stationary point is a saddle point for $\prod_k^n(x_k+1)-(q+1)^n$ as can be checked easily analyzing the behavior of

$$ (q+\epsilon+1)^n-(q+1)^n $$

for $\epsilon \in [-1,1]$

This is not a problem because the qualification should be done with the Hessian for

$$ F(x)=\left(\prod_k^n(x_k+1)-(q+1)^n\right)\circ \left(\prod_k^n x_k - q^n\right) $$

I leave it here in the hope of finding a suitable expression for such hessian.

NOTE

For the case $n = 3$ we have

$$ \left((x+1)(y+1)(z+1)-(q+1)^3\right)\circ\left(z=\frac{q^3}{x y}\right) = (x+1) (y+1) \left(\frac{q^3}{x y}+1\right)-(q+1)^3 $$

with Hessian $H$ evaluated at $x=y=z=q$

$$ H = \left( \begin{array}{cc} 2+\frac{2}{q} & 1+\frac{1}{q} \\ 1+\frac{1}{q} & 2+\frac{2}{q} \\ \end{array} \right) $$

with eigenvalues

$$ \left\{3 \left(\frac{1}{q}+1\right),\frac{1}{q}+1\right\} $$

characterizing a minimum.

$\endgroup$
  • $\begingroup$ Why is the Hessian of the composite function the important one for this problem? $\endgroup$ – B.Swan Jul 24 '18 at 14:52
  • $\begingroup$ I did not know that one has to be consider the Bordered Hessian! $\endgroup$ – B.Swan Jul 24 '18 at 15:01
1
$\begingroup$

Proof

Apply Carison's inequality, which also could be viewed as a generalized form of Cauchy-Schwarz inequality

$$(x_1+y_1+\cdots)(x_2+y_2+\cdots)\cdots(x_n+y_n+\cdots)\geq \left[\left(\prod_{i=1}^n x_i\right)^{\frac{1}{n}}+\left(\prod_{i=1}^n y_i\right)^{\frac{1}{n}}+\cdots\right]^n,$$where $x_i,y_i,\cdots\geq0$ for $i=1,2,\cdots$

Thus, $$(1+x_1)\cdots(1+x_n)\geq \left[\left(\prod_{i=1}^n 1\right)^{\frac{1}{n}}+\left(\prod_{i=1}^n x_i\right)^{\frac{1}{n}}\right]^{n}=\left[1+(q^n)^{\frac{1}{n}}\right]^n=(1+q)^n.$$

$\endgroup$
0
$\begingroup$

Since an answer with the Lagranian method has been given, here is an alternative proof using the Weighted AM-GM Inequality. Note that $$\frac{q}{1+q}\,\left(1+x_i\right)=\frac{1}{1+q}\cdot q+\frac{q}{1+q}\cdot x_i\geq q^{\frac{1}{1+q}}\,x_i^{\frac{q}{1+q}}\text{ for }i=1,2,\ldots,n\,.$$ Therefore, $$1+x_i\geq (1+q)\,\left(\frac{x_i}{q}\right)^{\frac{q}{1+q}}\text{ for }i=1,2,\ldots,n\,.$$ Consequently, $$\prod_{i=1}^n\,\left(1+x_i\right)\geq (1+q)^n\,\left(\frac{\prod\limits_{i=1}^n\,x_i}{q^n}\right)^{\frac{q}{1+q}}=(1+q)^n\,.$$

$\endgroup$

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.