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

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

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

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

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

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

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

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

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

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

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

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

Киров 2006

УДК 519.8

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

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

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

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

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

Цель работы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Требуется найти локальный минимум целевой функции на множестве X, т.е. такую точку , что

,

где .

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

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

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

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

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

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

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

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

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

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

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

_,

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

К описанной группе методов относятся метод проекции градиента и метод возможных направлений Зойтендейка.

Определение 1 Нулевой вектор d называется возможным направлением в точке , если существует такое , что для всех .

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

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