40111

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

Доклад

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

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

Русский

2013-10-15

141 KB

38 чел.

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а


 

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

39520. Управление строительством многоквартирного жилого дома №7 в программной среде Rillsoft Project 3.08 MB
  Куцепалова Объем дипломного проекта: дипломная работа –82 страницы графическая часть –. Куцепалова Объем дипломного проекта: дипломная работа – 82страницы графическая часть –. Целью проекта является исследование использования в современном строительном бизнесе информационных технологий и специализированного программное обеспечения. Областью возможного практического применения ПО Rillsoft Project 2007 являются оценка строительного проекта с точки зрения объемов работ стоимости общей потребности в ресурсах календарного плана работ графика...
39522. Восьмиэтажное административное здание – здание филиала «Приорбанка» на проспекте Победителей в городе Минске 1007 KB
  Вопросы экономики железобетонных конструкций следует решать совместно с вопросами прочности на протяжении всего процесса проектирования: при выборе объемнопланировочной и конструктивной схемы здания; членении конструкций на сборные элементы; выборе формы и размеров сечения элементов; назначении класса бетона класса стальной арматуры.пр  Nпр  RbtАb  pАпр  м из условия анкеровки арматуры колонны hoф20dпрк2000320640 м Принимаем hoф1 м Полная высота фундамента равна: hф hoфa1007107 м Принимаем hф1.4 Расчёт...
39523. Экономическое обоснование цены реализации строительной продукции 829.5 KB
  Составление локальной сметы на общестроительные работы. Составление акта приёмки выполненных работ. Составление локальной сметы на общестроительные работы Сметная документация в строительстве составляется на основе Методических указаний по определению стоимости строительства зданий и сооружений и составлению сметной документации с применением РСН РДС 8.
39524. Процесс проектирования металлических конструкций 1.84 MB
  Подбор сечения затяжки и проверка ее на прочность Наибольшее усилие в затяжке при полной расчетной нагрузке Nз=2137 кН; lз=52 м длина затяжки; Ез=195 ГПа модуль упругости затяжки; Rз=1200 МПа расчетное сопротивление материала затяжки в качестве затяжки принимаем высокопрочные канаты французской фирмы €œFreyssinet€.2 Подбор сечений стержней фермы В качестве материала фермы принята сталь С375 с расчетным сопротивлением стали Ry=365 МПа при толщине в интервале от...
39525. Промышленное и гражданское строительство 369.5 KB
  Методические указания содержат рекомендации по выполнению экономической части дипломных проектов и учитывают особенности определения техникоэкономических показателей строительных конструкций а также сметной стоимости строительства на основе ресурсносметных норм. БНТУ 2006 ВВЕДЕНИЕ Методические указания разработаны для студентов специальности 170 02 01 Промышленное и гражданское строительство и могут быть использованы при расчетах экономической части дипломных проектов а также при курсовом проектировании по дисциплинам...
39526. Разработка стратегии развития и совершенствование нынешней системы стратегического управления СУ-16 2.78 MB
  Если в прошлом многие компании могли весьма успешно функционировать обращая внимание в основном на внутренние проблемы связанные с повышением эффективности использования ресурсов в текущей деятельности то сегодняшнее развитие рыночных отношений делает необходимым изменение сложившихся стереотипов хозяйствования характера управления.Есть ли изменения существенные для фирмы Так туристические и транспортные компании постоянно оценивают динамику цен на топливо. Например реклама коттеджей – это тактика строительной компании выбравшей...
39527. Инвестиционный проект предприятия малого бизнеса 7.76 MB
  В настоящее время основными видами деятельности акционерного общества являются производство строительно-монтажных работ, проектно-изыскательские работы, торгово-закупочная деятельность в области жилищного и производственного строительства. Производственная деятельность акционерного общества осуществляется в сотрудничестве с организациями
39528. Разработка предложений по определению размера убытков, связанных с изъятием земельных участков 3.85 MB
  Областью возможного практического применения является использование разработанных предложений по определению размера убытков, связанных с изъятием земельных участков при выполнении изъятия земельных участков в Республике Беларусь.