proof of arithmetic-geometric means inequality using Lagrange multipliers

As an interesting example of the Lagrange multiplier method,we employ it to prove the arithmetic-geometric means inequality:

\\sqrt[n]{x_{1}\\cdots x_{n}}\\leq\\frac{x_{1}+\\cdots+x_{n}}{n}\\,,\\quad x_{i}\\geq 0\\,,

with equality if and only if all the $x_{i}$ are equal.

To begin with, define $f\\colon\\mathbb{R}_{\\geq 0}^{n}\\to\\mathbb{R}_{\\geq 0}$ by $f(x)=(x_{1}\\cdots x_{n})^{1/n}$ .

Fix $a>0$ (the arithmetic mean),and consider the set $M=\\{x\\in\\mathbb{R}^{n}:x_{i}\\geq 0\\text{ for all $i$, }\\sum_{i}x_{i}=na\\}$ .This is clearly a closed and bounded set in $\\mathbb{R}^{n}$ , and hence is compact.Therefore $f$ on $M$ has both a maximum and minimum.

$M$ is almost a manifold (a differentiable surface), except that it has a boundary consistingof points with $x_{i}=0$ for some $i$ .Clearly $f$ attains the minimum zero on this boundary,and on the “interior” of $M$ ,that is $M^{\\prime}=\\{x\\in\\mathbb{R}^{n}:x_{i}>0\\text{ for all $i$, }\\sum_{i}x_{i}=na\\}$ , $f$ is positive. Now $M^{\\prime}$ is a manifold, and the maximum of $f$ on $M$ is evidently a local maximum on $M^{\\prime}$ . Hencethe Lagrange multiplier method may be applied.

We have the constraint¹¹Although $g$ does not constrain that $x_{i}>0$ ,this does not really matter — for those who are worried about suchthings, a rigorous way to escape this annoyance is to simplydefine $f(x)=0$ to be zero whenever $x_{i}\\leq 0$ for some $i$ .Clearly the new $f$ cannot have a maximum at such points,so we may simply ignore the points with $x_{i}\\leq 0$ when solving the system.And for the same reason, the fact that $f$ fails to be differentiable at the boundarypoints is immaterial. $0=g(x)=\\sum_{i}x_{i}-na$ under which we are to maximize $f$ .

We compute:

\\displaystyle\\frac{f(x)}{nx_{i}}=\\frac{\\partial f}{\\partial x_{i}}=\\lambda\\,%\\frac{\\partial g}{\\partial x_{i}}=\\lambda\\,.

If we take the product, $i=1,\\ldots,n$ , of the extreme left- and right- hand sides of this equation,we obtain

\\frac{1}{n^{n}}=\\frac{f(x)^{n}}{n^{n}x_{1}\\cdots x_{n}}=\\lambda^{n}

from which it follows that $\\lambda=1/n$ ( $\\lambda=-1/n$ is obviously inadmissible).Then substituting back, we get $f(x)=x_{i}$ , which implies that the $x_{i}$ are all equal to $a$ ,The value of $f$ at this point is $a$ .

Since we have obtained a unique solution to the Lagrange multiplier system,this unique solution must be the unique maximum point of $f$ on $M$ .So $f(x)\\leq a$ amongst all numbers $x_{i}$ whose arithmetic mean is $a$ ,with equality occurring if and only if all the $x_{i}$ are equal to $a$ .

The case $a=0$ , which was not included in the above analysis, is trivial.

Proof of concavity

The question of whether the point obtained from solving Lagrange systemis actually a maximum for $f$ was taken care of by our preliminary compactness argument. Another popular way to determine whether a given stationary pointis a local maximum or minimum is by studying the Hessian of the functionat that point.For the sake of illustrating the relevant techniques,we will prove again that $x_{i}=a$ is a local maximum for $f$ ,this time by showing that the Hessian is negative definite.

Actually, it turns out to be not muchharder to show that $f$ is weakly concave everywhereon $\\mathbb{R}_{\\geq 0}^{n}$ , not just on $M$ .A plausibility argument for this factis that the graph of $t\\mapsto\\sqrt[n]{t}$ is concave, and since $f$ also involves an $n$ th root,it should be concave too. We will prove concavity of $f$ byshowing that the Hessian of $f$ is negative semi-definite.

Since $M$ is a convex²²If $M$ is not convex, then the arguments that follow will not work.In general, a prescription to determine whether a critical pointis a local minimum or maximum can be foundin tests for local extrema in Lagrange multiplier method. set, the restrictionof $f$ to $M$ will also be weakly concave;then we can conclude thatthe critical point $x_{i}=a$ on $M$ must be a global minimum on $M$ .

We begin by calculating second-order derivatives:

	$\\displaystyle\\frac{\\partial^{2}f}{\\partial x_{j}\\partial x_{i}}$	$\\displaystyle=\\frac{\\partial}{\\partial x_{j}}\\left(\\frac{f(x)}{nx_{i}}\\right)=%\\frac{1}{nx_{i}}\\frac{\\partial f}{\\partial x_{j}}+f(x)\\frac{\\partial}{\\partialx%_{j}}\\frac{1}{nx_{i}}$
		$\\displaystyle=\\frac{f(x)}{n^{2}x_{i}x_{j}}-\\delta_{ij}\\frac{f(x)}{nx_{i}^{2}}\\,.$

(The symbol $\\delta_{ij}$ is the Kronecker delta.)Thus the Hessian matrix is:

\\displaystyle\\operatorname{D}^{2}f(x)=\\frac{f(x)}{n^{2}}\\left[\\frac{1}{x_{i}x_%{j}}\\right]_{ij}-\\frac{f(x)}{n^{2}}\\begin{bmatrix}\\frac{n}{x_{1}^{2}}\\\\&\\ddots\\\\&&\\frac{n}{x_{n}^{2}}\\end{bmatrix}

Now if we had actual numbers to substitute for the $x_{i}$ ,then we can go to a computer and ask if the matrix is negative definite or not.But we want to prove global concavity, so we have to employ some cleveralgebra, and work directly from the definition.

Let $v=(v_{1},\\ldots,v_{n})$ be a test vector.Negative semi-definiteness means $v\\,\\operatorname{D}^{2}f(x)\\,v^{\\mathrm{T}}\\leq 0$ for all $v$ .So let us write out:

	$\\displaystyle v\\operatorname{D}^{2}f(x)v^{\\mathrm{T}}$	$\\displaystyle=\\frac{f(x)}{n^{2}}\\left(\\sum_{i,j}\\frac{v_{i}}{x_{i}}\\frac{v_{j}%}{x_{j}}-n\\sum_{i}\\frac{v_{i}^{2}}{x_{i}^{2}}\\right)$
		$\\displaystyle=\\frac{f(x)}{n^{2}}\\left(\\left(\\sum_{i}\\frac{v_{i}}{x_{i}}\\right)%^{2}-n\\sum_{i}\\left(\\frac{v_{i}}{x_{i}}\\right)^{2}\\right)\\,.$

We would be done if we can prove

\\left(\\sum_{i}w_{i}\\right)^{2}\\leq n\\sum_{i}w_{i}^{2}\\,,\\quad w_{i}=\\frac{v_{i%}}{x_{i}}\\,.

(1)

But look, this is just the Cauchy-Schwarz inequality,concerning the dot product of the vectors $(w_{1},\\ldots,w_{n})$ and $(1,\\ldots,1)$ !So $\\operatorname{D}^{2}f(x)$ is negative semi-definite everywhere,i.e. $f$ is weakly concave.

Moreover, the case of equality in the Cauchy-Schwarz inequality (1)only occurs when $(w_{1},\\ldots,w_{n})$ is parallel to $(1,\\ldots,1)$ ,i.e. $v_{i}=\\mu x_{i}$ for some scalar $\\mu$ .Notice that $(1,\\ldots,1)$ is the normal vector tothe tangent space of $M$ ,so $(1,\\ldots,1)\\cdot v=\\mu\\sum_{i}x_{i}\eq 0$ unless $\\mu=0$ .This means, equality never holds in (1)if $v\eq 0$ is restricted to the tangent space of $M$ .In turn, this means that $f$ is strictly concaveon the convex set $M$ , andso $x_{i}=a$ is a strict global minimum of $f$ on $M$ .

Proof of inequality by symmetry argument

Observe that the maximum point $x_{i}=a$ is pleasantly symmetric.We can show that the solution has to be symmetric,by exploiting the symmetry of the function $f$ and the set $M$ .

We have already calculated that $f$ is strictly concave on $M$ ;this was independent of the Lagrange multiplier method.Since $f$ is strictly concave on a closed convex set,it has a unique maximum there; call it $x$ .

Pick any indices $i$ and $j$ , ranging from $1$ to $n$ , and formthe linear transformation $T$ , which switches the $i$ th and $j$ th coordinatesof its argument.

By definition, $f(x)\\geq f(\\xi)$ for all $\\xi\\in M$ .But $f\\circ T=f$ , so this means $f(Tx)\\geq f(T\\xi)$ for all $\\xi\\in M$ .But $M$ is mapped to itself by the transformation $T$ ,so this is the same as saying that $f(Tx)\\geq f(\\xi)$ for all $\\xi\\in M$ .But the global maximum is unique, so $Tx=x$ ,that is, $x_{i}=x_{j}$ .

Note that the argument in this last proofis extremely general — it takes the form:if $x$ is the unique maximum of $f\\colon M\\to\\mathbb{R}$ ,and $T$ is any symmetry of $M$ such that $f\\circ T=f$ ,then $Tx=x$ . This kind of symmetry argument was used to great effectby Jakob Steiner in his famous attempted proof of the isoperimetric inequality:among all closed curves of a given arc length, the circle maximizesthe area enclosed. However, Steiner did not realize thatthe assumption that there is a unique maximizing curvehas to be proved. Actually, that is the hardest part of the proof —if the assumption is known, then one may easily calculate using the Lagrange multiplier methodthat the maximizing curve must be a circle!