2021年度知的システム<br>第12回：割当問題とオークション(4) 主双対アルゴリズムと競り上げオークション

--- lang: ja tags: OptMech-2021, lecture --- # 2021年度知的システム<br>第12回：割当問題とオークション(4) 主双対アルゴリズムと競り上げオークション [ポータルへ戻る](https://hackmd.io/@nagae/OptMech_2021) <div style="text-align: center"> このページへは以下のQRコードまたはURLからアクセスできます： ![](https://i.imgur.com/kQZdaFQ.png =200x) <code style="font-size:20pt">https://hackmd.io/@nagae/OptMech_2021-Ch11</code> </div> # 今回＆次回で学ぶこと **双対定理**と**相補性定理**を駆使した線形計画問題の解法である **主双対アルゴリズム** を学び，その手続きが **(主双対)競り上げオークション** として構成できることを学ぶ．本稿は以下の内容を整理したものです： - Bikhchandani, S. and Ostroy, J. “Ascending price Vickrey auctions,” *Games and Economic Behavior*, 55 (2), pp. 215–241 2006. - Demange, G., Gale, D., and Sotomayor, M. “Multi-Item Auctions,” *Journal of Political Economy*, 94 (4), pp. 863–872 1986. - de Vries, S., Schummer, J., and Vohra, R. V. “On ascending Vickrey auctions for heterogeneous objects,” *Journal of Economic Theory*, 132 (1), pp. 95–118 2007. # 主双対アルゴリズム ## 相補性定理と主双対アルゴリズム $\mathbf{A}\in\mathcal{R}^{M\times{}N}$, $\mathbf{b}\in \mathcal{R}^{M}$, $\mathbf{c} \in \mathcal{R}^{N}$を与件とした**線形計画問題**: $$\begin{equation} \min\left\{\left.\mathbf{c}^{\top}{x} \right| \mathbf{A} \mathbf{x} = \mathbf{b}, \mathbf{x} \geq \mathbf{0} \right\} \end{equation}$$ とその**双対問題**: $$\begin{equation} \max\left\{\left.\mathbf{b}^{\top}\mathbf{y} \right| \mathbf{A}^{\top} \mathbf{y} \leq \mathbf{c} \right\} \end{equation}$$ を考える． **相補性定理** より, $\mathbf{x} \in \mathcal{R}^{N}$, $\mathbf{y} \in \mathcal{R}^{M}$ が以下の3つの条件を全て満たすなら最適解． 1. $\mathbf{x}$ が**主実行可能**(i.e. $\mathbf{A}\mathbf{x} = \mathbf{b}, \mathbf{x} \geq \mathbf{0}$) 2. $\mathbf{y}$ が**双対実行可能**(i.e. $\mathbf{A}^{\top}\mathbf{y} \leq \mathbf{c}$) 3. $\mathbf{x}, \mathbf{y}$ が**相補性条件**を満足する： $$\begin{align} \mathbf{x}^{\top}\left(\mathbf{A}^{\top}\mathbf{y} - \mathbf{c}\right) &\Leftrightarrow \sum_{n \in \mathcal{N}} x_{n} \left(\sum_{m\in\mathcal{M}} a_{m,n}y_{m} - c_{n}\right) = 0\\ &\Leftrightarrow \begin{cases} x_{n} > 0 &\rightarrow \sum_{m} a_{m,n}y_{m} = c_{n} \\ x_{n} = 0 &\leftarrow \sum_{m} a_{m,n} y_{m} < c_{n} \end{cases} \end{align}$$ ここで，$\mathcal{N} = \{1, \cdots, N\}$および$\mathcal{M} = \{1, \cdots, M\}$は**添字の集合**． :::success **主双対アルゴリズムの基本的考え方** 双対実行可能な(2を満足する)$\mathbf{y}$を生成し，相補性条件(3)を満足するように$\mathbf{x}$を構築する．そうして得られた$\mathbf{x}$が主実行可能(1を満足する)なら最適解．そうでなければ，より最適解に近づくように$\mathbf{y}$を改訂． ::: ## 相補性条件を満足する主変数の構築ある**双対実行可能解** $\mathbf{y}^{(k)}$ に対して，**相補性条件**($\sum_{m} a_{m,n}y_{m} < c_{n} \rightarrow x_{n} = 0$)を満足するような主変数$\mathbf{x}^{(k)}$を構築するために，まず，**双対問題の不等式制約が厳密に満足される(主変数が0となる)添字の集合**を，以下のように定義する： $$\begin{equation} \mathcal{N}^{(k)}:=\left\{n \in \mathcal{N} \left| \sum_{m \in \mathcal{M}} a_{m,n}y_{k}^{(k)} < c_{n} \right.\right\} \end{equation}$$ 主変数$\mathbf{x}^{(k)}$が**相補性条件**を満足するためには，以下の制約を満たす必要がある: $$\begin{equation} x_{n}^{(k)} = 0, \forall n \in \mathcal{N}^{(k)} \end{equation}$$ 上述の制約の下で，**主実行可能解**$\mathbf{x}^{(k)}$を構築できるならば，$\mathbf{x}^{(k)}$および$\mathbf{y}^{(k)}$は**最適解**である．では，==どうすれば実行可能な$\mathbf{x}^{(k)}$を構築できる(もしくは不能であると判定できる)のだろうか?== → **二段階単体法**の**第1段階**(初期実行可能解の生成)に似た方法を使う． ## 主実行可能な解の構築方法 $x_{n}=0$となる添字集合$\mathcal{N}^{(k)}$を与えられた下で，**相補性条件**を満足する実行可能な主変数を構築したい．→**二段階単体法**の第1段階と同様の**補助問題**を考える．まず，主問題の**等式制約の右辺**がいずれも$b_{m}\geq0$となるように，$b_{m} < 0$となっている制約条件$m$の両辺に$-1$を乗じておく． $$\begin{align} \text{[P]} \qquad \min_{\mathbf{x}} &\sum_{n \in \mathcal{N}} c_{n} x_{n} \\ \text{s.t.}\quad & \sum_{n \in \mathcal{N}} a_{m,n} x_{n} = b_{m} (\geq 0), \qquad \forall m \in \mathcal{M},\\ & x_{n} \geq 0, \quad \forall n \in \mathcal{N}. \end{align}$$ 次に，相補性条件と等価な制約$x_{n}^{(k)} = 0, \forall n \in \mathcal{N}^{(k)}$を設けた以下の**制約付き問題**(restricted problem)を考える: $$\begin{align} \text{[RP]} \qquad \min_{\mathbf{x}^{(k)}, \mathbf{z}^{(k)}} &\sum_{m \in \mathcal{M}} z_{m}^{(k)} \\ \text{s.t.}\quad & \sum_{n \in \mathcal{N}} a_{m,n} x_{n} + z_{m}^{(k)} = b_{m} (\geq 0), \qquad \forall m \in \mathcal{M},\\ & x_{n}^{(k)} = 0, \quad \forall n \in \mathcal{N}^{(k)}\\ & x_{n}^{(k)} \geq 0, \quad \forall n \not \in \mathcal{N},\\ & z_{m}^{(k)} \geq 0, \quad \forall m \in \mathcal{M} \end{align}$$ ここで，$z_{m}^{(k)}$は$m$番目等式制約に対応する人工的な**補助変数**．この制約付き問題$\text{[RP]}$は，以下の便利な性質を持つ: 1. **自明な実行可能解**$(\mathbf{x}^{(k)}, \mathbf{z}^{(k)})=(\mathbf{0}, \mathbf{b})$を持つ． 2. 任意の実行可能解に対して**目的関数が非負**である． 3. $\text{[RP]}$の**最適値が0**，すなわち最適解において$\mathbf{z}^{(k)} = \mathbf{0}$であるとき，かつその時に限り，$\mathbf{x}^{(k)}$は**主実行可能**． :::warning [二段階単体法の第1段階](https://hackmd.io/@nagae/MTNS_2021-Ch06#%E4%BA%8C%E6%AE%B5%E9%9A%8E%E5%8D%98%E4%BD%93%E6%B3%95%E3%81%A7%E7%94%A8%E3%81%84%E3%82%8B%E8%A3%9C%E5%8A%A9%E5%95%8F%E9%A1%8C)では1次元の人工変数だけを用い，等式制約の右辺定数を非負にしておく必要も無かった．上記$\text{[RP]}$で$M$次元の補助変数を導入したり，$b_{m}$の非負性を要求したりするのは，続く制約付き双対問題を使って双対変数$\mathbf{y}$を改訂するためである． ::: ## 双対変数の改訂 **制約付き問題**$\text{[RP]}$の最適値が0より大きいとき，与えられた双対実行可能解$\mathbf{y}^{(k)}$の下で，**相補性条件を満足する主実行可能解は存在しない**．このとき，$\text{[RP]}$の**双対実行可能解**を用いることで，$\mathbf{y}^{(k)}$よりも**最適解に近い双対実行可能解**を求められる． $\text{[RP]}$の双対問題は，以下のように定式化される： $$\begin{align} \text{[RD]} \quad \max_{\mathbf{\psi}^{(k)}} &\sum_{m \in \mathcal{M}} b_{m} \psi_{m}^{(k)}\\ \text{s.t.} \quad & \sum_{m \in \mathcal{M}} a_{m, n} \psi_{m}^{(k)} \leq 0, \quad \forall n \not \in \mathcal{N}^{(k)}\\ & \psi_{m}^{(k)} \leq 1, \quad \forall m \in \mathcal{M} \end{align}$$ いま，**制約付き問題**$\text{[RP]}$の最適解が0より大きいとき，**弱双対定理**より， \begin{equation} 0 < \underbrace{\sum_{m \in \mathcal{M}} b_{m} \psi_{m}^{(k)}}_{\text{[RD]の目的関数}} \leq \underbrace{\sum_{m \in \mathcal{M}} z_{m}^{(k)}}_{\text{[RD]の最適値}} \end{equation} を満足し，かつ \begin{equation} \mathbf{y}^{(k+1)} =\mathbf{y}^{(k)} + \alpha^{(k)} \boldsymbol{\psi}^{(k)} \end{equation} が双対実行可能となるような$\text{[RD]}$の**実行可能解**(最適解である必要はない) $\boldsymbol{\psi}^{(k)}$ および**ステップ・サイズ**(正のスカラ) $\alpha^{(k)} > 0$が**必ず**存在する． $\mathbf{A}^{\top} \mathbf{y}^{(k)} \leq \mathbf{c}$ かつ$\mathbf{A}^{\top} \boldsymbol{\psi}^{(k)} \leq \mathbf{0}$だから， $$ \mathbf{A}^{\top} \mathbf{y}^{(k+1)} = \mathbf{A}^{\top} \mathbf{y}^{(k)} +\alpha^{(k)} \mathbf{A}^{\top}\boldsymbol{\psi}^{(k+1)} \leq \mathbf{c} $$ こうして得られる新しい**双対実行可能解** $\mathbf{y}^{(k+1)} = (y_{m}^{(k+1)})_{m \in \mathcal{M}}$ に対する**双対目的関数**は， \begin{align} \sum_{m \in \mathcal{M}} b_{m} y_{m}^{(k+1)} &= \sum_{m \in \mathcal{M}} b_{m} \left(y_{m}^{(k)} + \alpha \psi_{m}^{(k)}\right) \\ &= \sum_{m \in \mathcal{M}} b_{m} y_{m}^{(k)} + \alpha^{(k)} \underbrace{\sum_{m \in \mathcal{M}} b_{m} \psi_{m}^{(k)}}_{> 0}\\ &> \sum_{m \in \mathcal{M}} b_{m} y_{m}^{(k)} \end{align} となり， $\mathbf{y}^{(k)}$における目的関数よりも大きい，すなわち**最適解に「近い」** ことが保証される． ## 主双対アルゴリズム - **Step 0** (初期化): **初期双対実行可能解** $\mathbf{y}^{(1)}$ を選ぶ． $k:=1$． - **Step 1** (制約付き問題の構築): 双対問題の不等式制約が厳密に満足される($x_{n}=0$となる)添字集合$\mathcal{N}^{(k)}$を求める． - **Step 2** (最適性の確認): **制約付き問題**$\text{[RP]}$を解く．最適値が0ならば，$\mathbf{x}^{(k)}$および$\mathbf{y}^{(k)}$が**最適解**．最適値が正ならば，$\mathbf{y}^{(k)}$に対応する相補性条件を満足する主実行可能解は存在しない． **Step 3** へ． - **Step 3** (解の改訂方向の探索): $\mathbf{b}^{\top}\boldsymbol{\psi}^{(k)} > 0$かつ$\mathbf{y}^{(k)} + \alpha^{(k)} \boldsymbol{\psi}^{(k)}$が双対実行可能となるような**制約付き双対問題**$\text{[RD]}$の実行可能解$\boldsymbol{\psi}^{(k)}$およびステップ・サイズ$\alpha^{(k)}$を求める． - **Step 4** (解の改訂): **双対実行可能解**を $\mathbf{y}^{(k+1)} := \mathbf{y}^{(k)} + \alpha ^{(k)} \boldsymbol{\psi}^{(k)}$と改訂する．$k:=k+1$として **Step 1**へ．以下では，この手続きが，**競り上げオークション**として解釈できることを見ていこう．