Pull to refresh

Comments 25

1-го января днем и такую тему? :) А по теме — не пробовали нейронными сетями это как-то реализовать? С обучением на данных за последние лет 10.
Тема для того, чтобы разбудить народ после праздника=).
А вообще, нормальные люди наверное так и делают. Но мне почему-то кажется, что тут уместно сравнение с алгоритмами, один из которых находит корни квадратного уравнения точно, а другой — делением отрезка пополам. Первое более математично, второе более практично, уж извините, склад ума такой.
Я это к тому, что создать абсолютную математическую модель это сравнимо решению гипотезы римана по сложности.
Не, не, не. Не хочу дискутировать на эту тему). Вообще говоря, противоречивость математики не доказана, даже доказано, что это невозможно доказать! Сейчас вот найдут противоречие и получится, что гипотеза Римана тривиально следует оттуда.
Возможно, но тем не менее рынок акций во многом зависит от человеческого фактора, который заложить в модель довольно проблематично. Модель должна иметь представление обо всех процессах происходящих в мире, чтобы предугадывать форс-мажоры в виде того же «пузыря доткомов», кризисов всяких (кого затронет и в какой степени) и т.д.
Мне кажется, что мы говорим немного о разном. Я говорю о таком: «Вложил деньги в акции на 5-10 лет». Т.е. для кратковременных действий моя последняя глава совершенно не применима.
Так, конечно, это нужно делать нейронными сетями. Так это и делают, вообще говоря. У крупных компаний целые отделы программистов для этого есть.
Долгосрочные перспективы оценивать еще сложнее, чем краткосрочные. Вы не можете оценить политическую обстановку на 5-10 лет вперед. Например вкладываем в гуглъ, а через три года его блокируют скажем в 5 крупных странах — акции резко в минус. В общем использование только математики не даст нужного профита, нужно комбинировано подходить к вопросу. Изучать исторические данные, оценивать влияние людей и много другого. Одним уравнением, даже в многомерном пространстве тут не обойтись.
Мне кажется, это задача из области «найти объект, круглый и квадратный одновременно». Вероятно, какие-то мизерные доли процента прибыли с помощью такого алгоритма можно заработать, но не более того.

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

Цена акции устанавливается не от балды персонально кем-то, а быстренько корректируется рынком как раз исходя из доходности и рисковости. По сути те параметры (доходность / риск / цена), которые мы видим в таблицах — это не исходные числа, в которых можно найти «дырку» и заработать на разнице между идеальной ценой и реальной, а уже итоговые данные, полученные по сути выполнением многошагового алгоритма на основе нейросетей :)
компакт, задаваемый вот так x1 + x2 +… + xN = 1, x1 > 0, ..., xN > 0
Какой же это компакт?

Рассмотрим двумерный случай, N=2:
x1 + x2 = 1,
x1 > 0,
x2 > 0
Обозначим множество подходящих пар (x1, x2) за X.

Рассмотрим последовательность yn = (1/n, 1-1/n). Очевидно, что для любого натурального n соответствующее yn принадлежит нашему множеству X. В пределе же мы получим y = (0, 1), который не принадлежит нашему множеству. Значит, X не замкнуто.
Упс, спасибо, конечно там >= 0, сейчас исправлю. Доля акций компании вполне может быть равна 0, т.е. мы не выбираем эту компанию.
И как же метод множителей Лагранжа позволит решить задачу эффективно? У вас в любом случае будет куча условий вида "(x_i=0 и lambda_i>=0) или lambda_i=0". Когда раскроете систему — получится 2^100 линейных систем. Меньше, чем 100!, но времени всё равно не хватит, каждый симплекс границы придётся проверять отдельно. Наверное, для многочлена 2-й степени можно найти особый подход (привести его к каноническому виду как квадратичную форму и т.д.), но это уже не для 1 января :)
Да, была идея рассматривать как квадратичную форму.
Нет, там всего порядка N уравнений получается.
N линейных уравнений? Или большинство вида x_i*l_i=0?
Одно — многочлен, на котором нужно искать максимум. Одно — сумма всех x_i равна 0. Еще N штук, что каждое x_i >= 0. И того не так уж много.
Возьмём такой пример. N=6, симплекс x1+x2+...+x6=1, xi>=0. Ищем минимум многочлена (x1+x2+x3-x4-x5-x6)^2-eps*(x1^2+x2^2+...+x6^2), где eps>0 достаточно мало. Очевидно, что этот минимум будет достигаться где-то вблизи сечения симплекса гиперплоскостью x1+x2+x3=x4+x5+x6 (чтобы минимизировать первое слагаемое), причем как можно дальше от центра этого сечения, чтобы максимизировать сумму квадратов координат. То есть, вблизи вершин сечения.
Сечение симплекса этой гиперплоскостью является так называемой 3,3-дуопризмой. Это 4-мерный многогранник, который является декартовым произведением двух перпендикулярных треугольников, его грани — 6 треугольных призм, а вершин у него 9=(6/2)^2. В окрестности этих девяти вершин и лежат локальные минимумы нашего многочлена. В терминах исходного симплекса — это окрестности середин ребер (точек (1/2,0,0,1/2,0,0), (1/2,0,0,0,1/2,0),...,(0,0,1/2,0,0,1/2)). И для выяснения, какой минимум будет глобальным, придётся найти и проверить все эти точки.
Если N=100, то подозрительных точек будет уже 2500. И я думаю, что можно подобрать многочлен, который давал бы минимумы на симплексах границы, размерность которых еще ближе к N/2, а значит, и число их гораздо больше (в силу симметрии). В голову приходит P=(x1+x2-x3-x4)^2+(x5+x6-x7-x8)^2+...+(x97+x98-x99-x100)^2-eps*(x1^2+x2^2+...+x100^2), предполагаемое число локальных минимумов — 2^50 (но это надо проверять). Так что исходная оценка сложности в N! могла быть не так уж далека от истины.
Если нам надо искать максимумы многочлена — просто поменяем его знак, картина от этого не изменится.
Утверждение. Есть оптимальные методы нахождения максимума на подобных симплексах, не проверяя границы. Я тоже сначала не верил.
Удалось найти работу Ю.Нестерова про поиск экстремума квадратичной функции на симплексе с какой-то погрешностью. Пока не разобрался, но может оказаться интересно.
С многочленом P я ошибся — у него только 1200 минимумов. Правильный ответ это Q=(x1^2+x2^2+...+x100^2)+3*(x1*x2+x3*x4+x5*x6+...+x99*x100). Нетрудно доказать, что его минимальное значение, равное 1/50, достигается ровно в 2^50 точках (олимпиадная задача для 10-го класса). Можно подобрать многочлен, у которого будет еще больше минимумов — 4*(3^32) (дальше фантазия отказывает), но это уже не важно, и так ясно, что задача имеет экспоненциальную сложность. И что надо искать эвристики.
Проблема существования решения и наличия эффективной стратегии поиска решения — две разные, практически слабокоррелирующие задачи.

Во-первых, не всегда существование решения означает принципиальную возможность его получить.
Принципиальные проблемы начинаются, если допускаются принципы по типу двойного отрицания. Для примера: можно показать, что для любого утверждения F существует такое число x, которое равно единице, если F истинно, и нулю в противном случае; кроме того, можно F выбрать таким образом, что x существует, но значение мы принципиально посчитать не можем. Избитый пример F=«числовая прямая R суть меншее по мощности из несчётных множеств».
Как следствие, мы можем говорить, в частности, что существует решение уравнения 100500-й степени, даже сами не зная, как его получить. А иногда не знаем не потому, что ещё метод не придумали, а потому что принципиально не можем знать (см. пример выше)

К счастью, эту проблему можно исключить, но для этого нужно отказаться от таких уютных принципов, как доказательство от противного и иже с ними. Примером такой неклассической теории служит конструктивизм, где утверждение «существует x, что ...» означает «уже описан алгоритм для нахождения x, что ...».

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

Математика не ставит цель решить задачу «оптимальным» доказательством, её цель — уменьшить размер доказательства и сделать его интуитивно понятным.
Ничего себе слабокореллирующие! Между прочим, если вы найдете стратегию поиска решения, то это автоматически значит, что оно существует.
Для квадратного уравнения есть эффективный (школьный) алгоритм поиска решения в действительных числах.
Но он может дать «решения не существует».
Это значит, что найден не алгоритм решения, а алгоритм решения, если оно существует и детекции нерешимости в противном случае.
Часто бывает так, что найти эффективное решение задачи — это подобрать формулировку задачи, дающую резуьтат, практически неотличимый от результата исходной задачи, но которую можно решить эффективно. Например, решать уравнение с точностью до epsilon. И в этом случае, несмотря на то, что мы нашли «эффективное решение» задачи, в математическом смысле решения (или алгоритма нахождения решения) может не быть вообще.
Да, пожалуй неточно выразил мысль. Действительно, если будет найдена любая (в частности, эффективная) стратегия поиска, то решение существует. Однако по своему качеству задачи «определить, есть ли решение» и «за кратчайшее время определить решение» существенно разные. Как правило, необходимость ответить на первый вопрос встаёт сразу, как формулируется проблема. Это своеобразный билет на корректность. Если ответ положительный, то второй вопрос корректен, посему уже тогда имеет смысл пытаться его решить.

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

Опять же, разные бывают задачи. Какие-то просто необходимо уметь решать с любой наперед заданной точностью, другие — нет. И здесь мы первый вопрос задаём «а есть ли решение вообще», а потом уже, по острой надобности, «как найти решение» и «как найти его оптимально».

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

P.P.S. что ж за наваждение такое-то: я ответил на сообщение Monnoroch, который ответил на мое сообщение выше. Не судите строго за нарушение иерархии сообщений )
Оценить риски для компаний я думаю посложнее (с учетом той информации, которой обладает рядовой игрок на бирже), чем по сути найти минимум конкретного функционала.
Only those users with full accounts are able to leave comments. Log in, please.