2024.10.15 閑話

怎么又來抄論文了

感受一下 2024 年集訓隊論文！雖然可能 joke3579 在 2022 年就讀過了（？

歌：all is ai - 歌愛ユキ & GUMI .

首先回憶一下拉格朗日乘數法 . 對于帶等式約束的最優化問題：

\[\begin{aligned}\max\ &f(\bm x)\\\text{s.t. }&\begin{cases}g_1(\bm x)=0\\\cdots\\g_m(\bm x)=0\\\end{cases}\end{aligned} \]

其中 \(f,g_{1\dots m}\) 是 \(\R^n\to\R\) 的連續可微函數，則可以加入拉格朗日乘數 \(\lambda_{1\dots m}\) 把問題改寫為

\[\max_{\bm x}\min_{\bm\lambda}\left\{f(\bm x)+\sum_{i=1}^m\lambda_ig_i(\bm x)\right\} \]

那么在 \(g_i(\bm x)\neq 0\) 的時候可以調整 \(\lambda_i\) 讓 min 取到 \(-\infty\)，所以所有 \(g_i(\bm x)\) 肯定都為 0 .

具體的拉格朗日乘數定理和拉格朗日乘數法可以看論文，這里先跳過一下 . 總之這部分只需要感受這股 \(\lambda\) 的勁！

介紹：拉格朗日對偶！

對于 \(f:\R^n\to\R,\,g:\R^n\to\R^m,\,h:\R^n\to\R^p\)，考慮最優化問題：

\[\begin{aligned}\max\ &f(\bm x)\\\text{s.t. }&g(\bm x)\ge 0\\&h(\bm x)=0\end{aligned} \]

定義拉格朗日函數 \(F:\R^n\times\R^m\times\R^p\to\R\) 為：

\[F(\bm x,\bm\lambda,\bm\nu)=f(\bm x)+\bm\lambda^{\sf T}g(\bm x)+\bm\nu^{\sf T}h(\bm x) \]

定義拉格朗日對偶函數 \(L:\R^m\times\R^p\to\R\)：

\[L(\bm\lambda,\bm\nu)=\max_{\bm x}F(\bm x,\bm\lambda,\bm\nu) \]

定義其拉格朗日對偶問題為：

\[\begin{aligned}\min\ &L(\bm\lambda,\bm\nu)\\\text{s.t. }&\bm\lambda\ge \bm 0\end{aligned} \]

此處首先 \(L\) 有凸性，其次在某些情況下原問題和拉格朗日對偶問題的解相等 .

凸性

考慮到應該也沒多少人想看所以就折疊一下 . 其實也比較簡單，就直接暴力代入定義就可以了 .

考慮：

\[L(a\bm\lambda_1+(1-a)\bm\lambda_2,a\bm\nu_1+(1-a)\bm\nu_2)=\max_{\bm x}F(\bm x,a\bm\lambda_1+(1-a)\bm\lambda_2,a\bm\nu_1+(1-a)\bm\nu_2) \]

最大值在 \(\bm x_0\) 處取到，則：

\[\begin{aligned}L(a\bm\lambda_1+(1-a)\bm\lambda_2,a\bm\nu_1+(1-a)\bm\nu_2)&=F(\bm x_0,a\bm\lambda_1+(1-a)\bm\lambda_2,a\bm\nu_1+(1-a)\bm\nu_2)\\&=f(\bm x_0)+(a\bm\lambda_1+(1-a)\bm\lambda_2)^{\sf T}g(\bm x_0)+(a\bm\nu_1+(1-a)\bm\nu_2)^{\sf T}h(\bm x_0)\\&=a(f(\bm x_0)+\bm\lambda_1^{\sf T}g(\bm x_0)+\bm\nu_1^{\sf T}h(\bm x_0))+(1-a)(f(\bm x_0)+\bm\lambda_2^{\sf T}g(\bm x_0)+\bm\nu_2^{\sf T}h(\bm x_0))\\&=aF(\bm x_0,\bm\lambda_1,\bm\nu_1)+(1-a)F(\bm x_0,\bm\lambda_2,\bm\nu_2)\\&\le aL(\bm\lambda_1,\bm\nu_1)+(1-a)L(\bm\lambda_2,\bm\nu_2)\end{aligned} \]

對于對偶性，先不加證明地給出幾個定理：

min-max 不等式

對于 \(F:D_x\times D_y\to\R\)，有 \(\displaystyle\max_y\min_x F(x,y)\le\min_x\max_yF(x,y)\) .

minimax 定理

對于 \(D_x\subseteq\R^n,D_y\subseteq R^m\) 是緊致凸集，連續函數 \(F:D_x\times D_y\to\R\) 關于 \(x\) 是凸函數、關于 \(y\) 是凹函數，有 \(\displaystyle\max_y\min_x F(x,y)=\min_x\max_yF(x,y)\) .

此處需要解釋一下定義：

\(\R^n\) 的子集是緊致的當且僅當它是閉集合且有界 .

\(\R^n\) 的子集 \(S\) 是凸集當且僅當它 \(\forall p,q\in S,\forall\lambda\in[0,1],\lambda p+(1-\lambda)q\in S\) .

對于凸集 \(C\)，\(f:C\to\R\) 是凸函數當且僅當 \(\forall p,q\in C,\forall\lambda\in[0,1],f(\lambda p+(1-\lambda)q)\le\lambda f(p)+(1-\lambda)f(q)\) .

對于凸集 \(C\)，\(f:C\to\R\) 是凹函數當且僅當 \(\forall p,q\in C,\forall\lambda\in[0,1],f(\lambda p+(1-\lambda)q)\ge\lambda f(p)+(1-\lambda)f(q)\) .

然后有弱對偶性：原問題的最優解一定不大于拉格朗日對偶問題的最優解 .

具體證明也是加入拉格朗日乘數：

\[\begin{aligned}s^{*}&=\max_{g(\bm x)\ge0,h(\bm x)=0}f(\bm x)\\&=\max_{\bm x}\min_{\bm\lambda\ge0,\bm\nu}\{f(\bm x)+\bm \lambda^{\sf T}g(\bm x)+\bm\nu^{\sf T}\}\\&\le\min_{\bm\lambda\ge0,\bm\nu}\max_{\bm x}\{f(\bm x)+\bm \lambda^{\sf T}g(\bm x)+\bm\nu^{\sf T}\}\\&=\min_{\bm\lambda\ge 0,\bm n}L(\bm\lambda,\bm\nu)\\&=t^{*}\end{aligned} \]

然后如果這里的不等號滿足 minimax 定理條件則等號成立 . 聽說 OI 中用這個等號成立條件就夠了？

然而對線性規劃使用拉格朗日對偶只會得到常規的對偶 .

其實用這種東西好像能更理性解釋一下納什均衡的規劃怎么做的，原來那個 2023.11.7 閑話的解釋有點玄學的感覺了 .

先跳過博弈論，雙人每人策略集合有限的完全信息靜態非合作零和博弈的納什均衡相當于這樣的問題：有一個 \(n\times m\) 矩陣 \(A\)，一種策略可以由列向量 \(\bm a,\bm b\) 表示，其中 \(\bm a,\bm b\) 的每個元素都在 \([0,1]\) 間且分別的和為 1 . 此時兩人的期望收益分別等于 \(\bm a^{\sf T}A\bm b\) 和 \(-\bm a^{\sf T}A\bm b\) . 策略是納什均衡的當且僅當每個人只改變自己的策略都不會讓自己的期望收益增加 .

可以證明這樣的博弈一定存在納什均衡點且這樣的納什均衡點期望收益相同 . 若納什均衡時雙方的策略為 \(\bm a_0,\bm b_0\)，則：

\[\max_{\bm a}\bm a^{\sf T}A\bm b_0=\min_{\bm b}\bm a_0^{\sf T}A\bm b \]

可以擴寫為：

\[\min_{\bm b}\max_{\bm a}\bm a^{\sf T}A\bm b\le\max_{\bm a}\bm a^{\sf T}A\bm b_0=\min_{\bm b}\bm a_0^{\sf T}A\bm b\le\max_{\bm a}\min_{\bm b}\bm a^{\sf T}A\bm b \]

根據 min-max 不等式可知此時不等號中等號全部成立，那么可以把納什均衡改成一個兩步的博弈，每步每人選擇自己的向量，這樣就方便分析了 . 原文寫的是用 minimax 定理但是感覺道理不多 .

習題：THUPC2023 初賽欺詐游戲 .

upd. 那個無意識之外的捉迷藏好像也是這種

Reference. 施開成《淺談拉格朗日乘數及對偶在 OI 中的應用》 .

但是不管你喜不喜歡，它永遠都在那里 .

圖