В робастной оптимизации форма и структура множества неопределенности $U$ являются не просто технической деталью, а фундаментальным элементом моделирования. Выбор геометрии $U$ напрямую определяет как вычислительную сложность робастного аналога (robust counterpart), так и степень консерватизма принимаемых решений. Задача состоит в том, чтобы найти баланс: с одной стороны, множество должно адекватно описывать возможные реализации неопределенных параметров, а с другой — сохранять задачу решаемой на практике. Каждая форма множества предлагает свой компромисс между точностью моделирования и вычислительной сложностью робастного аналога.

Полиэдральные множества являются одним из наиболее распространенных выборов благодаря их способности сохранять класс задачи линейного программирования (LP). Простейший случай — интервальная неопределенность, где каждый параметр $a_i$ может принимать любое значение в заданном интервале [ar{a}_i - \triangle_i, ar{a}_i + \triangle_i] независимо от других. Такое множество представляет собой гиперпрямоугольник («box») и эквивалентно шару в норме $L_{\infty}$.

Робастный аналог для линейного ограничения $a^Tx \le b$ с таким множеством неопределенности остается линейным. Используя свойство двойственности норм, получаем:

Другим важным полиэдральным множеством является шар в норме $L_1$. Геометрически он представляет собой кросс-политоп. Это множество менее консервативно, чем интервальное, так как ограничивает сумму абсолютных отклонений, а не каждое отклонение по отдельности.

Робастный аналог для этого множества также использует двойственность норм, но теперь с $L_{\infty}$-нормой:

Когда существует корреляция между неопределенными параметрами, полиэдральные множества могут быть не лучшим выбором. Эллипсоидальные множества, основанные на норме $L_2$, позволяют учесть эту взаимосвязь.

Главный недостаток такого подхода — усложнение робастного аналога. Задача перестает быть линейной и переходит в класс задач программирования в конусах второго порядка (SOCP), что является более сложным, но все еще вычислительно трактуемым классом задач.

Гибридным подходом, сочетающим простоту полиэдральных множеств с меньшим консерватизмом, является бюджетная неопределенность, предложенная Берцимасом и Симом. Здесь предполагается, что не все параметры одновременно отклонятся до своих худших значений. Вводится «бюджет неопределенности» $\Gamma$, который ограничивает количество параметров, принимающих экстремальные значения.

Формально, для каждого параметра $a_i$ вводится случайная переменная $\zeta_i$, принимающая значения в интервале $[-1, 1]$. Бюджетное множество определяется как:

Несмотря на наличие $L_0$-нормы, которая обычно приводит к комбинаторной сложности, Берцимас и Сим показали, что робастный аналог для этого множества может быть сформулирован как эквивалентная LP-задача с помощью методов теории двойственности. Это делает данный подход мощным инструментом для практического применения.

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