Седловая точка функции лагранжа

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

Определение. Говорят, что функция F(X, Y) имеет Седловую точку (х*, у*), если для всех х и у.

В определении седловой точки подразумевается, что при Х* минимизирует функцию F(X, Y*) По всем Х, а У* максимизирует функцию F(X*, Y) по всем У.

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

Определим функцию Лагранжа

Предположим, что при V = V* Минимум L(X; V*) достигается в точке Х = х*, причем Hk(X*)=0. В соответствии с методом множителей Лагранжа известно, что Х* есть оптимальное решение задачи нелинейного программирования. Можно показать, что (X*; V*) – седловая точка функции Лагранжа, т. е.

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

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

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

Задача Куна – Таккера о седловой точке формулируется следующим образом: найти такой вектор (X*; U*), чтобы неравенство

Имело место для всех и всех X S. При этом

Теорема 3. Достаточные условия оптимальности

Если (X*;U*) – решение задачи Куна – Таккера о седловой точке, то х* есть оптимальное решение задачи нелинейного программирования.

1) В теореме 3 не требуется выполнения предположений о выпуклости или вогнутости соответствующих функций.

2) Теорема 3 не опирается на условие регулярности допустимой области.

3) Учет нелинейных ограничений-равенств в виде Hk(X*)=0, K=1, . . . , K, можно осуществить путем переопределения функции Лагранжа: Здесь переменные Vk, K=1, …, K, не ограничены по знаку.

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

Читайте также:  Сколько стоит навител в плей маркете

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

Пусть Х* минимизирует F(X) при ограничениях Предполагается, что S – выпуклое множество, F(X) – выпуклая функция, а Gj(X) – функции, вогнутые на множестве S. Предполагается также, что существует такая точка , в которой для всех J=1, 2, …, J. Тогда существует такой вектор множителей , что (X*, U*) является седловой точкой функции Лагранжа

Выполняется для всех

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

Теорема 5. Вектор (X*; U*), где , определяет седловую точку в задаче Куна – Таккера о седловой точке тогда и только тогда, когда выполняются следующие условия:

1) х* минимизирует L(X; U*) по всем ;

2) для J =1, …, J;

3) для J=1, …, J.

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

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

2. Что такое седловая точка? Какую роль играет решение задачи о седловой точке в условной оптимизации?

3. При выполнении каких условий существуют седловые точки в задачах нелинейного программирования?

4. Укажите основные направления использования необходимых и достаточных условий оптимальности второго порядка.

Теорема. Критерий седловатости точки.

Точка ( ) при условях (В) есть седловой точкой ф-и Лагранжа тогда и только тогда, когда

Необходимости: (следует из определения седл. точки)

По определению седл. точка – это точка минимума.

Читайте также:  Сбился wifi как настроить

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: На стипендию можно купить что-нибудь, но не больше. 9127 – | 7292 – или читать все.

91.146.8.87 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.

Отключите adBlock!
и обновите страницу (F5)

очень нужно

Функцией Лагранжа задачи выпуклого программирования (3.3) — (3.5) называется функция

Точка называется седловой точкой функции Лагранжа, если для всех и

Теорема Куна-Таккера

Функцией Лагранжа задачи выпуклого программирования (3.3) — (3.5) называется функция

Точка называется седловой точкой функции Лагранжа, если для всех и

Центральное место в теории нелинейного программирования занимает теорема Куна — Таккера.

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

Основная идея градиентных методов решения ЗНЛП

Две группы: 1. барьерные 2. штрафные

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

Метод Франка –Вульфа

Итак, процесс нахождения решения задачи методом Франка-Вулфа включает следующие этапы:

Читайте также:  Служба аудио не запущена что это значит

1. Определяют исходные допустимые решения задачи.

2. Находят градиент функции в точке допустимого решения.

3. Строят функцию и находят ее максимальное значение при условиях

4. Определяют шаг вычислений.

5. По формулам находят компоненты нового допустимого решения.

6. Проверяют необходимость перехода к последующему допустимому решению. В случае необходимости переходят к этапу 2, в противном случае найдено приемлемое решение исходной задачи.

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

процесс нахождения решения задачи выпуклого программирования методом штрафных функций включает следующие этапы:

1. Определяют исходное допустимое решение.

2. Выбирают шаг вычислений.

3. Находят по всем переменным частные производные от целевой функции и функций, определяющих ОДР задачи.

4. По формуле находят координаты точки, определяющей возможное новое решение задачи.

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

6. Устанавливают значения весовых коэффициентов и переходят к этапу 4.

Метод наискорейшего спуска

1. выбирают любую точку X0, удовлетворяющую области решений (в дальнейшем эта точка Xk)

2. Находят частные производные, а затем градиент функции в точке.

3. определяют шаг лямбда

4.по формулам 1. Xk+1= Xk+”лямбда”*1 и 2. Xk+1= Xk+”лямбда”*”обратная дельта’Z(Xk) находят точку Xk+1

5. проверяют, находиться ли точка Xk+1 внутри области решений.

6. проверяют, точку Xk+1 на оптимальность. Если точка не является оптимальным решением повторяют пункты 2-6

Дата добавления: 2018-05-12 ; просмотров: 739 ; ЗАКАЗАТЬ РАБОТУ

Leave a Reply

Ваш адрес email не будет опубликован. Обязательные поля помечены *

You may use these HTML tags and attributes:

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>