Results 1 to 5 of 5

Math Help - How to minimize a quadratic function using linear algebra

  1. #1
    Newbie JCS007's Avatar
    Joined
    Jun 2008
    From
    Champaign, IL
    Posts
    10

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by JCS007 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jul 2008
    Posts
    2
    i just need the answer too ,who can help us?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Hello !

    This is Gauss's method.

    Quote Originally Posted by JCS007 View Post
    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
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by JCS007 View Post
    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!


    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.
    Last edited by NonCommAlg; July 9th 2008 at 01:12 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Quadratic Function + linear function
    Posted in the Algebra Forum
    Replies: 4
    Last Post: December 20th 2011, 05:46 PM
  2. Replies: 3
    Last Post: May 4th 2011, 10:27 AM
  3. Minimize linear function
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: February 8th 2011, 06:18 AM
  4. Quadratic & Linear Function problem
    Posted in the Pre-Calculus Forum
    Replies: 3
    Last Post: February 10th 2010, 03:53 AM
  5. Adding a Linear Function to a Quadratic Graph
    Posted in the Algebra Forum
    Replies: 2
    Last Post: March 26th 2009, 08:37 AM

Search Tags


/mathhelpforum @mathhelpforum