PDLP의 수학적 배경

이 페이지에는 OR-Tools에서 사용할 수 있는 선형 및 이차 프로그래밍 솔버인 PDLP의 개발자 및 고급 사용자를 위한 수학적 배경이 포함되어 있습니다. 코드 일부에 관한 참조 역할을 하며 그 자체로 읽기 위한 것이 아닙니다. 관심 있는 독자는 먼저 'Primal-Dual Hybrid Gradient를 사용한 실무형 대규모 선형 프로그래밍' 자료를 숙지한 후 코드를 살펴본 후 코드에서 언급하면 이 문서로 돌아오세요.

프라이멀

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

Dual

$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} \le Ax \le^{ \u^{c} \le Ax \le^{ ,

$$ \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$-term이 유한한 경우 $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}, \infty \{

$\mathcal{I}_{[a, b]} : \mathbb{R} \to \mathbb{R} \cup \{ \infty\}$를 간격의 표시 함수로 설정합니다. 즉, $\mathcal{I}_{[a, b]}(x)$는 0이고, 그렇지 않으면 $ \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 (\uhcly [

파생

보조변수 $\tilde a \in \mathbb{R}^m$ 및 $\tilde x \in \mathbb{R}^n$를 도입하면 1차 문제를 다음과 같이 다시 명시합니다.

$$ \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$의 정의를 확장하여 상단에 명시된 이중을 얻습니다.

안장-점 공식

원시-이중 하이브리드 그라데이션 (Chambolle 및 Pock 참고)은 형태의 원시 문제를 타겟팅합니다.

$$ \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^T Q x + \mathcal{I}_{[l^v, u^v]}(x)$
  • $h(a) = \mathcal{I}_{[-u^c,-l^c]}(a)$
  • $K = -A$

앞서 설명한 것처럼 $h^*(y) = p(y; -u^c,-l^c)$ 는 부분 선형 볼록 함수입니다. $g$ 와 $h^*$ 모두 무한한 값을 가질 수 있으므로, 각각 $x$ 와 $y$ 의 도메인을 효과적으로 제한합니다.

$g$ 의 근접 연산자는 $Q$ 가 대각선이라고 가정하고 $g$ 가 분리될 수 있다는 사실과 모든 함수 $f_1, f_2$에 대해 보유되는 다음 속성을 사용하여 PDLP에서 닫힌 형태로 계산될 수 있습니다.

$$ 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). $$

이 사실을 증명하려면 최적화의 1차 메서드에서 정리 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$로 정의합니다. 수정된 이중 목표는 이중 문제의 객관적 값이고, 항상 객관적 값의 하한값을 제공하지만 무한한 무한한 비용이 있을 때마다 $-0\infty$ 입니다.

PDLP에서 보고된 비용 절감 및 이중 목표가 OR 도구 버전 9.7과 9.8 간에 변경되었습니다. 적용되는 버전을 확인하려면 primal_dual_hybrid_gradient.h에서 SolverResult::reduced_costs를 설명하는 주석을 확인하여 버전 9.8을 언급하는지 확인합니다.

버전 9.7 이하

수정된 이중 목표가 $-\infty$일 때 더 의미 있는 이중 값을 갖기 위해 목표 값의 무한 항을 무시하는 이중 목표도 보고합니다. 이중 잔차는 정정된 이중 목표의 무한항에서 얻은 $r$ 값이며 다른 구성요소는 0이며, PDLP에서 반환된 비용은 정정된 이중 목표의 유한 항에 따른 $r$ 값이며 다른 구성요소에서는 0이 됩니다 (즉, $r = \mbox{residuals} + \m$).

버전 9.8 이상

수정된 이중 목표가 $-\infty$일 때 보다 의미 있는 이중 값을 갖기 위해 Google에서는 목표 값의 무한한 항을 유한한 항으로 대체하는 이중 목표도 보고합니다. 경계 중 하나가 유한하면 그 경계가 무한한 경우 대신 사용되고 그렇지 않으면 0이 경계에 사용됩니다. 이렇게 하면 이중 목표의 오목성이 유지되지만, 반드시 목표 값의 하한값이 지정되는 것은 아닙니다. 이중 잔차는 수정된 이중 목표의 무한항 $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 = R^T R$ 로 인수 (예: 콜레스키 분해)하고 제약 조건 $R x - z = 0$로 정의된 추가 변수 $z$ 를 도입하여 $x^T S x = z^T z$가 되도록 대칭 양의 반확정 목표 행렬 $S$를 이 형식으로 변환할 수 있습니다. ↩