Общие принципы методов поиска безусловного экстремума

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

ВЯТСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ФАКУЛЬТЕТ ПРИКЛАДНОЙ МАТЕМАТИКИ И ТЕЛЕКОММУНИКАЦИЙ

КАФЕДРА ПРИКЛАДНОЙ МАТЕМАТИКИ И ИНФОРМАТИКИ

Методы поиска безусловного экстремума

Методические указания по выполнению

лабораторных работ

Дисциплина: “Модели и методы поисковой оптимизации”

Для специальности 010200 - "Прикладная математика и информатика", 4 курс д/о

Киров 2006

УДК 519.8

Методические указания предназначены студентам специальности 010200-«Прикладная математика и информатика» дневного отделения при изучении дисциплин «Методы оптимизации» и «Методы и модели поисковой оптимизации». Они могут быть так же полезны и для студентов дневного отделения других специальностей при изучении методов оптимизации.

Составители: Груздева Н.А.,

д.ф.-м.н, профессор Рапопорт А.Н.

Рецензент: к.т.н., доцент каф. ЭВМ Матвеева Л.И.

Оформление лабораторной работы

Цель работы

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

Формирование отчета

Отчет по лабораторной работе должен содержать:

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

2. Краткое описание метода,

3. Блок – схему алгоритма,

4. Листинг программы. Результаты расчетов по программе для указанных функций,

5. Графическую интерпретацию,

6. Применение математических пакетов (Maple, Mathematika, Mathcad),

7. Выводы: анализ результатов и сравнение методов по эффективности.

8. Список использованной литературы.

Общие принципы методов поиска безусловного экстремума

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

Для определенности рассмотрим задачу поиска безусловного локального минимума:

. (1)

Численное решение задачи (1), как правило, связано с построением последовательности точек, обладающих свойством

. (2)

Общее правило построения последовательности имеет вид

, (3)

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

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

Приемлемое направление спуска должно удовлетворять условию

(4)

Обеспечивающему убывание функции . Примером приемлемого направления является направление вектора антиградиента .

Величина шага выбирается либо из условия (2), либо из условия минимума функции вдоль направления спуска:

. (5)

Выбор шага из условия (5) делает спуск в направлении наискорейшим.

Определение1 Последовательность называется минимизирующей, если , т.е. последовательность сходится к нижней грани .

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

В зависимости от наивысшего порядка частных производных функции , используемых для формирования и , численные методы решения задачи безусловной минимизации (1) делятся на 3 группы:

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

¾ Методы первого порядка, использующие информацию о первых производных функции ;

¾ Методы второго порядка, требующие для своей реализации знания вторых производных функции .

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

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

Определение 3 Последовательность называется сходящейся с порядком r, если r – максимальное число, для которого

.

Поскольку величина r определяется предельными свойствами , она называется асимптотической скоростью сходимости.

Определение 4 Если последовательность сходится с порядком r, то число

называется асимптотическим параметром ошибки.

Определение 5 Если r= 1, c< 1, то сходимость линейная; если r= 2, то сходимость квадратичная; если r 1, c= 0, то сходимость сверхлинейная.

Линейная сходимость является синонимом сходимости со скоростью геометрической прогрессии.

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

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

Дата добавления: 2015-07-20