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а


 

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

22733. Основні напрямки зовнішньої політики адміністрації Дж. Буша (мол.) 34.5 KB
  Такая политика известна почти всем так как каждое государство исключая США при администрации Клинтона ее практикует. В строгом смысле эта поддержка не была необходимой но она оказала важную дипломатическую и экономическую помощь в борьбе США против терроризма. Вместе с тем администрация США решительно отвергла более широкую коалицию которая могла помешать борьбе с терроризмом в целом и ведению войны против талибов в частности. Администрация США поняла это несмотря на четкое осознание всей слабости многосторонних мер и коалиций и решила...
22734. Створення НАТО 32.5 KB
  Створення НАТО. після тривалих переговорів у Великій залі Державного департаменту США у Вашингтоні відбулася церемонія підписання Статуту Організації Північноатлантичного Договору НАТО. згідно з цим законом СПІА уклали вісім двосторонніх угод із західноєвропейськими членами НАТО про фінансову допомогу у військовій сфері. керуючись законом конгрес затвердив суму асигнувань 95 млрд доларів для кредитування закупок військової техніки та обладнання членами НАТО.
22735. Зовнішньоекономічна програма США після ІІ світової війни 26.5 KB
  Зовнішньоекономічна програма США після ІІ світової війни. Проте США не зазнали на відміну від європейських держав проблем пов'язаних з війною руйнації міст та сіл. Зате на США припала третина воєнних витрат в антигітлерівській коаліції. Найголовніший результат американської участі у другій світовій війні полягав у тому що США перетворилися в наймогутнішу країну капіталістичного світу стали його економічним та фінансовим центром і незаперечним військовополітичним лідером.
22736. Ескалація інтервенції США у В'єтнамі 1965 - 1968 рр. 30.5 KB
  Ескалація інтервенції США у Вєтнамі 1965 1968 рр. Воспользовавшись спровоцированными инцидентами США подвергли 5 августа 1964 г. 10 августа президент США утвердил закон принятый 7 августа на совместном заседании палаты представителей в сената США. Эта так называемая тонкинская резолюция санкционировала принятие президентом США необходимых мер два отражения любого вооруженного нападения против военных сил США и предотвращения дальнейшей агрессии.
22737. Початок ’’холодної війни’’ США проти СРСР у 1946 – 1949 рр 37 KB
  Початок холодної війни США проти СРСР у 1946 1949 рр. Але наступного ж дня 3 лютого у США розпочалася пропагандистська кампанія з приводу радянського атомного шпіонажу до речі про інтерес спецслужб СРСР до Манхеттенського проекту американському керівництву стало відомо щонайменше за півроку до появи відповідної інформації у ЗМІ. Черчилль не висловив і побоювань щодо можливості воєнного нападу СРСР на країни Заходу. СРСР який переміг у війні та вперше розірвав буферний пояс що ізолював його від світу відчув за думкою...
22738. Зовнішня політика адміністрації Трумена. «Доктрина Трумена» 33 KB
  Американский империализм стремился использовать финансовоэкономические трудности Англии усугубленные кабальным займом полученным ею от США в июле 1946 г. Американские дипломаты убеждали своих английских коллег что для их правительства самым благоприятным выходом была бы передача этой доли наследства в руки США как для облегчения финансового бремени Англии так и для ухода от той критики которой повсеместно подвергался британский империализм за его интервенцию в Греции. правительство США получило две британские ноты в которых...
22739. Американська стратегія ’’гнучкого реагування’’ у 60-ті рр 30.5 KB
  В месте тем разработчики плана учитывали и возможность нанесения Советским Союзом ответного ядерного удара по территории США. Внезапное для США появление советских ракет средней дальности на Кубе и отсутствие у них подавляющего превосходства в количестве МБР и БРПЛ над Советским Союзом сделали военный путь разрешения конфликта невозможным. Желания военных нашли должную поддержку в сенате США. Учитывая такие факторы как практически безраздельное господство ВМС США и объединенного флота НАТО на просторах мирового океана в начале 60х годов...
22740. Канада і НАФТА 44 KB
  Канада і НАФТА. Североамериканскиое соглашение о свободной торговле НАФТА между Канадой Соединенными Штатами Америки и Мексикой вступило в силу 1 января 1994 года. Созданное для поощрения увеличения торговли и инвестиций между партнерами по НАФТА Соглашение содержит грандиозный план уничтожения тарифов и сокращения нетарифных барьеров наряду с обстоятельными положениями по ведению бизнеса в зоне свбодной торговли. НАФТА увеличила доступ Канады на американский и мексиканский рынки а также повысила привлекательность канадской экономики для...
22741. Латиноамериканський курс адміністрації Дж. Картера 23.5 KB
  Планы укрепления агрессивной межамериканской военной системы консолидации правых режимов на континенте были приняты на вооружение и администрацией США во главе с Дж. Столкнувшись с падением престижа США в Латинской Америке и стремясь укрепить здесь свои позиции официальный Вашингтон возвестил о пересмотре политики в отношении латиноамериканских государств. Дипломатия США стала усиленно афишировать свой постоянный интерес к этим странам. Президент США Дж.