40111

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

Доклад

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

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

Русский

2013-10-15

141 KB

44 чел.

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а


 

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

56141. СОВРЕМЕННЫЙ УРОК РУССКОГО ЯЗЫКА В НАЧАЛЬНОЙ ШКОЛЕ 310.5 KB
  Целевая установка учителя на безошибочное письмо. Реализуется последовательной работой по предупреждению возможных ошибок учащихся на всех этапах обучения: при устном анализе текста подлежащего записи в процессе письма и после написания работы.
56143. СОВРЕМЕННЫЙ УРОК РУССКОГО ЯЗЫКА В НАЧАЛЬНОЙ ШКОЛЕ 128.5 KB
  Существует несколько классификаций традиционных форм урока. Опираясь на устоявшиеся классификации уроков используя привычные этапы традиционных уроков учитель при коммуникативно деятельностном подходе к обучению меняет ценностные ориентации их структурных компонентов...
56144. Соціокультурний компонент змісту навчання як засіб підвищення мотивації студентів у процесі формування професійної компетенції майбутнього вчителя іноземної мови початкових класів 68.5 KB
  Одним із основних пріоритетів у процесі навчання іноземної мови у вищому навчальному закладі має стати розвиток соціокультурної компетенції основою якої є створення мотивації та інтересу до країнознавчої тематики...
56145. Передумови та проблеми застосування новітніх інформаційних технологій при викладанні соціальних дисциплін 2.78 MB
  Нові методики їх викладання повинні враховувати сучасні вимоги до застосування інформаційних технологій. У навчальних закладах компютерні технології повинні привести до поступового формування нового покоління, покоління техноінформаційного суспільства...
56146. Виховання соціальної компетентності учнів початкової школи 133.5 KB
  Сьогодні в умовах величезних змін у соціальному та політичному житті України постала проблема радикальної перебудови у сфері виховання мета якої формувати людину забезпечувати прогрес людського суспільства.
56147. РОЛЬ ІНФОРМАЦІЙНИХ ТЕХНОЛОГІЙ НАВЧАННЯ У ФОРМУВАННІ ПРОФЕСІЙНО-ДІЛОВИХ ЯКОСТЕЙ СПЕЦІАЛІСТА 131 KB
  Курс фізики за своїм змістом політехнічний, має професійну спрямованість. Фізика слугує теоретичною базою більшості галузей техніки, вона має широке та різноманітне застосування в людській діяльності.
56148. Роль спецкурсів у розвитку творчого потенціалу учнів 414.5 KB
  І кожний власну радість обирає Яка ізпоміж інших є гарніша Для мене все це вартості не має Людина від усіх багатств цінніша. Для мене ж це все не важливе Люблю тебе за те що є Думки корисливі і льстиві Я не поставлю над усе.
56149. ВІЧ і СНІД – проблема людства 721.5 KB
  Всесвітня організація охорони здоров′я розробила глобальну програму боротьби зі СНІДом. Серед медичних, профілактичних заходів передбачених цією програмою, велике значення бесід, тестування на цю актуальну тему.