2

Let $B$ be the closed domain in $\mathbb{R}^3$ defined by $|x_1|+|x_2|+|x_3|\leq 1$. Find the maximum of $F(x_1,x_2,x_3)=\sum_{i=1}^3x_i^2+\sum_{i=1}^3a_ix_i$ on $B$.

Using Lagrange multiplier seems too complicated. We can write $F$ as $r^2-\sum_{i=1}^3a_i^2/4$ where $r$ is the distance from $(x_1,x_2,x_3)$ to $(-a_1/2,-a_2/2,-a_3/2)$. So what to do from here? The maximum lies on the vertex but how do you know which vertex?

Thanks

Caleb Stanford
  • 45,895
nerd
  • 1,457
  • 12
  • 20

1 Answers1

1

The easiest thing to do, if you are convinced by some argument that the maximum occurs at a vertex (which it does), is to plug in all vertices--there are only $6$. So your answer is \begin{align*} \max&\{F(1,0,0),F(-1,0,0), F(0,1,0), F(0,-1,0), F(0,0,1), F(0,0,-1)\} \\ &= \max\{1 + a_1, 1-a_1, 1+a_2, 1-a_2, 1+a_3, 1-a_3\} \\ &= 1 + \max\{a_1, -a_1, a_2, -a_2, a_3, -a_3\} \\ &= 1 + \max\{|a_1|, |a_2|, |a_3|\} \\ &= 1 + \|(a_1, a_2, a_3)\|_\infty. \end{align*}

Why must the maximum occur at a vertex? Well, here are two arguments:

  1. As you note, minimizing $F$ is equivalent to minimizing the distance from a point on the octahedron to the point $P = (-a_1/2, -a_2/2, -a_3/2)$. Note that the distance function $d(x) = d(x,P)$ has the following property: along any line segment, $d$ attains its maximum on one of the endpoints$^1$. For any point $x$ on the octahedron that is NOT a vertex, there is a line segment contained within the octahedron such that $x$ is on the interior of the line segment. So $F$ cannot be maximized at $x$.

  2. You can also reason with Lagrange Multipliers, as follows:

    • If the maximum of $F$ occurs on the interior of the octahedron, then $F$ has a local maximum there, so $\nabla F = 0$.

    • If the maximum of $F$ occurs on the interior of one of the faces of the octahedron, then $F$ has a local maximum there when restricted to the plane containing that face. So you set up Lagrange multipliers, e.g. maximizing $F$ with the restriction that $x + y - z = 1$. There are 8 such planes--on none of the planes does $F$ have a local max.

    • If the maximum of $F$ occurs on the interior of one of the edges of the octahedron, then $F$ has a local maximum when restricted to the line containing that edge. So you set up Lagrange multipliers, e.g. maximizing $F$ with the restriction that $x + y - z = 1$ AND $x - y - z = 1$. There are 12 edges to check.

    After all these cases are ruled out, you know $F$ can only attain its maximum on one of the six vertices.

$^{1}$ This is a special property of Euclidean distance, it doesn't hold for other distances like the infinity norm. You can prove it by taking the derivative of the distance function in the direction of the line segment.

Caleb Stanford
  • 45,895