1.1. Контексты ньютоновских методов с регулировкой шага

Здесь и далее , - градиент, и гессиан, вычисленные на итерации в точке процесса безусловной минимизации гладкой функции . В приведённых обозначениях принципы построения большинства ньютоновских методов с регулировкой шага озвучим так. На каждой итерации сначала строится некоторая, связанная с исходной матрицей вторых производных , положительно определённая матрица , а затем направление спуска вычисляется как решение системы . Поскольку положительная определённость гарантирована, то вектор наверняка будет направлением спуска. При этом процедуру построения организуют так, чтобы совпадала с матрицей , если последняя сама является положительно определённой. Это означает, что на каждой итерации каким-то образом выясняется, все ли собственные числа положительны, причем выяснение определенности и построение осуществляется параллельно в рамках одной процедуры на основе некоторых матричных разложений, которые позволяют выявить знаки собственных чисел и приспособиться для генерации . Формула не применима, когда - седловая точка, так как в ней градиент равен нулю, и соответственно решение системы тоже будет нулевым. Здесь в качестве надо взять какое-нибудь направление отрицательной кривизны – вектор, удовлетворяющий неравенству . В седловой точке, где матрица не является знакоопределённой, такие векторы существуют, и при движении вдоль любого из них будет убывать. Важно, чтобы алгоритм его построения по возможности использовал информацию, полученную в процессе построения матрицы . Фактически к нему надо обращаться, как только текущая точка попадает в малую окрестность седловой точки, например, когда норма станет меньше заданного допуска .

1.2. Контексты подхода Гилла и Мюррея

Ниже приводится детальное описание всех операций, выполняемых по ходу построения модифицированной факторизации Холесского с перестановками, дана наиболее эффективная схема организации расчетов [5]. Все фигурирующие в ней величины при реализации на ЭВМ могут размещаться в памяти, первоначально выделяемой для записи исходной матрицы . При этом коэффициенты рассчитываемых факторов занимают места ее использованных элементов. В процессе вычисления - го столбца матрицы участвуют вспомогательные величины . Их также естественно заносить в массив, выделенный для . Точнее говоря, позиции использованных элементов сначала отводятся под запись чисел , а затем, по мере того как необходимость в каких-то числах отпадает, вместо них записываются соответствующие коэффициенты фактора .

Шаг 0. (Расчет порога для элементов). Вычислить , где , а числа и суть максимальные значения модулей диагонального и недиагонального элементов .

Шаг 1. (Инициализация). Присвоить индексу столбца значение 1. Положить .

Шаг 2. (Перестановка строк и столбцов). Найти индекс , такой, что . Поменять местами все данные, отвечающие столбцам матрицы с номерами и , а затем

проделать то же самое с данными, отвечающими ее - ой и - ой строкам.

Шаг 3. (Поиск максимальный по модулю величины ). Вычислить для и найти (если , взять ).

Шаг 4. (Расчет - го диагонального элемента фактора ). Вычислить

и поправку . Если , вычисления прекратить.

Шаг 5. (Расчет - ой строки ). Вычислить для . Для пересчитать диагональные элементы по формуле . Присвоить значение и вернуться к шагу 2.

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

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

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

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