# Minimum value of $x+4z$ subject to the constraint $x^2+y^2+z^2\leq 2$?

Consider the following problem:

Let $f:{\mathbb R}^3 \to{\mathbb R}$ be $$f(x,y,z)=x+4z$$ where $$x^2+y^2+z^2\leq 2.$$ Find the minimum of $f$.

This is similar to the question here. However, since this is not an analytic function with complex variable, one may not be able to use the "Maximum modulus principle".

What I think is that one may rewrite the inequality constraint $x^2+y^2+z^2\leq 2$ as $$x^2+y^2+z^2=2-\delta\qquad \delta\in[0,2]$$ then one can use the "Lagrange Multiplier Method" with the parameter $\delta$. Or one can do it on the xOz plane with the geometric meaning of $C$ in $C=x+4z$.

Is there any other way better than the idea above to solve this problem?

-
I'm not an expert in the field, but since $y$ is not involved in $f$ and you want minimize a linear function in $x,z$ you can assume $y=0$, $x^2 + z^2 =2$ and $x,z\leq 0$. So, you are reduced to the condition $z=\sqrt{2-x^2}$, and you want minimize $f(x)=x + 4 \sqrt{2-x^2}$ for $x\in [-\sqrt{2},0]$. –  Giovanni De Gaetano Jun 6 '11 at 16:20
You switch $1$ and $3$ in $F$ which is from $R^3$ to $R$, not the other way around. –  Luboš Motl Jun 6 '11 at 16:27
Calculating: $f(x)'=0$ for $x=-1$, since $f(0)=4\sqrt{2}$, $f(-1)=3$ and $f(-\sqrt{2})=-\sqrt{2}$, the function is minimized for $x=-\sqrt{2}, z=0, y=0$. Am I right? –  Giovanni De Gaetano Jun 6 '11 at 16:27
@Luboš: I just corrected that - good eye. –  mixedmath Jun 6 '11 at 16:29
As the function $f(x,y,z)$ does not have any extremal point on $\mathbb{R}^3$ the minimum will be on the boundary. Your problem reduces to the problem of minimizing $f(x,y,z)$ subject to the constraint $x^2+y^2+z^2=2$ which can be done with the method of Lagrange multiplier. –  Fabian Jun 6 '11 at 16:31

The function $x+4z$ increases most quickly (measured by the increase per unit length) in the direction of the vector $(1,0,4)$ - the coefficients of the monomials. The inequality $x^2+y^2+z^2 \leq 2$ is a solid ball with radius $\sqrt{2}$. So the minimum value of the linear function is on the boundary of the ball in the direction $(1,0,4)$ from the center which has to be a multiple that belongs to the surface, namely $$-\sqrt{\frac{2}{17}} (1,0,4)$$ The minus sign was added to make it a minimum. The opposite point with the plus sign is a maximum. The minimum itself is $-\sqrt{34}$.

-

This answer is just meant to compare the solutions obtained by Lagrange multipliers versus elimination. Notice in the first that x and z are treated equally until we needed to solve { u = 2, x = 4z }, but in the second x was heavily favored the entire time. In the first, we only dealt with polynomials, but in the second we divided by square roots of 2−xx, so had to deal with much weirder formulas. Generally, the elimination method will rely on simpler rules (one-variable minimization is "easy"), while the Lagrange method will rely on simpler formulas, but require slightly more complicated ideas (normals to hyper-surfaces and such). If you can get your head around why Lagrange multipliers work, then they should be quite a bit simpler to actually compute.

## Lagrange multiplier

Minimize C = x + 4z subject to u = xx + yy + zz ≤ 2. If the minimum occurs when u < 2, then the constraint had no effect and can be ignore. So we minimize C over all x, y, z by finding critical points. ∇C = (1,0,4) is never equal to 0, is always defined and continuous, so C has no critical points within the feasible region (or outside it!). Hence the minimum must occur on the boundary, when u = 2. This is then directly a Lagrange multiplier problem: We want ∇C to be a multiple of ∇u = (2x, 2y, 2z). So we set (1,0,4) = λ(2x, 2y, 2z), and read off that y = 0, and z = 4x. One must still have u = 2, so 17xx = 2, and the solution is (x, y, z) = ±(√(2/17), 0, 4√(2/17)) ≈ (0.34, 0, 1.37) with minimum C = −17√(2/17) ≈ −5.83 and maximum C = +17√(2/17) ≈ +5.83.

## Elimination of variables

Minimize C = x + 4z subject to u = xx + yy + zz ≤ 2. Again the interior is not relevant, and neither is y, so we can work the smaller problem: Minimize C = x + 4z subject to xx + zz = 2, that is, minimize C(x) = x ± 4√(2−xx). Take derivatives to get C′(x) = 1 ± 4x/√(2−xx), which is 0, precisely when 4x = ±√(2−xx), that is, when 16xx = 2 − xx, that is, when x = ±√(2/17) ≈ 0.34 with minimum C = −17√(2/17) ≈ −5.83 and maximum C = +17√(2/17) ≈ +5.83.

-

Here is an idea: Consider the plane $x+4z=c$, for different values of c. Changing c will shift the plane, and clearly, $c$ is the variable we want to minimize. Thus, we seek the minimal $c$ such that the plane intersects the sphere with radius 2. Therefore, the minimizing plane must be a tangent plane to the sphere, otherwise, we decrease c a little and still intersect the sphere.

The normal of the plane is the vector $(1,0,4),$ and thus, the ray $t(1,0,4)$ must hit the point of tangency. Therefore, the minimal/maximal value is given when $x=t,z=4t$ and $t^2 + (4t)^2 = 2$. The second equation gives $t = \pm \sqrt{2/17}.$ Hence $c = -\sqrt{2/17}-4(4\sqrt{2/17}) = -17\sqrt{2/17} = -\sqrt{34},$ which is the minimum.

-

The constraint $x^2 + y^2 + z^2 \le 2$ is equivalent to the constraint $$(x + 4z)^2 + (4x - z)^2 + 17y^2 \le 34$$

and this gives $x + 4z \ge - \sqrt{34}$ with equality when $y = 4x - z = 0$.

The lesson to take away from this argument is that balls are particularly easy to deal with because they can be rotated.

-
Hmm, I like your "magic" equivalent constraint from the algebraic manipulation. But I don't quite understand how the ball being able to be rotated is used here. –  Jack Oct 31 '11 at 23:23
@Jack: the equivalent constraint comes from a rotation of the problem about the $y$-axis, which involves a change of coordinates involving $x$ and $z$. Are you familiar with rotation matrices? –  Qiaochu Yuan Nov 1 '11 at 2:14
Let me write down what I understand so far from you "rotation". The equivalent constraint can written as $$(\frac{x+4z}{\sqrt{17}})^2+(\frac{4x-z}{\sqrt{17}})^2+y^2\leq 2.$$ And hence the coordinates change is $$u = \frac{x+4z}{\sqrt{17}},~v = \frac{4x-z}{\sqrt{17}}, ~y = y$$ –  Jack Nov 1 '11 at 3:34
@Jack: correct. –  Qiaochu Yuan Nov 1 '11 at 4:23

You should do the standard derivative test and see if any results come up within your region. You should then perform a Lagrange Multiplier Method on the boundary, i.e. on $x^2 + y^2 + z^2 = 2$. Because it's a compact place, you will have a max and a min, and it will either be on the interior or on the boundary.

One quickly notes that there is no need to perform the so-called second derivative test (which is annoying in higher dimensions), but should instead just compare the maxima and minima found.

Or you could be witty and realize that the gradient is constant - so follow it until it hits the boundary.

-

The other answers cover how to solve this with Lagrange multipliers, but I'd like to point out how the problem generalizes, using vector notation. If $\mathbf{x}=(1,0,4)$ and $r=\sqrt{2}$, then problem can be expressed: $$\min_{\|\mathbf{y}\|_2 \le r} \ \langle \mathbf{x}, \mathbf{y}\rangle = -r\|\mathbf{x}\|_{2}$$ Where the argmin is $-r\mathbf{x}/\|\mathbf{x}\|_2$. This is related to a problem that anyone familiar with analysis should know by heart: $$\max_{\|\mathbf{y}\|_2 \le 1} \ \langle \mathbf{x}, \mathbf{y}\rangle = \|\mathbf{x}\|_{2}$$ Where the argmax is $\mathbf{x}/\|\mathbf{x}\|_2$. The latter problem is particularly important because it's the definition of a dual norm, and it shows that the 2-norm is self-dual.

-