# How to minimize a quadratic function using linear algebra

• Jul 7th 2008, 02:11 PM
JCS007
How to minimize a quadratic function using linear algebra
How do you minimize the following quadratic function over all (real) $x_1 , x_2$:

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

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

in order to minimize it. How do I find $f$, a constant vector space?
• Jul 7th 2008, 08:20 PM
Isomorphism
Quote:

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

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

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

in order to minimize it. How do I find $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.
• Jul 7th 2008, 09:38 PM
niniandcat
i just need the answer too ,who can help us?
• Jul 7th 2008, 11:41 PM
Moo
Hello !

This is Gauss's method.

Quote:

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

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

$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
$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 $(a+b)^2=a^2+{\color{blue}2}ab+b^2$ and $2x_1$ contains a 2.

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

$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}}=$ $(2x_1-\tfrac 12 x_2+\tfrac 34)^2-(\tfrac 14 x_2^2-\tfrac 34 x_2+\tfrac{9}{16} x_2^2)$

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

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

$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 $\sum \alpha_n y_n$, where $\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 (Tongueout)
• Jul 8th 2008, 12:26 AM
NonCommAlg
Quote:

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

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

we have $p(x_1,x_2)=x^T K x + 3x_1-2x_2 + 1,$ where $x=\begin{pmatrix} x_1 \\ x_2 \end{pmatrix},$ and $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 $\lambda^2 - 7 \lambda + 11=0.$ so $\lambda_1 = \frac{7 + \sqrt{5}}{2}, \ \lambda_2 = \frac{7 - \sqrt{5}}{2}.$

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

$P=\begin{pmatrix} \alpha & \beta \\ \gamma & \delta \end{pmatrix},$ where $\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 $P^{-1}=P^T, \ \det (P) = 1$, and

$P^T K P = \begin{pmatrix} \lambda_1 & 0 \\ 0 & \lambda_2 \end{pmatrix}.$ now let $x=Py,$ where $y=\begin{pmatrix}y_1 \\ y_2 \end{pmatrix}.$ then: $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:

$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 $\lambda_1, \lambda_2 > 0.$ it's clear now that:

$\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 $P$ are the normalized (i.e. of length 1) eigenvectors of K. we know that P is orthogonal, so $\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 $\frac{-v_1}{||v_1||}$

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

Quote:

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

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

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