Minimize $x^2+y^2+z^2+w^2+2w(x+z)$ given certain constraints

Question

I am trying to figure out how to show that the minimum of $f(x,y,z,w)=x^2+y^2+z^2+w^2+2w(x+z),$ given that $x+y+z+w=1,$$ $$x+y\geq 0.7,$ and $x\geq 0, y\geq 0, z \geq 0, \text{ and } w\geq 0,$

is 0.335 and that it is achieved when $x=y=0.35,$ $z=0.3,$ and $w=0.$

Note that the partial derivatives of $f$ are $$\frac{\partial f}{\partial x}=2x+2w,$$ $$\frac{\partial f}{\partial y}=2y,$$ $$\frac{\partial f}{\partial z}=2z+2w,$$ and $$\frac{\partial f}{\partial w}=2x+2z+2w.$$

All of these are positive when the variables $x, y, z, w$ are all positive, meaning that this function is increasing with respect to all of it's variables when they are positive.

I think I can safely say that the minimum must occur when $x+y=0.7$, which means that $z+w=0.3$. Then $y=0.7-x$ and $w=0.3-z$. Substituting these into $f$ gives us $$g(x,z):=f(x,0.7-x,z,0.3-z)=2x^2-0.8x-2xz+0.58.$$

I believe that minimizing $f$ with the original constraints is equivalent to minimizing $g$ assuming that $0\leq x\leq 1$ and $0\leq z\leq 0.3.$ This, in fact, does lead to the right answer, but I want to make sure I haven't made a mistake. Thank you in advance.

Answer 1

It is equivalent to minimise the function

$$ f(x,y,z) = x^2+y^2+z^2+(1-x-y-z)^2+(1-x-y-z)(x+z).$$

over the polyhedron defined by the half spaces $x\geq 0,y\geq 0,z\geq 0,x+y \geq 0.7$ and $ 1 \geq x+y+z.$ To avoid confusion I will adopt the following definition

• I will call global minimum of $f$ is the minimum of $f$ over $\mathbb R^3$

• I will call local minimum of $f$ the minimum of $f$ over the polyhedron.

---

First expand and simplify the expression of $f$ to get

$$ f(x,y,z) = x^2 + 2y^2 + z^2 + xy + yz -x-2y-z + 1.$$

Let $a \in \mathbb R$ and consider the equation $f(x,y,z)= a$. You can show that this is the equation of an ellipsoid.

---

Define $E$ the closed volume defined by the ellipsoid (i.e. the filled ellipsoid.)

Make the following observation

The points which lie in $E$ are precisely the points which verify $f(x,y,z) \leq a.$

Consequences :

The ellipsoid grows as $a$ grows and shrinks when $a$ shrinks.

The global minimum of $f$ is the center of each ellipsoid regardless of the value which $a$ takes.

The idea to find the local minimum is to make the ellipse grow until it touches the polyhedron in a single point $p$. Obviously this should be on a on a face of the polyhedron.

---

You proposed the point $p = (0.35,0.35,0.3)$ as a local minimum. Let us check that this is indeed the case. To do so we will consider the tangent plane to the ellipsoid at $p$ and we will show that this plane seperates the polyhedron and the ellipse. That is, the plane is such that the polyhedron and the hyperplane lie on different sides of it.

---

The gradient of $f$ is $(2x+y-1,x+4y+z-2,y+2z-1)$ and evaluating at $p = (0.35,0.35,0.3)$ gives

$$ \nabla f(p) = (0.05,0.05,-0.05)$$

It follows that $(1,1,-1)$ is a normal vector the the tangent plane at $p$. Hence the tangent plane has the following equation

$$ (x-0.35) + (y-0.35) - (z-0.3) = 0$$

which we can be rewritten as

$$ x+y-z = 0.4.$$

Clearly the whole ellipsoid lies on one side of this plane since it is a convex shape and tangent to the plane. Moreover since the center of the ellipsoid lies at $(1/3,1/3,1/3)$ and $1/3+1/3-1/3 = 1/3 < 0.4$ we deduce that the ellipse lies in the halfspace $$ x+y-z \leq 0.4$$

However its not hard to check that all points of the polyhedron verify $x + y - z \geq 0.4$. Indeed this follows from $x+y \geq 0.7$ and $1\geq x+y+z \iff -z \geq x + y - 1$ since

$$ x+ y - z \geq x+y + x + y - 1 \geq 1.4-1= 0.4$$

---

Answer 2

This is the kind of problem to be handled with the help of Lagrange multipliers. Calling

$$ f = x^2+y^2+z^2+w^2+2w(x+z) $$

we have the lagrangian

$$ L = f+\lambda_1(x+y+z+w-1)+\lambda_2(x+y-0.7-s_2^2)+\lambda_3(x-s_3^2)+\lambda_4(y-s_4^2)+\lambda_5(z-s_5^2)+\lambda_6(w-s_6^2) $$ Here $s_k$ are slack variables whose purpose is to transform the inequality restrictions into equations.

Now from $\nabla_X L=0$ with $X=\{x,y,z,w,\lambda_1,\lambda_2,\lambda_3,\lambda_4,\lambda_5,\lambda_6,s_2,s_3,s_4,s_5,s_6\}$ we get the stationary points as the solutions for

$$ \left\{ \begin{array}{rcl} \lambda_1+\lambda_2+\lambda_3+2 w+2 x &=&0\\ \lambda_1+\lambda_2+\lambda_4+2 y &=&0\\ \lambda_1+\lambda_5+2 w+2 z &=&0\\ \lambda_1+\lambda_6+2 w+2 (x+z)&=&0 \\ w+x+y+z-1 &=&0\\ x+y-s_2^2-0.7&=&0 \\ x-s_3^2&=&0 \\ y-s_4^2&=&0\\ z-s_5^2&=&0 \\ w-s_6^2&=&0 \\ \lambda_2 s_2&=&0 \\ \lambda_3 s_3&=&0 \\ \lambda_4 s_4&=&0 \\ \lambda_5 s_5&=&0\\ \lambda_6 s_6&=&0\\ \end{array} \right. $$

Considering the development for $ \lambda_ks_k=0$ we have to solve linear systems, giving the results:

$$ \left[ \begin{array}{cccccccccccccccc} f&x&y&z&w&\lambda_1&\lambda_2&\lambda_3&\lambda_4&\lambda_5&\lambda_6&s_2^2&s_3^2&s_4^2&s_5^2&s_6^2\\ 0.5 & 0.2 & 0.5 & 0. & 0.3 & -1. & 0. & 0. & 0. & 0.4 & 0. & 0. & 0.2 & 0.5 & 0. & 0.3 \\ 0.5 & 0.5 & 0.5 & 0. & 0. & -1. & 0. & 0. & 0. & 1. & 0. & 0.3 & 0.5 & 0.5 & 0. & 0. \\ 0.58 & 0. & 0.7 & 0. & 0.3 & -0.6 & -0.8 & 0.8 & 0. & 0. & 0. & 0. & 0. & 0.7 & 0. & 0.3 \\ 0.58 & 0. & 0.7 & 0.3 & 0. & -0.6 & -0.8 & 1.4 & 0. & 0. & 0. & 0. & 0. & 0.7 & 0.3 & 0. \\ 1. & 0. & 1. & 0. & 0. & -2. & 0. & 2. & 0. & 2. & 2. & 0.3 & 0. & 1. & 0. & 0. \\ 1. & 0.7 & 0. & 0. & 0.3 & -2. & 0. & 0. & 2. & 1.4 & 0. & 0. & 0.7 & 0. & 0. & 0.3 \\ 1. & 1. & 0. & 0. & 0. & -2. & 0. & 0. & 2. & 2. & 0. & 0.3 & 1. & 0. & 0. & 0. \\ \end{array} \right] $$

Here, $s_k = 0$ means that the corresponding restriction is actuating.