1. Алгоритм Гольдштайна и Прайса

Можно строить аналогичные алгоритмы, аппроксимируя в процессе поиска не матрицу , а матрицу . А затем строить обратную к ней. Таким образом, на каждой итерации находится , где – оценка , а матрица – симметрическая матрица ранга 1, такая, что удовлетворяет уравнению . При этом

.                    (15)

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

К алгоритмам такого типа относится алгоритм Гольштайна и Прайса, который описывается следующей последовательностью действий и предназначен для минимизации выпуклых функций.

Гольштайн и Прайс использовали не (15), а проводили аппроксимацию матрицы при помощи разностной схемы, основанной на полу­фак­ториальном построении (полуфакториал – произведение n первых четных чисел), а затем проводили обращение матрицы. При этом для оценки требуется лишь информация о и .

На k-м этапе алгоритм выглядит следующим образом. Заранее заданы величины и .

1. Вычисляется в качестве аппроксимации матрица , j-й столбец которой определяется по формуле

,

где    для ,  ,   – j-й столбец единичной матрицы размерности . – вектор-столбец, определяемый в соответствии с условиями:

• , если или сингулярна, или , так что матрица не является положительно определенной;

• – в противном случае.

Заметим, что матрица не обязательно симметрическая матрица, и если , то предлагаемое направление поиска и направление градиента отличаются более чем на 90⁰. Следовательно, может быть направлено в сторону, в которой увеличивается.

2. Для выражения

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

3. Берется  .

4. Процесс заканчивается, когда .

Параметр следует выбирать так, чтобы матрица аппроксими­ровала как можно ближе. Величина выбирается так, чтобы значения , , представляли собой монотонно убывающую последователь­ность; чем ближе значение к 1/2, тем в большей степени приближается к своему минимуму по .