Введение в робастную оптимизацию07.02.2019 23:49

Как определить, сколько людей нужно нанять на новый fulfillment, чем именно его заполнить и куда положить конкретный товар? Чем больше становится бизнес, тем выше неопределенность и тем дороже стоит ошибка. Победить хаос и выбрать оптимальное решение — одна из задач команды data science. А поскольку в основе анализа данных — математика, с нее и начнём.

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

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

И это пример поста, где сложность растет экспоненциально.

Что значит «решить» задачу оптимизации?

Давайте начнем с краткого напоминания.

Задача оптимизации в общем виде выглядит так:

$\min_{x \in R^n} f(x)\\ s.t.\\ x \in X$

Здесь $f(x)$ называется целевой функцией, а $X$ — допустимым множеством.

Под решением задачи оптимизации подразумевают такую точку $x^* \in X$ , для которой выполнено:

$f(x) - f(x^*) \geq 0, \quad \forall x\in X$

Это стандартный концепт решения задачи оптимизации без неопределенности.

Что такое задача оптимизации с неопределенностью?

Пришло время задаться вопросом о происхождении функции $f(x)$ и ограничения $X$ .

Очень полезно разделять

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

Вот, например, пришел к нам человек из бизнеса и показал задачу линейного программирования:

$\min_{x \in R^2} 2.16 x_1+3.7 x_2\\ s.t.\\ 0.973 x_1+2.619 x_2\leq 3.32\\ x_1 \geq 0, x_2 \geq 0$

Вы видите эту задачу впервые. Человека тоже (может быть и нет, но в синих пиджаках все такие абстрактные!). Смысл переменных вы не знаете. Но даже сейчас можно с большой долей уверенности сказать, что:

Скорее всего задача линейная, потому что кто-то так решил. Линейность — это структура, которую выбрал человек.
Ограничения $x_1 \geq 0, x_2\geq 0$ являются техническими. То есть они пришли из «физики», а не из данных (например, продажи не могут быть отрицательными).
Конкретные значения коэффициентов $\{0.973, 2.619, 3.32\}$ в ограничении $0.973 x_1+2.619 x_2\leq 3.32$ в нашем примере были оценены из данных. То есть сначала кто-то сказал, что переменная связана с переменной , потом было сказано, что связь — линейная, и, наконец, коэффициенты в уравнении связи были оценены из данных. То же самое верно и про коэффициенты $\{2.16, 3.7\}$ в целевой функции.

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

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

Иногда для нас этого достаточно, и мы ее просто решаем.

Однако иногда решать задачку для одного сценария — дурацкая идея (например, если решение очень чувствительно к вариации данных).

Что делать в этом случае, и как моделировать неопределенность в данных?

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

Перенос неопределенности из целевой функции в ограничения или наоборот

Часто оказывается удобнее перенести всю неопределенность в одну часть задачи: целевую функцию или ограничения.

Перенос неопределенности из целевого функционала в ограничения

Для любой задачи оптимизации

$\min_{x \in R^n} f_0(x, w)\\ s.t.\\ f_i(x, \theta^i) \leq 0, \quad 1\leq i \leq k\\ h_i(x, \beta^i) = 0, \quad 1\leq i\leq m\\ x \in X$

можно построить эквивалентную без неопределенности в целевом функционале:

$\min_{x \in R^n, t \in R} t\\ s.t.\\ f_0(x, w) \leq t\\ f_i(x, \theta^i) \leq 0, \quad 1\leq i \leq k\\ h_i(x, \beta^i) = 0, \quad 1\leq i\leq m\\ x \in X$

Решение $(x^*, t^*)$ эквивалентной задачи содержит решение исходной $x^*$ .

Перенос неопределенности из ограничений в целевой функционал

Формально для любой задачи оптимизации с ограничениями

$\min_{x \in R^n} f(x)\\ s.t.\\ x \in X$

можно построить эквивалентную задачу без ограничений

$\min_{x \in R^n} f(x) + I_X(x)$

с помощью индикаторной функции

$I_X(x) = \begin{cases} 0, \quad x\in X\\ +\infty, \quad x\notin X \end{cases}$

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

Стохастическая, онлайн, робастная оптимизация и список продуктов

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

Не знаю, как ситуация обстоит у уважаемого читателя, но вот я женат (удачно) и периодически хожу в магазин за продуктами. С листочком, конечно (дает неуязвимость от импульсивных покупок). Иногда не просто в магазин, а в условный «Ашан», где дешевле, но куда далеко ехать.

Вот эту ситуацию мы и смоделируем: мы пришли в «Ашан» с листочком в руках за покупками.

Внимание, первый вопрос: как моделировать?

Входные данные: информация о продуктах для покупки и требуемом количестве.

Для удобства можем думать о листочке как о некотором целочисленном неотрицательном векторе $y \in Z_+^n$ .

В качестве переменных возьмем, соответственно, целочисленный неотрицательный вектор $x \in Z_+^n$ — сколько и каких продуктов мы в итоге купим (наше решение).

Дело за малым — взять какую-то целевую функцию $f(x,y)$ , которая говорит насколько сильно мы ошиблись с выбором продуктов.

В зависимости от контекста вид функции может меняться, но к ней есть некоторые базовые требования:

Таким образом получим задачу:

$min_{x\in R^n} f(x,y)$

А теперь представим, что листочек остался дома…

Вот так, одной ремаркой мы и попали в мир задач с неопределенностью.

Итак, что делать, если в задаче $min_{x\in R^n} f(x,y)$ нам неизвестен $y$ ?

Ответ, опять же, зависит от контекста.

Стохастическая оптимизация

Стохастическая оптимизация (обычно) предполагает

Неопределенность в данных имеет именно стохастическую природу. Полное знание о вероятностном распределении значений недетерминированных параметров
Ограничения, включающие неопределенность, являются мягкими

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

Окей, я не знаю, что было написано в листочке, но я же хожу с листочками уже 8 лет, и у меня есть достаточно хорошее знание о распределении вектора
Даже если я ошибусь с выбором (то есть с ), вернувшись домой я узнаю настоящий и, если совсем припрет, спущусь в «Пятерочку» и дозакуплюсь там, пусть и дороже.
Сейчас же я выберу такой , который будет минимизировать какой-то агрегат от исходной целевой функции и возможных «штрафов» за ошибку.

Это приведет нас к такой задаче:

$\min_{x \in R^n} E_y [f(x, y) + \psi (y, z)]\\ s.t.\\ x+z \geq y$

Заметим, что в этой задаче у нас де-факто решения принимаются два раза: сначала основное решение о покупке в «Ашане», за которое отвечает $x$ , потом «исправление ошибок» с помощью $z$ .

Основные проблемы этого подхода:

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

Онлайн-оптимизация

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

В контексте нашего игрушечного примера, мы бы:

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

Робастная оптимизация

Робастная оптимизация — это логическое расширение идеи минимаксного решения.

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

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

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

$\min_{x \in R^n, t\in R} t\\ s.t.\\ f(x,y) \leq t \quad \forall y\\ x\geq y\quad \forall y$

Понятно, что даже в этом игрушечном примере, если ничего не потребовать от $y$ , то никакого осмысленного решения не получится.

Так как же правильно работать с такими задачами?

Построение робастной версии задачи на примере задачи LP

Рассмотрим линейную задачу оптимизации с неопределенностью:

$\min_{x \in R^n} c^Tx + d\\ s.t.\\ Ax \leq b$

Параметры $\begin{pmatrix} c^T, d\\ A, b \end{pmatrix}$ были получены из данных и включают неопределенность.

Предположение 1: Множество значений (реализаций) $\begin{pmatrix} c^T, d\\ A, b \end{pmatrix}$ может быть параметризовано, т.е. существуют такие $\begin{pmatrix} c_0^T, d_0\\ A_0, b_0 \end{pmatrix}, \begin{pmatrix} c_1^T, d_1\\ A_1, b_1 \end{pmatrix}, \dots, \begin{pmatrix} c_k^T, d_k\\ A_k, b_k \end{pmatrix}$ , что любая реализация данных $\begin{pmatrix} c^T, d\\ A, b \end{pmatrix}$ лежит в множестве:

$\begin{pmatrix} c^T, d\\ A, b \end{pmatrix} \in U = \left \{\begin{pmatrix} c_0^T, d_0\\ A_0, b_0 \end{pmatrix} +\sum_{i=1}^k\zeta_i \begin{pmatrix} c_i^T, d_i\\ A_i, b_i \end{pmatrix} | \quad \zeta \in Q \subset R^k \right \}$

Здесь $\begin{pmatrix} c^T_0, d_0\\ A_0, b_0 \end{pmatrix}$ называются «номинальными» данными, а $\begin{pmatrix} c^T_i, d_i\\ A_i, b_i \end{pmatrix} \quad (1\leq i \leq k)$ — «сдвигами».

Мини-пример

Мы уже знаем, что всю неопределенность в задаче можно убрать в ограничения. Сделаем это.

Получим задачу

$\min_{x\in R^n, t\in R}t\\ s.t.\\ c^Tx + d \leq t, \quad \forall \begin{pmatrix} c^T, d \end{pmatrix} \in U\\ Ax\leq b, \quad \forall \begin{pmatrix} A, b \end{pmatrix} \in U\\$

Робастная версия задачи

Теперь настало время для одного из самых прикольных трюков в робастной оптимизации — как от бесконечного числа ограничений перейти к конечному набору хороших ограничений.

Для начала рассмотрим простой пример, когда

$Q = \{ \zeta \in R^k| \|\zeta\|_2 \leq 1 \}$

Все ограничения в системе

$c^Tx + d \leq t, \quad \forall \begin{pmatrix} c^T, d \end{pmatrix} \in U\\ Ax\leq b, \quad \forall \begin{pmatrix} A, b \end{pmatrix} \in U\\$

однотипны — это просто линейные неравенства. Научимся работать с одним — научимся работать со всеми.

Поэтому рассмотрим одно ограничение типа неравенства:

$a^Tx \leq b\quad \forall (a,b) \in U = \{ (a_0, b_0)+\sum_{i=1}^k \zeta_i \cdot (a_i, b_i)| \quad \zeta \in Q \}\\ (a_0+ \sum_{i=1}^k \zeta_i a_i)^Tx \leq b_0 + \sum_{i=1}^k \zeta_i b_i \quad \forall \zeta \in Q\\ \sum_{i=1}^k \zeta_i \cdot (a_i^T x - b_i) \leq b_0 - a_0^Tx \quad \forall \zeta \in Q\\ \max_{\zeta \in Q} \sum_{i=1}^k \zeta_i \cdot (a_i^T x - b_i) \leq b_0 - a_0^Tx$

Поясню, что произошло.

Сначала мы перенесли все части с неопределенностью в левую часть неравенства, за неопределенность отвечает $\zeta$ .
После этого мы посмотрели на худший случай (для каждого $x$ он свой).
В итоге у нас получилась следущая запись:

$g(x) = max_{\zeta \in Q} f(x, \zeta) \leq b_0 - a_0^Tx$

.

Следущий шаг — выписать явно функцию $g(x)$ . Для этого достаточно решить задачу оптимизации по $\zeta$ и подставить оптимальные $\zeta *$ :

$\max_{\|\zeta\|_2 \leq 1} \sum_{i=1}^k \zeta_i (a_i^Tx- b_i) = \sqrt{\sum_{i=1}^k (a_i^Tx - b_i)^2}$

что приводит к неравенству:

$\sqrt{\sum_{i=1}^k (a_i^Tx-b_i)^2} +a_0^Tx \leq b_0$

Заметим, что полученное неравенство выпукло и любой $x$ ему удовлетворяющий удовлетворяет и исходному $a^Tx \leq b$ для любой реализации $(a,b) \in U$ …

Ограничение $\sqrt{\sum_{i=1}^k (a_i^Tx-b_i)^2} +a_0^Tx \leq b_0$ называется робастной версией ограничения $a^Tx \leq b \quad \forall (a,b) \in U$ .

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

Что делать с более сложными (нелинейными) ограничениями?

Построение робастных версий ограничений с помощью конической двойственности

Очень много стандартных нелинейных ограничений можно представить в коническом виде (то есть в виде $Ax + b \in K$ , где $K$ является некоторым замкнутым выпуклым конусом):

Неотрицательность $X \geq 0 \quad \leftrightarrow \quad x \in R^n_+$
Ограничения на нормы $\|x\|_p \leq p\quad \leftrightarrow \quad \begin{pmatrix} x\\p \end{pmatrix} \in K_p^n =\left \{ (x,t) \in R^n\times R_+ | \quad \|x\|_p \leq t \right \}$
Ограничения на положительную определенность матрицы $x_1F_1 + \dots x_nF_n + G \succeq 0$

Вернемся к робастным ограничениям.

Предположим, что задача оптимизации по $\zeta$ удалось свести к конической форме

$\max_{\zeta} \sum_{i=1}^k \zeta_i (a_i^Tx - b_i)\\ s.t\\ C\zeta + d \in K$

Построим для этой задачи двойственную.

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

$\min_{\lambda} \lambda^Td\\ s.t.\\ C^T \lambda +\begin{pmatrix} a_1^Tx - b_1\\ \dots\\ a_k^Tx - b_k \end{pmatrix} = 0_k\\ \lambda \in K^*$

Теперь дело за малым — теоремой о слабой двойственности:

$\max_{[\zeta: \quad C\zeta+d \in K]} \sum_{i=1}^k \zeta_i (a_i^Tx-b_i) \leq \min_{\lambda \in G} \lambda^Td\\ where\\ G = \left \{ \lambda| \quad C^T \lambda +\begin{pmatrix} a_1^Tx - b_1\\ \dots\\ a_k^Tx - b_k \end{pmatrix} = 0_k; \quad \lambda \in K^* \right \}$

Следовательно, в качестве робастной аппроксимации исходного ограничения $a^Tx \leq b, \quad (a,b) \in U$ можно использовать ограничение

$\lambda^Td \leq b_0 - a_0^Tx\\ G = \left \{ \lambda| \quad C^T \lambda +\begin{pmatrix} a_1^Tx - b_1\\ \dots\\ a_k^Tx - b_k \end{pmatrix} = 0_k; \quad \lambda \in K^* \right \}$

где $\lambda$ такая же переменная, как и $x$ .

Так мы построили робастное ограничение для исходного неравенства.

Заключение

Мы рассмотрели технику аппроксимации плохих (стохастических) ограничений набором хороших выпуклых. Это может пригодиться, например, в случае если:

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