id: Гость   вход   регистрация
текущее время 21:59 28/03/2024
Автор темы: spinore, тема открыта 12/03/2012 07:06 Печать
Категории: криптография, приватность, прослушивание коммуникаций, разное, офф-топик, квантовая криптография
https://www.pgpru.com/Форум/Криптография/ПомогитеРешитьЗадачучисловоеИАналитическоеРешениеФункции
создать
просмотр
ссылки

Помогите решить задачу (числовое и аналитическое решение функции)

Учите, дети, абстрактную алгебру, топологию
и дифференциальную геометрию, иначе всю
жизнь будете страдать вот такими тупыми
первокурсными матановыми задачами.
کπιν∅rε ☭

Общая постановка


Дано:

Гладкая неотрицательная функция ƒ ( x, y ), заданная на квадранте x ≥ 0, y ≥ 0, и некоторая точка ( x0, y0 ) внутри этого квадранта. Известно, что ƒ обладает следующими свойствами:
  1. ƒ конечна, если конечны оба её аргумента, причём ƒ ( 0, 0 ) = 0.
  2. При любом фиксированном y функция ƒ выпукла вверх по x и монотонно растёт по x до бесконечности.
  3. При любом фиксированном x функция ƒ имеет предел limy→∞ ƒ ( x, y ) = log2 ( 2x + 1 ).
  4. ƒ — неявная функция обоих своих аргументов, зависящая от корня сложного трансцендентного уравнения, из-за чего прямой подход к аналитическому исследованию ƒ затруднён.
  5. Квадрант x ≥ 0, y ≥ 0 может быть разбит на конечное число областей, в каждой из которых функция ƒ является выпуклой.

Требуется:

Найти (описать аналитически) функцию

F ( x0, y0 ) := maxΔxy { ƒ ( x0 + Δx, y0 – Δy ) + ƒ ( x0 – &Deltax, y0 + &Deltay ) , ƒ ( x0 + Δx, y0 + &Deltay ) + ƒ ( x0 – Δx, y0 – Δy ) } / 2,

где 0 ≤ Δxx0 и 0 ≤ Δyy0, а также те значения Δx и Δy, на которых достигается максимум.

Важные частные случаи


Рассмотреть варианты:

  1. При любом фиксированном x функция ƒ:
    1. Монотонно убывает по y и выпукла вниз по y.
      Численное решение для конкретной интересуемой ƒ в этом случае всегда достигается при каких-то Δx, не обязательно равных нулю или x0, и при Δy = y (т.е. одна точка всегда на границе, а другая — на максимальном удалении от исходной y0). Существенным вкладом в решение может считаться нахождение контрпримера: любой конкретной ƒ с вышеоговоренными свойствами, подпадающей под пункт 1.a и приводящей к другому решению.
    2. Имеет только один экстремум по y, который является глобальным максимумом по y и досигается при каком-то конечном ненулевом y = ymax. На промежутке 0 ≤ y ≤ yinflec, содержащем точку ymax, функция ƒ выпукла вверх; а на промежукте
      yinflecy &le ∞ — выпукла вниз. Точка y = yinflec является единственной точкой изгиба ƒ.
  2. В зависимости от фиксированного значения x функция может быть как монотонно растущей по y (и, в том числе, иметь седловую точку при конечном ненулевом y), так и иметь два локальных экстремума, достижимых при конечных ненулевых y: локальный максимум при меньшем значении y, и локальный минимум — при большем (на промежутке от нуля до максимума ƒ выпукла вверх). Также, при каких-то фиксированных x может наблюдаться поведение, описанное в вышеприведённом случае 1.b.

Пояснения и идеи к решению


Геометрические смысл решения прост: можно вообразить себе две точки ( x1, y1 ) и ( x2, y2 ), которые изначально сидят в одном месте на плоскости ( x, y ) — в заданной точке ( x0, y0 ). Далее мы начинаем разносить эти точки так, чтобы как сумма их абцисс, так и сумма их ординат оставались одинаковыми и равными, соответственно x0 (для абцисс) и y0 (для ординат). Если мы пододвинули одну точку на некоторое расстояние влево, значит, на такое же расстояние другую точку надо пододвинуть вправо. Более того, «разносить» эти точки можно только до тех пор, пока они не достигнут границы прямоугольника 0 ≤ x ≤ 2x0, 0 ≤ y ≤ 2y0. Далее, перебрав все возможные «разношения» точек надо найти такое, которое даст максимальное усреднённое значение функции в этих точках, то есть максимум для
[ &fnof( x1, y1 ) + &fnof( x2, y2 ) ] / 2.


Для наглядности можно сначала рассмотреть модельный пример — функцию ƒ, зависящую только от одного аргумента. Решение тривиально, если ƒ монотонна на всём промежутке [ 0, ∞ ) и сохраняет на нём значение выпуклости: точки разносить не надо, если ƒ выпукла вверх, и точки надо разнести на максимальное расстояние, если ƒ выпукла вниз — геометрически это легко видеть из неравенства Йенсена. Однако, это не помогает решить даже случай 1.a, поскольку ƒ выпукла вверх по одной переменной, но вниз по другой.


Более сложный модельный случай — функция ƒ от одного аругмента, не являющаяся выпуклой на всём интервале [ 0, ∞ ). Гугление позволило найти, что интересуемая операция используется при обработке сигналов для устранения шума и называется «метод скользящих средних» («moving average»), только в этом случае Δx фиксировано (размер окна скольжения), а значения x0 перебираются. Это позволяет построить «сглаженную» функцию, без пиков, но имеющую то же качественное поведение глобально (хорошие графики на эту тему есть здесь). В интересуемом же нас случае размер окна надо подбирать под каждую точку, чтобы получающаяся сглаженная функция имела как можно большее значение — задача, которая не похоже, чтоб ставилась в теории сигналов. Тем не менее, есть нечто, что позволяет объединить как нашу задачу, так и обработку сигналов, в одну общую:


Допустим, что мы сглаживаем сигнал, выбирая все возможные размеры окон. В получившемся наборе кривых для каждой точки x0 мы выбираем такую кривую, которая имеет самое высокое значение в этой точке. Произведя эту процедуру для всех точек, мы получим некоторую верхнюю границу для всех «сглаженных» кривых — функцию

G ( x ) = supΔx [ ƒ ( x + Δx ) + ƒ ( x – Δx ) ] /2

Поскольку такое сглаживание перебирает все окна, не ограничивая их размер (но ограничение требуется в нашей задаче), нужная нам кривая F [см. выше, что есть F] будет лежать не выше этой G во всех точках, т.е. можно получить некоторую верхнюю границу, упрощающую анализ. Так как G имеет нетривиальный вид даже для качествнно простых ƒ, а также связана с обработкой сигналов1, наверняка фундаментальные математики задумывались о том, чтобы изучить эту операцию и её свойства. Было бы очень интересным узнать, как называется операция &fnof → G, и что про неё известно. К примеру, для ƒ = cos ( x ) получается
G = | cos ( x ) |.

Более грубой верхней границей на получающийся набор можно считать выпуклую оболочку, натянутую на множество всех рассматриваемых точек ( x, ƒ ( x ) ). Например, для функции ƒ = cos ( x ) это даст прямую, параллельную оси абцисс, проходящую через точку с оридинатой 1. Наглядно видно, что это — ещё более грубая граница, чем G = | cos ( x ) |. Основная идея — найти какие-то интересные топологические свойства кривых/поверхностей; понять, что в задаче определяется чисто выпуклостью функций, а что — следствие их конкретного вида. Очевидно, что если нечто является следствием выпуклости, то вид функции ƒ совершенно не важен — задачу можно решать в общем виде.

Физический смысл


Пусть ƒ — пропускная способность квантового канала, x — средняя энергия на его входе, и y — средняя энергия в его среде (т.е. доступная Еве). Рассмотрим два использования канала3, считая, что среднее количество энергии на входе на одно использование канала ограничено и равно x0. Аналогично, будем считать, что среднее значение энергии в среде ограничено, и равно в среднем y0 на одно использование канала. Тем не менее, у нас есть свобода перераспределять энергию между первым и вторым использованиями канала, и мы хотим найти метод делать это так, чтобы его пропускная способность была максимальной. Если вообразить, что шум/среда/Ева ограничена по энергии при воздействии на канал, мы найдём тот вид распределения, который наболее выгоден Алисе и Бобу.


Можно показать, что решение случая 1.a полностью решает поставленную задачу для канала с аддитивным классическим шумом, а также для любого числа его использований для посылки (классической) информации. Решение случая 1.b позволяет найти то же, но для двух, в общем случае, использований канала и некоторых параметров (если ещё опереться на ряд недоказанных гипотез). Решение задачи 2 полностью даёт ответ для двух использований «lossy»-канала (канал с затуханием амплитуды). Так как неоднородное распределение энергии по использованиям канала приводит к корреляциям между его использованиями, вид среды часто называют памятью, а сами каналы — каналами с памятью. Соответственно, задача может быть сформулирована, как «найти оптимальный вид памяти для гауссова канала при условии ограничения на энергию в его среде» (энергия на входе считается ограниченной всегда, иначе пропускная способность будет бесконечной, т.е. тривиальным случаем). Более подробно смысл задачи раскрыт в комментариях к топику «Проблема определения криптостойкости» (перенесено в «Вопросы по квантовым каналам, их моделирование и применение»).

Мотивация и плюшки


  1. Решение случая 1.a2 (вкупе с имеющимися наработками) — задача уровня публикации в Phys. Rev. A.
  2. Полное решение всей задачи (возможно, объединяя оба типа канала в один) и всех частных случаев, при условии, что удастся получить какие-то нетривиальные важные свойства, строго доказанные аналитически и мотивированные физически с точки зрения их смысла — уровень публикации в IEEE Tran. Inf. Theor.

Желающие есть помочь/поучаствовать?



1А, значит, и с финансовыми трейдерами, биржевиками, и прочими, кто использует сглаживание для отделения тренда от шума — гугл преиспещрен ссылками на эту тему.
2Как и случая 1.b или 2, каждый по отдельности.
3Обычно с разными использованиями канала ассоциируют его разные моды: одно использование n-модового канала в некотором смысле эквивалентно n использованиям одномодового, в котором разные его использования скоррелированы между собой (Ева по-разному воздействует на сигнал при разных его использованиях).


 
Комментарии
— unknown (12/03/2012 11:21)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Пальцем в небо: а метод скоростного спуска Нилдера-Мида не подойдёт? Или что-то похожее?
— spinore (12/03/2012 12:20)   профиль/связь   <#>
комментариев: 1515   документов: 44   редакций: 5786
unknown, не поверите, уже давно открыт в соседней вкладке браузера :) Правда, не в контексте этой задачи, а в контексте того, что Vadim_Z сказал «смотри, оказывается fminserach в MATLAB'е испольузется эвристический метод! Мы об этом никогда не подозревали, им пользуясь» (ссылку я ещё внимательно не читал).

Короче говоря, эффективный численный метод — это хорошо, этим надо будет заняться в любом случае, но главная мишень и трудность — то, что можно найти/оценить аналитически. Функция ƒ вычисляется быстро, так что разработка численного метода больших сложностей не составляет. Не буду скрывать, что решение 1.a и 1.b уже численно получено, не плохо (хотя и не до конца) исследовано, но с аналитикой и пониманием всё сложнее. Я ещё детально википедию/литературу не штудировал по вопросу метода скользящих средних и связанных с ними вопросам (это может что-то дать).

В случае 1.b, если взять для простоты (модельно), что от x он не зависит, получается следующее: пока y0 мал, в силу монотонного роста и выпуклости вверх оптимально точки не разносить. Потом, с увеличением y0, обе точки сидят в максимуме, и даже перескакивают через него. Однако, начиная с какого-то значения за максимумом, точки вдруг начинают разбегаться4: одна полёзёт обратно в максимум, на горку, а другая вправо, в сторону убывания функции. Как точка «разбегания» связана с точкой изгиба — вопрос.

Аналогичное решение получается и для большого числа точек5 (мод) [до сих пор выше всегда рассматривался случай только двух точек]: одна ползёт вниз, а все другие — обратно на горку. Т.е. n – 1 точек сидят в одном месте, и n'ая — в другом, на «мусорной моде», куда загоняется излишек энергии. Видимо, профит от движения n – 1 точек назад перекрывает убыль от движения одной точки вперёд, в сторону убывания функции. Когда ограничение по энергии растёт на бесконечность, естественно, все n – 1 точкек перебираться на горку в максимум, а одна — в бесконечность (но это тривиальное решение).

Куда более интересно, что даже если перебирать вообще все случаи и результаты числененной оптимизации, якобы решение всегда получается6 этого типа: всего два разных значения по y: одна точка в каком-то одном месте на кривой/поверхности, а все остальные совпадают друг с другом. В классической теории информации, говорят, результат такой же для каналов.


4Эдакий «перегрев по энергии, приводящий к фазовому переходу» — было б круто подвести под это дело какую-то теорию фазовых переходов.
5Такую задачу легко сформулировать как «расставь n точек на оси абцисс так, чтобы среднее значений функции в этих точках было максимальным, при условии что средняя абцисс точек фиксирована».
6Хотя, может, плохо исследовали.
— unknown (12/03/2012 12:43)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Напоминает шутку про "бифуркацию субмодальных сингулярностей".
— spinore (12/03/2012 12:53, исправлен 12/03/2012 12:58)   профиль/связь   <#>
комментариев: 1515   документов: 44   редакций: 5786

Главное, чтоб не чёрнодырочную проводимость с квадратно-гнездовым методом :)


Некие параллели с теорией фазовых переходов здесь есть, об этом действительно стоит подумать (правда, я с физикой твёрдого тела вообще плохо знаком, к сожалению). Обычно в физике по заданным свойствам модели восстанавливают «начинку» (функционал плотности?), а здесь обратная задача: начинка дана, и надо понять какая «физика» из неё следует.

— unknown (12/03/2012 16:43)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Название темы слегка переименовал, чтобы было хоть что-то запоминающееся в общем потоке :) Подправил отсылку на первоисточник — коментарии из обсуждения, которые послужили появлению всего этого. Те комментарии также вынесены в отдельную тему.
— spinore (12/03/2012 18:16)   профиль/связь   <#>
комментариев: 1515   документов: 44   редакций: 5786

Отлично! Изначальное название было дано по приколу, как пародия на последние топики в разделе «криптография» :)
Только, чтобы не терять связность, надо тогда поправить ссылки в том топике на этот — в местах

Сейчас стоит задача: найти[создать], когда распределение однородно

потому я решил не отставать[создать] от общества
— spinore (18/03/2012 03:51)   профиль/связь   <#>
комментариев: 1515   документов: 44   редакций: 5786
К слову сказать, 1.b, должно быть, анализируется методом множителей Лагранжа. Получится, наверное, какое-нибудь очередное траснцендентное уравнение, которое можно какими-то приближёнными методами порешать или какие-то его свойства поисследовать.

А вот для задаче 1.a, которая кажется более простой, метод Лагранжа не поможет: там решение строго на границе по y7, и показать это можно, лишь доказав монотонность или определённые свойства выпуклости, что сводится к аналитическому доказательству постоянства знака8 длинного крокодила-выражения.


7Т.е., если положить, что в одной из функций y нулевой, то задача становится тривиальной: нахождение оптимальных значений x при заданных значениях y — уже решённая задача (тут — для lossy, и тут — для additive-канала).
8Ещё и при любых параметрах.
— Гость (06/04/2012 17:28)   <#>
ABCD-параллелограмм,EC=3.AB=7.угол АЕД=15
найти площадь АВСД
— Гость (06/04/2012 22:38)   <#>
ABCD-параллелограмм,EC=3.AB=7.угол АЕД=15
найти площадь АВСД

5,4352;
— Гость (08/04/2012 09:58)   <#>
5,4352
Это ответ. А где (числовое и графическое) решение? :)
— spinore (26/05/2012 19:33, исправлен 26/05/2012 19:54)   профиль/связь   <#>
комментариев: 1515   документов: 44   редакций: 5786

> бифуркацию субмодальных сингулярностей

Даринский Б.М., Сапронов Ю.И., Царев С.Л. Бифуркация экстремалей фредгольмовых функционалов, — СМФН, 12, М., 2004, стр. 3–140.

Наткнулся случайно :)


В связи с 1.b возникла (ещё давно) задача:


Дано:

Гладкая неотрицательная функция ƒ ( x, y ), заданная на квадранте x ≥ 0, y ≥ 0. При любом фиксированном y функция ƒ выпукла вверх по x и монотонно растёт по x до бесконечности. При любом фиксированном x функция ƒ выпукла вверх по y и монотонно растёт по y до бесконечности.

Требуется:9

Выяснить, является ли ƒ выпуклой по обеим переменным вместе (как поверхность). Если да, то доказать, если нет, то привести контрпример.

Решение:10

Контрпример: ƒ ( x, y ) = ln ( x + y ) + xy на множестве x ≥ 1, y ≥ 1 (сдвиг роли не играет). По диагонали будет выпуклость вниз.

Мораль:

Халявы не будет: прийдётся честно писать гессиан и доказывать выпуклость. Если же так окажется, что в реальной задаче выпуклости действительно нет (при тех параметрах, где она предполагалась), это будет уже совсем тро-ло-ло :(


9Задача на всю жизнь испортит карму тому, кто осмелится дать её на экзамене студентам.
10Спасибо Vadim_Z.

— sentaus (26/05/2012 20:20, исправлен 26/05/2012 20:25)   профиль/связь   <#>
комментариев: 1060   документов: 16   редакций: 32

Кажется, можно и проще: f(x,y) = xy – гиперболический параболоид. Не кажется :) Строгой выпуклости по переменным нет.

— spinore (26/05/2012 21:13, исправлен 26/05/2012 21:16)   профиль/связь   <#>
комментариев: 1515   документов: 44   редакций: 5786
гиперболический параболоид.

Пример тоже интересный. Во всяком случае, сразу позволяет задуматься, что от недиагональных членов в гессиане не уйти. Просто поначалу думалось, что монотонный рост как-то меняет суть дела, но это не так: прибавкой линейной функции к заданной выпуклой её всегда можно сделать монотонно возрастающей (на ограниченной области), не испортив свойств выпуклости. Если не требовать монотонности, а ограничиться только выпуклостью, пример был найден ещё раньше: – x2y2 + 3xy. Добавляя к ней функцию nx + my, где n и m — большие числа, получим и монотонно растущую на ограниченной области. Пример с бесконечной областью был дан в предыдущем посте.

Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3