Методы решения задач условной оптимизации (1006297)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

55 Методы решения задач условной оптимизации.

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

Эти методы применяют для решения задач нелинейного программирования. Решаемая задача имеет вид : в векторной форме

Или в координатной форме

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

1. Метод непосредственного исключения

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

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

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

Это грубый метод с недостаточно хорошей сходимостью, но простой.Применяется для нахождения первоначального приближения ,а затем используют более точные методы. Согласно методу штрафных функций задача условной оптимизации функции сводится к задаче безусловной оптимизации вспомогательной функции: q(X)=f(X)+w(X),где w(X) – штрафная функция. Ее выбирают т.о. чтобы при выполнении заданных ограничений она обращалась в нуль, иначе резко возрастала. Поэтому в качестве w(X) можно взять следующую функцию:

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

1. Метод множителей Лагранжа.

В данном точном методе задача условной оптимизации функции f(X) сводится к задаче безусловной оптимизации функции Лагранжа, имеющей вид:

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

Находим необходимое условие экстремума функции :

Отсюда имеем

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

Достаточное условие минимума функции по Х точке Х* - положительная определенность в данной точке Х* той части размером nxn матрицы Гессе функции , которая соответствует вторым частным производным от по Х.

Обозначение введено для указания зависимости значения от Х*. Достаточное условие в точке Х* - отрицательная определенность .

Рассмотрим геометрическую интерпретацию данного метода.

Пусть n=2, m=1. На рисунке изобразим линии постоянного уровня функции и кривую ограничения . Имеется три точки касания кривой ограничения с линиями постоянного уровня.

Точки экстремума обязательно лежат на кривой ограничения и являются точками касания этой кривой с линиями постоянного уровня.

Точка Х* называется локальным максимумом функции f(X), если существует такая -окрестность этой точки, что для любой точки Х данной окрестности выполняется условие .При минимуме . Для глобального экстремума указанные условия должны выполняться для любой точки Х области допустимых значений.

Отсюда следует, что если при движении вдоль кривой ограничения в двух разных направлениях из точки касания данной кривой с линией постоянного уровня значение функции в -окрестности точки касания не будет возрастать по сравнению со значением функции в точке касания, то данная точка является локальным максимумом. Если же значение функции f(Х) не будет убывать, то точка касания — локальный минимум. Если при движении из точки касания линии постоянного уровня и кривой ограничения вдоль этой кривой в одном направлен функция f(X) возрастает, а в другом - убывает, то точка касания является точкой.

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

4. Метод поиска седловой точки функции Лагранжа

При нахождении минимума функции f(X) функция Лагранжа L(X,А) имеет в точке седловую точку, если выполняется неравенство

или, что то же самое:

В методе поиска Седловой точки функции Лагранжа задача условной минимизации функции f(X) при наличии ограничений сводится к нахождению Седловой точки функции Лагранжа L(X,А).

Из определения Седловой точки следует, что в ней достигается минимум функции Лагранжа по Х и максимум по . Поэтому для функции Лагранжа можно применять итерационные методы. Например, расчетные формулы поиска минимума функции f(x) согласно методу градиентного спуска будут следующими:

5.Метод проекции градиента

Для решения задачи условной оптимизации с заданными ограничениями нельзя непосредственно использовать метод градиентного спуска, т.к. не всякая полученная точка будет удовлетворять данным ограничениям, т.е. условию . Поэтому для учета этого условия в методе проекции градиента на каждой итерации к вначале определяем по точку Х' согласно методу градиентного спуска: (+ - при поиске максимума, «-» при поиске минимума), а затем находим проекцию точки Х' на поверхность Ф(Х)=0.

Геометрическая интерпретация метода: n=2, m=1, кривая ограничения (частный случай поверхности ограничения), прямая (частный случай гиперплоскости ), векторы Р и , связанные с точками , и Р соотношением:

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

1. Принимаем к=0. Выбираем начальное приближение Х(0), точность решения и шаг h в направлении поиска безусловного экстремума.

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

3.Вычисляем матрицу и вектор ,

где знак «+» при Е используем при поиске максимума функции f(X) и «-» при минимуме; Е- единичная матрица размером nxn.

1. Определяем

2. Проверяем условие завершения итерационного процесса поиска экстремума . Если условие выполняется, то переходим к п.6, иначе принимаем к=к+1 и переходим к п.2.

3. Конец алгоритма.

Отметим, что каждый элемент обратной матрицы (где S - квадратная матрица с ненулевым определителем detS) образуется как алгебраическое дополнение элемента и определителя det S, деленное на сам определитель:

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

Применяются для задач нелинейного программирования. Задача имеет вид:

или в координатной форме

1.Классический метод решения задач условной оптимизации при ограничениях типа неравенств.

Алгоритм:

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

2.Среди стационарных точек находим точки, принадлежащие области XD. Среди них ищем точки экстремума. Условием минимума (максимума) функции в точке будет положительная определенность матрицы Гессе в этой точке.

3.Если все стационарные точки не принадлежат области XD или являются точками перегиба, то точки экстремума ищем на границе этой области (где ). Среди граничных точек выбираем те, в которых функция принимает наименьшее и/или наибольшее значение. Эти точки и будут локальными условными экстремумами.

4. Конец алгоритма.

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

Геометрическая интерпретация классического метода решения задач условной оптимизации при ограничениях типа. На рис. (а) условный минимум функции f(X) совпадает с безусловным Х*_б. На рис. (б) безусловный минимум Х*_б не принадлежит области ХD₁ поэтому задача условной оптимизации имеет решение в т. . Этот условный экстремум лежит на границе области ХD₁ , и в нем достигается наименьшее значение функции f(X) в этой области.

Классический метод основан на следующих двух теоремах.

Теорема 1 (Вейерштрасса). Если f(X) непрерывна и определена на непрерывном на непустом, замкнутом пространстве и ограниченном множестве XD, то функция в этой области принимает, по крайней мере, один раз наибольшее и наименьшее значение.

Теорема 2. Если f(X) определена в допустимой области XD, то минимальное и/или максимальное значения этой функции, если они существуют, достигаются в одной или более точках, которые принадлежат одному из следующих множеств:

1. множеству внутренних точек (в которых ;

2. множеству граничных точек области XD (где )

3. множеству точек, в которых функция не дифференцируема.

Множество, содержащее все свои граничные точки, называется замкнутым.

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

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

2.Метод, основанный на теореме Куна-Такера.

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

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

Список файлов ответов (шпаргалок)