Методы оптимизации

«скалярную» меру качества – целевую функцию
Определяют набор независимых переменных и

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

Под оптимальностью обычно понимают минимальность целевой функции.

с методами нулевого порядка. Формулируются они следующим образом:
Пусть дан вектор

начального приближения , очередное
приближение рассчитывается по формуле

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

являются векторами спуска. Поскольку
рассматриваются дифференцируемые

функции, то для них всегда
существует достаточно малое , такое, что

Используя возможность разложения целевой функции в ряд Тейлора, и ее
непрерывность, можно записать:

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

минимизации:
Метод Ньютона, в котором направление спуска определяется по формуле


с положительно

определенной матрицей , что обеспечивает значительную область сходимости;
Приближенный метод Ньютона, в котором


где - подходящая аппроксимация матрицы ;

спуска по формуле

. Таким образом,
этот метод является приближенным методом Ньютона, в котором .
Он может рассматриваться и как градиентный метод, поскольку


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


где - скалярная величина, подбираемая таким образом, чтобы
обеспечить взаимную ортогональность направлений

задания метода спуска. Ведь остается еще проблема определения

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

Обычно метод выбора параметра заключается в решении одномерной задачи минимизации:
Найти значение , минимизирующее функцию


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

на каждом шаге метода.

Методы спуска

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

аппроксимации функции вдоль
прямой полиномом и минимизации этого полинома по
переменной .

Квадратичная интерполяция – метод Пауэлла.
Кубическая интерполяция – метод Давидона.


В общем случае процесс решения задачи одномерной минимизации для
определения шага метода носит название линейного поиска.

Методы спуска

критерия останова итеративного процесса. При этом предполагается, что условия, определяющие

направление спуска,



выполнены.

Практика показывает, что искать точное решение задачи о минимуме функции


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

при фиксированных и .

, которое затем уменьшается (делением
пополам)

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

(*)

при .

Линейный поиск

не меньше определенной доли от величины, достигнутой на предыдущей итерации.

Чтобы шаг метода не был слишком маленьким, накладывается еще одно условие (но так, чтобы удовлетворялось и предыдущее):

(**)
при . На практике обычно выбирают
Иногда последнее неравенство заменяют более слабым:

(***)
(вспомним, что поскольку - направление спуска).

Линейный поиск

для всех

. Тогда существует интервал такой, что в методе спуска условия (*) и (**) или (*) и (***) удовлетворяются для любых при
и .
Выбор параметров можно обеспечить многими способами, наиболее современной стратегией является перебор с возвратом
(backtracking technique): при фиксированном значении
начиная со значения уменьшаем его умножением на
до тех пор, пока не выполнится условие (*).
Эта процедура приводится ниже. В качестве входных параметров используются текущее значение вектора , содержащее , имена подпрограмм, вычисляющих значение функции и ее якобиана ,
вектор , содержащий текущее направление поиска, а также значения
, обычно порядка 1.0e-4, и масштабного множителя .
На выходе подпрограмма возвращает , вычисленное при подходящем значении .

Линейный поиск

которой требуется полный перебор всех возможных вариантов в некотором множестве

М. Как правило позволяет решать задачи, в которых ставятся вопросы типа: «Перечислите все возможные варианты …», «Сколько существует способов …», «Есть ли способ …», «Существует ли объект…» и т. п.
Термин backtrack был введен в 1950 году американским математиком Дерриком Генри Лемером.
Незначительные модификации метода поиска с возвратом, связанные с представлением данных или особенностями реализации, имеют и иные названия: метод ветвей и границ, поиск в глубину, метод проб и ошибок и т. д. Поиск с возвратом практически одновременно и независимо был изобретен многими исследователями еще до его формального описания.

Линейный поиск с возвратом