---
# System prepended metadata

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

---

---
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**へ．

以下では，この手続きが，**競り上げオークション**として解釈できることを見ていこう．

