Главная

Категории:

ДомЗдоровьеЗоологияИнформатикаИскусствоИскусствоКомпьютерыКулинарияМаркетингМатематикаМедицинаМенеджментОбразованиеПедагогикаПитомцыПрограммированиеПроизводствоПромышленностьПсихологияРазноеРелигияСоциологияСпортСтатистикаТранспортФизикаФилософияФинансыХимияХоббиЭкологияЭкономикаЭлектроника






Геометрическая интерпретация условий К-Т.


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

, при , т.е. вектор принадлежит этому конусу.

т. – точка оптимума

принадлежит конусу, натянутому на активные ограничения

т. – не является точкой оптимума

3. Необходимые условия Кука-Таккера для задачи со смешанными ограничениями (равенствами и неравенствами)

Рассмотрим задачу:

Минимизировать:

При условий:

– непустое открытое множество

Пусть – некотороая допустимая точка задачи

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

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

Если точка является локальным решением задачи, то в ней выполняются условия Кука-Таккера:

=0

В векторной форме условия К-Т: 52

– матрица (n x m)

– матрица (n x l)

При довольно слабых предположениях о выпуклости функций условия К-Т являются также достаточными для оптимальности условиями.

Условия К-Т являются обобщением правила множителей Лагранжа (учитывают ограничение в виде неравенств)

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

 

ЧИСЛЕННЫЕ МЕТОДЫ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ.

Простейший алгоритм, предназначенный для решения задач с ограничениями в виде равенств – метод множителей Лагранжа

Более сложные задачи – задачи с неравенствами

Алгоритмы для решения таких задач делятся на 2 основных класса:

- Алгоритм спуска

- Алгоритм штрафных функций

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

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

 

I. Методы спуска

1. Процедуры линейной аппроксимации

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

Линеаризация основана на разложении функций в ряд Тейлора.

 

Пусть дана задача:

минимизировать (1)

при ограничениях

Линеаризованная задача:

При ограничениях min

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

Пример:

Min

Пусть

Линейная аппроксимация задачи:

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

2. Методы линейной аппроксимации делятся на:

(1) Методы аппроксимирующего линейного программирования;

Проективные методы:

- (2) Метод допустимых направлений (метод Зойтендейка)

- (3) Метод проекции градиента (метод Розсна)

- и т.д.

(4) методы приведенного градиента

Рассмотрим первые 3 метода.

2.1 Метод аппроксимирующего программирования (градиентный метод с малой длиной шага).

Запишем ограничения – неравенства в виде , что легко достигается сменой знака, например:

Тогда после линеаризации получим:

При условиях:

(*)

Данная задача линейного программирования решается при следующем добавочном условии

(**)

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

Решение задачи (*) при дополнительном условии (**) дает

обозначает как

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

Пример:

При ограничениях:

(а)

Решением задачи (а) является

Решение задачи:

Шаг 1.

1. Пусть

2. Линеаризуем задачу (а) в точке

 

 

Решением задачи является 54

Вектор допустим по отношению к задаче , но НЕ ДОПУСТИМ для исходной задачи (а)

Чтобы не допустить выход из допустимой области задачи (а), накладывается ограничение в виде (**)

(в)

Выбор

При этом заметим, что движение из в влечет увеличение и уменьшение , т.е.

Поэтому полагаем , т.е.

В результате получаем:

Шаг 2.

Уменьшаем . Пусть

Линеаризуем задачу в точке

 

 

Решение задачи (2)

Последовательно уменьшаем (например

Решение заканчивается, когда

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

Т.о. при линеаризации функции задается некоторая зона допускаемой погрешности

Трудности, возникающие при аппроксимации линейного программирования:

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

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

2. Трудно сравнивать два «соседних» вектора и из-за несовпадения подмножеств ограничений на каждом шаге (различные (или те же самые) ограничения нарушаются по разному разными векторами)

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

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

1. Случай линейных ограничений

Минимизировать – нелинейна!

При условиях – матрица x

– матрица x

-мерный вектор

-мерный вектор

Вектор – вектор возможного направления спуска, если:

;


 

– матрица активных ограничений

направлен в стороны убывания

– нормали к ограничениям

Т.о. вектор возможного направления спуска обеспечивает убывание функции и выполнение ограничения

4-4 пространство направлений спуска

Любой вектор при дает сколь угодно большое значение функции

Т.е. ,

Следовательно, необходимое условие, ограничивающее вектор или , т.е. нормирующее условие

А) 3 типа нормировки (отыскание вектора )

Задача :

при условиях ограничение на модуль

Задача :

при условиях ограничение на норму вектора

Задача :

при условиях

Задачи – задачи линейного программирования.

Задача содержит квадратичное ограничение

Точка – допустимая во всех 3х задачах. В этой точке , т.е. значение целевой функции равно 0.

Если в задачах (1-3) отрицательно, то можно найти допустимое направление спуска.

Если , то – точка Кука-Таккера, т.е. – решение задачи (1-3)

Б) Линейный поиск минимума в направлении

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

Минимизировать

при условиях

Пусть теперь , , так что

– активные ограничения

– ограничения, несущественные на данном шаге (заведомо вычисленные)

Тогда т.к. , то 56

Т.о. ограничение не зависит от и становится излишним

Т.к. и , то для всех

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

(*)

при условии , где

(**)

Условия (**) обеспечивают соблюдение ограничивающих условий: при движении в сторону

В) Алгоритм Зойтендейка (случай линейных ограничений)

Начальный этап.

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

Основной этап.

Шаг 1. Пусть задан . Разбиваем матрицу :

и вектор , так что

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

В качестве берется оптимальное решение одной из задач (Пусть )

 

при условиях

Если – остановиться: – решение, иначе перейти к шагу 2.


Шаг 2. Положить равным оптимальному решению следующей задачи линейного поиска:

при условии

Положить

Определить новое множество активных ограничений в и переопределить и . Заменить на и перейти к шагу 1.

 

Пример:

При (1)

(2)

(3)

(4)

Итерация 1.

Шаг 1. Поиск направления

В имеем

Активными в являются ограничения (3) и (4)

Задача поиска направления имеет вид:

Задачу (*) можно решить симплекс-методом – решение

Шаг 2. Линейная оптимизация (шаг )

,

в т. 57

Задача (**) решается методом золотого сечения

Итерация 2.

Шаг 1. Поиск направления.

В точке имеем

Множество активных ограничений

Направление движения определяется из решения задачи:

При условиях

Оптимальное решение

Шаг 2. Линейный поиск:

Решаем задачу одномерной оптимизации

Действительно:

Итерация 3.

Шаг 1. Поиск направления:

В точке имеем

Множество активных ограничений

При условиях

 

либо либо любая точка не прямой

(

Во всех этих точках выполняется условие

Следовательно – решение задачи

Т.к. – точка Кукка-Таккера, то найдено оптимальное решение задачи


 

Условие К-Т

,

В т. – оптимум



Последнее изменение этой страницы: 2016-06-10

headinsider.info. Все права принадлежат авторам данных материалов.