40111

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

Доклад

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

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

Русский

2013-10-15

141 KB

39 чел.

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а


 

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

5688. Психологічні особливості спілкування і діяльності людини 308.03 KB
  Психологічні особливості спілкування і діяльності людини Значення спілкування у житті та діяльності людини. Функції та види спілкування. Засоби спілкування. Поняття про групи та колектив. Діяльність та ї...
5689. Психологічні основи навчання та виховання 222.47 KB
  Психологічні основи навчання та виховання Загальні поняття про навчання та виховання. Сутність і види навчання. Принципи навчання. Психологічні особливості виховання особистості...
5690. Унификация методов количественного определения лекарственных средств 139 KB
  Унификация методов количественного определения лекарственных средств Количественное определение - это заключительный этап фармацевтического анализа. Выбор оптимального метода количественного определения зависит от возможности оценить лекарствен...
5691. Генетика вирусов. Структурная организация генома клетки 138.5 KB
  Величайшие достижения середины XX века - открытие дискретных единиц наследственности (генов), разработка хромосомной теории наследственности, развитие биохимической генетики микроорганизмов и установление принципа один ген...
5692. Россия на пути суверенного развития (1991-2001 гг.) 59.64 KB
  Россия на пути суверенного развития (1991-2001 гг.) Переход к рыночным реформам. - Политический кризис 1993 г. Принятие Конституции РФ. Первая Чеченская война. Второй срок президентства Б. Ельцина и углубление кризиса. Вторая Чеченская война. И...
5693. Ответственность за нарушение экологического законодательства 155.5 KB
  Введение. Понятие и состав экологического правонарушения. Понятие и состав экологического преступления. Административная и гражданско-правовая ответственность за экологическое правонарушения. Заключение. Цель лекции: ознакомить сту...
5694. Организация производства мясных полуфабрикатов и мясоперерабатывающего цеха 747.55 KB
  Тема данной курсовой работы в настоящее время является актуальной, так как в России на долю пищевой и перерабатывающей промышленности приходится более половины продовольственного товарооборота страны. В состав этой отрасли входит более 30 подотраслей...
5695. Организация технологического процесса по приготовлению блюд Азу по-татарски и Сочни с творогом 484.94 KB
  Организация технологического процесса по приготовлению блюд Азу по-татарски и Сочни с творогом Общая характеристика кулинарии как науки Известно ли вам, что есть на свете две профессии, которые мы знаем с самого детства? Не просто знаем, а сразу...
5696. Технология татарской кухни и ее изучение в средней общеобразовательной школе 514.84 KB
  В настоящее время наряду с традиционными кухнями люди используют в своей жизнедеятельности достижения национальных кухонь. Многочисленные путешественники называли татарскую национальную кухню сытной и вкусной,простой и изысканной...