Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

?

share|improve this question
2  
I am sure there is an example of using Lagrange multipliers with two constraints in pretty much any calculus textbook (Google gives me, for the obvious query, a list of results such that I find such examples in 4 of the first 5 results) Try to follow any such example out there, explain to us what you did and then we can help you with what you were not able to do. –  Mariano Suárez-Alvarez Oct 20 '10 at 19:56
    
i made my lagrange function as a0(x1^3+...+xn^3)+a1(x1+...+xn)+a2(x1^2+...xn^2) where a0, a1, a2 are lambda 0, 1, 2 then i take partial derivative for xi's (dL/dxi)=a0(3xi^2)+a1+2a2(xi)=0 –  nur Oct 20 '10 at 20:05
    
i made my lagrange function as a0(x1^3+...+xn^3)+a1(x1+...+xn)+a2(x1^2+...xn^2) where a0, a1, a2 are lambda 0, 1, 2 then i take partial derivative for xi's (dL/dxi)=a0(3xi^2)+a1+2a2(xi)=0 i now i have n such equations and 2 constraints but i cannot eliminate a1 and a2 to get a relation between xi's. so what can i do? –  nur Oct 20 '10 at 20:11
    
Your question $\min f(x_{1},x_{2},\ldots ,x_{n})=\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})=-\left( \sum_{i=1}^{n-1}x_{i}\right) ^{3}+\sum_{i=1}^{n-1}x_{i}^{3}$ s.t. $\left( \sum_{i=1}^{n-1}x_{i}\right) ^{2}-n+\sum_{i=1}^{n-1}x_{i}^{2}=0.$. –  Américo Tavares Oct 20 '10 at 20:18
1  
Why don't you explain that in the body of the question, writing down the system of equations you got in detail, and change the title to "how do I solve this system of equations?". From what you wrote, it is clear that you don't have any problems with Lagrange multipliers :) –  Mariano Suárez-Alvarez Oct 20 '10 at 20:19

2 Answers 2

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.

share|improve this answer

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

share|improve this answer
    
Films: It seems to me there's a typo in the first equation of $aX+bY=0$ $aX^{2}+bY^{2}=0$. It should be $aX^{2}+bY^{2}=n$. Since $aX^{2}+bY^{2}=a\frac{b}{a}+b\frac{a}{b}=b+a=n$ and $a^{2}X^{2}+b^{2}Y^{2}+2abXY=a^{2}\frac{b}{a}+b^{2}\frac{a}{b}-2ab=ab+ab-2ab=0$ the system has the solutions you present $X^{2}=\frac{b}{a} $ and $Y^{2}=\frac{a}{b}$. –  Américo Tavares Oct 22 '10 at 23:08
    
+1 for the clever solution. –  Américo Tavares Oct 23 '10 at 1:10

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.