Задача квадратичной оптимизации - 6 - Метод сопряженных градиентов

Это 20-й день моего участия в ноябрьском испытании обновлений. Узнайте подробности события:Вызов последнего обновления 2021 г.

В этой статье представлен превосходный итерационный метод среди методов квадратичной оптимизации, метод сопряженных градиентов.

описание проблемы

Чтобы переформулировать проблему, нам нужно оптимизировать:

f({\bf{x} }) = \frac{1}{2}{\bf{x^TAx} } - { {\bf{b} }^{\bf{T} } }{\bf{x} } + {\bf{c} } \tag{1} \label{1}

матрица $\bf{A}$ положительно определенная симметрия
Цель состоит в том, чтобы оптимизировать $\bf{x}$ , так что $f(\bf{x})$ получить минимальное значение

Задача с методом наискорейшего спуска

Жадные вычисления локальных минимумов
Нет глобального обзора, нет моделирования реальной модели
В результате процесс оптимизации требует повторных итераций для постепенного приближения к оптимальному значению.

ярмо

Ярмо — это китайский иероглиф, произносимый как è, который изначально относится к изогнутому дереву, которое помещается на шею животного во время движения, а расширенное значение — сдержанность и контроль. Этот текст был записан в таких документах, как «И Ли Цзи Си Ли» и «Сюнь Цзы Чжэн Лунь». --Энциклопедия Baidu

В математике много содержания, связанного с сопряжением, здесь сопряжение означает, что они связаны друг с другом и могут взаимодействовать при определенных условиях.

Источник идеи метода сопряженных градиентов

Для того, чтобы решить задачу о методе наискорейшего спуска туда и обратно, люди стали задумываться над тем, можно ли его непосредственно оптимизировать по определению квадратичной функции, которую нужно оптимизировать, и можно ли получить реальное оптимальное решение через конечно-шаговый расчет.
Затем, предполагая, что мы используем точную модель для проблемы, а не приблизительную локальную оптимальную модель, если мы можем вычислить координаты каждого измерения оптимального решения в N-мерном пространстве, мы можем достичь вышеуказанной цели.
Итак, как спроектировать это пространство, как пошагово рассчитать и интегрировать в реальные результаты — вот задача, которую должен решить метод сопряженных градиентов.
Основная идея этого метода состоит в том, чтобы установить набор оснований, которые линейно независимы в N-мерном пространстве. Теоретически, линейная комбинация этого набора оснований может представлять любую точку в пространстве. Метод сопряженных градиентов может точно решить положение цели в пространстве с помощью нескольких вычислений.Каждый компонент коэффициента в этой группе базисных пространств достигает цели решения оптимального значения
Этот метод и метод наискорейшего спуска отличаются от точного моделирования тем, что с точки зрения Бога каждый итерационный расчет доводит до предела значение компонента, который необходимо настроить в этом направлении, то есть последующий расчет не требует рассмотрим составляющую движения в этом направлении.Теперь это процесс точного решения задачи,а не процесс аппроксимации перехода к оптимальному значению путем простого пошагового моделирования

Определение сопряженной группы

Предполагать $\bf{A}$ за $n$ порядок вещественной симметричной положительно определенной матрицы, если имеется два $n$ Виллевектор $\bf{s}_1$ и $\bf{s}_2$ удовлетворить

{% raw %}

{\bf{s}}_1^T{\bf{A}}{{\bf{s}}_2} = 0 \tag{2} \label{2}

{% endraw %}

вектор $\bf{s}_1$ и $\bf{s}_2$ для матрицы $\bf{A}$ Сопрягать. если $\bf{A}$ — единичная матрица, то формула $\eqref{2}$ стать $\bf{s}_1$$\bf{s}_2$ , так что скалярное произведение двух векторов равно нулю, а два вектора геометрически ортогональны, что является частным случаем сопряжения.

Пусть A — симметричная положительно определенная матрица, если набор ненулевых векторов $\bf{s}_1$ , $\bf{s}_2$ ,…, $\bf{s}_n$ удовлетворить {% сырой %}

{\bf{s}}_i^T{\bf{A}}{{\bf{s}}_j} = 0 (i≠j) \tag{3}

векторная система ${{\bf{s}}_i}(1 \le i \le n)$ речь идет о матрице $\bf{A}$ Сопрягать.

как ${{\bf{s}}_i}(1 \le i \le n)$ линейно независимы, то мы называем набор векторов как $n$ о матрицах в размерном пространстве $\bf{A}$ набор сопряженных групп. {% отрисовать%}

Роль сопряженных групп

Предположим, что имеется набор матриц о $\bf{A}$ сопряженная группа $\bf{D}$ :

\bf{D}=\{ {\bf{d}_1},{\bf{d}_2},...,{\bf{d}_n}\} \tag{4}

Пусть квадратичная функция $\eqref{1}$ Экстремальное значение $\bf{x}^*$ ,использовать $\bf{D}$ Это выглядит как:

{% raw %}

{ {\bf{x} }^*} = {\lambda _1}{ {\bf{d} }_1} + {\lambda _2}{ {\bf{d} }_2} + \cdots + {\lambda _n}{ {\bf{d} }_n} \tag{5}

{% endraw %}

Поскольку производная от экстремального значения функции равна 0 во всех направлениях:

{% raw %}

\begin{array}{l} f'({{\bf{x}}^*}) = {\bf{A}}{{\bf{x}}^*} - {\bf{b}} = 0\\ \Rightarrow {\bf{A}}{{\bf{x}}^*} = {\bf{b}} \end{array} \tag{6}

{% endraw %}

{%raw %} мы вычисляем ${\bf{d}}_i^T{\bf{A}}{{\bf{x}}^*}$ , по взаимному сопряжению между разными сопряженными группами: {% endraw %}

{% raw %}

\begin{array}{l} {\bf{d}}_i^T{\bf{A}}{{\bf{x}}^*} &= {\bf{d}}_i^T{\bf{A}}\left( {{\lambda _0}{{\bf{d}}_0} + \ldots + {\lambda _{n - 1}}{{\bf{d}}_{n - 1}}} \right)\\ &= {\lambda _i}{\bf{d}}_i^T{\bf{A}}{{\bf{d}}_i} + 0\\ \tag{7} \end{array}

{% endraw %}

получить:

{% raw %}

{\lambda _i} = \frac{{{\bf{d}}_i^T{\bf{A}}{{\bf{x}}^*}}}{{{\bf{d}}_i^T{\bf{A}}{{\bf{d}}_i}}} = \frac{{{\bf{d}}_i^T{\bf{b}}}}{{{\bf{d}}_i^T{\bf{A}}{{\bf{d}}_i}}} \tag{8} \label{8}

{% endraw %}

за ${\lambda _i}$ Решение для , мы знаем, что переменные $\bf{b}$ и $\bf{A}$ , если мы получили пространство о $\bf{A}$ Сопряженный базис (любой набор) мы можем решить непосредственно ${\lambda _i}$
Это захватывающий вывод, поэтому в настоящее время мы сосредоточимся на том, как быстро получить набор $\bf{A}$ сопряженная группа

Получить сопряженное основание по определению

С определением нетрудно придумать метод насильственного получения сопряженного основания:

С помощью этого метода мы можем получить сопряженное основание, вычисленное в соответствии с определением, внося $\eqref{8}$ Без проблем рассчитываются экстремальные значения
Но на самом деле это количество операций равно алгебраическому решению {%raw%} ${\bf{A}}{{\bf{x}}} = {\bf{b}}$ Процесс {%endraw%} имеет значительную вычислительную сложность и не приносит прироста производительности задаче оптимизации

Метод сопряженных градиентов

Основные шаги этого алгоритма такие же, как и в методе наискорейшего спуска, а именно нахождение сопряженного направления и вычисление размера шага движения.

Найдите сопряженное направление

Из-за простоты вычисления градиента процесс нахождения сопряженного градиента зависит от вычисления направления градиента.

Цель оптимизации $\bf{x}^*$ , начальное положение $\bf{x}_1$ , сопряженное основание, которое необходимо получить, равно $\bf{D}=\{ {\bf{d}_1},{\bf{d}_2},...,{\bf{d}_n}\}$
Рассчитать начальную $\bf{x}_1$ Градиент положения, первое сопряженное основание является противоположным направлением градиента:

{% raw %}

{{\bf{d}}_1} = - {{\bf{g}}_1} = - ({\bf{A}}{{\bf{x}}_1} - {\bf{b}}) = {\bf{b}} - {\bf{A}}{{\bf{x}}_1} \tag{9}

{% endraw %}

первое $i$ градиенты для удаления $j$ сопряженная группа $(j<i)$ Компонент направления, который необходимо вычесть из $\beta_j$ Количество:

{% raw %}

\begin{array}{l} {\bf{d}}_j^T{\bf{A}}({{\bf{g}}_i} - \beta_j {{\bf{d}}_j}) = 0\\ {\bf{d}}_j^T{\bf{A}}{{\bf{g}}_i} = \beta_j {\bf{d}}_j^T{\bf{A}}{{\bf{d}}_j}\\ \beta_j = \frac{{{\bf{d}}_j^T{\bf{A}}{{\bf{g}}_i}}}{{{\bf{d}}_j^T{\bf{A}}{{\bf{d}}_j}}} \end{array} \tag{10} \label{10}

{% endraw %}

Поэтому первый $k$ Сопряженные основания:

{% raw %}

\begin{array}{l} {{\bf{d}}_k} = {{\bf{g}}_k} - \sum\limits_{i = 1}^{k - 1} {\frac{{{\bf{d}}_i^T{\bf{A}}{{\bf{g}}_k}}}{{{\bf{d}}_i^T{\bf{A}}{{\bf{d}}_i}}}{{\bf{d}}_i}} \\ {{\bf{d}}_k}={{\bf{g}}_k} -\sum\limits_{i = 1}^{k - 1}\beta_i{{\bf{d}}_i} \end{array} \tag{11} \label{11}

{% endraw %}

В настоящее время, если мы можем определить, насколько перемещается каждая итерация $\bf{x}_i$ положение, получить $\bf{g}_i$ , то по первому в первый $i-1$ сопряженные основания определяют текущий $i$ сопряженная группа
Поэтому наша текущая цель состоит в том, как определить расстояние движения в этом направлении после того, как мы получим сопряженное направление

Определить расстояние

{% raw %} был перемещен $\bf{x}_k$ положение, следующее прямое направление ${{\bf{d}}_k}$ , Движение вперед ${\alpha _k}$ , ошибка $\bf{e}_{k}=\bf{x}^*-x_{k}$ , это:

{{\bf{x}}_{k + 1}}={{\bf{x}}_k} + {\alpha _k}{{\bf{d}}_k} \tag{12}

{% endraw %}

Вот два вида прогресса ${\alpha _k}$ идеи.

метод первый

определить первый $k$ длина шага ${\alpha _k}$ , то есть коэффициент сопряженного основания, а условия ограничения коэффициента таковы:

{% raw %} направление текущей сопряженной группы $\bf{d}_{k}$ с вектором ошибки $\bf{e}_{k+1}=\bf{x}^*-x_{k+1}$ Сопрягать:

\begin{aligned} \bf{d}_{k}^{T^{\prime}} A e_{k+1} &=\bf{d}_{k}^{T} A\left(x^{*}-x_{k+1}\right) \\ &=\bf{d}_{k}^{T} A\left(x^{*}-x_{k}+x_{k}-x_{k+1}\right) \\ &=\bf{d}_{k}^{T} A\left(e_{k}-\alpha_{k} \bf{d}_{k}\right) \\ &=\bf{d}_{k}^{T} A e_{k}-\alpha_{k} \bf{d}_{k}^{T} A \bf{d}_{k}=0 \end{aligned} \tag{13} \label{13}

{% endraw %}

имеют:

{% raw %}

\begin{aligned} \alpha_{k} &=\frac{\bf{d}_{k}^{T} A e_{k}}{\bf{d}_{k}^{T} A \bf{d}_{k}} \\ &=\frac{\bf{d}_{k}^{T} A\left(x^{*}-x_{k}\right)}{\bf{d}_{k}^{T} A \bf{d}_{k}} \\ &=\frac{\bf{d}_{k}^{T}\left(A x^{*}-A x_{k}\right)}{\bf{d}_{k}^{T} A \bf{d}_{k}} \\ &=\frac{\bf{d}_{k}^{T}\left(b-A x_{k}\right)}{\bf{d}_{k}^{T} A \bf{d}_{k}} \\ &=-\frac{\bf{d}_{k}^{T} g_{k}}{\bf{d}_{k}^{T} A \bf{d}_{k}} \end{aligned} \tag{14}

{% endraw %}

Способ второй

{% raw %} пара $f({{\bf{x}}_{k + 1}})$ середина ${\alpha _k}$ Берем производную так, чтобы производная была равна 0, вычисляем ${\alpha _k}$ :{% endraw %}

{% исходный %} с ${{\bf{x}}_k}$ выражать ${{\bf{x}}_{k+1}}$ :

\begin{array}{l} f({{\bf{x}}_{k + 1}}) &= f({{\bf{x}}_k} + {\alpha _k}{{\bf{d}}_k})\\ &= \frac{1}{2}{\bf{x}}_{k + 1}^T{\bf{A}}{{\bf{x}}_{k + 1}} - {{\bf{b}}^T}({{\bf{x}}_k} + {\alpha _k}{{\bf{d}}_k}) + c \end{array} \tag{15}

{% endraw %}

{% raw %} пара $f({{\bf{x}}_{k + 1}})$ середина ${\alpha _k}$ Руководство:

\begin{array}{l} f'({{\bf{x}}_{k + 1}}|{\alpha _k}) &= \frac{{\partial f({{\bf{x}}_{k + 1}})}}{{\partial {{\bf{x}}_{k + 1}}}}\frac{{\partial {{\bf{x}}_{k + 1}}}}{{\partial {\alpha _k}}}\\ &= {({\bf{A}}{{\bf{x}}_{k + 1}} - {\bf{b}})^T}{{\bf{d}}_k}\\ &= {({\bf{A}}{{\bf{x}}_k} + {\alpha _k}{\bf{A}}{{\bf{d}}_k} - {\bf{b}})^T}{{\bf{d}}_k}\\ &= {({\alpha _k}{\bf{A}}{{\bf{d}}_k} + {{\bf{g}}_k})^T}{{\bf{d}}_k}\\ &= {\alpha _k}{\bf{d}}_k^TA{{\bf{d}}_k} + {\bf{g}}_k^T{{\bf{d}}_k} \end{array} \tag{16}

{% endraw %}

{% raw %} делает производную нулевой, при этом:

\begin{array}{l} {\alpha _k}{\bf{d}}_k^TA{{\bf{d}}_k} + {\bf{g}}_k^T{{\bf{d}}_k} = 0\\ {\alpha _k} = - \frac{{{\bf{g}}_k^T{{\bf{d}}_k}}}{{{\bf{d}}_k^TA{{\bf{d}}_k}}} = - \frac{{{\bf{d}}_k^T{{\bf{g}}_k}}}{{{\bf{d}}_k^TA{{\bf{d}}_k}}} \end{array} \tag{17}

{% endraw %}

На данный момент мы рассчитали ряд методов для вычисления сопряженных градиентов, и мы можем по очереди получить набор сопряженных оснований, но некоторые из шагов можно еще продолжить для упрощения вычисления.

Упрощенные расчеты и некоторые выводы

Следствие одно

{% сырой %} $k$ шаг вычисляемого градиента $\bf{g}_k$ и до $k-1$ Сопряженный вектор шагов ${\bf{d}_1,\bf{d}_1,...,\bf{d}_{k-1}}$ Ортогональный: {% enddraw %}
{% raw %} доказывает, что когда $i < j$ Время:

\begin{array}{l} \bf{d}_i^T{g_j} &= \bf{d}_i^T(A{x_j} - b)\\ &= \bf{d}_i^T(A{x_j} - A{x^*})\\ &= - \bf{d}_i^T(A{x^*} - {x_{i + 1}} + {x_{i + 1}} - {x_j})\\ &= - \bf{d}_i^TA({e_{i + 1}} - \sum\limits_{k = i + 1}^{j - 1} {{\alpha _k}{d_k})} \\ &= - \bf{d}_i^TA{e_{i + 1}} + \sum\limits_{k = i + 1}^{j - 1} {{\alpha _k}d_i^TA{d_k}} \end{array} \tag{18} \label{18}

{% endraw %}

Режим $\eqref{18}$ ушел из-за $\bf{d}_i$ процесс расчета $\eqref{13}$ равно 0, в правой части, поскольку попарно сопряженные значения разных сопряженных векторов равны 0, конечное значение также равно 0
{% raw %} таким образом доказывает, что: $k$ шаг вычисляемого градиента $\bf{g}_k$ и до $k-1$ Сопряженный вектор шагов ${ \bf{d}_1,\bf{d}_1,...,\bf{d}_{k-1}}$ Ортогональный. {% отрисовать%}

Следствие два

{% сырой %} $k$ шаг вычисляемого градиента $\bf{g}_k$ и до $k-1$ ступенчатый градиент ${\bf{g}_1,\bf{g}_1,...,\bf{g}_{k-1}}$ Ортогональный: {% enddraw %}
{% raw %} доказывает, что когда $i < j$ Когда: {% выводить %}
Зависит от $\eqref{11}$ придется:

{% raw %}

{{\bf{g}}_i}={{\bf{d}}_i} +\sum\limits_{k = 1}^{i - 1}\beta_k{{\bf{d}}_k} \tag{19}

{% endraw %}

имеют:

{% raw %}

\begin{array}{l} {\bf{g}}_i^T{{\bf{g}}_j} &= {({{\bf{d}}_i} + \sum\limits_{k = 1}^{i - 1} {{\beta _k}} {{\bf{d}}_k})^T}{{\bf{g}}_j}\\ &= \sum\limits_{k = 1}^i {{\beta _k}} {{\bf{d}}_k}^T{{\bf{g}}_j} \qquad ({\beta _i} = 1) \tag{20} \label{20} \end{array}

{% endraw %}

в соответствии сСледствие одно,Режим $\eqref{20}$ значение равно 0
{%raw %} подтверждает вывод: первое $k$ шаг вычисляемого градиента $\bf{g}_k$ и до $k-1$ ступенчатый градиент ${\bf{g}_1,\bf{g}_1,...,\bf{g}_{k-1}}$ Ортогональный. {% отрисовать%}
{% raw %} затем для двух разных градиентов $\bf{g}_i, \bf{g}_j(i \ne j)$ , то два должны быть разделены на передний и задний, чтобы градиенты были ортогональны друг другу, то есть ${\bf{G}} = \{ {{\bf{g}}_{1,}}{{\bf{g}}_2},...,{{\bf{g}}_n}\}$ составил $n$ Набор ортонормированных базисов в размерном пространстве {% endraw %}

Следствие три

Расчет {% необработанных %} ${\bf{g}}_{j + 1}^T{{\bf{g}}_i}$ :

\begin{array}{l} {\bf{g}}_{j + 1}^T{{\bf{g}}_i} &= {({\bf{A}}{{\bf{x}}_{j + 1}} - {\bf{b}})^T}{{\bf{g}}_i}\\ &= {({\bf{A}}({{\bf{x}}_j} + {\alpha _j}{{\bf{d}}_j}) - {\bf{b}})^T}{{\bf{g}}_i}\\ &= {({\bf{A}}{{\bf{x}}_j} - {\bf{b}} + {\alpha _j}{\bf{A}}{{\bf{d}}_j})^T}{{\bf{g}}_i}\\ & = {({{\bf{g}}_j} + {\alpha _j}{\bf{A}}{{\bf{d}}_j})^T}{{\bf{g}}_i}\\ &= {\bf{g}}_j^T{{\bf{g}}_i} + {\alpha _j}{\bf{d}}_j^TA{{\bf{g}}_i}\\ {\bf{d}}_j^TA{{\bf{g}}_i}& = \frac{1}{{{\alpha _j}}}({\bf{g}}_{j + 1}^T{{\bf{g}}_i} - {\bf{g}}_j^T{{\bf{g}}_i}) \end{array} \tag{21} \label{21}

{% endraw %}

По формуле $\eqref{21}$ иСледствие два, {% raw %} из-за общего случая $\alpha _j$ не 0, поэтому гарантируется для всех случаев $\eqref{20}$ установлено, необходимо $i \ne j$ и $i \ne j+1$ час, ${\bf{d}}_j^TA{{\bf{g}}_i}=0$ {% endraw %}
Это означает, что текущее направление градиента сопряжено ортогонально всем сопряженным направлениям до и после текущего.

Упрощенные расчеты

Для формулы $\eqref{11}$ , при решении $\bf{d}_k$ Коэффициенты, полученные в процессе $\beta$ , здесь подчеркнуто $\eqref{10}$ :

{% raw %}

{\beta _i} = \frac{{{\bf{d}}_i^T{\bf{A}}{{\bf{g}}_k}}}{{{\bf{d}}_i^T{\bf{A}}{{\bf{d}}_i}}}

{% endraw %}

Зависит отСледствие три{%сырой%}, $\eqref{10}$ Чжундан $i\ne k$ и $i \ne k-1$ час, ${{\bf{d}}_i^T{\bf{A}}{{\bf{g}}_k}}$ Значение равно 0 {% выводить %}
{% raw %} таким образом $\eqref{11}$ можно упростить до:

\begin{array}{l} {{\bf{d}}_k} &= {{\bf{g}}_k} - \sum\limits_{i = 1}^{k - 1} {{\beta _i}} {{\bf{d}}_i}\\ &= {{\bf{g}}_k} - {{\beta _{k-1}}} {{\bf{d}}_{k-1}} \end{array} \tag{22} \label{22}

{% endraw %}

то есть решить $k$ Когда есть сопряженные основания, только текущий градиент $\bf{g}_k$ минус первый $k-1$ Сопряженные компоненты сопряженного основания могут быть

Следствие четвертое

в соответствии сУпрощенные расчетыформула $\eqref{22}$ ,имеют:

{% raw %}

\begin{array}{l} {{\bf{d}}_k} &= {{\bf{g}}_k} - {\beta _{k - 1}}{{\bf{d}}_{k - 1}}\\ &= {{\bf{g}}_k} - {\beta _{k - 1}}({{\bf{g}}_{k - 1}} - {\beta _{k - 2}}{{\bf{d}}_{k - 2}})\\ &= {{\bf{g}}_k} + {\gamma _{k - 1}}{{\bf{g}}_{k - 1}} + {\gamma _{k - 2}}{{\bf{g}}_{k - 2}} + \cdots {\gamma _1}{{\bf{g}}_1}\\ &= \sum\limits_{i = 1}^k {{\gamma _i}{{\bf{g}}_i}} \end{array} \tag{23}

{% endraw %}

где фиксированные постоянные коэффициенты $\gamma$ выражать
Тогда есть:

{% raw %}

\begin{array}{l} {\bf{g}}_i^T{{\bf{d}}_j} &= {\bf{g}}_i^T\sum\limits_{k = 1}^j {{\gamma _k}{{\bf{g}}_k}} \\ & = \sum\limits_{k = 1}^j {{\gamma _k}{\bf{g}}_i^T{{\bf{g}}_k}} \end{array} \tag{24} \label{24}

{% endraw %}

Режим $\eqref{24}$ в соответствии сСледствие дваВывод таков:

{% raw %}

{\bf{g}}_i^T{{\bf{d}}_j} = \left\{ {\begin{array}{*{20}{c}} {0,i > j}\\ {\gamma_i{\bf{g}}_i^T{{\bf{g}}_i},i \le j} \end{array}} \right. \tag{25}

{% endraw %}

То есть проекция градиента на все сопряженные основания равна 0 или константе (не является практическим выводом для этого метода).

Практические шаги метода сопряженных градиентов

Начальные условия: известны $\bf{A}, \bf{b}$ ,начальное положение $\bf{x}_1$
{% raw %} $\bf{g}_1=\bf{A}\bf{x}_1-\bf{b}$ {% endraw %}
{% raw %} ${{\bf{d}}_1} = - {{\bf{g}}_{\bf{1}}}$ {% endraw %}
$k=1$
$while \quad k \le n:$
- {% raw %} $\alpha_{k} = - \frac{{{\bf{d}}_k^T{{\bf{g}}_k}}}{{{\bf{d}}_k^TA{{\bf{d}}_k}}}$ {% endraw %}
- {% raw %} $\bf{x}_{k+1}=\bf{x}_k+\alpha_{k}{\bf{d}}_k$ {% endraw %}
- {% raw %} $\bf{g}_{k+1}=\bf{A}\bf{x}_{k+1}-\bf{b}$ {% endraw %}
- {% raw %} ${\beta _k} = \frac{{{\bf{d}}_k^T{\bf{A}}{{\bf{g}}_{k+1}}}}{{{\bf{d}}_k^T{\bf{A}}{{\bf{d}}_k}}}$ {% endraw %}
- {% raw %} ${{\bf{d}}_{k+1}}={{\bf{g}}_{k+1}} - {{\beta _{k}}} {{\bf{d}}_{k}}$ {% endraw %}
- $k=k+1$
$return \quad \bf{x}_{n+1}$