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а


 

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

11741. Работа с транзакциями. Кэширование изменений при работе с транзакциями 15.39 KB
  Лабораторная работа №1415 Работа с транзакциями. Кэширование изменений при работе с транзакциями. Цель: формирование практических умений и навыков работы с операторами TransactSQL объединенных транзакцией; создания транзакций; сохранения изменений; выполнение операций
11742. Обеспечение достоверности данных и перехват исключительных ситуаций 14.27 KB
  Лабораторная работа №16 Обеспечение достоверности данных и перехват исключительных ситуаций Цель: формирование практических умений и навыков определения и назначения определенного вида блокировки при работе с транзакциями; типа объекта для осуществления синхрониз
11743. Работа с отчетами 16.13 KB
  Лабораторная работа №17 Работа с отчетами Цель: формирование практических умений и навыков построения отчетов определение и составление запросов необходимых для содержания отчета. Ход работы Задание 1: Составить 3 запроса и сделать для них отчет: В Word Со
11744. Установка привилегий доступа 15.53 KB
  Лабораторная работа №18 Установка привилегий доступа Цель: формирование практических навыков в создании пользователей полей с помощью transactSQL. Установление привилегий пользователя роли обмена и изменение привилегий указанных для пользователя. Ход работы: Зада
11745. Автоматизированное тестирование 311.5 KB
  Лабораторная работа № 7. Автоматизированное тестирование. Цель: закрепить учебные навыки по автоматизированному тестированию. Ход работы 1. procedure TForm1.Button1ClickSender: TObject; VAR a: array [1..3] of real; zssum:real; ixns1:integer; begin n:=STRTOINTedit1.Text; x:=1; z:=0; s1:=10; For i:= 1 to 3 do begin ...
11746. Использование методов защиты информации в программах 99 KB
  ЛАБОРАТОРНАЯ РАБОТА № 8. Использование методов защиты информации в программах. Цель работы: освоить на практике методы защиты информации. Ход работы 1. Написать программу которая с использованием криптосистемы RSA шифрут сообщение: Истоpия кpиптогpафии pовесница
11747. Работа в составе бригады 42 KB
  Лабораторная работа №10. Работа в составе бригады. Цель: научиться коллективно обрабатывать разрабатывать отлаживать программные продукты. Ход работы Разработать программу выполняющую вычислительные действия над комплексными числами . var Form1: TForm1; ...
11748. Научиться пользоваться системой отладки 14.07 KB
  Лабораторная работа № 7. Автоматизированное тестирование. Цель: научиться пользоваться системой отладки. Выполнил: Романов П.Н. Группа: 091ПО Преподаватель: Кашталинская И.А. Дата: 30.11.12 Ход работы: Задание № 1. Составить программу вычислени
11749. Работа с БД. Создание сложных запросов 1.04 MB
  Лабораторная работа №4 Тема: Работа с БД. Создание сложных запросов Теоретический материал Современные информационные системы основанные на концепции интеграции данных характеризуются огромными объемами хранимых данных сложной организацией необходимостью у