Что Вас потрясло в математике?

[MrAsasin243]

svv в сообщении #1581037 писал(а):

MrAsasin243
И даже "определимых" чисел лишь счётное множество.

Да я это тоже узнал, но позже, но это уже было не так впечатлительно как в начале того как узнал про счетные и несчетные бесконечности.

[Mirage_Pick]

Школьницы из Нового Орлеана придумали новый способ доказать теорему Пифагора! Этой классической теореме геометрии более двух тысяч лет, и мириады придуманных за это время доказательств, казалось бы, уже разобрали на атомы эту тему. Умудриться при таких условиях найти принципиально новое - настоящий подвиг. Это показывает, что геометрия неисчерпаема на новые идеи.

[Ende]

Возникшая дискуссия отделена в тему «Касательно новых доказательств теоремы Пифагора»

[Anton_Peplov]

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

Задача о свадьбах? Вот те граф и алгоритм. Теория коллективного выбора? Вот те графы. А сколько б я искал пример нетранзитивного циклического отношения, когда б подбирал возможные пары, а не взял и нарисовал четырехугольник? Ей-диэдру, я б сравнил изобретение графов с изобретением, к примеру, векторов. Один из мощнейших математических инструментов. Ограниченный задачами на конечных множествах, но...

[Droog_Andrey]

А ещё ряд ординалов прекрасно иллюстрируется графами. По крайней мере, до ординала Бухгольца :)

[Alex Krylov]

Мощнейшие вещи!!!!

1. J. B. Lasserre. Moments, Positive Polynomials and Their Applications
2. R. Cominetti, F. Facchinei, J.B. Lasserre. Modern Optimization Modelling Techniques
3. D. Henrion, M. Korda and J. B. Lasserre. The Moment-SOS Hierarchy: Lectures in Probability, Statistics, Computational Geometry, Control and Nonlinear PDEs

[пианист]

Alex Krylov
А можно как-то пояснить, в чем замечательность указанной литературы?

[Alex Krylov]

пианист в сообщении #1592982 писал(а):

Alex Krylov
А можно как-то пояснить, в чем замечательность указанной литературы?

Я прежде всего про мощь приведенного там инструментария (имеющего массу приложений)! Если говорить собственно о "литературных" достоинствах, то четкость и ясность изложения заслуживают тут столь же высокой оценки, что и сам излагаемый материал ))

[пианист]

Alex Krylov
Полистайте тему: здесь люди делятся поразившими математическими результатами, построениями, конструкциями etc.
Вы кидаете список литературы - но зачем? Что, надо все это изучить и догадаться, что же Вас из этого поразило (в чем, собс-но, мощь состоит)?
Впрочем, воля Ваша, конечно.

[Alex Krylov]

пианист в сообщении #1593040 писал(а):

Alex Krylov
Полистайте тему: здесь люди делятся поразившими математическими результатами, построениями, конструкциями etc.
Вы кидаете список литературы - но зачем? Что, надо все это изучить и догадаться, что же Вас из этого поразило (в чем, собс-но, мощь состоит)?
Впрочем, воля Ваша, конечно.

Давайте через "игрушечный" примерчик...

Дан полином $p(x)=x^4-2 x^2+3$. Он имеет два минимума в точках $x=\left\lbrace-1, 1\right\rbrace$. В обоих случаях минимум равен $2$. Хотим найти глобальный минимум этого полинома на интервале $[-2, 2]$, т.е. хотим решить задачу: $\min\limits_{x}\left\lbrace p(x): x\in[-2; 2] \right\rbrace$. Эта задача, очевидно, эквивалентна следующей: $\sup\limits_{}\left\lbrace \lambda: p(x)-\lambda>0 \forall x\in[-2; 2] \right\rbrace$.

Для полинома $p(x)-\lambda$, положительного на отрезке $[-2, 2]$ справедливо представление $p(x)-\lambda =\begin{bmatrix} 1 \\ x \\ x^2 \end{bmatrix}^T \begin{bmatrix}p_{11}&p_{12}&p_{13} \\ p_{12}&p_{22}&p_{23} \\p_{13}&p_{23}&p_{33}\end{bmatrix} \begin{bmatrix} 1 \\ x \\ x^2 \end{bmatrix} + (4-x^2)\cdot\begin{bmatrix} 1 \\ x \end{bmatrix}^T \begin{bmatrix}q_{11}&q_{12} \\ q_{12}&q_{22}\end{bmatrix} \begin{bmatrix} 1 \\ x \end{bmatrix}, где $ \begin{bmatrix}p_{11}&p_{12}&p_{13} \\ p_{12}&p_{22}&p_{23} \\p_{13}&p_{23}&p_{33}\end{bmatrix}\geqslant 0, \begin{bmatrix}q_{11}&q_{12} \\ q_{12}&q_{22}\end{bmatrix}\geqslant 0$. Приводя подобные члены, получим: $(p_{33}-q_{22}-1)x^4+(2p_{23}-2q_{12})x^3+(2p_{13}+p_{22}-q_{11}+4q_{22}+2)x^2+(2p_{12}+8q_{12})x+(p_{11}+4q_{11}+\lambda-3)=0$
В итоге приходим к следующей задаче выпуклого (полуопределенного) программирования:
$\max\limits_{}\lbrace\lambda: \begin{bmatrix}p_{11}&p_{12}&p_{13} \\ p_{12}&p_{22}&p_{23} \\p_{13}&p_{23}&p_{33}\end{bmatrix}\geqslant 0, \begin{bmatrix}q_{11}&q_{12} \\ q_{12}&q_{22}\end{bmatrix}\geqslant 0, p_{33}-q_{22}-1=0, 2p_{23}-2q_{12}=0, 2p_{13}+p_{22}-q_{11}+4q_{22}+2=0, 2p_{12}+8q_{12}=0, p_{11}+4q_{11}+\lambda-3=0 \rbrace $

Двойственная задача тут еще интересней: вместо исходной целевой функции минимизируется её мат. ожидание: $E\left\lbrace p(x) \right\rbrace=y_4-2y_2+3$... минимизируется оно по совокупности моментов $\left\lbrace y_i \right\rbrace$ вероятностной меры, сосредоточенной на $[-2; 2]$. Условия того, что эти моменты, по которым происходит минимизация, являются моментами не просто меры вероятностной, но вероятностной меры, сосредоточенной на $[-2; 2]$, задаются в виде двух линейных матричных неравенств (относительно этих моментов). Глобальному минимуму, очевидно, соответствует атомарная мера с атомами в точках минимума $p(x)$ - эта ситуация алгоритмически фиксируется с помощью специального рангового условия для так называемой матрицы моментов. Если мы отфиксировали, что моменты, полученные в результате решения (двойственной) оптимизационной задачи, соответствуют атомарной мере, то мы можем (с помощью методов линейной алгебры) экстрагировать сами атомы.

С помощью Теоремы Путинара о представлении полиномов, положительных на компактных полуалгебраических множествах (в англоязычной литературе - Putinar's Positivstellensatz), этот подход (который я тут попытался обрисовать в режиме "express") распространяется на многомерный случай (общий случай глобальной полиномиальной оптимизации). Приведенная литература - она обо всем об этом... и о соотв. приложениях в теории управления, теории устойчивости, теории вероятностей итд...

[Alex Krylov]

И пару слов о двойственной задаче и о том, откуда там и каким образом возникают моментные условия...

Пусть $\mu$ - вероятностная мера, сосредоточенная на $[-2,2]$. Что такое вероятностная мера, сосредоточенная на $[-2,2]$? Эта мера, положительная для всех полиномов $p(x)$, положительных на $[-2,2]$, т.е. должна удовлетворять $\int\limits_{}^{}p d\mu\geqslant 0 $. Очевидно, что $p(x)=\begin{bmatrix} 1 \\ x \\ x^2 \end{bmatrix}^T \begin{bmatrix}p_{11}&p_{12}&p_{13} \\ p_{12}&p_{22}&p_{23} \\p_{13}&p_{23}&p_{33}\end{bmatrix} \begin{bmatrix} 1 \\ x \\ x^2 \end{bmatrix} + (4-x^2)\cdot\begin{bmatrix} 1 \\ x \end{bmatrix}^T \begin{bmatrix}q_{11}&q_{12} \\ q_{12}&q_{22}\end{bmatrix} \begin{bmatrix} 1 \\ x \end{bmatrix} - полином, положительный на $[-2,2]$. Тогда $\int\limits_{}^{}p d\mu\ = \int\limits_{}^{} \operatorname{tr}\left\lbrace \begin{bmatrix}p_{11}&p_{12}&p_{13} \\ p_{12}&p_{22}&p_{23} \\p_{13}&p_{23}&p_{33}\end{bmatrix} \begin{bmatrix} 1 \\ x \\ x^2 \end{bmatrix} \begin{bmatrix} 1 \\ x \\ x^2 \end{bmatrix}^T \right\rbrace + \operatorname{tr}\left\lbrace \begin{bmatrix}q_{11}&q_{12} \\ q_{12}&q_{22}\end{bmatrix} (4-x^2)\begin{bmatrix} 1 \\ x \end{bmatrix} \begin{bmatrix} 1 \\ x \end{bmatrix}^T \right\rbrace d\mu = \\$
$= \operatorname{tr}\left\lbrace \begin{bmatrix}p_{11}&p_{12}&p_{13} \\ p_{12}&p_{22}&p_{23} \\p_{13}&p_{23}&p_{33}\end{bmatrix} \int\limits_{}^{} \left\lbrace \begin{bmatrix} 1 \\ x \\ x^2 \end{bmatrix} \begin{bmatrix} 1 \\ x \\ x^2 \end{bmatrix}^T \right\rbrace d\mu \right\rbrace + \operatorname{tr}\left\lbrace \begin{bmatrix}q_{11}&q_{12} \\ q_{12}&q_{22}\end{bmatrix} \int\limits_{}^{} \left\lbrace (4-x^2) \begin{bmatrix} 1 \\ x \end{bmatrix} \begin{bmatrix} 1 \\ x \end{bmatrix}^T \right\rbrace d\mu \right\rbrace \geqslant0$

Собственно вот таким образом возникают моментные условия в двойственной задаче: $\int\limits_{}^{} \left\lbrace \begin{bmatrix} 1 \\ x \\ x^2 \end{bmatrix} \begin{bmatrix} 1 \\ x \\ x^2 \end{bmatrix}^T \right\rbrace d\mu \geqslant 0, \int\limits_{}^{} \left\lbrace (4-x^2) \begin{bmatrix} 1 \\ x \end{bmatrix} \begin{bmatrix} 1 \\ x \end{bmatrix}^T \right\rbrace d\mu \geqslant 0$. Или: $\begin{bmatrix} 1&y_1 &y_2 \\y_1&y_2 &y_3\\y_2&y_3 &y_4\end{bmatrix} \geqslant 0, $\begin{bmatrix} 4-y_2&4y_1-y_3 \\4y_1-y_3&4y_2-y_4\end{bmatrix} \geqslant 0$

В общем многомерном случае с несколькими ограничениями в форме алгебраических равенств и неравенств все тоже самое... Берется положительный полином в форме Путинара, и все то же самое с ним проделывается... Вернее, уже проделано товарищем J.B. Lasserre (двойственную сторону проблемы именно он и развивал) и выработан соотв. формализм.

[Alex Krylov]

И вот как приведенный выше "игрушечный" примерчик выглядит в Matlab:

Цитата:

Требования (должны быть установлены):
Matlab,
YALMIP (свободно распространяемый парсер для решения оптимизационных задач),
любой SDP-решатель, поддерживаемый YALMIP (напр. свободно распространяемые: SeDuMi, SDPT3; проприетарный (с бесплатной академической лицензией): MOSEK)

Используется синтаксис Matlab M

d = 2;%Уровень релаксации в рамках иерархии релаксаций Lasserre
x = sdpvar;%Определяем переменную

v1 = monolist(x,d-1);%Мономы вплоть до степени d-1 включительно
v2 = monolist(x,d);%Мономы вплоть до степени d включительно

obj = x^4-2*x^2+3;%Целевая функция

M = v2*v2';%Матрица моментов
M_loc = (4-x^2)*(v1*v1');%Локализующая матрица (в терминологии Lasserre)

constr = [M>=0, M_loc>=0];%Полуопределенные ограничения
ops = sdpsettings('relax',3);%Трактовать все нелинейности как отдельные переменные, т.е. [x,x^2,x^3,x^4] => [y1 y2,y3,y4]

optimize(constr,obj,ops);%Запуск процедуры оптимизации

format('short');
relaxvalue(obj) %Значение целевой функции после оптимизации
M_ = relaxvalue(M)%Матрица моментов после оптимизации
format('long');
eig(M_(1:2,1:2))%Смотрим ранг
eig(M_)%матрицы моментов и ее подматрицы
%Видим, что rank(M_[1:2,1:2])=rank(M_[1:3,1:3])=2.Это и есть то самое ранговое условие, говорящее нам о том, 
%что для данной совокупности моментов существует атомарная мера.

%Экстрагируем решения (т.е. атомы)
opts.SYM = true;
Mx = linsolve(M_(1:2,1:2), M_(1:2,2:3),opts);%Матрица умножнения
eig(Mx)%Её собственные числа суть искомые решения, т.е. атомы атомарной меры

[Doctor Boom]

Неориентируемые многообразия)

[мат-ламер]

Doctor Boom в сообщении #1596058 писал(а):

Неориентируемые многообразия)

Мне понравилась следующая задача. Что будет, если разрезать ленту Мёбиуса вдоль средней линии? Так в уме (не прибегая к эксперименту) я её решить тогда не смог. Видимо слабо геометрическое воображение.

[Doctor Boom]

мат-ламер
Получится все та же лента Мебиуса?

-- 01.06.2023, 19:45 --

Ой нет, кольцо обычное получится