3
$\begingroup$

Find the max of a function $$f(x_1, x_2,...,x_m)=x_1 x_2 \cdots x_m$$ when $x_1^2+x_2^2+ \cdots +x_m^2=1$

I am looking for unique solutions. So far I've tried two different ways.

One of them was with Lagrange multiplier but there seem to be quite too many variables and I couldn't express $x_1,...,x_m$ separately.

The second one solution is with the Inequality of arithmetic and geometric means.

$$\frac{x_1^2+...+x_m^2}{m}\ge \sqrt[m]{x_1^2 \cdots x_m^2} \implies \frac{1}{m} \ge \sqrt[m]{x_1^2 \cdots x_m^2}=(x_1 \cdots x_m)^{\frac{2}{m}} \implies $$ $$x_1 \cdots x_m \le \frac{1}{m^{\frac{m}{2}}}$$ So we can assume that $$\max f(x_1, x_2,...,x_m)=\frac{1}{m^{\frac{m}{2}}} \quad \forall x_i=\frac{1}{\sqrt m}, \quad i=1,2,...,m.$$

I'd love to know if somebody solved this exercise with Langrange multiplier or in other way. Thanks in advance!

$\endgroup$
  • $\begingroup$ Note: $x_i$ don't have to be positive. We can assume they are positive without loss of generality however. $\endgroup$ – Jakobian Feb 27 at 18:42
5
$\begingroup$

$$x_1x_2...x_m\neq\sqrt{x_1^2x_2^2...x_m^2}$$

The right way it's the following:

By AM-GM $$x_1x_2...x_m\leq\sqrt{x_1^2x_2^2...x_m^2}\leq\sqrt{\left(\frac{x_1^2+x_2^2+...+x_m^2}{m}\right)^m}=\frac{1}{m^{\frac{m}{2}}}$$ The equality occurs for $x_1=x_2=...=x_m=\frac{1}{\sqrt{m}},$ which says that we got a maximal value.

$\endgroup$
  • $\begingroup$ That's basically the answer in OPs question. $\endgroup$ – Thomas Andrews Feb 27 at 18:50
  • $\begingroup$ @Thomas Andrews See please better our solutions. They are different in some point. $\endgroup$ – Michael Rozenberg Feb 27 at 18:51
3
$\begingroup$

Let $g(x) = ||x||_2^2 - 1 = 0$ be the constraint. $\nabla g(x) = 2x$, $$\nabla f(x)= (f(x)/x_1,\dots,f(x)/x_m) = \lambda \nabla g(x) = 2\lambda x.$$ $$\frac{x_1\cdots x_m}{x_i} = 2 \lambda x_i \\ x_1\cdots x_m = 2 \lambda x_i^2$$ Observe the the LHS is symmetric by interchange of indices $i$ and $j$ in $\{1,\dots,m\}$, so $x_i = \pm x_j$. Sum the above inequality over $i$ to get $m x_1 \cdots x_m = 2 \lambda$. This should give $|x_i| = \sqrt[m]{\dfrac{2|\lambda|}{m}}$.

Substitute this back to $g(x) = 0$: $m \cdot \sqrt[m]{\dfrac{4\lambda^2}{m^2}} = 1,$ so $\dfrac{2|\lambda|}{m} = \pm \dfrac{1}{\sqrt{m^m}},$ giving a critical point $x^* = \left(\dfrac{1}{\sqrt{m}},\dots,\dfrac{1}{\sqrt{m}}\right)$ when $\lambda^* = \dfrac{m^{1-m/2}}{2}$, which is the same as the one found by AM-GM inequality in the question body.

Evaluating the objective at $x^*$, we find that $f(x^*) = x_1^* x_2^* \dots x_m^* = \dfrac{1}{\sqrt{m^m}}$.

To determine whether this is a local maximum, define the Lagrangian

$$\begin{aligned}{\mathcal {L}}(x,\lambda) &= f(x)-\lambda g(x)\\ \nabla{\cal L}(x,\lambda) &= \left({\frac {\partial {\mathcal {L}}}{\partial x}},{\frac {\partial {\mathcal {L}}}{\partial \lambda }}\right) = \left(\frac{x_1\cdots x_m}{x_1} - 2\lambda x_1, \dots, \frac{x_1\cdots x_m}{x_m} - 2\lambda x_m, -\sum_{i=1}^m x_i^2 \right) \end{aligned}$$

We compute the Hessian matrix of ${\cal L}$ at $x^*$. For all $i,j \in \{1,\dots, m\}$ with $i \ne j$, \begin{alignat}{2} \frac{\partial^2{\mathcal {L}}}{\partial x_i^2} &= -2\lambda \quad & \frac{\partial^2{\mathcal {L}}}{\partial x_i \partial x_j} &= \frac{x_1\cdots x_m}{x_i x_j} \\ \frac{\partial^2{\mathcal {L}}}{\partial \lambda^2} &= 0 & \frac{\partial^2{\mathcal {L}}}{\partial \lambda \partial x_i} &= -2 x_i \end{alignat}

This gives a symmetric matrix

\begin{bmatrix} -2\lambda & \dfrac{x_1\cdots x_m}{x_1 x_2} & \dots & \dfrac{x_1\cdots x_m}{x_1 x_m} & -2 x_1 \\ \dfrac{x_1\cdots x_m}{x_1 x_2} & -2\lambda & \dots & \dfrac{x_1\cdots x_m}{x_2 x_m} & -2 x_2 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ \dfrac{x_1\cdots x_m}{x_1 x_m} & \dfrac{x_1\cdots x_m}{x_2 x_m} & \dots & -2\lambda & -2 x_m \\ -2x_1 & -2x_2 & \dots & -2x_m & 0 \end{bmatrix}

Substituting $(x^*,\lambda^*) = (m^{-1/2},\dots,m^{-1/2},m^{1-m/2}/2)$, we have

$$H = \begin{bmatrix} -m^{1-m/2} & m^{1-m/2} & \dots & m^{1-m/2} & -2 m^{-1/2} \\ m^{1-m/2} & -m^{1-m/2} & \dots & m^{1-m/2} & -2 m^{-1/2} \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ m^{1-m/2} & m^{1-m/2} & \dots & -m^{1-m/2} & -2 m^{-1/2} \\ -2 m^{-1/2} & -2 m^{-1/2} & \dots & -2 m^{-1/2} & 0 \end{bmatrix}$$

For $k = 1,\dots,m$, let $M_k$ be the $k$-th leading principal minor of $-H$. Then the $M_k$'s are whose associated polynomial is $f(x) = C \left( 1-\sum\limits_{\ell=1}^{k-1} x^\ell \right)$, where $C = m^{1-m/2} \in (0,1)$ for $m \ge 3$.

Let $\omega = e^{2\pi i /k}$. A simple geometric sum would give

$$ \sum_{\ell=0}^{k-1} (\omega^j)^\ell = \begin{cases} 0 &\text{ if } j = 1,\dots,k-1 \\ k &\text{ if } j = 0 \end{cases} $$

Then $\det(M_k) = \prod\limits_{j = 0}^{k-1} f(\omega^j) = C^k \cdot [-(k-2)] \cdot 2^{k-1} < 0$ for all $k > 3$.

$\endgroup$
  • $\begingroup$ Are you sure? Why these give a maximal value? $\endgroup$ – Michael Rozenberg Feb 27 at 18:56
  • $\begingroup$ @MichaelRozenberg Take one of the $x_i = 0$, say $(1,0,\dots,0)$, then that gives objective value zero, so the $x$ found by Lagrange multipliers is not a constrained minimum. $\endgroup$ – GNUSupporter 8964民主女神 地下教會 Feb 27 at 19:05
  • $\begingroup$ Maybe we got a saddle point... Also, maybe a maximum occurs in another point. Your solution is very not full. $\endgroup$ – Michael Rozenberg Feb 27 at 19:08
  • $\begingroup$ I don't understand how you get $\nabla f(x)=(1,1,\dots,1)$ Why isn't it $\left({f(x)\over x_1}, \dots, {f(x)\over x_m}\right)?$ $\endgroup$ – saulspatz Feb 27 at 19:45
  • $\begingroup$ @saulspatz Nice catch! I'm rewriting my solution. $\endgroup$ – GNUSupporter 8964民主女神 地下教會 Feb 27 at 19:47
1
$\begingroup$

Either the function and the constraint are symmetrical wrt $x_1=x_2= \cdots=x_m$.

The function $f(x_1,\cdots,x_m)=x_1 x_2 \cdots x_m=s$ is one of the sheets of a 2-sheets hyperboloid, of revolution around the axis above, with minimum (apex) at $x_1= \cdots =x_m=s^{1/m}$.

The constraint is a sphere.

Thus ..

$\endgroup$
1
$\begingroup$

I would do it another way. The symmetry suggests that the maximum will occur when all the coordinates are equal, so I would try to show that if two coordinates say $x_i$ and $x_j$ are different, then we can increase the objective function by replacing both of them by some value $c$ and leaving the other coordinates the same. Since we have to maintain the constraint, this comes down to showing that the maximum of $g(x,y)=xy$ subject to $x^2+y^2=k$ is attained when $x=y$ This is easy with Lagrange multipliers.

Once we know that $x_1=x_2=\cdots=x_m$ we solve for the common value.

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