40111

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

Доклад

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

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

Русский

2013-10-15

141 KB

48 чел.

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а


 

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

44987. Математическое описание звеньев и САУ. Типовые звенья 23 KB
  Типовые звенья. Получение модели начинается с разбиения системы на звенья по математическому описанию причем звенья направленного действия передают сигнал в одном направлении и изменение состояния этого звена не влияет на состояние предшествующего звена работающего на его вход. Типовые звенья САУ различают по виду их передаточной функции и виду дифференициалного уравнения. Позиционными звеньями называются такие звенья в передаточной функции которых многочлены NS и MS имеют свободный член равный 1 т.
44988. Типовые воздействия в системе и реакция на них 410 KB
  Весовой фей звена наз. YS = WSXS Kt = yt если XS=1→ Xt=δt δt идиализированный импульс с бесконечно большой амплитудой Весовая фия реакция звена на единичный импульс. Смысл Kt переходный процесс на выходе звена при подаче на его вход единичного импульса. реакция звена на единичное ступенчатое воздействие т.
44989. Устойчивость систем управления. Первый метод Ляпунова 87.5 KB
  Устойчивость систем управления. Устойчивость свойство системы возвращаться в исходный или близкий к нему установившийся режим после всякого выхода из него в результате какоголибо воздействия. когда установившийся режим вообще отсутствует дается общее определение устойчивости: Система устойчива если её выходная величина остаётся ограниченной в условиях действия на систему ограниченных по величине возмущений. Если в характеристическом уравнении системы имеется хотя бы один нулевой корень или хотя бы одна пара чисто мнимых корней λii1 =...
44990. Качество как экономическая категория и объект управления 800.06 KB
  Понятие качества. Значение повышения качества. Качество как объект управления и основные концепции менеджмента качества. Академия проблем качества России.
44991. Управление затратами на обеспечения качества 741.03 KB
  Этапы формирования и виды затрат на качество продукции. Информационная база анализа затрат на качество продукции. Методы анализа затрат на качество продукции. Экономическая эффективность новой продукции.
44992. Сертификация продукции и систем качества 1.35 MB
  Понятие сертификации продукции. Преимущества сертификации продукции. Этапы проведения сертификации системы качества. Международная практика сертификации.
44994. Оборотный капитал предприятия 67.5 KB
  Определение плановой потребности в оборотных средствах Источники финансирования оборотных средств Оборотными текущими активами называется постоянно находящаяся в движении совокупность производственных оборотных фондов и фондов обращения в денежном выражении предназначенных для обеспечения бесперебойного процесса производства продукции и ее реализации. Классификация оборотных фондов Первый уровень классификации по функциональному признаку. Второй уровень по видам оборотных средств.