# Find the minimum value of $x_1^2+x_2^2+x_3^2+x_4^2$ subject to $x_1+x_2+x_3+x_4=a$ and $x_1-x_2+x_3-x_4=b$.

Question: Find the minimum value of $$x_1^2+x_2^2+x_3^2+x_4^2$$ subject to $$x_1+x_2+x_3+x_4=a$$ and $$x_1-x_2+x_3-x_4=b$$.

My attempt: It can be easily seen that $$x_1+x_3=\frac{a+b}{2}$$ and $$x_2+x_4=\frac{a-b}{2}$$. Further, the expression $$[x_1^2+x_2^2+x_3^2+x_4^2]$$ can be written as $$[(x_1+x_3)^2+(x_2+x_4)^2-2(x_1x_3+x_2x_4)].$$ I'm having trouble eliminating $$(x_1x_3+x_2x_4)$$ from this expression. Failing to make any sense out of this, I manipulated the existing expressions to deduce $$x_1x_2+x_1x_4+x_2x_3+x_3x_4=\frac{a^2-b^2}{4}$$and $$(x_1^2+x_3^2)-(x_2^2+x_4^2)+2(x_1x_3-x_2x_4)=a\cdot b$$Beyond this, I cannot make sense of the expressions anymore. I have no idea how to proceed with simplifying the expressions further, and would appreciate hints in the same direction.

• By Titu's Lemma, $x_1^2+x_2^2+x_3^2+x_4^2 \geq \frac{(x_1+x_2+x_3+x_4)^2}{4}$
– V.G
Commented Aug 14, 2020 at 10:28
• @ABCD So the minimum value is supposed to be $\frac{a^2}{4}$? Commented Aug 14, 2020 at 10:30
• No, actually due to the other equation, bounds will change as shown by @Michael Rozenberg. He has used the same thing.
– V.G
Commented Aug 14, 2020 at 10:31
• To anyone who stumbles upon this question: Consider reading and upvoting all the excellent, creative solutions to this problem. Commented Aug 14, 2020 at 11:22

## 4 Answers

By your work and by C-S $$x_1^2+x_2^2+x_3^2+x_4^2\geq\frac{1}{2}\left(\frac{a+b}{2}\right)^2+\frac{1}{2}\left(\frac{a-b}{2}\right)^2=\frac{a^2+b^2}{4}.$$ The equality occurs for $$x_1=x_3=\frac{a+b}{4}$$ and $$x_2=x_4=\frac{a-b}{4},$$ which says that we got a minimal value.

We used the following C-S: $$x^2+y^2=\frac{1}{2}(1^2+1^2)(x^2+y^2)\geq\frac{1}{2}(x+y)^2.$$

Why not use a Lagrangian and find an optimal value for a constrained optimization problem?

That is, $$\begin{array}{cl} \min_{x} & x^T x \\ \text{subject to} & v_1^T x = a, v_2^T x = b \end{array}$$ where $$x = [\begin{array}{cccc} x_1 & x_2 & x_3 & x_4 \end{array}]^T$$, $$v_1 = [\begin{array}{cccc} 1 & 1 & 1 & 1 \end{array}]^T$$, and $$v_2 = [\begin{array}{cccc} 1 & -1 & 1 & -1 \end{array}]^T$$.

The Lagrangian is given by $$L = x^T x + \lambda_1 (a-v_1^T x) + \lambda_2 (b-v_2^T x).$$ The gradient of $$L$$ is $$\nabla_x L = 2x - \lambda_1 v_1 - \lambda_2 v_2$$, setting it to zero gives the optimal solution $$x^* = \frac{\lambda_1 v_1 + \lambda_2 v_2}{2}.$$ The solution must satisfy the constraints $$v_1^T x^* = a$$ and $$v_2^T x^* = b$$, which gives us two equations $$\begin{array}{ccl} \displaystyle \frac{\lambda_1 v_1^T v_1 + \lambda_2 v_1^T v_2}{2} &=& a \\ \displaystyle \frac{\lambda_1 v_2^T v_1 + \lambda_2 v_2^T v_2}{2} &=& b. \end{array}$$ By solving these equations, we obtain $$\lambda_1 = a/2$$ and $$\lambda_2 = b/2$$. (Notice that $$v_1^T v_2 = v_2^T v_1 = 0$$ and $$v_1^T v_1 = v_2^T v_2 = 4$$.)

Finally, the minimum value of $$x^T x$$ under the constraints $$v_1^T x = a$$ and $$v_2^T x = b$$ is given by $$\begin{array}{ccl} x^T x &=& \displaystyle \left(\frac{a v_1 + b v_2}{4}\right)^T \left(\frac{a v_1 + b v_2}{4}\right) \\ &=& \displaystyle \frac{a^2 + b^2}{4}. \end{array}$$

Define $$p=x_1+x_2$$, $$q=x_3+x_4$$, $$r=x_1-x_2$$, $$s=x_3-x_4$$.

Restate the problem:

find the minimum of $$\frac{p^{2}+q^{2}+r^{2}+s^{2}}{2}$$ with constrain $$p+q=a$$ and $$r+s=b$$.

QM - AM inequality:

$$\frac{p^{2}+q^{2}}{2}\geq\frac{(p+q)^{2}}{4}=\frac{a^{2}}{4}$$

$$\frac{r^{2}+s^{2}}{2}\geq\frac{(r^{2}+s^{2})^{2}}{4}=\frac{b^{2}}{4}$$

$$\frac{p^{2}+q^{2}+r^{2}+s^{2}}{2}\geq\frac{a^{2}+b^{2}}{4}$$

• Shouldn't $p+q=r$ and $r+s=b$ instead of what you've written? Commented Aug 14, 2020 at 11:31
• @Manan that is right, thank you my friend Commented Aug 14, 2020 at 11:32

Using algebra.

Use the two equality constraints to get $$x_3$$ and $$x_4$$ as linear functions of $$x_1$$ and $$x_2$$.

This makes

$$x_1^2+x_2^2+x_3^2+x_4^2=x_1^2+x_2^2+\frac{1}{4} (a+b-2 x_1)^2+\frac{1}{4} (-a+b+2 x_2)^2$$

Compute the partial derivatives wrt $$x_1$$ and $$x_2$$ and set them equal to $$0$$. This would give $$x_1=\frac {a+b}4$$ and $$x_2=\frac {a+b}4$$. So, for the minimum $$x_1^2+x_2^2+x_3^2+x_4^2=\frac {a^2+b^2}4$$