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

Question

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.

Answer 1

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$.

Answer 2

\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)$.

Answer 3

See How to Find the Vertex of a Quadratic Equation.

$\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})$$

Answer 4

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.

Answer 5

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.

Answer 6

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$.

Answer 7

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.

Answer 8

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$$

Answer 9

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) $$