# Minimize this real function on $\mathbb{R}^{2}$ without calculus?

When it comes to minimizing a differentiable real function, calculus comes into play immediately. If $$f: (x,y) \mapsto (x+y-1)^{2} + (x+2y-3)^{2} + (x+3y-6)^{2}$$ on $$\mathbb{R}^{2}$$, and if one is asked to find the minimum of $$f$$ along with the minimizer(s), is it possible to do that without calculus? The three equations do not admit a common solution; besides, I was not seeing an elementary inequality that might be useful at this point. Although this question itself may not be very interesting, I am interested in knowing an elegant way for the (more or less recreational) minimization.

• It is a least squares minimisation problem with an algebraic solution. But calculus is used implicitly. – copper.hat Jun 4 at 15:00
• @copper.hat, Hi, thanks. Yes, I noticed that too. Wondering if a brute force method exists. – Megadeth Jun 4 at 15:01
• Well, the solution is $(A^TA)^{-1} Ab$ with $A,b$ taken from above. But that has implicit calculus. – copper.hat Jun 4 at 15:05
• If you are willing to countenance geometry, there is a nice answer. I have elaborated below. – copper.hat Jun 4 at 16:08
• @GaryMoore How about my solution? – user679470 Jun 5 at 3:17

\begin{align*} f(x,y)&=3x^2+12xy+14y^2-20x-50y+46\\ &=3(x+2y)^2+2y^2-20(x+2y)-10y+46\\ &=\frac13(3x+6y-10)^2+2y^2-10y+\frac{38}3\\ &=\frac13(3x+6y-10)^2+\frac12(2y-5)^2+\frac16 \end{align*}

The minimum value is $$\dfrac16$$. It happens when $$\displaystyle (x,y)=\left(-\dfrac53,\dfrac52\right)$$.

• Arriving at the first equality seems inevitable, though annoying. – Megadeth Jun 4 at 15:45

In general, any quadratic function $$\ f\$$ on $$\ \mathbb{R}^n\$$ can be written as $$f\left(x\right) = x^\top A x + b^\top x + c\ ,$$ where $$\ A\$$ is a symetric $$\ n\times n\$$ matrix, $$\ b\$$ an $$\ n\times 1\$$ column vector and $$\ c\$$ a constant. A minimum exists if and only if $$\ A\$$ is positive definite or semidefinite and $$\ b\$$ lies in its column space. If these conditions are satisfied, and $$\ b=-2 Ax_0\$$, then $$f\left(x\right) = (x-x_0)^\top A\, (x-x_0) + c-x_0^\top A x_0\ ,$$ and has a minimum value $$\ c-x_0^\top A x_0\$$ when $$\ x=x_0\$$.

For the function $$\ f\$$ given in the question, $$f\left(x,y\right) = \pmatrix{x&y}^\top\pmatrix{3&6\\6&14}\pmatrix{x\\y} + \pmatrix{-20&-50}\pmatrix{x\\y}+46\ ,$$ and we have $$\pmatrix{-20\\-50} = -2\pmatrix{3&6\\6&14}\pmatrix{-\frac{5}{3}\\ \frac{5}{2}}\ ,$$ leading to the same result as given in the other answers.

By C-S $$f(x,y)=\frac{1}{6}(1+4+1)\left((1-x-y)^2+\left(x+2y-3\right)^2+(6-x-3y)^2\right)\geq$$ $$=\frac{1}{6}\left(1-x-y+2x+4y-6+6-x-3y\right)^2=\frac{1}{6}.$$ The equality occurs for $$(1,2,1)||(1-x-y,x+2y-3,6-x-3y),$$ id est, for $$(x,y)=\left(-\frac{5}{3},\frac{5}{2}\right),$$ which says that $$\frac{1}{6}$$ is a minimal value.

It is possible to minimize this function without using calculus, but this method is going, instead, to use some linear algebra. This is all possible because it's a quadratic form. Here are the steps:

1. Expand the function completely to obtain $$f(x,y)=3x^2+12xy+14y^2-20x-50y+46.$$
2. Now we need a change of coordinates in order to eliminate the $$xy$$ term. This amounts to a rotation, and the result of this is that we should be able to complete the square separately in $$x$$ and $$y$$. We are rotating the axes by an angle $$\theta,$$ given by $$\cot(2\theta)=\frac{3-14}{12}=-\frac{11}{12}\quad\implies\quad \theta=\frac12\,\operatorname{arccot}\left(-\frac{11}{12}\right).$$ The new coordinates $$(x', y')$$ will be given by the rotation matrix $$\left[\begin{matrix}x\\y\end{matrix}\right]=\left[\begin{matrix}\cos(\theta) &-\sin(\theta)\\\sin(\theta) &\cos(\theta)\end{matrix}\right]\left[\begin{matrix}x'\\y'\end{matrix}\right]\quad\implies\quad \left[\begin{matrix}x'\\y'\end{matrix}\right]=\left[\begin{matrix}\cos(\theta) &\sin(\theta)\\-\sin(\theta) &\cos(\theta)\end{matrix}\right]\left[\begin{matrix}x\\y\end{matrix}\right] .$$ Note that we can write these out explicitly, since \begin{align*} \cos\left(\frac12\,\underbrace{\operatorname{arccot}\left(-\frac{11}{12}\right)}_{\varphi}\right)&= \underbrace{\operatorname{sgn}\left(\pi+\varphi+4\pi\left\lfloor\frac{\pi-\varphi}{4\pi}\right\rfloor\right)}_{=1}\sqrt{\frac{1+\cos(\varphi)}{2}}\\ &=\sqrt{\frac{1+11/\sqrt{265}}{2}},\\ \sin\left(\frac12\,\operatorname{arccot}\left(-\frac{11}{12}\right)\right)&= \underbrace{\operatorname{sgn}\left(2\pi-\varphi+4\pi\left\lfloor\frac{\varphi}{4\pi}\right\rfloor\right)}_{=-1}\sqrt{\frac{1-\cos(\varphi)}{2}}\\ &=-\sqrt{\frac{1-11/\sqrt{265}}{2}}. \end{align*}
3. The original expression $$f(x,y)$$ in terms of the new coordinates, becomes $$f(x',y')=-\frac{1}{2} \left(\sqrt{265}-17\right) x'^2-2 \sqrt{50+110 \sqrt{\frac{5}{53}}} x'+5 \sqrt{50-110 \sqrt{\frac{5}{53}}} x'+\frac{1}{2} \left(17+\sqrt{265}\right) y'^2-5 \sqrt{50+110 \sqrt{\frac{5}{53}}} y'-2 \sqrt{50-110 \sqrt{\frac{5}{53}}} y'+46.$$ While this is certainly complicated-looking, notice that there is no cross-term! That's what we needed. Now it's a matter of completing the square separately. This is normally straight-forward, but with this monster, it will be helpful to have some symbolic manipulation (true confessions: I've already used Mathematica on this one to take out some of the tedium). Using the depress function defined here, we obtain the following results. Suppose we define \begin{align*} g(x')&=-\frac{1}{2} \left(\sqrt{265}-17\right) x'^2-2 \sqrt{50+110 \sqrt{\frac{5}{53}}} x'+5 \sqrt{50-110 \sqrt{\frac{5}{53}}} x'\\ h(y')&=\frac{1}{2} \left(17+\sqrt{265}\right) y'^2-5 \sqrt{50+110 \sqrt{\frac{5}{53}}} y'-2 \sqrt{50-110 \sqrt{\frac{5}{53}}} y', \end{align*} not forgetting the $$46$$ left (actually, we can ignore it later), we can complete the square on these to obtain \begin{align*} g(x')&=\frac{1}{2} \left(17-\sqrt{265}\right) \left(x'+\frac{5 \sqrt{50-110 \sqrt{\frac{5}{53}}}-2 \sqrt{50+110 \sqrt{\frac{5}{53}}}}{17-\sqrt{265}}\right)^2-\frac{5 \left(471 \sqrt{265}-7685\right)}{53 \left(\sqrt{265}-17\right)}\\ h(y')&=\frac{1}{2} \left(17+\sqrt{265}\right) \left(y'+\frac{-2 \sqrt{50-110 \sqrt{\frac{5}{53}}}-5 \sqrt{50+110 \sqrt{\frac{5}{53}}}}{17+\sqrt{265}}\right)^2-\frac{5 \left(7685+471 \sqrt{265}\right)}{53 \left(17+\sqrt{265}\right)}. \end{align*}
4. Now we are in a position to minimize the function, because we just minimize the perfect squares to get \begin{align*} x'&=-\frac{5 \sqrt{50-110 \sqrt{\frac{5}{53}}}-2 \sqrt{50+110 \sqrt{\frac{5}{53}}}}{17-\sqrt{265}} \\ y'&=\frac{2 \sqrt{50-110 \sqrt{\frac{5}{53}}}+5 \sqrt{50+110 \sqrt{\frac{5}{53}}}}{17+\sqrt{265}}. \end{align*}
5. Getting back to the original $$x$$ and $$y,$$ we have \begin{align*} x&=-\frac53\\ y&=\frac52. \end{align*} The actual minimum value of the function at this point would be $$1/6.$$

To recap: the mathematics used here, in principle, are matrix rotations, some trigonometry, and completing the square.

While this procedure is certainly more complicated-looking than some of the other answers, it is also more algorithmic: just turn the crank.

Here is a geometric answer. This is slightly cheating since the duality between planes and normals is essentially what one obtains from the optimality conditions from calculus.

Note that $$n=(1,-2,1)^T$$ is orthogonal to the plane spanning $$(1,1,1)^T, (1,2,3)^T$$ and we are trying to find the closest point to $$b=(1,3,6)^T$$. From the closest point we can find $$x,y$$.

The plane is defined by $$\{ x | n^T x =0 \}$$. Let $$p$$ denote the closest point. We must have $$b-p=tn$$ for some $$t$$.

Since $$b-p$$ is orthogonal to the plane, we have $$n^Tp = 0$$, or $$t = {n^Tb \over n^T n} = {1 \over 6}$$ and so $$p={1 \over 6}(5,20,35)^T$$.

Now we can solve for $$x,y$$ to get $$(x,y)^T = {1 \over 6}(-10,15)^T$$.

$$\tag 1 f(x,y) = 3 x^2 + 4 x (3 y - 5) + 2 (7 y^2 - 25 y + 23)$$

Let

$$\tag 2 x = \frac{-4(3y-5)}{6}$$ (Vertex = $$\frac{-b}{2a}$$).
and plug back into $$\text{(1)}$$, giving

$$M(y) = 1/2 (2 y - 5)^2 + 1/6$$

as the quantity to be minimized.

So at $$y = \frac{5}{2}$$ the minimum of $$\frac{1}{6}$$ is achieved.

Plugging $$\frac{5}{2}$$ into $$\text{(2)}$$ (certainly easier than using $$\text{(1)}$$ again), we get

# $$\tag 3 x = \frac{-4(3(\frac{5}{2})-5)}{6} = -\frac{5}{3}$$

So

$$(x,y) = (-\frac{5}{3},\frac{5}{2})$$

• Another way is to find discriminant of the quadratic equation in $x$ – lab bhattacharjee Jun 4 at 15:21

No calculus or cleverness required.

Note how he third diagonal element in $$D$$ is the constant $$1/6.$$ The whole polynomial is $$3 f^2 + 2 g^2 + \frac{1}{6},$$ where the coefficients of $$f,g$$ are given by the first two rows of $$Q.$$ In this direction, this is usually called Lagrange's method or repeated completing squares.

$$Q^T D Q = H$$ $$\left( \begin{array}{rrr} 1 & 0 & 0 \\ 2 & 1 & 0 \\ - \frac{ 10 }{ 3 } & - \frac{ 5 }{ 2 } & 1 \\ \end{array} \right) \left( \begin{array}{rrr} 3 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & \frac{ 1 }{ 6 } \\ \end{array} \right) \left( \begin{array}{rrr} 1 & 2 & - \frac{ 10 }{ 3 } \\ 0 & 1 & - \frac{ 5 }{ 2 } \\ 0 & 0 & 1 \\ \end{array} \right) = \left( \begin{array}{rrr} 3 & 6 & - 10 \\ 6 & 14 & - 25 \\ - 10 & - 25 & 46 \\ \end{array} \right)$$

Algorithm discussed at http://math.stackexchange.com/questions/1388421/reference-for-linear-algebra-books-that-teach-reverse-hermite-method-for-symmetr
https://en.wikipedia.org/wiki/Sylvester%27s_law_of_inertia
$$H = \left( \begin{array}{rrr} 3 & 6 & - 10 \\ 6 & 14 & - 25 \\ - 10 & - 25 & 46 \\ \end{array} \right)$$ $$D_0 = H$$ $$E_j^T D_{j-1} E_j = D_j$$ $$P_{j-1} E_j = P_j$$ $$E_j^{-1} Q_{j-1} = Q_j$$ $$P_j Q_j = Q_j P_j = I$$ $$P_j^T H P_j = D_j$$ $$Q_j^T D_j Q_j = H$$

$$H = \left( \begin{array}{rrr} 3 & 6 & - 10 \\ 6 & 14 & - 25 \\ - 10 & - 25 & 46 \\ \end{array} \right)$$

==============================================

$$E_{1} = \left( \begin{array}{rrr} 1 & - 2 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{array} \right)$$ $$P_{1} = \left( \begin{array}{rrr} 1 & - 2 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{array} \right) , \; \; \; Q_{1} = \left( \begin{array}{rrr} 1 & 2 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{array} \right) , \; \; \; D_{1} = \left( \begin{array}{rrr} 3 & 0 & - 10 \\ 0 & 2 & - 5 \\ - 10 & - 5 & 46 \\ \end{array} \right)$$

==============================================

$$E_{2} = \left( \begin{array}{rrr} 1 & 0 & \frac{ 10 }{ 3 } \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{array} \right)$$ $$P_{2} = \left( \begin{array}{rrr} 1 & - 2 & \frac{ 10 }{ 3 } \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{array} \right) , \; \; \; Q_{2} = \left( \begin{array}{rrr} 1 & 2 & - \frac{ 10 }{ 3 } \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{array} \right) , \; \; \; D_{2} = \left( \begin{array}{rrr} 3 & 0 & 0 \\ 0 & 2 & - 5 \\ 0 & - 5 & \frac{ 38 }{ 3 } \\ \end{array} \right)$$

==============================================

$$E_{3} = \left( \begin{array}{rrr} 1 & 0 & 0 \\ 0 & 1 & \frac{ 5 }{ 2 } \\ 0 & 0 & 1 \\ \end{array} \right)$$ $$P_{3} = \left( \begin{array}{rrr} 1 & - 2 & - \frac{ 5 }{ 3 } \\ 0 & 1 & \frac{ 5 }{ 2 } \\ 0 & 0 & 1 \\ \end{array} \right) , \; \; \; Q_{3} = \left( \begin{array}{rrr} 1 & 2 & - \frac{ 10 }{ 3 } \\ 0 & 1 & - \frac{ 5 }{ 2 } \\ 0 & 0 & 1 \\ \end{array} \right) , \; \; \; D_{3} = \left( \begin{array}{rrr} 3 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & \frac{ 1 }{ 6 } \\ \end{array} \right)$$

==============================================

$$P^T H P = D$$ $$\left( \begin{array}{rrr} 1 & 0 & 0 \\ - 2 & 1 & 0 \\ - \frac{ 5 }{ 3 } & \frac{ 5 }{ 2 } & 1 \\ \end{array} \right) \left( \begin{array}{rrr} 3 & 6 & - 10 \\ 6 & 14 & - 25 \\ - 10 & - 25 & 46 \\ \end{array} \right) \left( \begin{array}{rrr} 1 & - 2 & - \frac{ 5 }{ 3 } \\ 0 & 1 & \frac{ 5 }{ 2 } \\ 0 & 0 & 1 \\ \end{array} \right) = \left( \begin{array}{rrr} 3 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & \frac{ 1 }{ 6 } \\ \end{array} \right)$$ $$Q^T D Q = H$$ $$\left( \begin{array}{rrr} 1 & 0 & 0 \\ 2 & 1 & 0 \\ - \frac{ 10 }{ 3 } & - \frac{ 5 }{ 2 } & 1 \\ \end{array} \right) \left( \begin{array}{rrr} 3 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & \frac{ 1 }{ 6 } \\ \end{array} \right) \left( \begin{array}{rrr} 1 & 2 & - \frac{ 10 }{ 3 } \\ 0 & 1 & - \frac{ 5 }{ 2 } \\ 0 & 0 & 1 \\ \end{array} \right) = \left( \begin{array}{rrr} 3 & 6 & - 10 \\ 6 & 14 & - 25 \\ - 10 & - 25 & 46 \\ \end{array} \right)$$

• OK, for those new to this matrix manipulation - you fill in 3x3 $H$ matrix with the nine entries (well, there is a way) from the OP's polynomial $\quad$ $f(x,y)=3x^2+14y^2+46+ 6xy + 6xy -10x-10x-25y-25y$ – CopyPasteIt Jun 6 at 2:28

Here's my solution without calculus (not sure how elegant it is though).

We make a few changes of variable; firstly replace $$x$$ with $$x + 3$$, and then let $$a = x+2y, b = y$$. We obtain $$(a-b-2)^2 + a^2 + (a+b+3)^2$$, and maximising this over $$a$$ and $$b$$ allows us to recover $$x$$ and $$y$$.

Note that we have a $$(a-b-2)^2$$ term and a $$(a+b+3)^2$$ term; one has $$b$$ and one has $$-b$$ so the sum is maximised when they are closest together, i.e. $$b = -\frac{5}{2}$$ both squares become $$(a+ \frac{1}{2})^2$$. So we now need to minimise $$2(a+ \frac{1}{2})^2 + a^2 = 3a^2 + a + \frac{1}{2}$$, but since this is a quadratic this minimum occurs at $$a = \frac{-1}{6}$$, and so we simply substitute back to find $$x, y$$.

Let

$$3\,x^{\,2}+ 12\,xy+ 14\,y^{\,2}- 20\,x- 56\,y+ 46- \frac{1}{6}= \frac{1}{3}(\,3\,x+ 5\,)(\,3\,x+ 12\,y- 25\,)+ \frac{7}{2}(\,5- 2\,y\,)^{\,2}$$

$$18(3 x^{ 2}+ 12 xy+ 14 y^{ 2}- 20 x- 56 y+ 46- \frac{1}{6})= 7(3 x+ 6 y- 10)^{ 2}- (3 x+ 5)(3 x+ 12 y- 25)$$

$$\therefore\,3\,x^{\,2}+ 12\,xy+ 14\,y^{\,2}- 20\,x- 56\,y+ 46- \frac{1}{6}\geqq 0$$

Furthermore

$$\because\,{\rm discriminant}[\,3\,x^{\,2}+ 12\,xy+ 14\,y^{\,2}- 20\,x- 56\,y+ 46- \frac{1}{6},\,x\,]= -\,6(\,5- 2\,y\,)^{\,2}\leqq 0$$