10
$\begingroup$

For a project, I have to implement these two methods and compare how they perform on different functions.

It looks like the conjugate gradient method is meant to solve systems of linear equations of the for

$$ A\mathbf{x} = \mathbf{b} $$

Where $A$ is an n-by-n matrix that is symmetric, positive-definite and real.

On the other hand, when I read about gradient descent I see the example of the Rosenbrock function, which is

$$ f(x_1,x_2) = (1-x_1)^2+100(x_2-x_1^2)^2 $$

As I see it, I can't solve this with a conjugate gradient method. Or do I miss something?

$\endgroup$
13
$\begingroup$

Gradiant descent and the conjugate gradient method are both algorithms for minimizing nonlinear functions, that is, functions like the Rosenbrock function

$ f(x_1,x_2) = (1-x_1)^2 + 100(x_2 - x_1^2)^2 $

or a multivariate quadratic function (in this case with a symmetric quadratic term)

$ f(x) = \frac{1}{2} x^T A^T A x - b^T A x. $

Both algorithms are also iterative and search-direction based. For the rest of this post, $x$, and $d$ will be vectors of length $n$; $f(x)$ and $\alpha$ are scalars, and superscripts denote iteration index. Gradient descent and the conjugate gradient method can be used to find the value $x^*$ that solves

$ \min f(x) $

Both methods start from an initial guess, $x^0$, and then compute the next iterate using a function of the form

$ x^{i+1} = x^i + \alpha^i d^i. $

In words, the next value of $x$ is found by starting at the current location $x^i$, and moving in the search direction $d^i$ for some distance $\alpha^i$. In both methods, the distance to move may be found by a line search (minimize $f(x^i + \alpha^i d^i)$ over $\alpha_i$). Other criteria may also be applied. Where the two methods differ is in their choice of $d^i$. For the gradient method, $d^i = -\nabla f(x^i)$. For the conjugate gradient method, the Grahm-Schmidt procedure is used to orthogonalize the gradient vectors. In particular, $d^0 = -\nabla f(x^0)$, but then $d^1$ is equal $-\nabla f(x^1)$ minus that vector's projection onto $d^0$ such that $(d^1)^Td^0 = 0$. Each subsequent gradient vector is orthogonalized against all the previous ones, which leads to very nice properties for the quadratic function above.

The above quadratic function (and related formulations) is also where the discussion of solving $Ax = b$ using the conjugate gradient method comes from, since the minimum of that $f(x)$ is achieved at the point $x$ where $Ax = b$.

$\endgroup$
9
$\begingroup$

In this context, both methods can be thought of as minimization problems of the function: $$ \phi(\boldsymbol{x}) = \frac{1}{2}\boldsymbol{x}^T\boldsymbol{A}\boldsymbol{x} - \boldsymbol{x}^T\boldsymbol{b} $$ When $\boldsymbol{A}$ is symmetric, then $\phi$ is minimized when $\boldsymbol{A}\boldsymbol{x} = \boldsymbol{b}$.

Gradient descent is the method that iteratively searches for a minimizer by looking in the gradient direction. Conjugate gradient is similar, but the search directions are also required to be orthogonal to each other in the sense that $\boldsymbol{p}_i^T\boldsymbol{A}\boldsymbol{p_j} = 0 \; \; \forall i,j$.

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