24

1. Методы одномерной минимизации.

1Основные понятия

1.1Постановка задачи.

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

( 3.1.0 )

- наименьшее значение на ;

, удовлетворяющее ( 3.1 .0 ) называется точкой минимума на ;

- множество точек минимума на ;

может быть пустым, содержать конечное или бесконечное число точек.

Замечание. Задача поиска максимума сводится к задаче поиска минимума :

Задача одномерной минимизации состоит из двух частей:

• локализации точек минимума, то есть указания отрезков, содержащих единственную точку минимума;

• поиска точки минимума на заданном отрезке при наличии информации о том, что на этом отрезке заведомо существует единственный минимум.

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

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

В основном, ниже рассматриваются численные методы, позволяющие решать локализованные задачи.

2Классический подход.

Напомним 2 важные для данного рассмотрения теоремы из классического анализа.

Теорема Вейерштрасса. Если непрерывна на , то существует.

Теорема Ферма. Пусть дифференцируема в точке . Если доставляет локальный минимум , то

Определение. называется точкой локального минимума, если существует  > 0 такое, что для выполняется

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

Тогда точками минимума могут быть такие точки, в которых:

- терпит разрыв;

- непрерывна, но не существует;

-

- либо , либо .

Рисунки ниже иллюстрируют эти 4 случая.

Рисунок 3.2.1

терпит разрыв в точке .

Рисунок 3.2.2

непрерывна, но производной не существует.

Рисунок 3.2.3

.

Рисунок 3.2.4

.

3Методы решения задачи минимизации для унимодальных функций.

3.1Понятие унимодальной функции.

Определение. унимодальна на , если существуют такие, что

1. строго монотонно убывает на ,

2. строго монотонно возрастает на ,

3. для

Если ,то строго унимодальна.

Унимодальная функция не обязательно должна быть непрерывной и дифференцируемой. Ниже представлены примеры унимодальных функций.

Рисунок 3.3.5

Строго унимодальная, непрерывная, дифференцируемая функция.

Рисунок 3.3.6

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

Рисунок 3.3.7

При имеет разрыв I - го рода, при , производной у не существует.

3.2Общие сведения о численных методах оптимизации, их классификация.

Определение 1. Под численным методом одномерной минимизации понимается процедура получения числовой последовательности приближений к точному решению задачи минимизации.

Определение 2. Под численным методом одномерной минимизации понимается процедура получения вложенных отрезков, покрывающих точное решение:

.

3.2.1Порядок метода.

Метод имеет порядок k, если он использует информацию о производных до k - порядка включительно. Обычно применяются методы 0-го, 1-го и 2-го порядков.

3.2.2Сходимость метода.

Численный метод сходится, если последовательность сходится к точному решению, то есть (скорость сходимости характеризуется ) или метод сходится, если ; (скорость сходимости характеризуется разностью ).

3.2.3Критерии останова.

Процесс вычислений желательно прервать, если

• достигнута требуемая точность вычислений;

• хорошее приближение не найдено, но скорость продвижения к оптимуму так упала, что нет смысла продолжать дальше;

• метод начал расходится или зациклился.

Часто на практике критерием прерывания по 2-й или 3-й причине является выполнение предельно допустимого числа получений приближенных решений.

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

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

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

Поэтому, наряду с этим критерием обычно применяют один из двух следующих или даже сразу два:

где - малые константы.

3.3Методы минимизации 0-го порядка.

Напоминаем, что эти методы оперируют только со значениями .

3.3.1Метод дихотомии.

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

Это значит, что если - точное решение задачи минимизации на , а - приближенное, то

Суть метода заключается в последовательном уменьшении отрезка, покрывающего точку минимума.

Рассмотрим один шаг метода.

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

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

Рисунок 3.3.8

Следовательно, по значению функции в средней точке отрезка нельзя сузить отрезок неопределенности.

Внутри отрезка выберем две точки:

;

где - параметр метода, .

Напоминаем, что выбор малых констант должен быть согласован с машинной точностью, то есть не должны быть меньше машинной точности.

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

Если , то не может в этом случае попасть в отрезок , так как нарушилась бы унимодальность .

Если , то .

Если , то . Но часто этот случай не выделяют отдельно, а включают знак равенства в один из выше рассмотренных случаев.

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

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

На рисунке ниже представлена блок-схема метода дихотомии.

Рисунок 3.3.9

Пометим индексами номер шага.

- левый конец отрезка неопределенности при й итерации.

- соответственно правый конец

Тогда согласно описанию I - го шага

По математической индукции предположим, что

Рассмотрим :

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

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

или

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

Замечание 1.

Из последней оценки видим, что число шагов метода не зависит от вида .

Замечание 2.

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

Пример.

Найти минимум на отрезке c

Решение.

Предварительно оценим, сколько шагов для этого потребуется. Выберем .

.

Поскольку - целое, то потребуется 7 шагов. Осуществим их.

1-й шаг.

.

2-й шаг.

;

.

3-й шаг.

;

.

4-й шаг.

;

.

5-й шаг.

;

.

6-й шаг.

; .

7-й шаг.

;

.

Следовательно, действительно, только 7 шагов приводят к решению с заданной точностью. В качестве принимаем -0,01.

На следующем рисунке проиллюстрировано уменьшение отрезка неопределенности по шагам.

П

Рисунок 3.3.10

ошаговое уменьшение отрезка неопределенности.

3.3.2Метод Фибоначчи.

Часто в вычислительных процедурах существенные трудности возникают в связи с вычислениями значений . Например, вычисляется в процессе эксперимента, либо задана сложной формулой.

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

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

Определение.

Последовательность чисел

называется последовательностью Фибоначчи.

Зададимся некоторым и выпишем последовательность чисел Фибоначчи.

Итак, необходимо найти минимум на отрезке с точностью .

Опишем 1-й шаг метода Фибоначчи.

Как и в предыдущем методе найдем на отрезке :