Гладкая задача. Теорема Куна-Таккера для гладкой задачи.

называется гладкой задачей, если и являются строго дифференцируемыми. , X, Y – Банаховы пространства, .

Алгоритм решения данных задач:
1) Составляем функцию Лагранжа - сопряженное пространство.

2) Выписываем необходимое условие: а) б)
в)

3) Находим критические точки, т.е. допустимые точки, удовлетворяющие условиям 2. При этом рассматривают случаи, когда

4) Находим решения среди критических точек или показываем, что его не существует.

Теорема. Пусть - решение гладкой задачи нелинейного программирования вида (1). - банаховы пространства. – замкнутые подпространства У. Тогда множитель Лагранжа и линейный ограниченный функционал Причем не все из них равны нулю. Если множители Лагранжа, такие что выполняется условие пункта 2 в алгоритме.

Теорема Куна-Таккера. 1. Пусть X – линейное векторное пространство, - подмножество в X, тогда, если является решением задачи выпуклого программирования, то найдется такой ненулевой вектор во множестве Лагранжа , что выполняются следующие условия:

A – принцип множителей Лагранжа.

условие дополняющей не жесткости, т.е.

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

2) Если то а)-в) являются достаточными условиями, чтобы являлся решением задачи.

3) Для того, чтобы достаточно выполнения условия Слейтора, т.е. такой, что .

22. Градиентные методы решения задач нелинейного программирования. Метод приведённого градиента Вульфа.

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

Метод Франка - Вульфа. Пусть требуется найти максимальное значе­ние вогнутой функции

(1)

при условиях

, (2)

(3)

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

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

строят линейную функцию.

(4)

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

,

Где - некоторое число, называемое шагом вычислений . За принимают наименьший корень уравнения или выбирают произвольно, если он не принадлежит интервалу (0; 1).