Оптимизация функций

Постановка задачи: на множестве (допустимое множество) задана функция (целевая функция) одного или нескольких аргументов, требуется приближенно с заданной точностью найти те значения аргумента (аргументов) из X, в которых эта функция принимает минимальное значение:

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

Метод половинного деления (дихотомия). Предполага-

Рис. 1. Дихотомия

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

где (см. рис. 1). Затем исходный отрезок, содержащий точку минимума, сокращается до следующим способом: если , то выбирается левая часть отрезка, полагаем , , а если , то — правая, , . К полученному отрезку применяется та же процедура выбора пробных точек и сокращения отрезка локализации минимума и т.д., пока не станет

(1)

В качестве приближенного решения можно взять точку

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

Исходный отрезок сокращается до следующим способом: если , то выбирается левая часть отрезка, полагаем , , , а если , то — правая, , , . В алгоритме метода золотого сечения, в отличие от дихотомии, на всех последующих итерациях производится расчет только той точки и значение функции в ней, которые необходимо обновить. При выполнении неравенства вычисляются и , а при — и . Процедура прекращается, когда становится истинным неравенство (1).

Метод градиентного спуска. Алгоритм использует тот факт, что направление, обратное градиенту функции есть направление её самого быстрого убывания (см. Рис. 2). Здесь допустимое множество и функция предполагается непрерывно дифференцируемой в указанной области.