Симплекс: определение и применение в оптимизации¶

Симплекс — в широком смысле, простейший геометрический объект в n-мерном пространстве, являющийся обобщением треугольника (n=2) и тетраэдра (n=3) на случай произвольной размерности. В математическом программировании термин чаще всего используется для обозначения симплекс-метода — итеративного алгоритма решения задач линейного программирования, разработанного американским математиком Джорджем Данцигом в 1947 году.

¶Определение и геометрическая сущность

Симплексом размерности n (или n-симплексом) называется выпуклая оболочка n+1 аффинно независимых точек в евклидовом пространстве. Аффинная независимость означает, что ни одна из точек не лежит в гиперплоскости размерности n-1, образованной остальными точками. Таким образом, 0-симплекс — точка, 1-симплекс — отрезок, 2-симплекс — треугольник, 3-симплекс — тетраэдр.

Каждый n-симплекс имеет n+1 вершин и n+1 граней, каждая из которых является (n-1)-симплексом. Например, тетраэдр имеет 4 треугольные грани, а треугольник — 3 отрезка-ребра. Симплексы являются фундаментальными объектами топологии и используются для построения симплициальных комплексов — способов триангуляции пространств.

¶Симплекс-метод в линейном программировании

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

¶Принцип работы алгоритма

Задача линейного программирования в стандартной форме записывается как максимизация функции c^T x при условиях Ax ≤ b и x ≥ 0. Множество допустимых решений образует выпуклый многогранник. Теорема линейного программирования утверждает, что если оптимум существует, то он достигается в одной из вершин этого многогранника.

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

¶Вычислительная сложность и модификации

В худшем случае симплекс-метод может потребовать экспоненциального числа итераций — пример Клее — Минти (1972) демонстрирует траекторию, проходящую через все 2^n вершин n-мерного гиперкуба. Однако на практике алгоритм демонстрирует высокую эффективность, обычно совершая O(m) итераций, где m — число ограничений. Средняя сложность оценивается как полиномиальная.

Существует ряд модификаций, улучшающих работу метода: двойственный симплекс-метод (для задач, начинающихся с недопустимой, но лучшей точки), revised симплекс-метод (работающий с обратной матрицей базиса для уменьшения объёма вычислений), метод с ограниченным вводом переменных для задач с большим числом переменных. В 1984 году Нарендра Кармаркар предложил полиномиальный метод внутренней точки, который для некоторых классов задач превосходит симплекс-метод, однако последний остаётся стандартом для большинства практических приложений.

¶Симплекс-метод Нелдера — Мида

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

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

¶Применение в других областях

¶Симплициальные комплексы в топологии

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

¶Симплекс-метод в статистике

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

¶Симплекс в теории вероятностей

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

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

• Название «симплекс» происходит от латинского simplex — «простой», «одинарный». Термин ввёл в употребление немецкий математик Герман Грассман в XIX веке.
• В 1984 году симплекс-метод был включён в список десяти алгоритмов, оказавших наибольшее влияние на развитие науки и техники в XX веке, составленный журналом Computing in Science & Engineering.
• Джордж Данциг разработал симплекс-метод в 1947 году, работая над задачами планирования для Военно-воздушных сил США. Согласно распространённой легенде, первые идеи метода пришли к нему во время размышлений о планировании продовольственного снабжения армии.
• Внутренняя точка любого симплекса может быть представлена как выпуклая комбинация его вершин с положительными коэффициентами, сумма которых равна единице — это свойство используется в симплекс-методе для представления текущего решения.

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

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