40111

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

Доклад

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

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

Русский

2013-10-15

141 KB

33 чел.

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а


 

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

29131. Основания возникновения права собственности и их классификация 32 KB
  Находка Нашедший потерянную вещь обязан немедленно уведомить об этом лицо потерявшее ее или собственника вещи и возвратить ему найденную вещь. Вещь может быть также сдана транспортной организации в милицию или орган местного самоуправления. В случае неустановления владельца вещи в 6 месяцев нашедший вещь приобретает право собственности на нее. При возврате вещи владельцу нашедший вещь вправе потребовать от него вознаграждение за находку в размере до 20 стоимости вещи а также возмещение необходимых расходов связанных с хранением или...
29132. Приобретательская давность как основание возникновение права собственности 26.5 KB
  Приобретательная давность лицо гражданин юридическое лицо не являющееся собственником имущества но добросовестно открыто и непрерывно владеющее как своим собственным недвижимым имуществом в течение 15 лет либо иным имуществом в течение 5 лет приобретает право собственности на это имущество. Приобретательная давность это новая для отечественного законодательства форма приобретения права собственности. Право собственности на недвижимое и иное имущество подлежащее государственной регистрации возникает у лица приобретшего это...
29133. Прекращение права собственности 39.5 KB
  Прекращение права собственности – право прекращающие юридические факты которые могут быть связаны с действиями по отчуждению имущества с событиями смерть. Классификация прекращения права собственности: Добровольная – собственник передает это право другому лицу на основании различных договоров административных актов а также при отказе его от права собственности гибели или уничтожении имущества и при утрате права собственности на имущество. Принудительная – обращение взыскания на имущество по обязательствам на основании решения суда...
29134. Отступное в гражданском праве 29.5 KB
  По какимлибо причинам вы ничем кроме честного слова должника свой договор не обеспечили. Пришел час расплаты а денег у должника нет. Первый подать в суд потребовать продажи имущества должника и обязать его расплатиться с вами деньгами вырученными от продажи его имущества. Получив имущество вы отступаете от должника со своими требованиями о возврате долга.
29135. Прекращение обязательства зачетом. Недопустимость зачета 27 KB
  Обязательство прекращается полностью или частично зачетом встречного однородного требования срок которого наступил либо срок которого не указан или определен моментом востребования. Не допускается зачет требований: если по заявлению другой стороны к требованию подлежит применению срок исковой давности и этот срок истек; о возмещении вреда причиненного жизни или здоровью; о взыскании алиментов; о пожизненном содержании; в иных случаях предусмотренных законом или договором. Зачет производится если требование возникло по основанию...
29136. Новация 26 KB
  Новация. Новация обязательство прекращается соглашением сторон о замене первоначального обязательства существовавшего между ними другим обязательством между теми же лицами предусматривающим иной предмет или способ исполнения. Новация не допускается в отношении обязательств по возмещению вреда причиненного жизни или здоровью и по уплате алиментов. Новация прекращает дополнительные обязательства связанные с первоначальным если иное не предусмотрено соглашением сторон.
29137. Понятие и виды договоров. Существенные условия договора 29.5 KB
  Существенные условия договора. К договорам применяются правила о двух и многосторонних сделках. Граждане и юридические лица свободны в заключении договора. Условия договора определяются по усмотрению сторон.
29138. Толкование договора 22 KB
  Толкование договора. Форма договора закрепляет и правильно отражает согласованное волеизъявление участников договора. Форма для того и нужна чтобы правильно выражать и закреплять согласованное волеизъявление всех участников этого договора. Но как бы тщательно стороны при заключении договора ни работали над смыслом договора всетаки иногда встречаются определенные сложности в выявлении смысла этого договора и тех условий на которых заключен договор.
29139. Заключение договора. Заключение договора в обязательном порядке. Заключение договора на торгах 26.5 KB
  Заключение договора. Заключение договора в обязательном порядке. Заключение договора на торгах. Основные положения о заключении договора Договор считается заключенным если между сторонами в требуемой в подлежащих случаях форме достигнуто соглашение по всем существенным условиям договора.