1
$\begingroup$

i couldn't do the following question for hours

minimize $\sum_{i=1}^{n}x_{i}^{3}$

s.t. $\sum_{i=1}^{n}x_{i}=0$ and $\sum_{i=1}^{n}x_{i}^{2}=n$.

by Lagrange multiplier rule

?

  • 0
    Should$n$'t the title be " ... for 2 ..." i$n$stead of " ... for more tha$n$ 2 ..."?2010-10-23

2 Answers 2

3

This is a development of my comment, changing the restraints from two to one.

Since $x_{n}=-\sum_{i=1}^{n-1}x_{i}$, the question "find

$\min \sum_{i=1}^{n}x_{i}^{3}$

s.t.

$\sum_{i=1}^{n}x_{i}=0$

and

\sum_{i=1}^{n}x_{i}^{2}=n\ "

is equivalent to find

$\min f(x_{1},x_{2},\ldots ,x_{n-1}),$

where $f(x_{1},x_{2},\ldots ,x_{n-1})=\left( \sum_{i=1}^{n-1}x_{i}^{3}\right) -\left( \sum_{i=1}^{n-1}x_{i}\right) ^{3}$

s.t.

$c(x_{1},x_{2},\ldots ,x_{n-1})=0,$

where

$c(x_{1},x_{2},\ldots ,x_{n-1})=\left( \sum_{i=1}^{n-1}x_{i}\right) ^{2}-n+\sum_{i=1}^{n-1}x_{i}^{2}=0.$

The conditions regarding first derivatives are

$\nabla f(x_{1},x_{2},\ldots ,x_{n-1})-\nabla c(x_{1},x_{2},\ldots ,x_{n-1})\lambda =0\qquad (\ast ),$

where

$\nabla f(x)=\begin{pmatrix}\frac{\partial f}{\partial x_{1}} & \ldots & \frac{\partial f}{\partial x_{n-1}}\end{pmatrix}^{T}$

$=% \begin{pmatrix} 3x_{1}^{2}-3\left( \sum_{i=1}^{n-1}x_{i}\right) ^{2} & \ldots & 3x_{n-1}^{2}-3\left( \sum_{i=1}^{n-1}x_{i}\right) ^{2}% \end{pmatrix}% ^{T}$

$\nabla c(x)=% \begin{pmatrix} \frac{\partial c}{\partial x_{1}} & \ldots & \frac{\partial c}{\partial x_{n-1}}% \end{pmatrix}% ^{T}$

$=% \begin{pmatrix} 2\left( \sum_{i=1}^{n-1}x_{i}\right) +2x_{1} & \ldots & 2\left( \sum_{i=1}^{n-1}x_{i}\right) +2x_{n-1}% \end{pmatrix}% ^{T}.$

Condition $(\ast )$ is

$3x_{1}^{2}-3\left( \sum_{i=1}^{n-1}x_{i}\right) ^{2}-2\lambda \left( \sum_{i=1}^{n-1}x_{i}\right) -\lambda 2x_{1}=0$

$\ldots $

$3x_{n-1}^{2}-3\left( \sum_{i=1}^{n-1}x_{i}\right) ^{2}-2\lambda \left( \sum_{i=1}^{n-1}x_{i}\right) -\lambda 2x_{n-1}=0.$

All these equations have the same form (the coefficients of $x_k$, $1\lt k\lt n-1$, are independent of $k$). Thus the solution is atained when all the $n-1$ variables are equal

$x_{1}=\ldots =x_{n-1}=x^{\ast }$

Hence, we have to solve the new system of two equations

$3(x^{\ast })^{2}-3\left( \sum_{i=1}^{n-1}x^{\ast }\right) ^{2}-2\lambda \left( \sum_{i=1}^{n-1}x^{\ast }\right) -2\lambda x^{\ast }=0\qquad (\ast \ast )$

$\left( \sum_{i=1}^{n-1}x^{\ast }\right) ^{2}-n+\sum_{i=1}^{n-1}(x^{\ast })^{2}=0.$

We obtain, successively

$3(x^{\ast })^{2}-3n+3\sum_{i=1}^{n}(x^{\ast })^{2}-2\lambda \left( \sum_{i=1}^{n-1}x^{\ast }\right) -2\lambda x^{\ast }=0$

$3(x^{\ast })^{2}-3n+3(x^{\ast })^{2}(n-1)-2\lambda x^{\ast }(n-1)-2\lambda x^{\ast }=0$

$(x^{\ast })^{2}(n-1)-1=0$

$x^{\ast }=x_{1}=\ldots =x_{n-1}=\pm \frac{1}{\sqrt{n-1}}.$

Therefore

$x_{n}=-\sum_{i=1}^{n-1}x_{i}=\mp \frac{n-1}{\sqrt{n-1}}.$

Since for $n>2$

$\left( \frac{1}{\sqrt{n-1}}\right) ^{3}-\left( \frac{n-1}{\sqrt{n-1}}% \right) ^{3}<-\left( \frac{1}{\sqrt{n-1}}\right) ^{3}+\left( \frac{n-1}{% \sqrt{n-1}}\right) ^{3},$

the minimum is obtained at

$x^{\ast }=x_{1}=\ldots =x_{n-1}=\frac{1}{\sqrt{n-1}},x_{n}=-\frac{n-1}{% \sqrt{n-1}}$

and its value is equal to

$\left( \frac{1}{\sqrt{n-1}}\right) ^{3}-\left( \frac{n-1}{\sqrt{n-1}}% \right) ^{3}.$


Added: The original problem in $n$ variables is the solution of $n$ equations

$\nabla f(x_{1},x_{2},\ldots ,x_{n})-\nabla c(x_{1},x_{2},\ldots ,x_{n})\lambda =0\qquad (\ast\ast\ast )$

plus the two conditions

$c_{1}(x_{1},x_{2},\ldots ,x_{n})=0$

$c_{2}(x_{1},x_{2},\ldots ,x_{n})=0,$

where

$\nabla f=% \begin{pmatrix} \frac{\partial f}{\partial x_{1}} & \ldots & \frac{\partial f}{\partial x_{n}}% \end{pmatrix}% ^{T}$

$\nabla c=% \begin{pmatrix} \left( \nabla c_{1}\right) ^{T} & \left( \nabla c_{2}\right) ^{T}% \end{pmatrix}% $

$\lambda =\begin{pmatrix} \lambda _{1} & \lambda _{2}\end{pmatrix}^{T}.$

Note: The equations would be similar for $m$ constraints $c_1,\dots ,c_m.$

Remark: Since I don't know how to write here matrices with more than one row, I wrote them in the transposed form.

2

Using Lagrange multipliers we get $x_i^2 = \lambda x + \mu$, so that $x_i$ can take only two values, say X > 0 and $Y < 0$ (we can't have $X=Y=0$ for obvious reasons). Suppose that $X$ is taken $a$ times, and $Y$ is taken $b = n-a$ times. We have

$aX + bY = 0$

$aX^2 + bY^2 = n$

You can check that the solution is

$X^2 = b/a, Y^2 = a/b$

The objective function that we want to minimize is

$aX^3 + bY^3 = b\sqrt{b/a} - a\sqrt{a/b}$

We want to make the first summand small and the second big. Note that as we increase $a$, the first summand becomes smaller, and the second one becomes bigger, so we might as well choose $a=n-1$ and $b=1$. So $X = 1/\sqrt{(n-1)}$ and $Y = -\sqrt{n-1}$.

Concluding, the optimum is obtained with the sequence $-\sqrt{n-1}, 1/\sqrt{(n-1)} \times (n-1)$, and the optimal value is

$ -(n-1)\sqrt{n-1} + 1/\sqrt{n-1} $

  • 0
    @user2987 I would help but unfortunately your question is not an easy one for me.2015-05-27