Выпуклость

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

Определение и основные понятия

Формально, множество \( S \) в евклидовом пространстве \(\mathbb{R}^n\) называется выпуклым, если для любых двух точек \( x, y \in S \) и любого числа \( t \in [0, 1] \) точка \( (1-t)x + ty \) также принадлежит \( S \). Это условие означает, что весь отрезок между \( x \) и \( y \) лежит внутри множества. Для невыпуклых множеств существует хотя бы одна пара точек, отрезок между которыми частично выходит за пределы множества.

Понятие выпуклости тесно связано с понятием выпуклой оболочки — наименьшего выпуклого множества, содержащего данное множество. Выпуклая оболочка конечного набора точек в \(\mathbb{R}^n\) представляет собой выпуклый многогранник (симплекс или полиэдр).

Выпуклость в геометрии

Выпуклые фигуры на плоскости

На плоскости к выпуклым фигурам относятся:

• Выпуклые многоугольники — все внутренние углы которых меньше 180° (например, треугольник, квадрат, правильный пятиугольник). Любой отрезок, соединяющий две точки такого многоугольника, лежит внутри него.
• Окружность и круг — круг является выпуклым множеством, так как любая хорда лежит внутри круга.
• Эллипс — выпуклая замкнутая кривая.
• Парабола и гипербола — их ветви не являются выпуклыми множествами в целом, но отдельные дуги могут быть выпуклыми.

Невыпуклые фигуры: звездчатые многоугольники, серповидные фигуры, многоугольники с вогнутыми углами (например, пятиконечная звезда).

Выпуклые тела в пространстве

В трёхмерном пространстве выпуклыми телами являются:

• Выпуклые многогранники — все грани которых являются выпуклыми многоугольниками, а сам многогранник не имеет вогнутостей (куб, тетраэдр, октаэдр, додекаэдр, икосаэдр).
• Шар — множество точек, расстояние от которых до центра не превышает заданного радиуса; является выпуклым.
• Эллипсоид — выпуклое тело.
• Цилиндр и конус — являются выпуклыми, если рассматривать их как замкнутые множества (включая основания).

Выпуклость в математическом анализе

Выпуклые функции

Функция \( f(x) \), определённая на выпуклом множестве \( D \subset \mathbb{R}^n \), называется выпуклой, если для любых \( x, y \in D \) и \( t \in [0, 1] \) выполняется неравенство: \[ f((1-t)x + ty) \le (1-t)f(x) + tf(y) \] Геометрически это означает, что график функции лежит не выше хорды, соединяющей любые две его точки. Если неравенство строгое (\( < \)) для \( t \in (0, 1) \) и \( x \ne y \), функция называется строго выпуклой.

Свойства выпуклых функций:

• Локальный минимум выпуклой функции является глобальным минимумом.
• Множество точек, где выпуклая функция принимает значения не больше заданного, является выпуклым.
• Вторая производная (если существует) неотрицательна: \( f''(x) \ge 0 \) для одномерного случая.
• Выпуклые функции непрерывны на внутренности области определения.

Примеры выпуклых функций: \( f(x) = x^2 \), \( f(x) = e^x \), \( f(x) = -\ln x \) (на положительной полуоси), \( f(x) = |x| \).

Вогнутые функции

Функция \( f \) называется вогнутой, если \( -f \) является выпуклой. Для вогнутых функций выполняется обратное неравенство: \[ f((1-t)x + ty) \ge (1-t)f(x) + tf(y) \] Примеры: \( f(x) = \sqrt{x} \), \( f(x) = \ln x \), \( f(x) = -x^2 \).

Классификация выпуклости

По типу множества

• Выпуклое множество — как определено выше.
• Строго выпуклое множество — множество, в котором любая граничная точка является крайней (не может быть представлена как выпуклая комбинация других точек множества). Пример: шар, но не куб (у куба грани состоят из крайних точек, но рёбра — нет).
• Локально выпуклое множество — множество, у которого для каждой точки существует окрестность, пересечение которой с множеством выпукло.

По типу функции

• Выпуклая функция — удовлетворяет неравенству Йенсена.
• Строго выпуклая функция — неравенство строгое для различных точек.
• Квазивыпуклая функция — все её подуровневые множества \( \{x: f(x) \le \alpha\} \) выпуклы.
• Псевдовыпуклая функция — обобщение, используемое в оптимизации.

Выпуклость в оптимизации

Выпуклость играет ключевую роль в математическом программировании. Задача оптимизации называется выпуклой, если целевая функция выпукла (или вогнута для задачи максимизации), а допустимое множество выпукло. Для выпуклых задач любой локальный оптимум является глобальным, что существенно упрощает поиск решения.

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

Выпуклость в экономике

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

Функция полезности считается выпуклой (или вогнутой) в зависимости от отношения к риску: вогнутая функция полезности соответствует неприятию риска, выпуклая — склонности к риску.

Выпуклость в теории графов

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

Выпуклость в компьютерной графике

В компьютерной графике выпуклые многоугольники и многогранники используются для построения трёхмерных моделей. Алгоритмы отсечения (например, алгоритм Сазерленда — Ходжмана) работают эффективнее для выпуклых объектов, так как не требуют сложной обработки вогнутостей. Выпуклая оболочка набора точек применяется для коллизионного обнаружения, визуализации и упрощения геометрии.

Интересные факты

• В 1913 году немецкий математик Герман Минковский заложил основы теории выпуклых тел, введя понятие опорной функции и смешанных объёмов.
• Теорема Хелли (1913) утверждает, что если семейство выпуклых множеств в \(\mathbb{R}^n\) таково, что любые \( n+1 \) из них имеют общую точку, то все множества имеют общую точку.
• Выпуклость является одним из ключевых свойств в теории игр: в кооперативных играх выпуклые игры обладают непустым ядром.
• В природе выпуклые формы встречаются повсеместно: капли жидкости в невесомости принимают форму шара (выпуклое тело), мыльные пузыри стремятся к минимальной поверхности при заданном объёме, что часто приводит к выпуклым формам.
• В оптике выпуклые линзы собирают свет, а вогнутые — рассеивают; это свойство основано на геометрической выпуклости поверхностей.

Критика и ограничения

Понятие выпуклости, несмотря на свою плодотворность, имеет ограничения. Многие реальные задачи не являются выпуклыми, что требует использования методов глобальной оптимизации, эвристик или аппроксимаций. В экономике предположение о выпуклости предпочтений не всегда выполняется (например, при наличии товаров-заменителей). В геометрии существуют невыпуклые множества, обладающие интересными свойствами (например, фракталы), которые не поддаются анализу с помощью выпуклого анализа.

Источники

• Рокафеллар Р. Т. «Выпуклый анализ». — М.: Мир, 1973.
• Бойд С., Ванденберге Л. «Выпуклая оптимизация». — М.: Издательство МЦНМО, 2018.
• Александров А. Д. «Выпуклые многогранники». — М.: ГИТТЛ, 1950.
• Хорн Р., Джонсон Ч. «Матричный анализ». — М.: Мир, 1989 (раздел о выпуклых функциях от матриц).
• Шикин Е. В., Плис А. И. «Кривые и поверхности на экране компьютера». — М.: Диалог-МИФИ, 1996.
• Mas-Colell A., Whinston M. D., Green J. R. «Microeconomic Theory». — Oxford University Press, 1995.