Глава 7. Методы одномерной оптимизации

1. Постановка задачи. Основные понятия

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

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

, . (7.1)

Решением или точкой максимума (минимума) этой задачи назовем такую точку , что .

Методы одномерной оптимизации условно подразделяются на три группы.

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

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

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

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

Определение 7.1. Функция называется унимодальной на множестве , если существует единственная точка ее максимума на и

, если и

,если для любых .

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

Рис. 7.1.Унимодальные функции.

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

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

Теорема 7.1.

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

1. Если , то точка минимума не лежит в интервале , т.е.

2. Если , то точка минимума не лежит в интервале , т.е.

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

при

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

Примечание.

Если , то можно исключить оба крайних интервала и ; при этом точка минимума должна располагаться в интервале .

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

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

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

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