40111

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

Доклад

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

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

Русский

2013-10-15

141 KB

34 чел.

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а


 

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

79736. Учет товарных потерь 52.5 KB
  Учет товарных потерь Нормируемые и ненормируемые потери Взаимозачет недостатков одних товаров излишками других Отражение в учете сумм недостач хищений и потерь от порчи ценностей Учет товарных потерь вследствие естественной убыли Товарные потери при транспортировке Нормы естественной убыли на складах Резерв на списание естественной убыли Нормируемые и ненормируемые потери Товарные потери возникают при транспортировке хранении и отпуске товаров. К ненормируемым относятся потери от боя брака и порчи товаров а также потери по...
79737. Учет финансовых результатов 93.5 KB
  Учет прибыли убытков предприятия. Распределение прибыли. Учет прибыли убытков предприятия Финансовый результат хозяйственной деятельности предприятия определяется показателем прибыли или убытка формируемым в течение календарного хозяйственного года. Формирование итогов годового финансового результата осуществляется накопительным путем в течение всего года на счете 80 Прибыли и убытки виде его свернутого остатка отражающего либо прибыль по кредиту счета либо убыток по дебету счета.
79738. Бухгалтерский учет банковских кредитов 106 KB
  Любое предприятие, получив в банке кредит, должно, во-первых, правильно выбрать источник списания затрат на оплату процентов за пользование ссудой, и во-вторых, достоверно отразить в учете и отчетности сумму возникшего перед банком обязательства.
79739. Бухгалтерский учет выпуска готовой продукции 76 KB
  Бухгалтерский учет выпуска готовой продукции Методика расчета фактической себестоимости отгруженной продукции на счете. Методика расчета фактической себестоимости отгруженной продукции с использованием учетных цен Методика использования фактической себестоимости по прямому принципу без использования учетных цен Речь идет о решении организации применять или не применять счет...
79740. Бухгалтерский учет материалов 107.5 KB
  Аналитический текущий учет материальных ценностей можно вести: либо в оценке по учетным ценам, либо в оценке по фактической средней себестоимости. На малых предприятиях, где количество наименований материалов невелико
79741. Бухгалтерский учет МБП и инвентаризация производственных запасов 34 KB
  Бухгалтерский учет МБП и инвентаризация производственных запасов Первичные документы по учету МБПУчет МБП в бухгалтерии предприятия Инвентаризация производственных запасов Первичные документы по учету МБП Форма МБ1 Ведомость на пополнение изъятие постоянного запаса инструментов приспособлений применяется для учета изменения запасов инструментов в раздаточных кладовых на тех предприятиях где учет ведется по принципу формирования постоянного оборотного фонда. Форма МБ–2 Карточка учета МБП Служит для регистрации различных МБП...
79742. Учет нематериальных активов 104.5 KB
  Учет нематериальных активов. Учет нематериальных активов. Поступление нематериальных активов А Приобретение нематериальных активов за плату Б Создание нематериальных активов собственными силами Амортизация нематериальных активов А Амортизируемые нематериальные активы Б Неамортизируемые нематериальные активы В Амортизация деловой репутации организации. Выбытие нематериальных активов 1. Учет нематериальных активов Планом счетов для учета нематериальных активов предусмотрен счет 04 Нематериальные активы а для обобщения информации о...
79743. Бухгалтерский учет скидок в организации оптовой торговли 36.5 KB
  Бухгалтерский учет скидок в организации оптовой торговли Порядок отражения в бухгалтерском учете скидки при приобретении товаров в определенном количестве либо на установленную суммуПорядок отражения в бухгалтерском учете скидки за скорейшую оплату проданных товаров Порядок отражения в бухгалтерском учете скидки при приобретении товаров в определенном количестве либо на установленную сумму Торговая скидка – это сумма на которую снижается проданная цена товаров реализуемых покупателю исполнившему условие необходимое для ее получения....
79744. Командировочные расходы: учет и налогообложение 62.5 KB
  Командировочные расходы: учет и налогообложение Состав расходов возмещаемых командировочному лицу Документальное оформление командировочных расходов. Включение командировочных расходов в себестоимость продукции Налоговые отношения возникающие при наличии командировочных расходов...