Conjugate gradient methods: Difference between revisions

From Cornell University Computational Optimization Open Textbook - Optimization Wiki
Jump to navigation Jump to search
VisualWikitext
Line 70: Line 70:
Here '''Alg 1''' is with a particular choice of <math>\left\{ \textbf{d}_{0},\textbf{d}_{1},..., \textbf{d}_{n-1}\right\}</math>. Let <math>\textbf{g}_{k} = \textbf{A}\textbf{x}_{k} - \textbf{b}</math> be the gradient at <math>\textbf{x}_k</math>. A practical way to enforce this is by requiring that the next search direction be built out of the current gradient and all previous search directions. The CG method picks <math>\textbf{d}_{k+1}</math> as the component of <math>\textbf{g}_k</math> '''A'''-conjugate to <math>\left\{ \textbf{d}_{0},\textbf{d}_{1},..., \textbf{d}_{n-1}\right\}</math>:<br>
Here '''Alg 1''' is with a particular choice of <math>\left\{ \textbf{d}_{0},\textbf{d}_{1},..., \textbf{d}_{n-1}\right\}</math>. Let <math>\textbf{g}_{k} = \textbf{A}\textbf{x}_{k} - \textbf{b}</math> be the gradient at <math>\textbf{x}_k</math>. A practical way to enforce this is by requiring that the next search direction be built out of the current gradient and all previous search directions. The CG method picks <math>\textbf{d}_{k+1}</math> as the component of <math>\textbf{g}_k</math> '''A'''-conjugate to <math>\left\{ \textbf{d}_{0},\textbf{d}_{1},..., \textbf{d}_{n-1}\right\}</math>:<br>


<math>\textbf{d}_{k+1} = \textbf{g}_k-\sum_{i=0}^{k}\frac{\textbf{g}_{k}^{T}\textbf{A}\textbf{d}_{i}}{\textbf{d}_{i}^{T}\textbf{A}\textbf{d}_{i}}\textbf{d}_i</math><br>
<math>\textbf{d}_{k+1} = \textbf{g}_k-\sum_{i=0}^{k}\frac{\textbf{g}_{k}^{T}\textbf{A}\textbf{d}_{i}}{\textbf{d}_{i}^{T}\textbf{A}\textbf{d}_{i}}\textbf{d}_i</math><br><br>


As <math>\textbf{g}_{k}^{T}\textbf{A}\textbf{d}_{i} = 0</math>, for ''i = 1,...,k'', giving the following CG algorithm:<br>
As <math>\textbf{g}_{k}^{T}\textbf{A}\textbf{d}_{i} = 0</math>, for ''i = 1,...,k'', giving the following CG algorithm:<br>
'''Alg 2''': From a random <math>\text{x}_0</math>,<br>
'''Alg 2''': From a random <math>\text{x}_0</math>,<br>
For ''k = 1'' to ''n'' <br>
For ''k = 1'' to ''n'' <br>
Line 89: Line 87:


The formulas in the '''Alg 2''' can be simplified as the following:<br>
The formulas in the '''Alg 2''' can be simplified as the following:<br>
$$\textbf{x}_i = \textbf{x}_{i-1}+\alpha_i\textbf{d}_i$$<br>
<math>\textbf{x}_i = \textbf{x}_{i-1}+\alpha_i\textbf{d}_i</math><br>
$$\textbf{b}-\textbf{A}\textbf{x}_i = \textbf{b}-\textbf{A}\textbf{x}_{i-1}-\alpha_i\textbf{A}\textbf{d}_i$$<br>
<math>\textbf{b}-\textbf{A}\textbf{x}_i = \textbf{b}-\textbf{A}\textbf{x}_{i-1}-\alpha_i\textbf{A}\textbf{d}_i</math><br>
$$\textbf{g}_i = \textbf{g}_{i-1}-\alpha_i\textbf{A}\textbf{d}_i$$<br><br>
<math>\textbf{g}_i = \textbf{g}_{i-1}-\alpha_i\textbf{A}\textbf{d}_i</math><br>
 
Then <math>\beta_i</math> and <math>\alpha_i</math> can be simplified by multiplying the above gradient formula by <math>\textbf{g}_i</math> and <math>\textbf{g}_{i-1}</math> as the following:<br>
Then $$\beta_i$$ and $$\alpha_i$$ can be simplified by multiplying the above gradient formula by $$\textbf{g}_i$$ and $$\textbf{g}_{i-1}$$ as the following:<br>
<math>\textbf{g}_{i}^{T}\textbf{g}_i = -\alpha_i\textbf{g}_{i}^{T}\textbf{A}\textbf{d}_i</math><br>
$$\textbf{g}_{i}^{T}\textbf{g}_i = -\alpha_i\textbf{g}_{i}^{T}\textbf{A}\textbf{d}_i$$<br>
<math>\textbf{g}_{i-1}^{T}\textbf{g}_{i-1} = \alpha_i\textbf{g}_{i-1}^{T}\textbf{A}\textbf{d}_i</math><br>
$$\textbf{g}_{i-1}^{T}\textbf{g}_{i-1} = \alpha_i\textbf{g}_{i-1}^{T}\textbf{A}\textbf{d}_i$$<br>
As <math>\textbf{g}_{i-1} = \textbf{d}_i+\beta_i\textbf{d}_{i-1}</math>,<br>
As $$\textbf{g}_{i-1} = \textbf{d}_i+\beta_i\textbf{d}_{i-1}$$, so we have<br>
so we have<br>
$$\textbf{g}_{i-1}^{T}\textbf{g}_{i-1} = \alpha_i\textbf{g}_{i-1}^{T}\textbf{A}\textbf{d}_i=\alpha_i\textbf{d}_{i}^{T}\textbf{A}\textbf{d}_i$$<br>
<math>\textbf{g}_{i-1}^{T}\textbf{g}_{i-1} = \alpha_i\textbf{g}_{i-1}^{T}\textbf{A}\textbf{d}_i=\alpha_i\textbf{d}_{i}^{T}\textbf{A}\textbf{d}_i</math><br>
Therefore <br>
Therefore <br>
$$\beta_{i+1} = -\frac{\textbf{g}_{i}^{T}\textbf{g}_{i}}{\textbf{g}_{i-1}^{T}\textbf{g}_{i-1}}$$<br><br>
<math>\beta_{i+1} = -\frac{\textbf{g}_{i}^{T}\textbf{g}_{i}}{\textbf{g}_{i-1}^{T}\textbf{g}_{i-1}}</math><br>
 
This gives the following simplified version of '''Alg 2''':<br>
This gives the following simplified version of '''Alg 2''':<br>
'''Alg 3''': From a random <math>\textbf{x}_0</math>, and set <math>\textbf{g}_0 = \textbf{b} - \textbf{A}\textbf{x}_0</math>,<br>
For k = 1 to n<br>
{<br>
#if <math>\textbf{g}_{k-1} = 0</math> return <math>\textbf{x}_{k-1}</math>;<br>
#if (''k > 1'') <math>\beta_k = -(\textbf{g}_{k-1}^{T}\textbf{g}_{k-1})/(\textbf{g}_{k-2}^{T}\textbf{g}_{k-2})</math>;<br>
#if (''k = 1'') <math>\textbf{d}_k = \textbf{g}_0</math>;<br>
#else <math>\textbf{d}_{k} = \textbf{g}_{k-1}-\beta_k\textbf{d}_{k-1}</math>;<br>
#<math>\alpha_k=(\textbf{g}_{k-1}^{T}\textbf{g}_{k-1})/(\textbf{d}_{k}^{T}\textbf{A}\textbf{d}_k)</math>;<br>
#<math>\textbf{x}_k = \textbf{x}_{i-1} + \alpha_i\textbf{d}_i</math><br>
#<math>\textbf{g}_{i}=\textbf{g}_{i-1}-\alpha_i\textbf{A}\textbf{d}_i</math>;<br>
}<br>
Return <math>\textbf{x}_n</math><br>


== Numerical example ==
== Numerical example ==

Revision as of 03:03, 28 November 2021

Author: Alexandra Roberts, Anye Shi, Yue Sun (SYSEN6800 Fall 2021)

Introduction

The conjugate gradient method (CG) was originally invented to minimize a quadratic function:
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F(\textbf{x})=\frac{1}{2}\textbf{x}^{T}\textbf{A}\textbf{x}-\textbf{b}\textbf{x}}
where A is an n × n symmetric positive definite matrix, x and b are n × 1 vectors.
The solution to the minimization problem is equivalent to solving the linear system, i.e. determining x when Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \nabla F(x) = 0} , i.e.Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textbf{A}\textbf{x}-\textbf{b} = \textbf{0}}

The conjugate gradient method is often implemented as an iterative algorithm and can be considered as being between Newton’s method, a second-order method that incorporates Hessian and gradient, and the method of steepest descent, a first-order method that uses gradient [1]. Newton’s Method usually reduces the number of iterations needed, but the calculation of the Hessian matrix and its inverse increases the computation required for each iteration. Steepest descent takes repeated steps in the opposite direction of the gradient of the function at the current point. It often takes steps in the same direction as earlier ones, resulting in slow convergence (Figure 1). To avoid the high computational cost of Newton’s method and to accelerate the convergence rate of steepest descent, the conjugate gradient method was developed.

The idea of the CG method is to pick n orthogonal search directions first and, in each search direction, take exactly one step such that the step size is to the proposed solution x at that direction. The solution is reached after n steps as, theoretically, the number of iterations needed by the CG method is equal to the number of different eigenvalues of A, i.e. at most n. This makes it attractive for large and sparse problems. The method can be used to solve least-squares problems and can also be generalized to a minimization method for general smooth functions[2].

Theory

The definition of A-conjugate direction

Let A be a symmetric positive definite matrix. are the vectors that orthogonal (conjugate) to each other with respect to A if
.

Note that if A = 0, any two vectors will be conjugated to each other. If A = I, conjugacy is equivalent to the conventional notion of orthogonality. If are A-conjugated to each other, then the set of vectors are linearly independent.

The motivation of A-conjugacy

As is a set of n A-conjugate vectors, then can be used as a basis and express the solution x* to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \nabla F(\textbf{x}) = \textbf{Ax} - \textbf{b} = \textbf{0}} is:
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textbf{x}^{*} = \sum_{i=0}^{n-1}\alpha _{i} \textbf{d}_{i}}

Then multiplying dKT on both sides
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textbf{d}_{k}^{T}\textbf{A}\textbf{x}^{*} = \sum_{i=0}^{n-1}\alpha _{i} \textbf{d}_{k}^{T}\textbf{A}\textbf{d}_{i}}
Because and the A-conjugacy of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D} , i.e. Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textbf{d}_{k}^{T}\textbf{A}\textbf{d}_i = 0, \forall k \neq i} , the multiplication will cancel out all the terms except for term k
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textbf{d}_{k}^{T}\textbf{b} = \alpha _{k} \textbf{d}_{k}^{T}\textbf{A}\textbf{d}_{k}}

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha_{k}=\frac{\textbf{d}_{k}^{T}\textbf{b}}{\textbf{d}_{k}^{T}\textbf{A}\textbf{d}_{k}}}

Then the solution x* will be
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textbf{x}^{*}= \sum_{i=0}^{n-1}\alpha _{i}\textbf{d}_{i}=\sum_{i=0}^{n-1}\frac{\textbf{d}_{i}^{T}\textbf{b}}{\textbf{d}_{i}^{T}\textbf{A}\textbf{d}_{i}}\textbf{d}_{i}}

Because A is a symmetric and positive-definite matrix, so the term Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textbf{d}_{i}^{T}\textbf{A}\textbf{d}_{i}} defines an inner product and, therefore, no need to calculate the inversion of matrix A.

Conjugate Direction Theorem

Let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D=\left\{ \textbf{d}_{0},\textbf{d}_{1},..., \textbf{d}_{n-1}\right\}} be a set of n A-conjugate vectors, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textbf{x}_0 \in \textbf{R}^n} be a random starting point. Then
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textbf{x}_{k+1} = \textbf{x}_{k} + \alpha_{k} \textbf{d}_{k}}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textbf{g}_{k} = \textbf{b}- \textbf{A}\textbf{x}_{k}}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha_{k} = \frac{\textbf{g}_{k}^{T}\textbf{d}_{k}}{\textbf{d}_{k}^{T}\textbf{A}\textbf{d}_{k}} =\frac{(\textbf{b}-\textbf{A}\textbf{x}_{k})^{T}\textbf{d}_{k}}{\textbf{d}_{k}^{T}\textbf{A}\textbf{d}_{k}}}
After n steps, xn = x*.

Proof:
Given
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textbf{x}^* - \textbf{x}_0 = \alpha_0\textbf{d}_0 + \alpha_1\textbf{d}_1+...+\alpha_{n-1}\textbf{d}_{n-1}}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textbf{x}^k - \textbf{x}_0 = \alpha_0\textbf{d}_0 + \alpha_1\textbf{d}_1+...+\alpha_{k-1}\textbf{d}_{k-1}}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textbf{g}_k = \textbf{b}-\textbf{A}\textbf{x}_k = \textbf{A}\textbf{x}^{*}-\textbf{A}\textbf{x}_k = \textbf{A}(\textbf{x}^{*}-\textbf{x}_k)}
Therefore

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textbf{d}_{k}^{T}\textbf{A}(\textbf{x}^*-\textbf{x}_0) = \textbf{d}_{k}^{T}\textbf{A}(\alpha_0\textbf{d}_0+\alpha_1\textbf{d}_1 +...+\alpha_{n-1}\textbf{d}_{n-1}) = \alpha_k\textbf{d}_{k}^{T}\textbf{A}\textbf{d}_k}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha_{k} = \frac{\textbf{d}_{k}^{T}\textbf{A}(\textbf{x}^*-\textbf{x}_0)}{\textbf{d}_{k}^{T}\textbf{A}\textbf{d}_k}}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textbf{d}_{k}^{T}\textbf{A}(\textbf{x}_k-\textbf{x}_0) = \textbf{d}_{k}^{T}\textbf{A}(\alpha_0\textbf{d}_0+\alpha_1\textbf{d}_1 +...+\alpha_{k-1}\textbf{d}_{k-1} ) = 0}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textbf{d}_{k}^{T}\textbf{A}(\textbf{x}^*-\textbf{x}_0) = \textbf{d}_{k}^{T}\textbf{A}(\textbf{x}^*-\textbf{x}_k + \textbf{x}_k - \textbf{x}_0) =\textbf{d}_{k}^{T}\textbf{A}(\textbf{x}^*-\textbf{x}_k) }
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha_k = \frac{\textbf{d}_{k}^{T}\textbf{A}(\textbf{x}^*-\textbf{x}_0)}{\textbf{d}_{k}^{T}\textbf{A}\textbf{d}_k} = \frac{\textbf{d}_{k}^{T}\textbf{A}(\textbf{x}^*-\textbf{x}_k)}{\textbf{d}_{k}^{T}\textbf{A}\textbf{d}_k}=\frac{\textbf{d}_{k}^{T}\textbf{g}_k}{\textbf{d}_{k}^{T}\textbf{A}\textbf{d}_k}}

The conjugate gradient method

The conjugate gradient method is a conjugate direction method in which selected successive direction vectors are treated as a conjugate version of the successive gradients obtained while the method progresses. The conjugate directions are not specified beforehand but rather are determined sequentially at each step of the iteration[3]. If the conjugate vectors are carefully chosen, then not all the conjugate vectors may be needed to obtain the solution. Therefore, the conjugate gradient method is regarded as an iterative method. This also allows approximate solutions to systems where n is so large that the direct method requires too much time.

Algorithm

Given Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D=\left\{ \textbf{d}_{0},\textbf{d}_{1},..., \textbf{d}_{n-1}\right\}} be a set of n A-conjugate vectors, then Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F(\textbf{x}_0 +\alpha_1\textbf{d}_1 + \alpha_2\textbf{d}_2+...+\alpha_{n}\textbf{d}_{n})} can be minimized by stepping from Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textbf{x}_0} along Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textbf{d}_1} to the minimum Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textbf{x}_1} , stepping from Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textbf{x}_1} along Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textbf{d}_2} to the minimum Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textbf{x}_2} , etc. And let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textbf{x}_0 \in \textbf{R}_n} be randomly chosen, then the algorithm is the following:

Alg 1: Pick Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left\{ \textbf{d}_{0},\textbf{d}_{1},..., \textbf{d}_{n-1}\right\}} mutually A-conjugate, and from a random Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textbf{x}_0} ,
For k = 1 to n
{

  1. Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha_k = \textbf{d}_{k}^{T}(\textbf{b}-\textbf{A}\textbf{x}_{k-1})/\textbf{d}_{k}^{T}\textbf{A}\textbf{d}_k} ;
  2. Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textbf{x}_{k} = \textbf{x}_{k-1} + \alpha_{k}\textbf{d}_{k}} ;

}
Return Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textbf{x}_n}

Here Alg 1 is with a particular choice of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left\{ \textbf{d}_{0},\textbf{d}_{1},..., \textbf{d}_{n-1}\right\}} . Let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textbf{g}_{k} = \textbf{A}\textbf{x}_{k} - \textbf{b}} be the gradient at Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textbf{x}_k} . A practical way to enforce this is by requiring that the next search direction be built out of the current gradient and all previous search directions. The CG method picks Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textbf{d}_{k+1}} as the component of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textbf{g}_k} A-conjugate to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left\{ \textbf{d}_{0},\textbf{d}_{1},..., \textbf{d}_{n-1}\right\}} :

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textbf{d}_{k+1} = \textbf{g}_k-\sum_{i=0}^{k}\frac{\textbf{g}_{k}^{T}\textbf{A}\textbf{d}_{i}}{\textbf{d}_{i}^{T}\textbf{A}\textbf{d}_{i}}\textbf{d}_i}

As Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textbf{g}_{k}^{T}\textbf{A}\textbf{d}_{i} = 0} , for i = 1,...,k, giving the following CG algorithm:
Alg 2: From a random Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{x}_0} ,
For k = 1 to n
{

  1. Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textbf{g}_{k-1} = \textbf{b}-\textbf{A}\textbf{x}_{k-1}} ;
  2. if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textbf{g}_{k-1} = 0} return Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textbf{x}_{k-1}} ;
  3. if (k > 1) Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \beta_k = \textbf{d}_{k-1}^T\textbf{A}\textbf{g}_{k-1}/{\textbf{d}_{k-1}^T\textbf{A}\textbf{d}_{k-1}}} ;
  4. if (k = 1) Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textbf{d}_k = \textbf{g}_0} ;
  5. else Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textbf{d}_{k} = \textbf{g}_{k-1}-\beta_k\textbf{d}_{k-1}} ;
  6. Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha_{k} = \textbf{d}_{k}^{T}\textbf{g}_{k-1}/\textbf{d}_{k}^{T}\textbf{A}\textbf{d}_{k}} ;
  7. Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textbf{x}_{k} = \textbf{x}_{k-1} + \alpha_{k}\textbf{d}_{k} } ;

}
Return Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textbf{x}_n}

The formulas in the Alg 2 can be simplified as the following:
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textbf{x}_i = \textbf{x}_{i-1}+\alpha_i\textbf{d}_i}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textbf{b}-\textbf{A}\textbf{x}_i = \textbf{b}-\textbf{A}\textbf{x}_{i-1}-\alpha_i\textbf{A}\textbf{d}_i}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textbf{g}_i = \textbf{g}_{i-1}-\alpha_i\textbf{A}\textbf{d}_i}
Then Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \beta_i} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha_i} can be simplified by multiplying the above gradient formula by Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textbf{g}_i} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textbf{g}_{i-1}} as the following:
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textbf{g}_{i}^{T}\textbf{g}_i = -\alpha_i\textbf{g}_{i}^{T}\textbf{A}\textbf{d}_i}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textbf{g}_{i-1}^{T}\textbf{g}_{i-1} = \alpha_i\textbf{g}_{i-1}^{T}\textbf{A}\textbf{d}_i}
As Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textbf{g}_{i-1} = \textbf{d}_i+\beta_i\textbf{d}_{i-1}} ,
so we have
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textbf{g}_{i-1}^{T}\textbf{g}_{i-1} = \alpha_i\textbf{g}_{i-1}^{T}\textbf{A}\textbf{d}_i=\alpha_i\textbf{d}_{i}^{T}\textbf{A}\textbf{d}_i}
Therefore
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \beta_{i+1} = -\frac{\textbf{g}_{i}^{T}\textbf{g}_{i}}{\textbf{g}_{i-1}^{T}\textbf{g}_{i-1}}}
This gives the following simplified version of Alg 2:
Alg 3: From a random Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textbf{x}_0} , and set Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textbf{g}_0 = \textbf{b} - \textbf{A}\textbf{x}_0} ,
For k = 1 to n
{

  1. if Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textbf{g}_{k-1} = 0} return Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textbf{x}_{k-1}} ;
  2. if (k > 1) Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \beta_k = -(\textbf{g}_{k-1}^{T}\textbf{g}_{k-1})/(\textbf{g}_{k-2}^{T}\textbf{g}_{k-2})} ;
  3. if (k = 1) Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textbf{d}_k = \textbf{g}_0} ;
  4. else Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textbf{d}_{k} = \textbf{g}_{k-1}-\beta_k\textbf{d}_{k-1}} ;
  5. Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha_k=(\textbf{g}_{k-1}^{T}\textbf{g}_{k-1})/(\textbf{d}_{k}^{T}\textbf{A}\textbf{d}_k)} ;
  6. Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textbf{x}_k = \textbf{x}_{i-1} + \alpha_i\textbf{d}_i}
  7. Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textbf{g}_{i}=\textbf{g}_{i-1}-\alpha_i\textbf{A}\textbf{d}_i} ;

}
Return Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textbf{x}_n}

Numerical example

Application

Conclusion

Reference

Jonathan Shewchuk, “An Introduction to the Conjugate Gradient Method Without the Agonizing Pain,” 1994.

  1. ↑ “Conjugate gradient method,” Wikipedia. Nov. 25, 2021. Accessed: Nov. 26, 2021. [Online]. Available: https://en.wikipedia.org/w/index.php?title=Conjugate_gradient_method&oldid=1057033318
  2. ↑ W. Stuetzle, “The Conjugate Gradient Method.” 2001. [Online]. Available: https://sites.stat.washington.edu/wxs/Stat538-w03/conjugate-gradients.pdf
  3. ↑ A. Singh and P. Ravikumar, “Conjugate Gradient Descent.” 2012. [Online]. Available: http://www.cs.cmu.edu/~pradeepr/convexopt/Lecture_Slides/conjugate_direction_methods.pdf
Retrieved from "https://optimization.cbe.cornell.edu/index.php?title=Conjugate_gradient_methods&oldid=3915"