Scribd Logo
Upload

Welcome to Scribd!

  • 21 views

    Ex 3

    Uploaded by

    danieldemelashalem
    This document discusses the conjugate gradient method for optimization. It begins by defining conjugate directions and linear independence. It then discusses the conjugate gradient algorithm and asks the reader to prove several properties about it. Specifically, it asks the reader to: 1) Show that the coefficients relating the current solution to the optimal solution can be expressed in terms of the conjugate direction vectors. 2) Prove that the residual vector is orthogonal to previous conjugate direction vectors, and use this to show the residual gets smaller at each step. 3) Derive expressions for the denominator of terms in the algorithm and show they are equivalent between two common forms. So in summary, the document introduces conjugate directions and asks the reader to

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Ex 3

    Uploaded by

    danieldemelashalem
    21 views3 pages
    This document discusses the conjugate gradient method for optimization. It begins by defining conjugate directions and linear independence. It then discusses the conjugate gradient algorithm and asks the reader to prove several properties about it. Specifically, it asks the reader to: 1) Show that the coefficients relating the current solution to the optimal solution can be expressed in terms of the conjugate direction vectors. 2) Prove that the residual vector is orthogonal to previous conjugate direction vectors, and use this to show the residual gets smaller at each step. 3) Derive expressions for the denominator of terms in the algorithm and show they are equivalent between two common forms. So in summary, the document introduces conjugate directions and asks the reader to

    Original Title

    ex3

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document discusses the conjugate gradient method for optimization. It begins by defining conjugate directions and linear independence. It then discusses the conjugate gradient algorithm and asks the reader to prove several properties about it. Specifically, it asks the reader to: 1) Show that the coefficients relating the current solution to the optimal solution can be expressed in terms of the conjugate direction vectors. 2) Prove that the residual vector is orthogonal to previous conjugate direction vectors, and use this to show the residual gets smaller at each step. 3) Derive expressions for the denominator of terms in the algorithm and show they are equivalent between two common forms. So in summary, the document introduces conjugate directions and asks the reader to

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    21 views3 pages

    Ex 3

    Uploaded by

    danieldemelashalem
    This document discusses the conjugate gradient method for optimization. It begins by defining conjugate directions and linear independence. It then discusses the conjugate gradient algorithm and asks the reader to prove several properties about it. Specifically, it asks the reader to: 1) Show that the coefficients relating the current solution to the optimal solution can be expressed in terms of the conjugate direction vectors. 2) Prove that the residual vector is orthogonal to previous conjugate direction vectors, and use this to show the residual gets smaller at each step. 3) Derive expressions for the denominator of terms in the algorithm and show they are equivalent between two common forms. So in summary, the document introduces conjugate directions and asks the reader to

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 3

    45010: Optimization I 2019W

    Exercise 3: Conjugate gradient method


    Your Name: Id:

    Note: In all notes, bold face letters denote vectors.

    3.1 Conjugate directions

    The following two questions are about the conjugate directions, be cautious they are different.

    Definition 3.1 If {p0 , p1 , . . . , pl } are A-orthogonal then for i 6= j

    pTi Apj = 0 (3.1)

    Definition 3.2 If {p0 , p1 , . . . , pl } are linearly independent then


    l
    X
    ck pk = 0 (3.2)
    k=1

    only permits solution ck ≡ 0 for all k.

    1. Show that if matrix A of size n × n is positive definite, then there exists a set of nonzero vectors
    {p0 , p1 , . . . , pn−1 } that are A-orthogonal.
    2. Show that if nonzero vectors p0 , p1 , . . . , pl (l < n) are A-orthogonal to each other, then these vectors
    are linearly independent.

    3-1
    3-2 Exercise 3: Conjugate gradient method

    3.2 Conjugate gradient

    See the algorithms listed below (in last page) and answer the following questions. Suppose we know the
    vectors {p0 , p1 , . . . , pn−1 } generated in both algorithms are A-orthogonal.

    1. Suppose x∗ is the minimizer (Ax∗ = b) and x0 is the starting point. Briefly state why can we find
    coefficients ck that
    x0 − x∗ = c0 p0 + · · · + cn−1 pn−1 . (3.3)

    2. Use above relation to show that the k-th step xk satisfies

    (xk − x∗ )T Apl = 0 (3.4)

    for all l ≤ k − 1, then show rkT pl = 0 for l ≤ k − 1.

    3. Use 2. and pk = −rk + βk pk−1 to show that rkT pk = −rkT rk . See (5.14a) and (5.24a). Then use 2. to
    show
    T
    rk+1 rk = 0 (3.5)

    4. Use the conclusion in 2. and 3. to show


    rkT rk
    pTk Apk = (3.6)
    αk
    1
    Hint: write Apk = αk (rk+1 − rk ).

    5. Use the conclusion in 2. and 3. to show


    T
    T rk+1 rk+1
    rk+1 Apk = (3.7)
    αk

    Then show (5.14d) and (5.24d) are equivalent.


    Lecture 3: Conjugate gradient method 3-3

    You might also like