Номера задач из "упражнений" указаны в таблице ниже



страница14/26
Дата04.05.2016
Размер1.06 Mb.
1   ...   10   11   12   13   14   15   16   17   ...   26

Лекция 1.5. Нелинейное программирование. Теоремы Куна — Таккера.


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

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


Выпуклые функции. Субградиент выпуклой функции


Напомним, что, говоря о выпуклой функции на множестве , мы требуем выполнения двух условий:

1) множество должно быть выпуклым;

2) для любых и выполняется неравенство

.

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



.

Выпуклые функции — это такие функции, у которых надграфик является выпуклым множеством.

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

также выпукло (или, возможно, пусто).

Выпуклая функция необязательно является непрерывной,но разрывы у выпуклых функций могут быть только на границе области задания. В любой же внутренней точке своей области задания выпуклая функция обязательно непрерывна. Более того, в любой внутренней точке своей области задания выпуклая функция имеет производные по всем направлениям, хотя может и не быть дифференцируемой. Поэтому возникает вопрос о получении формулы, задающей эти производные по направлениям. Для дифференцируемых функций производная по направлениям легко получается через градиент функции: производная функции в точке х° по направлению, задаваемому вектором h, равна скалярному произведению градиента на вектор h:

.

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

Пусть — выпуклая (но необязательно дифференцируемая) функция, Будем говорить, что вектор g является субградиентом функции в точке , если

. (25)

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

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

,

т.е. , и все множество лежит по одну сторону от гиперплоскости , заданной уравнением, и имеет с ней одну общую точку (см. рис. 9).





Рис. 9. Геометрическая интерпретация субградиента для случая

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



Теорема о субдифференциале. Для выпуклой функции , при субдифференциал является непустым выпуклым компактом, и производная функции в точке по направлению задается формулой

. (26)
1   ...   10   11   12   13   14   15   16   17   ...   26


База данных защищена авторским правом ©bezogr.ru 2016
обратиться к администрации

    Главная страница