2
$\begingroup$

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.

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

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

$\endgroup$
  • $\begingroup$ Arriving at the first equality seems inevitable, though annoying. $\endgroup$ – Megadeth Jun 4 at 15:45
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

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

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

$\endgroup$
  • $\begingroup$ 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$ $\endgroup$ – CopyPasteIt Jun 6 at 2:28
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.