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

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

(13)

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

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

При практической реализации методов поиска экстремума функции выделяют два этапа:

- этап установления границ интервала, на котором реализуется процедура поиска границ достаточно широкого интервала, содержащего экстремум функции;

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

На первом этапе обычно используют эвристические методы поиска. В качестве примера приведем здесь эвристический метод, предложенный Свенном. Согласно этому методу (k+1)-ая пробная точка определяется по рекуррентной формуле :

(14)

где - произвольно выбранная начальная точка, D - шаг изменения по оси абсцисс.

Знак D определяется путем сравнения значений функции , и . Если

, (15)

то, согласно предположению об унимодальности, точка минимума х* должна располагаться правее точки и величина D выбирается положительной. Если изменить знаки неравенства (24) на противоположные, то D следует выбрать отрицательной. Если же

, (16)

то точка минимума х* расположена между и и поиск граничных точек закончен.

После того, как установлены границы интервала, содержащего точку экстремума функции, приступают к реализации второго этапа, т.е. уменьшению интервала поиска с целью получения уточненных оценок координаты точки х*. Для этого используют различные итерационные методы, которые отличаются друг от друга объемом производимых вычислений и получаемой при этом точностью. Рассмотрим наиболее употребительные методы поиска координаты точки х* функции .

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

Предлагаю ознакомиться с аналогичными статьями:

Алгоритмы

• Метод золотого сечения
• Изучение и практическое применение методов приближения функций.
• Аутентификация
• Динамические ОЗУ.
• Регулярные выражения. Свойства регулярных выражений

Оптимизация

• Безусловная минимизация функций численными методами второго порядка.
• Метод сопряженных градиентов Флетчера-Ривса.
• Метод наискорейшего спуска.
• Градиентные методы.
• Формулировка задачи многомерной оптимизации.
• Метод поиска минимума функции одной переменной с использованием кубичной аппроксимации

Моделирование

• Определение требуемого размера выборки.
• Задачи имитационных экспериментов.
• Определение длительности переходного процесса.
• Исследование свойств имитационной модели.
• Калибровка имитационной модели.