Модели и методы конечномерной оптимизации

Одномерная оптимизация, метод "золотого сечения". Условная нелинейная оптимизация, применение теоремы Джона-Куна-Таккера. Исследование функции на выпуклость и овражность. Безусловная оптимизация неквадратичной функции, метод Дэвидона-Флетчера-Пауэлла.
Краткое сожержание материала:

Размещено на

Содержание

1. Одномерная оптимизация. Метод «золотого сечения»

2. Условная нелинейная оптимизация. Применение теоремы Джона-Куна-Таккера

3. Линейное программирование. Симплекс-метод

4. Исследование множества на выпуклость

5. Исследование функции на выпуклость

6. Исследование функции на овражность

7. Безусловная оптимизация неквадратичной функции овражной структуры. Метод Дэвидона-Флетчера-Пауэлла

8. Сведение задачи условной оптимизации к безусловной задаче оптимизации

8.1 Метод внешних штрафных функций

8.2 Метод возможных направлений Зойтендейка

9. Вывод

10. Список литературы

11. Приложения

1. Одномерная оптимизация. Метод «золотого сечения»

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

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

Теоретические сведения:

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

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

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

Точка называется точкой локального (относительного) минимума (максимума) функции на множестве , если существует , такое, что, если , то .

Здесь - норма вектора в конечном n-мерном евклидовом пространстве.

Теорема 1.1 (необходимые условия экстремума первого порядка)

Пусть есть точка локального минимума (максимума) функции на множестве и дифференцируема в точке . Тогда аргумент функции в точке равен нулю, т.е.



или

Теорема 1.2 (достаточные условия экстремума первого порядка)

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

и

, тогда точка есть точка локального минимума (максимума) функции на множестве .

Решение:

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

(1)

что соответствует формуле площади поверхности закрытого цилиндра с параметрами радиуса r и высоты h.

Т.к. в задаче указано, что у бака фиксированный объем, то можно записать уравнение связи между параметрами бака, т.е.:

(2)

Уравнение (2) дает возможность свести задачу минимизации целевой функции от двух параметров к одномерной минимизации целевой функции одного параметра, например:

(3)

Используя необходимые и достаточные условия экстремума функции:

(4)

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

С учетом уравнения связи (2) получаем решение:

(5)

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

(6)

Программная реализация данной задачи методом «золотого сечения» находится в приложении 11.1.

Метод «золотого сечения»:

«Золотым сечением» отрезка называется такое разбиение отрезка на две неравные части, что отношение длины всего отрезка к длине большей части равно отношению длины большей части к длине меньшей части отрезка.

«Золотое сечение» отрезка осуществляется каждой из двух симметрично расположенных относительно центра отрезка точек:

Алгоритм:

(шаг 1)Находим точки, осуществляющие «золотое сечение» отрезка из системы:

, где

(шаг 2) Сравниваем значения функций в точках «золотого сечения»

-Если

-Если

(шаг 3) Проверяем условие остановки алгоритма

, если не выполняется, переходим на (шаг 1),

иначе вычисляем точку минимума

2. Условная нелинейная оптимизация. Применение теоремы Джона-Куна-Таккера

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

Требуется решить задачу вида:

Теоретические сведения:

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

Обобщенной функцией Лагранжа называется функция вида:

где - множители Лагранжа

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

Градиентом обобщенной функции Лагранжа по х называется вектор-столбец, составленный из ее частных производных первого порядка ():

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

Вторым дифференциалом обобщенной функции Лагранжа называется функция:

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

Первым дифференциалом ограничений называется функция:

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

Ограничение называется активным в точке , если . Если , то ограничение называется пассивным.

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

Градиенты ограничений являются линейно независимыми в точке , если равенство

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

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

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

Теорема 2.1 (Джона-Куна-Таккера) (необходимые условия минимума (максимума) первого порядка)

Пусть - точка локального минимума (максимума) в данной задаче, тогда найдется такое число и вектор , не равные одновременно нулю, что выполняются условия:

а) Условие нетривиальности:

б) Условие стационарности обобщенной функции Лагранжа:

в) Условие допустимости решения:

г) Условие согласования знаков:

д) Условие дополняющей нежесткости:

Теорема 2.2(достаточные условия минимума (максимума) первого порядка)

Пусть имеется точка , удовлетворяющая системе уравнений теоремы 2.1 при , число активных ограничений в точке совпадает с числом переменных (при этом условие регулярности выполняется, т.е. градиенты активных ограничений в точке линейно независимы). Если для всех , то точка - точка условного локального минимума. Если для всех , то - точка условного локального максимума.

Теорема 2.3(достаточное условие экстремума второго порядка)

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

Если в этой точке для всех ненулевых таких, что

То точка является точкой локального минимума (максимума) в данной задаче.

Замечание 2.1

Если функции выпуклые, то условия теоремы 2.1 являются одновременно и достаточными условиями глобального минимума

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

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

Решение:

Перепишем условие



(ШАГ 1)

Составим обобщенную функцию Лагранжа:

(ШАГ 2)

Запишем необходимые условия экстремума первого порядка:

а) Условие нетривиальности:

б) Условие стационарности обобщенной функции Лагранжа:

или

в) Условие допустимости решения:

г) Условие согласования знаков:

д) Условие дополняющей нежесткости:

(ШАГ 3)

Решаем систему

для двух случаев:

Тогда получаем две системы для рассмотрения:

1) Рассмотрим случай и соответствующие ему вариантов (различных комбинаций ), удовлетворяющих условию дополняющей нежесткости:

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

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

Система перепишется как:

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

Видно, что решение можно найти из последних двух уравнений системы, т.е.:



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

2) Рассмотрим случай и соответствующие ему вариантов (различных комбинаций ), удовлетворяющих условию дополняющей нежесткости:

Из первых двух уравнений получаем:

Полученную точку следует проверить на выполнение условий, записанных на (шаге 2).

Условия выполняются. Активное ограничение: . Пассивное ограничение: .

Из системы получаем:



Полученные точки проверяем на выполнение условий, записанных на (шаге 2).

Все три точки не л...