Одномерная минимизация. Горячев Л.В. - 3 стр.

                                                                                                    3

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


                                              min f (x)


при условии a ≤ x ≤ b, где a и b-заданные концы отрезка.
Из курса математического анализа известно, что дифференцируемая функция f (x) достигает сво-
его минимума в точках x∗ , где f  (x) = 0 или в граничных точках. Точки, в которых f  (x∗ ) = 0
называются стационарными, их локализация-первый этап решения задачи на экстремум. Из мно-
жества стационарных точек необходимо выделить те, в которых действительно необходимо сравнит
значения функции в точках локального минимума и на концах отрезка и выбрать среди них ми-
нимальное. Соответствующая ему точка будет являться точкой глобального минимума. Решением
нашей задачи будет точка глобального минимума и значение f (x) в этой точке.
Напомним, что для идентификации точки локального минимума исследуют знак второй производ-
ной функции. Достаточным условием локального минимума является положительностьf  (x∗ ) Если
f  (x∗ ) не существует, то следует проследить за знаком первой производной. Перемена знака с “−”
на “+” соответствует случаю убывания функции слева от точки x∗ , и возрастанию справа, т. е.
минимуму функции. Если же f  (x) меняет знак с “−” на “+” при переходе через x∗ , то имеет место
локальный максимум.
Такой способ поиска минимума можно применять в тех случаях, когда функции f (x) и ее производ-
ные вычисляются сравнительно просто. В практических задачах нахождение производных функций
и нахождение корней уравнения f  (x∗ ) = 0 может представлять большие трудности. В связи с этим
важно иметь в арсенале методов оптимизации и методы, основанные не на вычислении производ-
ных, а на вычислении только значений функции в ряде специально подбираемых точек. При этом
естественно желать, чтобы число таких точек стало возможно меньшим, а точность определения
точки оптимума была не ниже заданной.
Последовательность действий при реализации большинства этих методов такова:
1. Согласно некоторому правилу выбирается несколько точек на отрезке [a, b] и на основе анализа
значений в этих точках производится локализация минимума (максимума), т. е. выделяется новый
отрезок[a1 , b1 ], a ≤ a1 < b1 ≤ b, на котором продолжается дальнейший поиск.
2. На полученном отрезке [a1 , b1 ] снова по указанному правилу берется ряд точек для последующей
локализации точки минимума, т. е. получаем новый отрезок. Процесс продолжается до тех пор, по-
ка длина очередного отрезка не станет меньше заданной величины, либо пока не будет вычислено
априори заданное число значений функции.
3. Имеется правило, по которому на последнем отрезке для x∗ .
Очень простые алгоритмы поиска точек минимума (максимума) могут быть получены, если предпо-
ложить, что исследуемая функция f (x) удовлетворяет условию унимодальности (одноэкстремаль-
ности).
Определение: Функция f (x) называется унимодальной на отрезке [a, b], если ∃! точка на этом от-
резке такая, что для любых точек x1 , x2 этого отрезка из x∗ ≤ x1 ≤ x2 =⇒ f (x∗ ) ≤ f (x1 ) ≤ f (x2 );
из x∗ ≥ x1 ≥ x2 =⇒ f (x∗ ) ≥ f (x1 ) ≥ f (x2 ). Другими словами унимодальная функция монотонна на
обе стороны от точки минимума x∗ . Аналогично определяется унимодальная функция и для зада-
чи на максимум. Унимодальные функции могут быть непрерывными, разрывными, дискретными
и другими. . .
   Основное свойство унимодальной функции состоит в том, что при помощи любой пары точек
отрезка можно уменьшить отрезок поиска точки минимума.