Математическая основа для PDLP

Эта страница содержит математическую информацию для разработчиков и опытных пользователей PDLP, решателя линейного и квадратичного программирования, доступного в OR-Tools. Он служит ссылкой на части кода и не предназначен для чтения отдельно. Заинтересованным читателям следует сначала ознакомиться со статьей « Практическое крупномасштабное линейное программирование с использованием первично-двойного гибридного градиента », затем просмотреть код, а затем вернуться к этому документу, когда код ссылается на него.

Первобытный

PDLP рассматривает следующую задачу выпуклого квадратичного программирования:

$$ \begin{align} \min_x & \, c^Tx + \frac{1}{2}x^TQx \\ \text{s.t.}\; & l^{c} \le Ax \le u^{c} \\ & l^{v} \le x \le u^{v} \end{align} $$

где $A$ — матрица $m \times n$, а $Q$ — диагональная неотрицательная $n \times n$ матрица 1 . Векторы верхней границы $u^{c}$ и $u^{v}$ имеют записи в $\mathbb{R} \cup \{ \infty\}$, а векторы нижней границы $l^{c}$ и $l^{v}$ имеют записи в $\mathbb{R} \cup \{ -\infty\}$. Мы предполагаем $l^{c} \le u^{c}$ и $l^{v} \le u^{v}$.

Двойной

Пусть $a \in \mathbb{R}$. Пусть $[a]_+$ обозначает его положительную часть, а $[a]_-$ — отрицательную часть, т. е. $a = [a]_+ - [a]_-$. При применении к вектору положительная и отрицательная части вычисляются поэлементно.

Двойственная к предыдущей простой задаче находится над $x \in \mathbb{R}^n$, $y \in \mathbb{R}^m$ и $r \in \mathbb{R}^n$. Вектор $y$ содержит двойственные множители на линейные ограничения ($l^{c} \le Ax \le u^{c}$). Вектор $r$, называемый приведенными затратами , содержит двойственные множители на связанных ограничениях ($l^{v} \le x \le u^{v}$).

$$ \begin{align} \max_{x, y, r} & \, -\frac{1}{2}x^TQx + \left((l^{c})^T[y]_+ - (u^{c})^T[y]_- \right) + \left((l^{v})^T[r]_+ - (u^{v})^T[r]_- \right) \\ \text{s.t.}\; & Qx + c - A^Ty = r \end{align} $$

Когда $Q = 0$, $x$ можно исключить из двойственности, восстановив двойственность LP.

Двойные границы переменных

Мы говорим, что $y$ удовлетворяет границам двойственной переменной, если $y$-терм в цели конечен, то есть:

$$ y_i \geq 0 \qquad \text{if }u^c_i = \infty, \\ y_i \leq 0 \qquad \text{if }l^c_i = -\infty. $$

Вывод с использованием сопряженной двойственности

Предварительные сведения

Пусть $a \in \mathbb{R} \cup \{-\infty\}$ и $b \in \mathbb{R} \cup \{\infty\}$ с $b \ge a$ и рассмотрим интервал $[a, b] \subseteq \mathbb{R} \cup \{-\infty, \infty\}$.

Пусть $\mathcal{I}_{[a, b]} : \mathbb{R} \to \mathbb{R} \cup \{ \infty\}$ — индикаторная функция интервала, т. е. $\ mathcal{I}_{[a, b]}(x)$ равен нулю, если $x \in [a, b]$, и $\infty$ в противном случае.

Определите $p(y; a, b): \mathbb{R} \to \mathbb{R} \cup \{\infty\}$ как:

$$ p(y; a, b) = \begin{cases} ay & \text{ if } y < 0 \\ 0 & \text{ if } y = 0 \\ by & \text{ if } y > 0 \end{cases}. $$

Когда $a$ или $b$ бесконечны, следуйте стандартной расширенной вещественной арифметике .

Основной результат: $p(y; a, b) = (\mathcal{I}_{[a, b]})^*(y)$, где $(\cdot)^*$ обозначает выпуклое сопряжение.

Для векторов $l \subseteq (\mathbb{R} \cup \{-\infty\})^n$ и $u \subseteq (\mathbb{R} \cup \{\infty\})^n$ индикаторная функция $\mathcal{I}_{[l, u]} : \mathbb{R}^n \to \mathbb{R} \cup \{ \infty\}$ определяется аналогично $\mathcal{I} _{[l,u]}(x) = \sum_{i=1}^n \mathcal{I}_{[l_i, u_i]}(x_i)$, и аналогично $p(y; l, u) = (\mathcal{I}_{[l, u]})^*(y) = \sum_{i=1}^n p(y_i; l_i, u_i)$.

Вывод

Вводя вспомогательные переменные $\tilde a \in \mathbb{R}^m$ и $\tilde x \in \mathbb{R}^n$, переформулируем основную задачу как:

$$ \begin{align} \min_{x, \tilde x, \tilde a} & \, c^Tx + \frac{1}{2}x^TQx + \mathcal{I}_{[l^c,u^c]}(\tilde a) + \mathcal{I}_{[l^v,u^v]}(\tilde x) \\ \text{s.t.}\; & \tilde a = Ax \\ & \tilde x = x \end{align} $$

Дуализируя ограничения-равенства, получаем:

$$ \min_{x, \tilde x, \tilde a} \max_{y, r} c^Tx + \frac{1}{2}x^TQx + y^T\tilde a - y^TAx + r^T\tilde x - r^Tx + \mathcal{I}_{[l^c,u^c]}(\tilde a) + \mathcal{I}_{[l^v,u^v]}(\tilde x) $$

Обмен мин на макс и перегруппировка:

$$ \max_{y, r} \min_{x, \tilde x, \tilde a} c^Tx + \frac{1}{2}x^TQx - y^TAx - r^Tx + \left( \mathcal{I}_{[l^c,u^c]}(\tilde a) + y^T\tilde a \right) + \left(\mathcal{I}_{[l^v,u^v]}(\tilde x) + r^T\tilde x \right) $$

Совместная минимизация по $x$, $\tilde x$ и $\tilde a$ распадается. Для $x$ мы видим, что минимизатор, если он существует, удовлетворяет условию $Qx + c - A^Ty = r$, и в этом случае минимальное значение равно $-\frac{1}{2} x^TQx$. Для $\tilde x$ и $\tilde a$ мы применяем определение выпуклых сопряжений с небольшими поправками на знаки.

Это дает двойное:

$$ \begin{align} \max_{x, y, r} & \, -\frac{1}{2}x^TQx - p(-y, l^c, u^c) - p(-r, l^v, u^v) \\ \text{s.t.}\; & Qx + c - A^Ty = r \end{align} $$

Расширяя определение $p$, мы получаем двойственное, указанное вверху.

Формулировка седловой точки

Первично-двойственный гибридный градиент (см. Шамболь и Пок ) нацелен на основную проблему формы

$$ \begin{align} \min_x f(x) + g(x) + h(Kx) \end{align} $$

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

$$ \begin{align} \min_x \max_y f(x) + g(x) + y^TKx - h^*(y) \end{align} $$

PDLP приводит задачу выпуклого квадратичного программирования к этой форме, устанавливая:

  • $f(x) = 0$
  • $g(x) = c^T x + \frac{1}{2} x^TQ x + \mathcal{I}_{[l^v, u^v]}(x)$
  • $h(a) = \mathcal{I}_{[-u^c,-l^c]}(a)$
  • $К = -А$

Как было получено ранее, $h^*(y) = p(y; -u^c,-l^c)$ — кусочно-линейная выпуклая функция. И $g$, и $h^*$ могут принимать бесконечные значения, что эффективно ограничивает области определения $x$ и $y$ соответственно.

Обратите внимание, что проксимальный оператор $g$ вычислим в замкнутой форме в предположении PDLP о диагонали $Q$, используя факт сепарабельности $g$ и следующее свойство, справедливое для любых функций $f_1, f_2$:

$$ f_2(t) = f_1(t) + \frac{\mu}{2} t^2 \Rightarrow \mathrm{prox}_{\lambda f_2}(t) = \mathrm{prox}_{\frac{\lambda}{1 + \lambda \mu} f_1}\left( \frac{t}{1 + \lambda \mu} \right). $$

Доказательство этого факта см., например, в теореме 6.13 в книге «Методы первого порядка в оптимизации» . Полученное выражение имеет вид

$$ \begin{equation} \mathrm{prox}_{\lambda g}(x) = \mathrm{proj}_{[l^v, u^v]}\left( (I + \lambda Q)^{-1} (x - \lambda c) \right) \end{equation} $$

Снижение затрат, двойные остатки и исправленная двойная цель.

Формулировка седловой точки явно работает только с $(x,y)$; приведенные затраты $r$ неявны. Чтобы вернуть $(x,y,r)$ при решении формулы перевала, мы определяем $r$ как $r = Qx + c - A^Ty$. Скорректированная двойная цель является объективным значением двойственной задачи и всегда дает нижнюю границу целевого значения, но равна $-\infty$ всякий раз, когда на бесконечной границе существует ненулевая приведенная стоимость.

Снижение затрат и двойная цель, о которых сообщил PDLP, были изменены в версиях OR-tools 9.7 и 9.8. Чтобы проверить, какая версия применима, проверьте комментарий, описывающий SolverResult::reduced_costs в primal_dual_hybrid_gradient.h , и посмотрите, упоминается ли там версия 9.8.

Версия 9.7 и более ранние версии

Чтобы иметь более значимое двойное значение, когда исправленная двойная цель равна $-\infty$, мы также сообщаем о двойной цели , которая игнорирует бесконечные члены в целевом значении. Двойные остатки — это значения $r$ из бесконечных членов в скорректированной двойной цели с 0 в других компонентах, а приведенные затраты, возвращаемые PDLP , — это значения $r$ из конечных членов в скорректированной двойной цели, с 0 в остальных компонентах (так что $r = \mbox{остатки} + \mbox{приведённые затраты}$).

Версия 9.8 и более поздние версии

Чтобы иметь более значимое двойное значение, когда исправленная двойная цель равна $-\infty$, мы также сообщаем о двойной цели , которая заменяет бесконечные члены в целевом значении конечными следующим образом: если одна из границ конечна, эта граница используется вместо бесконечной; в противном случае для границы используется ноль. Этот выбор сохраняет вогнутость двойной цели, но не обязательно дает нижнюю границу объективного значения. Двойственные остатки — это значения $r$ из бесконечных членов в скорректированной двойной цели. Сниженные затраты, возвращаемые PDLP, составляют $r$.

Обработка границ некоторых переменных как бесконечных

В обеих версиях, если опция решателя handle_some_primal_gradients_on_finite_bounds_as_residuals имеет true (по умолчанию), дополнительные границы переменных могут рассматриваться как бесконечные при вычислении двойной цели и двойных остатков. В частности, если $|x_i - l^v_i| > |x_i|$, $l^v_i$ рассматривается как бесконечный, и аналогично, если $|x_i - u^v_i| > |x_i|$, $u^v_i$ рассматривается как бесконечный.

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

Изменение масштаба

Предположим, нам даны диагональная (столбцовая) матрица масштабирования $C$ и диагональная (строка) матрица масштабирования $R$ с положительными элементами на диагонали. Применяя масштабирование, как в ShardedQuadraticProgram::RescaleQuadraticProgram , мы получаем следующую преобразованную задачу:

$$ \begin{align} \min_{\tilde x} & \, (Cc)^T{\tilde x} + \frac{1}{2}{\tilde x}^T(CQC){\tilde x} \\ \text{s.t.}\; & Rl^{c} \le RAC\tilde x \le Ru^{c} \\ & C^{-1}l^{v} \le \tilde x \le C^{-1}u^{v} \end{align} $$

Решение исходной задачи находится как $x = C\tilde x$. Если $\tilde y$ — двойственное решение и $\tilde r$ — приведенные затраты преобразованной задачи, то $y = R\tilde y$ — двойственное решение и $r = C^{-1}\tilde r $ — приведенные затраты исходной задачи (вывод опущен).

Идентификация неосуществимости

Сертификатом первичной невыполнимости является точка $(y, r) \in \mathbb{R}^m \times \mathbb{R}^n$, удовлетворяющая:

$$ \begin{equation} \left((l^{c})^T[y]_+ - (u^{c})^T[y]_- \right) + \left((l^{v})^T[r]_+ - (u^{v})^T[r]_- \right) > 0 \\ -A^T y = r . \end{equation} $$

Существование такой точки означает, что основная задача не имеет решения.

Аналогично, сертификатом двойной невыполнимости является точка $x \in \mathbb{R}^n$ такая, что:

$$ \begin{equation} Qx = 0 \\ c^T x < 0 \\ (Ax)_i \begin{cases} = 0 & \text{if }l^c_i , u^c_i \in \mathbb{R}, \\ \geq 0 & \text{if }l^c_i \in \mathbb{R}, u^c_i = \infty, \\ \leq 0 & \text{if }l^c_i = -\infty, u^c_i \in \mathbb{R}, \end{cases} \\ x_i \begin{cases} = 0 & \text{if }l^v_i , u^v_i \in \mathbb{R}, \\ \geq 0 & \text{if }l^v_i \in \mathbb{R}, u^v_i = \infty, \\ \leq 0 & \text{if }l^v_i = -\infty, u^v_i \in \mathbb{R}. \end{cases} \end{equation} $$

Обратите внимание, что сертификаты для линейной программы можно получить, установив $Q=0$.

  1. Симметричную положительную полуопределенную целевую матрицу $S$ можно преобразовать в эту форму, факторизовав $S$ как $S = R^TR$ (например, факторизация Холецкого), введя дополнительные переменные $z$, определенные ограничениями $R x - z = 0$, так что $x^TS x = z^T z$. ↩