Имеет решение и эффективно решается, в чем разница?

    Доброго времени суток, хабралюди! Частенько математики останавливаются на существовании решения, и получается что-то подобное.

    В гостинице поселились инженер, физик, и математик. У каждого в номере возникает пожар.
    Инженер выбегает в коридор, видит на стене пожарный шланг, хватает его, открывает воду, вбегает в номер и заливает очаг возгорания.
    Физик, быстро прикинув объем горючих веществ, температуру пламени, теплоемкость воды и пара, атмосферное давление и т.п., наливает в стакан из графина строго определенное количество воды и заливает огонь этой водой.
    Математик выскакивает в коридор, видит на стене огнетушитель, и, обрадованно воскликнув: “Решение существует!”, спокойно возвращается в номер.


    А о том, какие грабли попадаются на пути «до победного конца», я расскажу под катом.

    Воспоминания


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

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

    То есть задачи и правда часто возникают.

    Так что в них плохого?


    В задаче под номером 1 ничего плохого на данном этапе развития человечества нет. Можно сказать, что мы умеем ее достаточно эффективно решать. Уравнения степеней < 5 разрешимы в радикалах (т.е. можно найти точные значения корней). Доказано, что уравнения степеней > 4 не разрешимы в радикалах (а именно, приведены конкретные уравнения, которые нельзя решить), для этого используются группы Галуа. Но бывает так, что нам все-таки нужно найти корни уравнения, например 100-й степени. А вот это уже умеют решать алгоритмически, а именно — искать все корни со сколь угодно большой точностью. Если кто не верит — wolframalpha.com.

    Задача номер 2 чуточку интереснее. Вообще говоря, это следствие теоремы Тарского – Зайденберга. Доказательство ее простое, его можно рассказывать хоть школьникам, которые умеют брать производную многочлена и делить многочлены столбиком. Если вкратце и по-простому, то суть теоремы в том, что из любого выражения про многочлены в действительных числах можно убрать кванторы («существует х», «для любого х»).
    Например выражение: «существует х, что x^2 + px + q = 0». Т.е. у нас спрашивается, когда подобное квадратное уравнение имеет корни. Это мы знаем, когда p^2 — 4q >= 0 (заметим, что тут квантора уже нет!). Идея теоремы в том, что можно написать алгоритм, который за нас бы это выяснял, причем степень не важна.
    Как это связано с геометрией? А вот как, практически любое утверждение можно записать введя систему координат и навесив кучу кванторов. Идея в том, что когда мы «убиваем» квантор, у нас уходит одна переменная. А когда у нас не останется переменных, то мы получим выражение вида 5 > 3, об истинности которого мы уже все знаем.
    Пфф, так получается, что геометрия — тривиальная наука? Есть алгоритм, который бы выяснял: верно утверждение, или ложно. Наверное, так и подумали некоторые математики, но не все так просто. Если мы рассмотрим пример с x^2 + px + q = 0, то чтобы «убить» один квантор, нам понадобится достаточно большое количество шагов. А чтобы уже подобным способом доказать какую-то содержательную геометрическую теорему, понадобится время, сравнимое со временем существования Земли.
    Но может мы решаем как-то неправильно? На самом деле доказано, что нет эффективного алгоритма, решающего эту задачу.
    Ура, геометрия не тривиальна. Фух, разобрались. Едем дальше.

    Задача 3, как все было


    Тут расскажу маленькую предысторию. Вообще, математика — достаточно абстрактная наука, посему летом я решил позаниматься финансами и прошел онлайн курс на coursera.org. Там тщательно разбирались акции, что да как. Но преподаватель часто говорил, что тут всегда выбор, либо у тебя большой риск и большой доход, либо мальникй риск и низкий доход. Мне стало интересно, а есть ли золотая середина? Можно ли из N компаний выбрать акции так, чтобы у тебя был маленкий риск и большой доход? Неплохо бы еще написать алгоритм по решению этой задачи. Формулировка ясна, теперь детали.

    Человеку не сведующему в данном деле покажется, что у рисков зависимость линейная, у дохода линейная — и чего тут вообще решать? Как бы не так, риски считаются более хитрым способом, ибо компании друг с другом взаимосвязаны. Благо, что итоговый риск считается, как многочлен второй степени, но конечно же от N переменных, где N — число компаний.
    Окей, как теперь связать риски и доходы? Если риск например 5%, а доход 100$ это лучше, чем риск 10%, а доход 150$, или хуже? Грубо говоря, можно посчитать средний риск, например 10%, средний доход, например 200$ и приравнять 1 процент риска к 20$ (200 / 10). Эм, и что нам это дало? А вот что — пусть у нас есть N компаний. Долевые соотношения акций — x1, x2, ..., xN. Тогда риск считается как некоторый многочлен (каждый моном которого не больше второй степени), а доход считается линейно. Возьмем и вычтем одно уравнение из другого, домножив на поправочный коэффициент (Доход с "+", риск с "-"). Это и будет итоговая формула, у которой нужно найти максимум. Кстати у нас есть ограничение, что x1 + x2 +… + xN = 1, x1 >= 0, ..., xN >= 0.

    Теперь постараемся проанализировать задачку. Мне, как математику, в голову сразу пришла идея рассмотреть N-мерное пространство, там у нас есть компакт, задаваемый вот так x1 + x2 +… + xN = 1, x1 >= 0, ..., xN >= 0 и многочлен второй степени. Пфф, да все элементарно — подумал я. Мы знаем, что на компакте уравнение принимает наибольшее значение, причем либо градиент в этой точке нулевой, либо максимум лежит на границе, т.е. нужно проверить и то и то. С этими мыслями я откинул задачу где-то на месяц. Но что-то не оставляло в покое. Вот выдалось свободное время, было взято произвольное уравнение, бумага и ручка. Оппа — да мое решение работает за (N!) — факториал. Если его реализовать на компьютере, то для 100 компаний это будет работать много больше времени существования Солнечной системы. Краткие объяснения: когда мы проверяем границы компакта, мы переходим от N-мерного простарнства к N штукам (N-1)-мерных пространств. Ужасно — подумал я, но надежды решить задачу не потерял.

    Походив среди умных математиков и поспрашивая их, я узнал о методе множителей Лагрнажа для неравенств (мы проходили лишь для уравнений). И вот он как раз решает эту задачу эффективно. Можете почитать немного на википедии.

    Не останавливайтесь на существовании решения, а идите до конца. Удачи вам в новом году :)!
    Спасибо за прочтение!
    Share post
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 25

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

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

        Цена акции устанавливается не от балды персонально кем-то, а быстренько корректируется рынком как раз исходя из доходности и рисковости. По сути те параметры (доходность / риск / цена), которые мы видим в таблицах — это не исходные числа, в которых можно найти «дырку» и заработать на разнице между идеальной ценой и реальной, а уже итоговые данные, полученные по сути выполнением многошагового алгоритма на основе нейросетей :)
          +2
          компакт, задаваемый вот так 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, сейчас исправлю. Доля акций компании вполне может быть равна 0, т.е. мы не выбираем эту компанию.
            0
            И как же метод множителей Лагранжа позволит решить задачу эффективно? У вас в любом случае будет куча условий вида "(x_i=0 и lambda_i>=0) или lambda_i=0". Когда раскроете систему — получится 2^100 линейных систем. Меньше, чем 100!, но времени всё равно не хватит, каждый симплекс границы придётся проверять отдельно. Наверное, для многочлена 2-й степени можно найти особый подход (привести его к каноническому виду как квадратичную форму и т.д.), но это уже не для 1 января :)
              0
              Да, была идея рассматривать как квадратичную форму.
              Нет, там всего порядка N уравнений получается.
                0
                N линейных уравнений? Или большинство вида x_i*l_i=0?
                  0
                  Одно — многочлен, на котором нужно искать максимум. Одно — сумма всех x_i равна 0. Еще N штук, что каждое x_i >= 0. И того не так уж много.
                  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! могла быть не так уж далека от истины.
                  Если нам надо искать максимумы многочлена — просто поменяем его знак, картина от этого не изменится.
                    0
                    Утверждение. Есть оптимальные методы нахождения максимума на подобных симплексах, не проверяя границы. Я тоже сначала не верил.
                      0
                      Удалось найти работу Ю.Нестерова про поиск экстремума квадратичной функции на симплексе с какой-то погрешностью. Пока не разобрался, но может оказаться интересно.
                      0
                      С многочленом 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) (дальше фантазия отказывает), но это уже не важно, и так ясно, что задача имеет экспоненциальную сложность. И что надо искать эвристики.
                  +4
                  Проблема существования решения и наличия эффективной стратегии поиска решения — две разные, практически слабокоррелирующие задачи.

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

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

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

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

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

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

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

                        P.P.S. что ж за наваждение такое-то: я ответил на сообщение Monnoroch, который ответил на мое сообщение выше. Не судите строго за нарушение иерархии сообщений )
                          0
                          Оценить риски для компаний я думаю посложнее (с учетом той информации, которой обладает рядовой игрок на бирже), чем по сути найти минимум конкретного функционала.

                          Only users with full accounts can post comments. Log in, please.