---
lang: ja
tags: MTNS-2022, lecture, linear programming
---
# 2022年度 交通社会システム論<br>第12回：割当問題とオークション(4) 主双対アルゴリズム | Primal-Dual Algorithm
[ポータルへ戻る](https://hackmd.io/@nagae/MTNS_2022)
<div style="text-align: center">

このページへは以下のQRコードまたはURLからアクセスできます：

<code style="font-size:20pt">https://hackmd.io/@nagae/MTNS_2022-Ch11</code>
</div>

# 今回＆次回で学ぶこと | What we learn in this and next session
**双対定理**と**相補性定理**を駆使した線形計画問題の解法である **主双対アルゴリズム** を学び，その手続きが **(主双対)競り上げオークション** として構成できることを学ぶ．
Study the **primal-dual algorithm** as a solution method for linear programming problems that exploits the duality and complementarity theorems, and understand that its procedure can be regarded as **a (primal-dual) ascending auction**.

本稿は以下の内容を整理したものです：
For more details, readers are referred to:
- 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.

# 主双対アルゴリズム | Primal-Dual Algorithm
## 相補性定理と主双対アルゴリズム | Complementarity Theorem and PD Algorithm
$\boldsymbol{A}\in\mathcal{R}^{M\times{}N}$, $\boldsymbol{b}\in \mathcal{R}^{M}$, $\boldsymbol{c} \in \mathcal{R}^{N}$を与件とした**線形計画問題**:
Given $\boldsymbol{A}\in\mathcal{R}^{M\times{}N}$, $\boldsymbol{b}\in \mathcal{R}^{M}$, $\boldsymbol{c} \in \mathcal{R}^{N}$, suppose a linear programming:
$$\begin{equation}
\min\left\{\left.\boldsymbol{c}^{\top}{x} \right| \boldsymbol{A} \boldsymbol{x} = \boldsymbol{b}, \boldsymbol{x} \geq \boldsymbol{0} \right\}
\end{equation}$$
とその**双対問題**:
and its dual:
$$\begin{equation}
\max\left\{\left.\boldsymbol{b}^{\top}\boldsymbol{y} \right| \boldsymbol{A}^{\top} \boldsymbol{y} \leq \boldsymbol{c} \right\}
\end{equation}$$
を考える．

**相補性定理** より, $\boldsymbol{x} \in \mathcal{R}^{N}$, $\boldsymbol{y} \in \mathcal{R}^{M}$ が以下の3つの条件を全て満たすなら最適解．
From the complementarity problem, $\boldsymbol{x} \in \mathcal{R}^{N}$, $\boldsymbol{y} \in \mathcal{R}^{M}$ are optimal if and only if:
1. $\boldsymbol{x}$ が**主実行可能**(i.e. $\boldsymbol{A}\boldsymbol{x} = \boldsymbol{b}, \boldsymbol{x} \geq \boldsymbol{0}$) | $\boldsymbol{x}$ is primal-feasible;
2. $\boldsymbol{y}$ が**双対実行可能**(i.e. $\boldsymbol{A}^{\top}\boldsymbol{y} \leq \boldsymbol{c}$) | $\boldsymbol{y}$ is dual-feasible;
3. $\boldsymbol{x}, \boldsymbol{y}$ が**相補性条件**を満足する：
$\boldsymbol{x}, \boldsymbol{y}$ satisfy the complementarity conditions:
$$\begin{align}
\boldsymbol{x}^{\top}\left(\boldsymbol{A}^{\top}\boldsymbol{y} - \boldsymbol{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\}$は**添字の集合**．
where $\mathcal{N} = \{1, \cdots, N\}$ and $\mathcal{M} = \{1, \cdots, M\}$ are the sets of indices.

:::success
**主双対アルゴリズムの基本的考え方 | The basic idea of the PD algorithm**
双対実行可能な(2を満足する)$\boldsymbol{y}$を生成し，相補性条件(3)を満足するように$\boldsymbol{x}$を構築する．そうして得られた$\boldsymbol{x}$が主実行可能(1を満足する)なら最適解．そうでなければ，より最適解に近づくように$\boldsymbol{y}$を改訂．

Generate a dual feasible $\boldsymbol{y}$ (satisfying cond. 2) and construct a corresponding primal $\boldsymbol{x}$ that satisfies the complementarity (cond. 3). If such $\boldsymbol{x}$ is primal feasible (i.e. satisfies cond. 1), it is optimal. Otherwise, update $\boldsymbol{y}$ to be closer to the optimal.
:::

## 相補性条件を満足する主変数の構築 | How to construct a primal solution that satisfies the complementarity?
ある**双対実行可能解** $\boldsymbol{y}^{(k)}$ に対して，**相補性条件**($\sum_{m} a_{m,n}y_{m} < c_{n} \rightarrow x_{n} = 0$)を満足するような主変数$\boldsymbol{x}^{(k)}$を構築したい．そのため，まず，**双対問題の不等式制約が厳密に満足される(主変数が0となる)添字の集合**を，以下のように定義する：
Given a dual feasible solution $\boldsymbol{y}^{(k)}$, in order to obtain a primal solution that satisfies the complementarity condition ($\sum_{m} a_{m,n}y_{m} < c_{n} \rightarrow x_{n} = 0$), we first define a set of primal indices such that the corresponding dual constraint is strictly satisfied (i.e. the primal variable becomes 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}$$

主変数$\boldsymbol{x}^{(k)}$が**相補性条件**を満足するためには，以下の制約を満たす必要がある:
The following condition should be met for the primal variable $\boldsymbol{x}^{(k)}$ satisfying the **complementarity condition**:
$$\begin{equation}
x_{n}^{(k)} = 0, \forall n \in \mathcal{N}^{(k)}
\end{equation}$$

上述の制約の下で，**主実行可能解**$\boldsymbol{x}^{(k)}$を構築できるならば，$\boldsymbol{x}^{(k)}$および$\boldsymbol{y}^{(k)}$は**最適解**である．
If we can construct a **primal feasible solution** $\boldsymbol{x}^{(k)}$ satisfying the above condition, $\boldsymbol{x}^{(k)}$ and $\boldsymbol{y}^{(k)}$ are optimal.

では，==どうすれば実行可能な$\boldsymbol{x}^{(k)}$を構築できる(もしくは不能であると判定できる)のだろうか?== → **二段階単体法**の**第1段階**(初期実行可能解の生成)に似た方法を使う．
Then how can we construct a feasible primal $\boldsymbol{x}^{(k)}$ (or identify there is no feasible primal)? By a method that resembles the **Phase I** of **Two-phase simplex method**.

## 主実行可能な解の構築方法 | The construction of a Primal Feasible Solution
$x_{n}=0$となる添字集合$\mathcal{N}^{(k)}$を与えられた下で，**相補性条件**を満足する実行可能な主変数を構築したい．→**二段階単体法**の第1段階と同様の**補助問題**を考える．
Given a index set $\mathcal{N}^{(k)}$, at which $x_{n}=0$, a primal feasible solution can be obtained via an **auxiliary problem** similar to Phase-I of the two phase simplex method.

まず，主問題の**等式制約の右辺**がいずれも$b_{m}\geq0$となるように，$b_{m} < 0$となっている制約条件$m$の両辺に$-1$を乗じておく．
First, let all of the right hand side constant of the equality conditions be non-negative, i.e. $b_{m} \geq 0$, by multiplying $-1$ to both side of conditions with negative RHS $b_{m} < 0$.
$$\begin{align}
\text{[P]} \qquad \min_{\boldsymbol{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)を考える:
The consider the following restricted problem with $x_{n}^{(k)} = 0, \forall n \in \mathcal{N}^{(k)}$, that is equivalent to the complementarity condition:
$$\begin{align}
\text{[RP]} \qquad \min_{\boldsymbol{x}^{(k)}, \boldsymbol{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$番目等式制約に対応する人工的な**補助変数**．
where $z_{m}^{(k)}$ is an artificial **auxiliary variable** corresponding to the $m$th equality constraint.

この制約付き問題$\text{[RP]}$は，以下の便利な性質を持つ:
The restricted problem $\mathrm{[RP]}$ has the following advantages:
1. **自明な実行可能解**$(\boldsymbol{x}^{(k)}, \boldsymbol{z}^{(k)})=(\boldsymbol{0}, \boldsymbol{b})$を持つ．
It has a trivial feasible solution, $(\boldsymbol{x}^{(k)}, \boldsymbol{z}^{(k)})=(\boldsymbol{0}, \boldsymbol{b})$.
2. 任意の実行可能解に対して**目的関数が非負**である．
The objective function is non-negative for every feasible solution.
4. $\text{[RP]}$の**最適値が0**，すなわち最適解において$\boldsymbol{z}^{(k)} = \boldsymbol{0}$であるとき，かつその時に限り，$\boldsymbol{x}^{(k)}$は**主実行可能**．
The optimal value of $\mathrm{[RP]}$ is 0, i.e. $\boldsymbol{z}^{(k)}=\boldsymbol{0}$ at the optimal, if and only if $\boldsymbol{x}^{(k)}$ is primal feasible.

:::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次元の人工変数だけを用い，等式制約の右辺定数を非負にしておく必要も無かった．
Note that, in the Phase-I of the two-phase simplex method, we use a scalar artificial variable and non-negativity of the RHS constants is not required.

上記$\text{[RP]}$で$M$次元の補助変数を導入したり，$b_{m}$の非負性を要求したりするのは，続く制約付き双対問題を使って双対変数$\boldsymbol{y}$を改訂するためである．
The reason of introducing $M$-dimensional auxiliary variables and non-negativity of $b_{m}$ is to *improve* the dual variable $\boldsymbol{y}$ by using the *restricted dual* below.
:::

## 双対変数の改訂 | Improve the Dual
**制約付き問題**$\text{[RP]}$の最適値が0より大きいとき，与えられた双対実行可能解$\boldsymbol{y}^{(k)}$の下で，**相補性条件を満足する主実行可能解は存在しない**． このとき，$\text{[RP]}$の**双対実行可能解**を用いることで，$\boldsymbol{y}^{(k)}$よりも**最適解に近い双対実行可能解**を求められる．
When the optimal value of the restricted problem $\mathrm{[RP]}$ is larger than $0$, there is no primal feasible solution that satisfies the complementarity condition with given dual feasible solution $\boldsymbol{y}^{(k)}$. In this case, another dual feasible solution that is closer to the optimal than $\boldsymbol{y}^{(k)}$ can be obtained by using the **dual feasible solution of** $\mathrm{[RP]}$.

$\text{[RP]}$の双対問題は，以下のように定式化される：
The dual of $\mathrm{[RP]}$ is formulated as follows:
$$\begin{align}
\text{[RD]} \quad \max_{\boldsymbol{\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より大きいとき，**弱双対定理**より，以下を満足する$\mathrm{[RD]}$ の**実行可能解**(最適解である必要はない) $\boldsymbol{\psi}^{(k)}$および正のスカラ$\alpha^{(k)} > 0$ が**必ず**存在する:
When the optimal value of the restricted primal $\mathrm{[RP]}$ is larger than 0, from the weak duality theorem, there is a **feasible solution** (might not be optimal solution) of $\mathrm{[RD]}$, $\boldsymbol{\psi}^{(k)}$ and a positive scalar $\alpha^{(k)} > 0$ that satisfy
$$\begin{equation}
0 < \underbrace{\sum_{m \in \mathcal{M}} b_{m} \psi_{m}^{(k)}}_{\begin{array}{c}\text{[RD]の目的関数}\\\text{obj. of $\mathrm{[RP]}$}\end{array}} \leq \underbrace{\sum_{m \in \mathcal{M}} z_{m}^{(k)}}_{\begin{array}{c}\text{[RP]の最適値}\\\text{the optimal value of $\mathrm{[RP]}$}\end{array}}
\end{equation}$$
and
$$\begin{equation}
\boldsymbol{y}^{(k+1)} =\boldsymbol{y}^{(k)} + \alpha^{(k)} \boldsymbol{\psi}^{(k)} \geq \boldsymbol{0}
\end{equation}$$

$\boldsymbol{A}^{\top} \boldsymbol{y}^{(k)} \leq \boldsymbol{c}$ かつ$\boldsymbol{A}^{\top} \boldsymbol{\psi}^{(k)} \leq \boldsymbol{0}$だから，
Since $\boldsymbol{A}^{\top} \boldsymbol{y}^{(k)} \leq \boldsymbol{c}$ and $\boldsymbol{A}^{\top} \boldsymbol{\psi}^{(k)} \leq \boldsymbol{0}$, it is met:
$$
\boldsymbol{A}^{\top} \boldsymbol{y}^{(k+1)} = \boldsymbol{A}^{\top} \boldsymbol{y}^{(k)}
+\alpha^{(k)} \boldsymbol{A}^{\top}\boldsymbol{\psi}^{(k+1)} \leq \boldsymbol{c}
$$
従って，$\boldsymbol{y}^{(k+1)}$は**双対実行可能**である．
That is, $\boldsymbol{y}^{(k+1)}$ is dual feasible.

こうして得られる新しい**双対実行可能解** $\boldsymbol{y}^{(k+1)} = (y_{m}^{(k+1)})_{m \in \mathcal{M}}$ に対する**双対目的関数**は，
The dual objective of the new dual feasible solution $\boldsymbol{y}^{(k+1)} = (y_{m}^{(k+1)})_{m \in \mathcal{M}}$ is greater than that of $\boldsymbol{y}^{(k)}$:
$$\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}$$
となり， $\boldsymbol{y}^{(k)}$における目的関数よりも大きい，すなわち**最適解に「近い」** ことが保証される．
In other words, $\boldsymbol{y}^{(k+1)}$ is **closer** to the optimal than $\boldsymbol{y}^{(k)}$.

## 主双対アルゴリズム | Primal-Dual Algorithm
- **Step 0** (初期化): **初期双対実行可能解** $\boldsymbol{y}^{(1)}$ を選ぶ． $k:=1$．
| (Initialization): Find a dual feasible solution $\boldsymbol{y}^{(1)}$ and let $k:=1$.
- **Step 1** (制約付き問題の構築): 双対問題の不等式制約が厳密に満足される($x_{n}=0$となる)添字集合$\mathcal{N}^{(k)}$を求める．
| (Formulate restricted primal): Find the index set $\mathcal{N}^{(k)}$ at which the dual inequality is strictly satisfied (i.e. $x_{n} = 0$).
- **Step 2** (最適性の確認): $\mathcal{N}^{(k)}$についての**制約付き問題**$\text{[RP]}$を解く．最適値が0ならば，$\boldsymbol{x}^{(k)}$および$\boldsymbol{y}^{(k)}$が**最適解**．最適値が正ならば，$\boldsymbol{y}^{(k)}$に対応する相補性条件を満足する主実行可能解は存在しない． **Step 3** へ．
| (Optimality check): Solve $\mathrm{[RP]}$ with respect to $\mathcal{N}^{(k)}$. If the optimal value is 0, $\boldsymbol{x}^{(k)}$ and $\boldsymbol{y}^{(k)}$ are **optimal** and **STOP**. If the optimal value is positive, there is no primal feasible solution that satisfies the complementarity condition corresponding to $\boldsymbol{y}^{(k)}$.
- **Step 3** (解の改訂方向の探索): $\boldsymbol{b}^{\top}\boldsymbol{\psi}^{(k)} > 0$かつ$\boldsymbol{y}^{(k)} + \alpha^{(k)} \boldsymbol{\psi}^{(k)} \geq \boldsymbol{0}$となるような**制約付き双対問題**$\text{[RD]}$の実行可能解$\boldsymbol{\psi}^{(k)}$およびステップ・サイズ$\alpha^{(k)} > 0$を求める．
|(Find descent direction): Find a feasible solution to a restricted primal $\mathrm{[RD]}$, $\boldsymbol{\psi}^{(k)}$ and a step size $\alpha^{(k)} > 0$ such that $\boldsymbol{b}^{\top}\boldsymbol{\psi}^{(k)} > 0$ and $\boldsymbol{y}^{(k)} + \alpha^{(k)} \boldsymbol{\psi}^{(k)} \geq \boldsymbol{0}$.
- **Step 4** (解の改訂): **双対実行可能解**を $\boldsymbol{y}^{(k+1)} := \boldsymbol{y}^{(k)} + \alpha ^{(k)} \boldsymbol{\psi}^{(k)}$と改訂する．$k:=k+1$として **Step 1**へ．
| (Update the solution): Let $\boldsymbol{y}^{(k+1)} := \boldsymbol{y}^{(k)} + \alpha ^{(k)} \boldsymbol{\psi}^{(k)}$ be a new **dual feasible solution** and $k:=k+1$. Back to **Step 1**.

以下では，この手続きが，**競り上げオークション**として解釈できることを見ていこう．
In the next (and last) session, we study that this PD algorithm can be regarded as an ascending auction.