Я уже писал о множествах здесь, здесь и здесь. Но, тем не менее, есть еще много что сказать про множества, и сегодня мы познакомимся с так называемым выпуклыми множествами. Что это такое, попытаюсь объяснить простыми словами. Посмотрите на эти фигуры:
В чем разница между красным и синим многоугольником (кроме цвета). Если вы сказали, что красный «выпуклый», а «синий» – нет, то поздравляю, вы абсолютно правы! Тад-а-ам!
Итак, если мы возьмем множество точек красной фигуры, то оно у нас будет выпуклым, а синей – не будет. В таком наглядном виде нам это кажется очевидным. Но математика – строгая наука, поэтому придется немного углубится в скучную теорию. Вот так определение выпуклых множество звучит по-научному: «Выпуклое множество в аффинном или векторном пространстве — множество, в котором все точки отрезка, образуемого любыми двумя точками данного множества, также принадлежат данному множеству».
В графическом виде это можно показать так:
Нетрудно догадаться, какие бы мы точки не взяли внутри красной фигуры, соединяющая их линия тоже будет внутри фигуры (чего не скажешь про синюю).
Предвижу вопрос: а для чего вообще подразделять множества на выпуклые или не выпуклые? А это нужно в задачах оптимизации. Есть даже целый раздел в математике, называемый выпуклое программирование, который как раз занимается оптимизацией выпуклых функций над выпуклыми множествами. Чем же отличаются такие задачи оптимизации от других задач оптимизации? Главное отличие, это то, что задача оптимизации выпуклых функций над выпуклыми множествами может быть решена алгоритмом, выполняемым в течение так называемого полиномиального времени, а в общем случае задача оптимизации является NP-трудной. Не пугайтесь, сейчас объясню значение этих терминов.
Для начала, давайте представим типичную задачу оптимизации. Если не помните, как она формулируется математическая, то можете заглянуть сюда: Математика для чайников. Глава 18. Методы математической оптимизации. А если помните, то вы сразу можете сказать, в чем проблема: в огромное число вариантов. Пусть у нас функция, которую мы хотим оптимизировать, имеет только один аргумент. Как мы найдем ее максимум или минимум? Будем вычислять все значения? Но если аргумент – вещественное число, то количество таких значений бесконечность, даже если у нас задан интервал, на котором нам надо найти этот самый оптимум. Можно, конечно, пройтись по этому интервалу с каким-то шагом. А если нам требуется большая точность, значит, и шаг должен быть маленьким. Но тогда количество шагов будет большим. А если аргументов несколько? Тогда нам надо будет все количества шагов для каждого аргумента перемножить. Например, у нас первый аргумент – это числа от 1 до 100. Их сто. А если таких аргументов 2, то всевозможных комбинаций, которые нам нужно обсчитать, будет уже 100*100=10’000.
А если аргументов 3, и более? Тогда у нас количество вариантов будет еще больше, 100^3 – это уже 1’000’000. Но степенная зависимость от количества параметров – это еще не самая большая проблема. Проблема может быть в том, что мы можем не знать, на каком диапазоне оптимизировать, и с какой точностью. Представьте, если надо перебрать диапазон от 0 до 1’000’000 с шагом 0.001. У нас будет миллиард вариантов только для одного параметра.
Теперь я объясню, что такое NP-трудная задача. Сначала определение: «NP-трудная задача – это класс задач, которые не менее сложны, чем самые сложные задачи в NP». Возникает вопрос: а что такое NP? Строгое определение гласит: «В теории алгоритмов классом NP (от англ. non-deterministic polynomial) называют множество задач разрешимости, решение которых возможно проверить на машине Тьюринга за время, не превосходящее значения некоторого многочлена от размера входных данных, при наличии некоторых дополнительных сведений». Может показаться непонятным. Тогда объясню простыми словами:
Представь, что ты - блондинка, и тебе нужно выбрать платье на вечеринку. Ты хочешь выбрать самое красивое платье, но у тебя всего час на поиски.
NP-трудная задача – это как поиск идеального платья.
• NP – это «недетерминированный полиномиальный».
• «Недетерминированный» означает, что ты можешь просто попробовать все платья одновременно (в мире фантазий).
• «Полиномиальный» означает, что время, которое ты тратишь на проверку каждого платья, растет не слишком быстро (например, если ты проверяешь 10 платьев, ты потратишь в 10 раз больше времени, чем если бы проверяла 1 платье).
Но проблема в том, что у тебя только час. Ты не можешь попробовать все платья! NP-трудная задача - это задача, для которой нет простого способа найти самое лучшее решение за разумное время. Ты можешь просто пробовать платья по одному, но ты не сможешь гарантировать, что найдешь самое красивое.
Например:
• Найти самый короткий путь между двумя городами: Ты можешь просто пробовать разные дороги, но ты не сможешь гарантировать, что найдешь самый короткий путь.
• Расставить королев на шахматной доске так, чтобы они не били друг друга: Ты можешь просто пробовать разные расстановки, но ты не сможешь гарантировать, что найдешь правильную.
И так, NP-трудные задачи – это как поиск идеального платья: можно пробовать разные варианты, но нет гарантии, что ты найдешь самое лучшее решение за разумное время.
В общем, применительно к нашей теме, мы можем сказать, что искать оптимум тупым перебором не вариант. Как быть? Если у нас имеется случай, когда нужно оптимизировать выпуклую функцию на выпуклых множествах, то мы можем уже использовать не тупой перебор, а специальный быстрый алгоритм, который работает как раз в таких случаях. Если у нас не такая задача, то тут надо думать: или преобразовать ее в задачу оптимизации на выпуклых множествах, либо использовать другой метод, они есть, правда, работают тоже в определенных конкретных случаях, так что тут надо смотреть, выбирать. Но мы пока рассматриваем выпуклые множества, так что, поехали дальше.
Примером выпуклых множество в двумерном пространстве могут служить правильные многоугольники, а в трехмерном – правильные многогранники. Выпуклыми так же являются все пространство и пустое множество.
Если мы будем рассматривать выпуклые множества в контексте задачи оптимизации, то будет полезным изучить другое определение выпуклости множества: Пусть U – вещественное векторное пространство Q – подмножество U. Множество Q называется выпуклым, если для любых двух точек x, y из множества Q и любого λ ∈ [0, 1] точка λx + (1 − λ)y также принадлежит множеству Q.
Давайте рассмотрим пример. Допустим, у нас есть график функции y=5-x^2:
Отменим на ней точку (-1;2):
Пусть у нас λ=0.5, тогда мы получаем новую точку λx + (1 − λ)y, равную (-0.5;1):
Возьмем λ=0.1, это будет точка (-0.1;1.8):
Для λ=0.9, это будет точка (-0.9;0.2):
Как видим, если точка лежит ниже графика функции, то при применении данного правила она и будет лежать ниже. А если на пересечении? Например, точка (-1;4):
Давайте проверим. Возьмем λ=0.1, это будет точка (-0.1;3.6):
Как видим из примеров, точка по условию λx + (1 − λ)y лежит ниже графика.
Такая функция называется выпуклой. Если говорить строго математически, то выпуклая функция – это такая функция, надграфик или подграфик которой является выпуклым множеством.
Надграфиком функции называют множество точек, которые лежат над ее графиком. Визуально это выглядит вот так:
Подграфик – это с точностью до наоборот, множество точек под графиком.
Функция может быть выпуклой вниз, или выпуклой вверх. В случае, если функция выпукла вниз, любой отрезок между любыми двумя точками лежит не ниже соответствующей дуги графика. В нашем примере все наоборот, любой отрезок лежит не выше, поэтому она выпукла вверх:
Тут следует еще вот что заметить. Помимо терминов «выпукла вниз» и «выпукла вверх» существуют еще термины «выпуклая» и «вогнутая» функция. Но тут есть путаница. В частности, одни авторы называют вогнутой выпуклую вверх функцию, а выпуклую вниз – просто выпуклой, так как считают, что раз мы определяем выпуклость функции по надграфику, именно выпуклая вниз функция и образует то самое выпуклое множество. Другие авторы выпуклую вниз функцию наоборот, называют вогнутой, так как ее график на картинке смотрится «вогнуто». Дабы избежать этой путаницы, все-таки лучше использовать термины «выпукла вниз» и «выпукла вверх».
Но как же практически определить, является ли функция выпуклой вниз или выпуклой вверх?
Существует два основных подхода: по определению (геометрический) и с использованием производных (аналитический).
Геометрическое определение (через хорды).
Функция f(x) называется выпуклой вниз (в старой терминологии часто просто «выпуклой»), если для любых двух точек x1 и x2 из ее области определения, хорда, соединяющая точки (x1, f(x1)) и (x2, f(x2)) на графике, лежит выше или на самом графике функции на интервале [x1, x2]. Геометрически это означает, что график функции на этом интервале «открыт» вверх, как чаша.
Соответственно, функция f(x) называется выпуклой вверх (в старой терминологии часто «вогнутой»), если для любых x1 и x2 хорда, соединяющая эти точки на графике, лежит ниже или на самом графике функции на интервале [x1, x2]. Ее график «открыт» вниз, как перевернутая чаша.
Определение с помощью второй производной (наиболее практичный способ):
Для функций, которые дважды дифференцируемы на некотором интервале, характер выпуклости можно легко определить с помощью знака их второй производной:
Если на некотором интервале вторая производная функции f(x) положительна (f''(x) > 0), то функция на этом интервале является выпуклой вниз. Это логично, поскольку положительная вторая производная означает, что первая производная (скорость изменения наклона касательной) возрастает. То есть, наклон касательной становится все круче, что и формирует график, «открытый» вверх.
И наоборот, если на некотором интервале вторая производная функции f(x) отрицательна (f''(x) < 0), то функция на этом интервале является выпуклой вверх. В этом случае первая производная убывает, и наклон касательной становится менее крутым или даже меняет знак, изгибая график вниз.
Точки, в которых вторая производная равна нулю (f''(x) = 0) или не существует, и при переходе через которые вторая производная меняет свой знак, называются точками перегиба функции. В этих точках функция меняет характер своей выпуклости – например, переходит из выпуклой вниз в выпуклую вверх, или наоборот.
Таким образом, анализ знака второй производной является наиболее надежным и широко используемым методом для исследования выпуклости функции в математическом анализе.
Рассмотрим все это на примере параболы, потому что это можно свести к физике. Именно по параболе летит камень, брошенный под углом к горизонту (если пренебречь сопротивление воздуха, разумеется). Почему по параболе? Потому что если разложить его скорость на горизонтальную и вертикальную, то горизонтальная скорость будет равномерной, а по вертикали камень будет двигаться равнозамедленно. Таким образом, в единицу времени по горизонтали будет проходить одно и тоже расстояние, как бы отмеряя время. Иными словами, горизонтальную ось мы можем считать как бы осью времени. Тогда высота – это функция от времени, квадратичная функцию, которая есть парабола:
Производная параболы – линейная функция, вторая производная – константа. В данной формуле это ускорение. Так как оно направлено вниз, то его знак – «минус», парабола выпукла вверх.
Итак, подытожим. Мы познакомились с понятием выпуклых множеств и выпуклых функций. Эти понятия можно применить в задачах оптимизации, до них мы еще дойдем.