Константа Липшица квадратичного функционала

daeus

Вот есть функция f(x)=||Ax||^4
A - матрица (n x n) положительно определенная симметричная.
х - вектор размерности n
далее сказано, что f''(x) (вторая производная) липшицева с коснстантой L
а kappa - коэфициент сильной выпуклости f(x)
Задача найти kappa и L.
Я все забыл с времен, когда подобное проходилось. ничего не получается. долго уже бьюсь, гугл мне что-то не помогает. помогите, плз.

daeus

ап :(

svetik5623190

коэфициент сильной выпуклости
что это?

daeus

ну, есть много определений. одно из них:
<u-v,f'(u)-f'(v)> <= kappa*||u-v||^2

daeus

ах, да. обеспечу разумное вонаграждение, если желаете.
просто ну ооочень надо. :(

daeus

ап2

svetik5623190

Пространство, я полагаю, вещественное.
f(x)=||Ax||^4
Если я верно понимаю обозначения, то f(x) = (<Ax,Ax>)^2. Тогда
Первая производная (Фреше) (f'(x (h) = 4 <Ax,Ax> <Ax,Аh>
(использовано правило дифференцирования многочлена, правило дифференцирования сложной функции и тот факт, что производна Фреше функционала <x,x> по направлению h равна 2<x,h>)
Вторая производная (Фреше) f"(x (hk) = 4 <Ax,k> <Ax,h> + 4 <Ax,Ax> <Ak,Аh>
(использовано правило Лейбница дифференцирования произведения и тот факт, что прозводная линейного функционала совпадает с ним самим)
Как понимать в этом разрезе константу Липшица и константу сильной выпуклости - не улавливаю, ведь производная функционала - это линейный функционал. К чему он применяется в определениях константы Липшица и константы сильной выпуклости?

vovatroff

ведь производная функционала - это линейный функционал
линейный по h, но не по x (в ваших обозначениях выше)

daeus

линейный по h, но не по x (в ваших обозначениях выше)
именно. нужна липшицевость по x.
все это используется (я должен использовать) для оценки скорости сходимости метода Ньютона (из методов оптимизации). Все обозначения и формулировки стянул оттуда (лекции и книжка Васильева Ф.П. "Методы Оптимизации").

svetik5623190

линейный по h, но не по x (в ваших обозначениях выше)
Я понимаю. Если бы не понимал, вряд ли смог бы написать эти две производные выше :)
Я не понимаю, как записать формулы, содержащие требуемые константы.Запишите плиз формулы-определения констант, подставив в них найденные мной производные, может так мне будет понятнее, что нужно сделать.
Получатся некоторые неравенства. Они должы выполняться при всех h и k или что?

vovatroff

ну я бы предположил, что для оценки константы Липшица f''(x) стоит продифференцировать
его в третий раз и взять норму третьей производной (как функционала) как константу Липшица. Интуитивно так мне кажется.
Насчет постоянной сильной выпуклости интуиция ничего не говорит.
Слабая выпуклость - это, наверное, выпуклость F(x+th) как функции t?
А в сильном смысле - не понятно.
PS тут все не в бесконечномерном, а в n-мерном случае, к счастью. Единственный +.

vovatroff

для оценки скорости сходимости метода Ньютона
Сходимость метода Ньютона хорошо изучена в общем случае.
Есть теоремы, и есть явные оценки, наверняка они есть и в той
книжке, на которую вы ссылаетесь. Что конкретно требуется от вас?
Зачем вам дали этот конкретный функционал с 4-й степенью?

svetik5623190

ну я бы предположил, что для оценки константы Липшица f''(x) стоит продифференцировать
его в третий раз и взять норму третьей производной (как функционала) как константу Липшица. Интуитивно так мне кажется.
Согласен. Только брать норму как функционала на декартовом произведении четырёх исходных пространств (по трём - линейного, по х - как фишка ляжет, дифференцировать надо, там видно быдет)? Или при фиксированных h,k,v?
Насчет постоянной сильной выпуклости интуиция ничего не говорит.
Слабая выпуклость - это, наверное, выпуклость F(x+th) как функции t?
А в сильном смысле - не понятно.
В сильном смысле значит не просто "касательная над графиком, хорда под графиком", а с коэффицинтом. Примерно как метрическое и ультраметрическое пространство. Хотя нет, это плохой пример, в ультраметрике нет константы.
Свои вопросы по нахождению этой константы я уже задал выше.
PS тут все не в бесконечномерном, а в n-мерном случае, к счастью. Единственный +.
А чем + то? Методы всё равно пока что используем одни и те же. В вещественном гильбертовом пространстве было бы всё то же самое по виду.

daeus

В общем случае, конечно, и рассмотрено. Но там как раз и используются для оценки данные константы. Почему именно случай 4й степени - функционал легко решаем аналитически (находится минимальная точка. там ноль ессно а 2я степень не попадает под условие f''(x)\in Lip(X) с L>0, т.к. это константа. Вот потому мы с научником решили рассматривать этот функционал.
От меня требуется сравнить мои результаты и теоретическую оценку. А для этого очень нужны эти константы.
если кому совсем интересно, то: ftp://vniief.hackers/mo0032c.pdf - конспект лекций (теорема 16, страница 38).
да, кстати, вспомнил еще теореску по сильную выпуклость.
она эквивалентна <f''(x)*ksi, ksi> >= kappa*|ksi|^2
для всех x из X и всех ksi из Lin X, параллельному аффинной оболочке мн. X
т.е. в данном случае "для всех ksi из E^n", как я понимаю.
а еще мн.X можно ограничить так, x_i 'in [-1,1], т.к. дальше метод не поползет.

svetik5623190

На всякий случай, третья производная Фреше будет такая:
f'''(x (hkv) = 4 <Av,Аk> <Ax,Аh> +4 <Ax,Аk> <Av,Аh> + 8 <Ax,Av> <Ak,Аh>
Ну и чтоб закрыть вопрос окончательно, напишу и четвёртую. Как и положено четвёртой производной от многочлена, она не зависит от переменной, по которой дифференцировали. Чтобы не городить скобки, напишу аргументы через запятую.
f''''(x)[h,k,v,w] = 4 <Av,Аk> <Aw,Аh> +4 <Aw,Аk> <Av,h> + 8 <Aw,Av> <Ak,Аh>
Пятая производная тождественно равна нулю.
За сим я и отправляюсь спать. Надеюсь, в выкладках выше нигде не наврал. Что-то Формула для четвёртой производной не симметричка относительно h,k,v,w. Как-то неприятно это, непонятно откуда берётся неравноправность переменных. Думать над этим сейчас уже не в состоянии, но если кто ответит - скажу спасибо.

vovatroff

Только брать норму как функционала на декартовом произведении четырёх исходных пространств (по трём - линейного, по х - как фишка ляжет, дифференцировать надо, там видно быдет)? Или при фиксированных h.k.v?
Думаю, что при фиксированных h.k.v. В обычных обозначениях h.k.v - символы
дифференциалов независимых переменных dx, dy... А производная f'''(x) - коэффициент
ряда Тейлора по переменным h, k, v - есть функция от выбора точки разложения x.
Именно ее изменение в зависимости от x и нужно ограничить сверху оценкой Липшица,
по идее.
В сильном смысле значит не просто "касательная над графиком, хорда под графиком", а с коэффицинтом. Примерна как метрическое и ультраметрическое пространство. Хотя нет, это плохой пример, в ультраметрике нет константы.
Можно как-то объяснить на примере функции одной переменной f(x что такое сильная выпуклость и чем она отличается от просто выпуклости? Допустим, f'' существует,
тогда просто f''>0 не достаточно? Нужно что-то типа f'' > c> 0?
А чем + то? Методы всё равно пока что используем одни и те же. В вещественном гильбертовом пространстве было бы всё то же самое по виду.
Ну хотя бы в том, что при n=1 будем иметь просто функцию (Ax)^4, A=const, уж с
ней-то как-нибудь совладаем :)

daeus

я даже вам могу n сказать, но ИМХО оно не существенно абсолютно. :)
размерность 5.
Производная по Фреше, это клево, но в данном случае получаем так: производная просто вектор, вторая - матрица. т.е. никаких зависимостей от h,k,v нет.
Спасибо, что пытаетесь помочь.

svetik5623190

Чую, что мы общими усилиями уже почти во всём разобрались, осталось только заварить чайку, выпить его, перечитать тред, после чего наверняка в голове появится мысль как всё сделать. Что Вам и рекомендую предпринять.
Напишите формулы от руки, некоторым это помогает. Запишите формылы-определения констант, используя найденные мной выражения для производных, и мне кажется всё легко посчитается.
А я - спать

vovatroff

да, кстати, вспомнил еще теореску по сильную выпуклость.
она эквивалентна <f''(x)*ksi, ksi> >= kappa*|ksi|^2
А, ну то есть для функции одной переменной f(x) это, в самом деле,
эквивалентно тому, что я написал постом выше: f''(x) >= kappa > 0 при всех x.
Так?
Для одномерного аналога вашей функции это будет: f(x) = (Ax)^4, A=const,
f''(x) = 12A^4 * x^2, т.е. kappa = 12A^4
Ну и поскольку max | f'''(x)| = 24A^4 * max |x|,
то для x из [-1,1], соответственно, константа Липшица второй производной: L = 24A^4
Я правильно все понимаю для этого тривиального случая?

svetik5623190

Производная по Фреше, это клево, но в данном случае получаем так: производная просто вектор, вторая - матрица. т.е. никаких зависимостей от h,k,v нет.
Производная по Фреше это оно самое и есть! Gросто я написал в правой части (например для 3 производной) не компоненты тензора 3 ранга, а значение трилинейного функционала на векторах (=направлениях) h,k,v.
Вектор - линейный функционал, матрица - билинейный функционал, третья производная (тензор 3 ранга) - трилинейный функционал и т.п.
Гляньте в любом учебнике функционального анализа определение производной Фреше - сразу станет всё ясно :)
Ну а я-таки иду спать :)

vovatroff

да мы уже закончили почти!
я готов огласить свой бездоказательный ответ :)

daeus

Производная по Фреше это оно самое и есть!
я знаю, просто заметил, так, чтобы не занимались ненужным поиском зависимостей. :)

svetik5623190

да мы уже закончили почти!
Я уже писал об этом выше:
Чую, что мы общими усилиями уже почти во всём разобрались, осталось только заварить чайку, выпить его, перечитать тред, после чего наверняка в голове появится мысль как всё сделать.

я готов огласить свой бездоказательный ответ

Ответ подожду. Всё равно пока поправляю матрас (а он у меня не маленький) и стелю постель какое-то время пройдёт.

vovatroff

Производная по Фреше, это клево, но в данном случае получаем так: производная просто вектор, вторая - матрица. т.е. никаких зависимостей от h,k,v нет.
Я вас прекрасно понимаю. Производная - градиент, вторая - гессиан, ...
же под производными понимает дифференциалы: первый, второй и т.д.
Именно как Фреше их и вводил, если я не ошибаюсь.
Чтобы что-то понять, полезно снизойти до уровня одной независимой
переменной, имхо.

svetik5623190

Производная - градиент, вторая - гессиан, ...
Кстати а дальше что?

daeus

Кстати а дальше что?
тссс. не сбивай его, мы ждем бездоказательный ответ :)

vovatroff

Мой ответ такой:
kappa = 12*|a_min|^4,
L = 24|a_max|^4
где a_min, a_max - соответственно минимальное по модулю и максимальное
по модулю собственное значение матрицы A
Но его нужно тщательно проверить.

daeus

спасибо, проверять на числах буду завтра.

svetik5623190

Забавно, что если одно поделить на другое, будет число обусловленности в четвёртой степени с коэффициентом.
Ну что ж, теперь я точно ложусь.
Всем спокойной ночи и спасибо за миную беседу. Приятно, что в 3 ночи ещё кто-то готов поговорить о математике совершенно бескорыстно и с интересом.

svetik5623190

спасибо, проверять на числах буду завтра.
Не на числах надо проверять, а выкладки провести!
Всё у вас у прогеров так: докажем что все чётные числа простые. Проверим. 0 - вообще не натуральное, особый случай, пропустим. 2 - простое. Работает! Включаем это утверждение в библиотеку. :grin:

vovatroff

Спок ночи, взаимно.
To : проверьте, у вас не потерялись A при дифференицрованиях?
Сдается мне, там всюду по 4 штуки должно стоять (типа A^4)

vovatroff

выкладки провести!
Именно проверить, по всем законам жанра!
Потому как я просто взял свои одномерные оценки и тупо попытался
придать им n-мерный вид, сославшись про себя на вариационный принцип
для квадратичных форм.

svetik5623190

To : проверьте, у вас не потерялись A при дифференицрованиях?
Ну конечно я облажался, в первой же производной А не хватает, а потом и дальше потащилась ошибка. Время позднее, не мудрено. Ещё и удивляюсь потом, что
Что-то Формула для четвёртой производной не симметрична относительно h,k,v,w. Как-то неприятно это, непонятно откуда берётся неравноправность переменных

svetik5623190

в первой же производной А не хватает
Поправил, а то ведь стыд и позор. Впрочем, всё равно наверное ещё лажа где-то есть, ничего уже не соображаю, спать хочу.

daeus

kappa = 12*|a_min|^4,
нет :) . научник сказал, что kappa=0 (мэпл такого значения и в помине не выдал). Собственно так у меня опосля и получилось.
Соответственно с Липшицом вопрос, наверное, открыт. kappa больше не надо.
Да и функция изменилась на ||Ax-f||^4

vovatroff

научник сказал, что kappa=0 (мэпл такого значения и в помине не выдал). Собственно так у меня опосля и получилось.
Странно, что 0 ... Я же для одномерного случая, надеюсь, не наврал со второй производной?
Возможно, я неправильно понял, что такое kappa.
Липшицева константа хоть правильная была? Или вы ее еще не проверяли?

svetik5623190

Да и функция изменилась на ||Ax-f||^4
Для начала продифференцируй подобно тому, как я это сделал выше.

daeus

а ее как проверить? для этого надо знать (в нашей задаче kappa>0).
а для функций такого вида (как сказал научник) этоизвестно, что она не сильно выпукла. потому решили взять функцию ||A_1x-f_1||^4+||A_2x-f_2||
со второй частью проблем нет. в первой известно, что kappa=0, осталась только Липшицевость. Считать буду завтра утром :)
Оставить комментарий
Имя или ник:
Комментарий: