40111

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

Доклад

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

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

Русский

2013-10-15

141 KB

41 чел.

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а


 

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

48025. ПЕРША МЕДИЧНА ДОПОМОГА В ЗАГРОЗЛИВИХ ДЛЯ ЖИТТЯ СТАНАХ, ЯКІ ВИНИКАЮТЬ ПРИ ЗАХВОРЮВАННЯХ ВНУТРІШНІХ ОРГАНІВ, ІНФЕКЦІЙНИХ ХВОРОБАХ 114 KB
  Причини ознаки попередження цих порушень. Ознаки нормальної постави. Плоскостопість вроджена та набута її перші ознаки. Загальні ознаки для всіх форм неврозів: моторні порушення зайва рухливість тік заїкання розлади вегетативної регуляції.
48026. Методика викладання природознавства 512 KB
  Метод спостереження цілеспрямоване сприйняття того чи іншого педагогічного явища без втручання в його хід. Ефективність спостереження залежить від чіткості визначення дослідником обєктів сприймання мети способів фіксації його наслідків ведення протоколу фото і кінозйомка відео та аудіо записи. У процесі констатуючого експерименту проводяться спостереження бесіди анкетування учителів батьків учнів вивчається шкільна документація й письмові роботи дітей та виконуються учнями діагностуючі завдання. Спостереження це...
48027. Логіка. Конспекти лекцій 846.5 KB
  Поняття і судження Основними формами абстрактного мислення є поняття судження й умовиводи. Судження форма мислення в якій щонебудь стверджується або заперечується про предмети їхні властивості або відносини. Поняття судження умовивід мають свою специфічну форму структуру.
48028. ЛОГІКА. ОПОРНИЙ КОНСПЕКТ ЛЕКЦІЙ 4.48 MB
  Теоретичні питання для самоконтролю Що означає термін логіка і в чому полягає проблема визначення логіки як науки Назвіть об'єкт предмет вивчення формальної логіки Яку сторону мислення вивчає логіка Що таке пізнання форми мислення Який взаємозв'язок між пізнанням і мисленням Що означає поняття абстрактне мислення Дайте визначення логічної форми істинності та правильності думки Дайте визначення мови та назвіть основні види знаків Що таке процес формалізації в вузькому та широкому значенні Що таке зміст і значення мовних виразів...
48029. Моделі і методи прийняття рішень в економіці 779.5 KB
  Оптимізація календарного плану реалізації запасів сільськогосподарської продукції за умов цінового ризику. У числі найвідоміших задач математичного програмування можна назвати такі: оптимізація виробничої програми фірми оптимізація плану перевезень продукції оптимізація варіанту розподілу завдань між виконавцями оптимізація плану введення в дію нових виробничих потужностей оптимізація портфеля фінансових активів тощо. За умов забезпечення випуску заданих обсягів виробництва продукції й обмежень із кількості основних виробничих ресурсів...
48030. МОДЕЛИРОВАНИЕ, АНАЛИЗ И ОПТИМИЗАЦИЯ БИЗНЕС-ПРОЦЕССОВ 2.2 MB
  Пудовкина МОДЕЛИРОВАНИЕ АНАЛИЗ И ОПТИМИЗАЦИЯ БИЗНЕСПРОЦЕССОВ Учебное пособие Челябинск Издательство ЮУрГУ 2006 УДК Пудовкина С. Учебное пособие предназначено для студентов изучающих дисциплины Математические методы и модели в экономике Математическая экономика Моделирование экономических систем и процессов Имитационное моделирование Анализ и оптимизация бизнеспроцессов и обучающихся по специальностям Менеджмент организаций Экономика и управление на предприятии Финансы и кредит Прикладная информатика в экономике....
48031. Макроекономіка. Опорний конспект 1.62 MB
  Сукупні видатки і ВВП. Високий і зростаючий рівень національного виробництва тобто рівень реального валового внутрішнього продукту ВВП. Сукупним вимірником національного виробництва виступає валовий внутрішній продукт ВВП що виражає ринкову вартість кінцевих товарів і послуг. Агреговані величини характеризують ринкову кон'юнктуру і її зміну ринкова ставка відсотка ВВП загальний рівень цін рівень інфляції рівень безробіття й ін.
48032. Етика. Курс лекцій 2.21 MB
  СЕНС ЖИТТЯ І СТАВЛЕННЯ ДО СМЕРТІ Звідки постає проблема сенсу життя людини 150 Способи осмислення людського буття 155 Феномен смерті 166 Життя як дарунок і відповідь 176 Лекція 7. МОРАЛЬНА САМОСВІДОМІСТЬ Поняття моральної самосвідомості 221 Честь і гідність людини 223 Совість центральний чинник моральної самосвідомості людини 229 Розкаяння 238 Поняття сорому 241 Лекція 9. ДІЯ І СВОБОДА ЛЮДИНИ Поняття свободи етичний аспект 259 Свобода дії свобода вибору свобода волі 261 Свобода як моральна цінність людського буття 269 ...