40111

Субградиент как обобщение понятия градиента. Субградиент для функции максимума. Субградиентный метод и его геометрическая интерпретация в R2

Доклад

Менеджмент, консалтинг и предпринимательство

Субградиент для функции максимума. Градиентом дифференцируемой функции fx в точке называется вектор частных производных.x0 y0 а значение lim называется частной производной функции f по x в т. Вектор называется субградиентом опорным вектором функции fx в точке если выполняется: Таких с множество но это множество ограничено и замкнуто.

Русский

2013-10-15

141 KB

37 чел.

26. Субградиент как обобщение понятия градиента. Субградиент для функции максимума. Субградиентный метод и его геометрическая интерпретация в R2.

Градиентом дифференцируемой функции f(x) в точке  называется вектор частных производных.

Пусть функция f(x, y) определена в некоторой окрестности т.(x0, y0). Рассмотрим

 

Если lim сущ. и  конечен, то функция f называется дифференцируемой по X в т.(x0, y0), а значение lim называется частной производной функции f по x  в т. (x0, y0).

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

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

Вектор   называется субградиентом (опорным вектором)  функции f(x) в точке , если выполняется:

Таких с множество, но это множество ограничено и замкнуто. Множество субградиентов функции f(x) в т. x0 называется субдифференциалом. Для дифференцируемых функций градиент совпадает с субградиентом.

Рассмотрим

Для выпуклых дифференцируемых функций имеет место:

 График f(x) лежит не ниже графика  линейной функции(x)

Вектора (xx0) направлены внутрь Лебегова множества. Нас интересуют вектора, образующие тупой угол со всеми векторами убывания, вектора, лежащие за линией прямого угла.

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

Теорема: пусть ci – субградиент функции fi(x) в точке x0, тогда вектор  будет субградиентом функции максимума F(x) в точке x0

– множество активных индексов в точке x0.

Это не единственный субградиент. По этой формуле можно найти хоть какой-нибудь субградиент

Док-во:

.

СЛЕДСТВИЕ:

Векторы, концы которых лежат на отрезке [f1’(x0);  f2’(x0)] являются субградиентами. Векторы f1’(x0);  f2’(x0) также являются субградиентами

Субградиент на множестве R1 – это число! Он равен tg угла наклона касательной к точке и направлен в сторону возрастания функции.

Можно откладывать как от точки x0, так и от начала координат:

Для непрерывной функции f(x)

Для функции максимума F(x)

Субградиентный метод

 ~           

– множество допустимых решений.

Пусть имеется последовательность

Алгоритм

0 шаг. Выбираем , k = k + 1

1 шаг. Если, то решение найдено

2 шаг. Строим , где

ck – субградиент f0(x) в точке xk, если  и

ck – субградиент F(x) в точке xk, если 

Остановка |xk+1xk| 

Геометрическая интерпретация в R2

От выпуклости функции совсем отказываться нельзя. Например, даже дифференцируемая невыпуклая функция может не иметь субградиента ни в одной точке. Напр., f(x) = x3

C другой стороны, если рассматривать x3 только на x  0, то во всех точках x  0 субградиент.

Теорема [о сходимости субградиентного метода] пусть множество D – выпуклое и имеет непустую внутренность. Тогда из последовательности {xk}, построенной по субградиентному методу, можно выбрать подпоследовательность, которая сходится к точке min.


Субградиенты

x0

с2

с1

F(x)

f1(x)

f2(x)

3(x)

f4(x)

f2’(x0)

f1’(x0)

f1(x)

f2(x)

x0

x0

tg 

f’(x0)

f(x)

x0

F(x)

f3(x)

f2(x)

f1(x)

tg 1

1

x0

2

f2(x)

f1(x)

tg 2

субградиенты

f4(x)

f0(x) = c

x*

x3

x2

x1

x4

c0 = f1’(x0)

c4 = f4’(x0)

c2 = f4’(x0)

c3

c1

tg = c

(x)

f(xа


 

А также другие работы, которые могут Вас заинтересовать

18164. ПРИВАТИЗАЦІЯ ЗЕМЕЛЬНИХ ДІЛЯНОК 83.5 KB
  Лекція 6 ПРИВАТИЗАЦІЯ ЗЕМЕЛЬНИХ ДІЛЯНОК План: Поняття та правові моделі приватизації. Приватизація земельних ділянок із земель запасу та земельних ділянок надані раніше у користування громадянам. Приватизація земельних ділянок колективами громадян ю...
18165. НАБУТТЯ ПРАВА ВЛАСНОСТІ НА ЗЕМЕЛЬНІ ДІЛЯНКИ ЗА ЦИВІЛЬНО - ПРАВОВИМИ УГОДАМИ 81 KB
  Лекція 7. НАБУТТЯ ПРАВА ВЛАСНОСТІ НА ЗЕМЕЛЬНІ ДІЛЯНКИ ЗА ЦИВІЛЬНО ПРАВОВИМИ УГОДАМИ План: 1. Загальні положення. 2. Купівля – продаж. 3. Міна. 4. Дарування. 5. Спадкування. 6. Рента. Питання для самоконтролю: Питання для самостійного опрацювання: 1. Загальні ...
18166. ПРИПИНЕННЯ ПРАВА ПРИВАТНОЇ ВЛАСНОСТІ 84 KB
  Лекція 8 ПРИПИНЕННЯ ПРАВА ПРИВАТНОЇ ВЛАСНОСТІ План: Припинення права приватної власності як санкція за вчинене правопорушення. Викуп земельних ділянок приватної власності для суспільних потреб Примусове припинення права власності. Викуп земельних...
18167. ПРАВО ЗЕМЛЕКОРИСТУВАННЯ 95 KB
  Лекція 9. ПРАВО ЗЕМЛЕКОРИСТУВАННЯ План: Поняття права землекористування Особливості підстав виникнення права землекористування Особливості підстав припинення права землекористування Захист права землекористування Питання для самоконтро
18168. ОСОБЛИВОСТІ ОРЕНДНОГО ЗЕМЛЕКОРИСТУВАННЯ 79 KB
  Лекція 10. ОСОБЛИВОСТІ ОРЕНДНОГО ЗЕМЛЕКОРИСТУВАННЯ План: Загальна характеристика оренди землі та договору оренди землі Порядок укладання договорів оренди землі Умови договору оренди землі Зміна припинення поновлення договорів оренди землі Субо
18169. ОБМЕЖЕННЯ ТА ОБТЯЖЕННЯ ПРАВ НА ЗЕМЛЮ 66.5 KB
  Лекція 11. ОБМЕЖЕННЯ ТА ОБТЯЖЕННЯ ПРАВ НА ЗЕМЛЮ План: Поняття обмежень та обтяжень прав на землю Загальна характеристика обмежень прав на землю Загальна характеристика обтяжень прав на землю Питання для самоконтролю: Питання на самостійну підгото
18170. ЗЕМЕЛЬНИЙ СЕРВІТУТ ЯК ОКРЕМИЙ РІЗНОВИД ОБТЯЖЕНЬ ПРАВ НА ЗЕМЛЮ 60.5 KB
  Лекція 12. ЗЕМЕЛЬНИЙ СЕРВІТУТ ЯК ОКРЕМИЙ РІЗНОВИД ОБТЯЖЕНЬ ПРАВ НА ЗЕМЛЮ План: Поняття земельного сервітуту Види земельних сервітутів Встановлення земельних сервітутів: підстави та порядок Підстави та порядок припинення земельних сервітутів П...
18171. Структуры языка ANSI C, операции над структурами 1.07 MB
  Задача лабораторной работы состоит в практическом освоении объявления и работы с структурами, написание приложения по индивидуальному варианту.
18172. ПРАВО НА ЗЕМЕЛЬНУ ЧАСТКУ (ПАЙ) 83.5 KB
  Лекція 13 ПРАВО НА ЗЕМЕЛЬНУ ЧАСТКУ ПАЙ План: Правова природа права на земельну частку пай Право на земельну частку пай у землях що були передані у колективну власність сільськогосподарських підприємств Співвідношення права на земельну частку пай із...