40111

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

Доклад

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

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

Русский

2013-10-15

141 KB

30 чел.

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а


 

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

48763. Задача о 8 ферзях 142.5 KB
  Задача состоит в нахождении всевозможных комбинаций расстановки восьми ферзей на пустой шахматной доске, в которой ни один из ферзей не находится под боем другого
48764. Темпи зростання та порівняння заробітної плати в Україні та інших країнах світу 537 KB
  З оплатою праці пов’язане розширення ємності внутрішнього ринку для стимулювання вітчизняних товаровиробників збільшення заощаджень населення як важливого джерела інвестицій в економічний розвиток. Нарешті необхідність належної збалансованості економічних інтересів учасників виробництва потребує збільшення частки оплати праці у структурі суспільного продукту. Отже для розвитку економіки збільшення інвестицій необхідне зростання рівня оплати праці.
48765. Поиск неисправностей 2.14 MB
  Методика поиска неисправностей и обозначение различных вариантов поиска Анализ неисправности на структурном уровне По структурной схеме СВ устанавливаем вероятный неисправный блок. Согласно внешним признакам проявления неисправности очевидно что неисправен может быть либо сам ПОУ СВ либо блок ВчУ структурный уровень так как только эти устройства участвуют в записи информации с ПОУ СВ на ВчУ. Анализ неисправности на функциональном уровне По функциональной схеме из альбома схем к курсу занятий по теме СВ устанавливаем вероятные...
48766. Поиск неисправностей 2.48 MB
  Методика поиска неисправностей и обозначение различных вариантов поиска Анализ неисправности на структурном уровне По структурной схеме СВ устанавливаем вероятный неисправный блок. Согласно внешним признакам проявления неисправности очевидно что неисправен может быть либо сам ПОУ СВ либо блок ВчУ структурный уровень так как только эти устройства участвуют в записи информации с ПОУ СВ на ВчУ. Анализ неисправности на функциональном уровне По функциональной схеме устанавливаем вероятные неисправные устройства блока ПОУ СВ и ВчУ. Учитывая...
48767. Формування Європейської Валютної Системи 282 KB
  Перші спроби європейських країн об'єднати свої валютні системи були ще в XVIIXVIII ст. Проте будучи підсистемою світової валютної системи ЄВС відчуває негативні наслідки нестабільності останньої і вплив долара США. Проаналізувавши економічну літературу з даної теми ми зробили висновок що звертається недостатня увага на існування світової валютної системи а отже і ЄВС як її складової за умов сучасної фінансової кризи. Ця фінансова криза може призвести до краху сучасної системи паперового та кредитного обігу.
48768. СИСТЕМА УПРАВЛЕНИЯ ЭЛЕКТРОДВИГАТЕЛЕМ ПОСТОЯННОГО ТОКА С НЕЗАВИСИМЫМ ВОЗБУЖДЕНИЕМ 1.44 MB
  Для последовательного соединения пассивных звеньев необходимо минимизировать их взаимное влияние. Для этого обычно используют буферные неинвертирующие усилители с единичным коэффициентом усиления и широкой полосой пропускания.
48771. Расчет вала гидротурбины 630.5 KB
  Толщины: Сварка покрытыми электродами выполняется при толщине листов 4 мм. В строительстве применяется ограниченно при возведении мостов листовая сварка в судостроении. Толщины: Минимальная толщина листов при сварке под флюсом от 3 мм. Дуговая сварка неплавящимся вольфрамовым электродом в инертных газах Применение: Она является лучшим способом для сварки изделий из тонколистового металла так как обеспечивает минимальную деформацию изделия и высокое качество сварного шва.