1. ## How to minimize a quadratic function using linear algebra

How do you minimize the following quadratic function over all (real) $\displaystyle x_1 , x_2$:

$\displaystyle p(x_1 , x_2) = 4x_1^2-2x_1x_2+3x_2^2+3x_1-2x_2+1$

Also, I have to somehow write the function in the form of:

$\displaystyle p(x)=x^TKx-2x^Tf+c$

in order to minimize it. How do I find $\displaystyle f$, a constant vector space?

2. Originally Posted by JCS007
How do you minimize the following quadratic function over all (real) $\displaystyle x_1 , x_2$:

$\displaystyle p(x_1 , x_2) = 4x_1^2-2x_1x_2+3x_2^2+3x_1-2x_2+1$

Also, I have to somehow write the function in the form of:

$\displaystyle p(x)=x^TKx-2x^Tf+c$

in order to minimize it. How do I find $\displaystyle f$, a constant vector space?
I want to learn how to do it too. But I am not finding any references for this... Can you tell me the general method to minimize functions using linear algebra as given in your text book. Or at least tell me a good reference?

And ya... I can write 4x_1^2-2x_1x_2+3x_2^2+3x_1-2x_2+1 in the matrix form... I figured out K,f and c.

3. i just need the answer too ,who can help us?

4. Hello !

This is Gauss's method.

Originally Posted by JCS007
How do you minimize the following quadratic function over all (real) $\displaystyle x_1 , x_2$:

$\displaystyle p(x_1 , x_2) = 4x_1^2-2x_1x_2+3x_2^2+3x_1-2x_2+1$
The general idea of minimizing (I don't think I'm misunderstanding) is to get a sum of linearly independent squares.

The thing is to group the terms containing $\displaystyle x_1$ (for example, but we could start with another one) in a first time, and then, to complete the square or use a known formula. I'll try to show it (and detail the calculations, so don't worry ^^)

$\displaystyle p(x_1 , x_2)=(4x_1^2-2x_1x_2+3x_1)+3x_2^2-2x_2+1$

------------------------------
Let's deal with the parenthesis thing. It's here where there are two methods, but one looks more familiar (completing the square) whereas the other one is more thouroughly (using a known formula). I'll show only one;

Complete the square
$\displaystyle 4x_1^2-2x_1x_2+3x_1=(2x_1)^2+{\color{blue}x_1(-2x_2+3)}$
We need to factor 4 in the blue part because $\displaystyle (a+b)^2=a^2+{\color{blue}2}ab+b^2$ and $\displaystyle 2x_1$ contains a 2.

--> $\displaystyle 4x_1^2-2x_1x_2+3x_1=(\overbrace{2x_1}^{a})^2+2 \cdot 2x_1(\overbrace{-\tfrac 12 x_2+\tfrac 34}^{b})$

$\displaystyle 4x_1^2-2x_1x_2+3x_1=\overbrace{(2x_1-\tfrac 12 x_2+\tfrac 34)^2}^{a^2+2ab{\color{red}+b^2}}\overbrace{-(-\tfrac 12 x_2+\tfrac 34)^2}^{{\color{red}-b^2}}=$$\displaystyle (2x_1-\tfrac 12 x_2+\tfrac 34)^2-(\tfrac 14 x_2^2-\tfrac 34 x_2+\tfrac{9}{16} x_2^2)$

-------------------------------

$\displaystyle p(x_1 , x_2)=(2x_1-\tfrac 12 x_2+\tfrac 34)^2+(-\tfrac 14 x_2^2+\tfrac 34 x_2-\tfrac{9}{16} x_2^2)+3x_2^2-2x_2+1$

$\displaystyle p(x_1 , x_2)=(2x_1-\tfrac 12 x_2+\tfrac 34)^2+\tfrac{11}{12} x_2^2-\tfrac 54 x_2+\tfrac{7}{16}$

And now, do the same.

Remember one thing : the minimized form is $\displaystyle \sum \alpha_n y_n$, where $\displaystyle \alpha_n$ is not necessarily 1 or positive. It can be negative and it can be different from 1. Why ? Because we will consider the coordinates in the squares as coordinates in a new basis. And one knows that it is possible to multiply a vector by a scalar, it doesn't change anything.

It may look messy, but hmmm... this one looks sadistic to me lol ! Otherwise, it's quite useful once you've mastered it

5. Originally Posted by JCS007
How do you minimize the following quadratic function over all (real) $\displaystyle x_1 , x_2$:

$\displaystyle p(x_1 , x_2) = 4x_1^2-2x_1x_2+3x_2^2+3x_1-2x_2+1$
we have $\displaystyle p(x_1,x_2)=x^T K x + 3x_1-2x_2 + 1,$ where $\displaystyle x=\begin{pmatrix} x_1 \\ x_2 \end{pmatrix},$ and $\displaystyle K=\begin{pmatrix}4 & -1 \\ -1 & 3 \end{pmatrix}.$ note that K is always chosen to be

symmetric. next we find the eigenvalues of K, which are the roots of $\displaystyle \lambda^2 - 7 \lambda + 11=0.$ so $\displaystyle \lambda_1 = \frac{7 + \sqrt{5}}{2}, \ \lambda_2 = \frac{7 - \sqrt{5}}{2}.$

the eigenvectors of K are: $\displaystyle v_1=\begin{pmatrix} 1 \\ 4 - \lambda_1 \end{pmatrix}, \ \ v_2 = \begin{pmatrix} 1 \\ 4- \lambda_2 \end{pmatrix}.$ we have $\displaystyle ||v_1|| = \sqrt{6-\lambda_1}, \ \ ||v_2|| = \sqrt{6-\lambda_2}.$ now define:

$\displaystyle P=\begin{pmatrix} \alpha & \beta \\ \gamma & \delta \end{pmatrix},$ where $\displaystyle \alpha=\frac{1}{\sqrt{6-\lambda_1}}, \ \beta =\frac{1}{\sqrt{6-\lambda_2}}, \ \gamma = \frac{4-\lambda_1}{\sqrt{6-\lambda_1}}, \ \delta= \frac{4 - \lambda_2}{\sqrt{6 - \lambda_2}}.$ then $\displaystyle P^{-1}=P^T, \ \det (P) = 1$, and

$\displaystyle P^T K P = \begin{pmatrix} \lambda_1 & 0 \\ 0 & \lambda_2 \end{pmatrix}.$ now let $\displaystyle x=Py,$ where $\displaystyle y=\begin{pmatrix}y_1 \\ y_2 \end{pmatrix}.$ then: $\displaystyle p(x_1,x_2)=\lambda_1 y_1^2 + \lambda_2 y_2^2 + (3\alpha - 2\gamma)y_1 + (3\beta - 2 \delta)y_2 +1,$

which after completing the square gives us:

$\displaystyle p(x_1,x_2)=\lambda_1 \left(y_1 + \frac{3\alpha - 2\gamma}{2\lambda_1} \right)^2 + \lambda_2 \left(y_2 + \frac{3 \beta - 2 \delta}{2\lambda_2} \right)^2 - \frac{(3\alpha - 2\gamma)^2}{4\lambda_1} - \frac{(3\beta - 2 \delta)^2}{4\lambda_2} + 1.$ note that $\displaystyle \lambda_1, \lambda_2 > 0.$ it's clear now that:

$\displaystyle \min_{x_1,x_2 \in \mathbb{R}} p(x_1,x_2) = 1-\frac{(3\alpha - 2\gamma)^2}{4\lambda_1} - \frac{(3\beta - 2\delta)^2}{4\lambda_2}=\frac{13}{44}. \ \ \ \square$

Note: the columns of $\displaystyle P$ are the normalized (i.e. of length 1) eigenvectors of K. we know that P is orthogonal, so $\displaystyle \det(P)=\pm 1.$

so, in general, in order to make sure that the determinant of P is 1, you might need to choose the first column of P to be $\displaystyle \frac{-v_1}{||v_1||}$

other than $\displaystyle \frac{v_1}{||v_1||}.$ that's not the case for our problem though!

Also, I have to somehow write the function in the form of:

$\displaystyle p(x)=x^TKx-2x^Tf+c$

in order to minimize it. How do I find $\displaystyle f$, a constant vector space?
i already gave you the matrix $\displaystyle K.$ it's obvious that you need to choose: $\displaystyle f=[-1.5 \ , \ 1]^T,$ and $\displaystyle c=1.$