YuraDorn 7 фев 2019 в 21:51

Введение в робастную оптимизацию [… и маленький листочек со списком покупок, который я забыл...]

8 мин

5.9K

Блог компании Ozon TechМатематика*Машинное обучение*

Туториал

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

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

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

И да, это пример поста, где сложность растет экспоненциально (сорян уж)…

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

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

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

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

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

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

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

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

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

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

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

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

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

$\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$ в нашем примере были оценены из данных. То есть сначала кто-то сказал, что переменная $inline$ связана с переменной $inline$ , потом было сказано, что связь — линейная, и, наконец, коэффициенты в уравнении связи были оценены из данных. То же самое верно и про коэффициенты $\{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$

Решение $inline$ эквивалентной задачи содержит решение исходной $inline$ .

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

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

$\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$ — сколько и каких продуктов мы в итоге купим (наше решение).

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

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

Функция $inline$ должна иметь минимум $x^* = \arg \min_{x\in R^n} f(x,y) = y$ (то есть в оптимуме мы купим именно то, что написано в листочке)
Функция $inline$ должна быть выпуклой по $inline$ (и желательно гладкой) — чтобы была возможность эффективно посчитать $inline$ .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В идеале мы прямо сейчас должны принять решение, которое будет оставаться допустимым всегда, вне зависимости от обстоятельств. Люди, которые проектировали кастрюли, утюги и холодильники в СССР делали это в канве робастной оптимизации: продукт должен работать даже если его 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$

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

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

Построение робастной версии задачи на примере задачи 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)$ — «сдвигами».

Мини-пример

Хочу немного пояснить их значение на модельном примере из финансов: задаче о выборе оптимального портфеля ценных бумаг. Допустим, вы хотите инвестировать. Сейчас на доступной вам бирже котируется $inline$ акций, и нужно понять, как распределить свой капитал (вложить) по этим бумагам так, чтобы максимизировать свой доход при ограничении на риск. Одна из первых моделей для решения этой задачи (модель Марковица) предлагала делать следующее:

Собрать исторические данные о доходности ценной бумаги: $r_i^t = \frac{S_i^t - S_i^{t-1}}{S_i^{t-1}}$ , где $inline$ — это цена актива $inline$ в момент времени $inline$ .
Найти эмпирические средние значения доходности бумаг $\hat{r}_i = \frac{1}{T}\sum_{t=1}^T r_i^t$ и эмпирическую матрицу ковариации доходностей $\Sigma = \|cov(r_i, r_j)\|_{i,j}$
Решить задачу оптимизации
$\max_{x\in R^n_+} x^T\hat{r}\\ s.t.\\ \frac{1}{2} x^T\Sigma x \leq \sigma\\ \sum_{i=1}^nx_i \leq 1$

Решением задачи является оптимальное распределение (доли) капитала по бумагам.

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

В контексте параметризации $inline$ именно $\hat{r}$ служит в качестве «номинальных» данных.

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

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

$\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$ .
После этого мы посмотрели на худший случай (для каждого $inline$ он свой).
В итоге у нас получилась следущая запись:

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

.

Следущий шаг — выписать явно функцию $inline$ . Для этого достаточно решить задачу оптимизации по $\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$

Заметим, что полученное неравенство выпукло и любой $inline$ ему удовлетворяющий удовлетворяет и исходному $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$ , где $inline$ является некоторым замкнутым выпуклым конусом):

Неотрицательность $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$ такая же переменная, как и $inline$ .

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

Заключение

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

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

Теги:

Хабы: