3
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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}$ $\endgroup$
    – V.G
    Commented Aug 14, 2020 at 10:28
  • 1
    $\begingroup$ @ABCD So the minimum value is supposed to be $\frac{a^2}{4}$? $\endgroup$
    – Manan
    Commented Aug 14, 2020 at 10:30
  • 1
    $\begingroup$ No, actually due to the other equation, bounds will change as shown by @Michael Rozenberg. He has used the same thing. $\endgroup$
    – V.G
    Commented Aug 14, 2020 at 10:31
  • $\begingroup$ To anyone who stumbles upon this question: Consider reading and upvoting all the excellent, creative solutions to this problem. $\endgroup$
    – Manan
    Commented Aug 14, 2020 at 11:22

4 Answers 4

4
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

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

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .