24



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

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

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

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

( 3.1.0 )

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

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

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

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


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

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

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

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


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

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

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

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

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

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

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

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


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

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

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

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

-

- либо , либо .

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

Рисунок 3.2.1

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

Рисунок 3.2.2

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

Рисунок 3.2.3

.

Рисунок 3.2.4

.

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

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

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

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

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

  3. для


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

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

Рисунок 3.3.5

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

Рисунок 3.3.6

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

Рисунок 3.3.7

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

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


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


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

.

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

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

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

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

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

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

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

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

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


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

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

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

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

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


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

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

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

        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

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

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

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

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

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


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

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

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


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

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

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

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

;

Из формул видно, что симметричны относительно середины отрезка .

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

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

Если , то полагают, что , в противном случае .

Посмотрим, как уменьшается отрезок неопределенности

;

....................................................................................

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

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


Замечание 1.

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


Случайные файлы

Файл
169939.rtf
111775.doc
fizmuz.doc
31162.rtf
105057.rtf