東京大学 情報理工学研究科 数理情報学 2019年8月実施 第5問

标签：

• 东京大学
• 保序回归与 PAVA

Author

hari64boli64, 祭音Myyura

Description

各要素が有理数の配列を考える。配列 $A$ の第 $i$ 番目の要素を $A[i]$ で表す。長さ $n$ の配列 $A$ に対し、

$$\sum_{i=1}^n (A[i] - B[i])^2$$

を最小にする長さ $n$ の単調非減少配列 $B$ を、$A$ の近似配列と定義する。 ただし、$B$ が単調非減少とは、$B[1] \leq B[2] \leq \cdots \leq B[n]$ を満たすこととする。 以下の設問に答えよ。

(1) 長さ $n$ の配列 $A$ の末尾に要素を1つ追加した配列を $A'$ とする。つまり $A'[i]=A[i] \ (1 \leq i \leq n)$ が成り立つ。また、$B, B'$ をそれぞれ $A, A'$ の近似配列とする。

• (1-1) $A'[n+1] \geq B[n]$ ならば、$B'[i]=B[i] \ (1 \leq i \leq n)$ かつ $B'[n+1]=A'[n+1]$ であることを示せ。
• (1-2) $B[1]=B[2]=\cdots =B[n]$ かつ $A'[n+1] < B[n]$ とする。このとき $B'[1] = B'[2] = \cdots = B'[n+1]$ かつ $B'[n+1] < B[n]$ であることを示し、$B'[n+1]$ を求めよ。

(2) 配列 $A$ の近似配列を求める多項式時間アルゴリズムを与えよ。ただし、有理数どうしの四則演算は定数時間で行えるものと仮定してよい。

题目描述

考虑元素均为有理数的数组。对长度为 $n$ 的数组 $A$，把使

$$\sum_{i=1}^n(A[i]-B[i])^2$$

最小的单调非降数组

$$B[1]\le B[2]\le\cdots\le B[n]$$

称为 $A$ 的近似数组。

1. 在 $A$ 末尾追加一个元素得到 $A'$，即 $A'[i]=A[i]$（$1\le i\le n$）。设 $B,B'$ 分别为 $A,A'$ 的近似数组。

   1. 若 $A'[n+1]\ge B[n]$，证明

      $$B'[i]=B[i]\ (1\le i\le n),\qquad B'[n+1]=A'[n+1].$$

   2. 若 $B[1]=\cdots=B[n]$ 且 $A'[n+1]<B[n]$，证明

      $$B'[1]=\cdots=B'[n+1]<B[n],$$

      并求这个公共值。

2. 给出求任意数组 $A$ 的近似数组的多项式时间算法。可假设有理数四则运算耗时为常数。

Kai

目的関数は連続で無限遠で発散し、実行可能集合は非空閉凸集合なので、最小解が存在する。さらに狭義凸性より一意である。

$S_k=\sum_{i=1}^k(A[i]-B[i])$ とおく。制約 $B[k]-B[k+1]\le0$ の乗数を $\lambda_k$ とすれば、停留条件は $2(B[i]-A[i])+\lambda_i-\lambda_{i-1}=0$（$\lambda_0=\lambda_n=0$）である。 したがって KKT 条件は

$$S_n=0,\qquad S_k\ge0,\qquad S_k(B[k]-B[k+1])=0\quad(1\le k<n)$$

および $B$ の単調非減少性であり、これらは凸性より最適性の十分条件でもある。

(1)

(1-1)

$(B[1],\ldots,B[n],A'[n+1])$ は仮定より単調非減少である。任意の実行可能な配列 $C$ に対し、

$$\sum_{i=1}^{n+1}(A'[i]-C[i])^2 \geq\sum_{i=1}^{n}(A[i]-B[i])^2$$

であり、左辺は上の配列で等号を取る。一意性より、これが $B'$ である。

(1-2)

$B[i]=b$ とおく。全成分を同時に動かす方向は実行可能なので、最適性より

$$b=\frac1n\sum_{i=1}^nA[i].$$

単調回帰の KKT 条件から、元の定数解について

$$\sum_{i=1}^k(A[i]-b)\geq0\quad(1\leq k<n)$$

が成り立つ。ここで

$$b'=\frac{nb+A'[n+1]}{n+1} =\frac{\sum_{i=1}^nA[i]+A'[n+1]}{n+1}<b$$

とおく。$k\leq n$ に対して

$$\sum_{i=1}^k(A'[i]-b') =\sum_{i=1}^k(A[i]-b)+k(b-b')\geq0$$

であり、$k=n+1$ では和が $0$ である。したがって KKT 条件を満たす定数配列 $(b',\ldots,b')$ が唯一の最適解である。

(2)

各ブロックについて要素数と要素和をスタックに保持する。

1. $A[i]$ を要素数 $1$、和 $A[i]$ の新しいブロックとして末尾に追加する。
2. 末尾二ブロックの平均が非減少順に反している間、それらを一つに併合し、要素数と和を加える。
3. 最後に各ブロック内の $B[i]$ を、そのブロックの平均にする。

これは pool-adjacent-violators algorithm である。各ブロックは「先頭から任意の位置までの $A[i]$ とブロック平均との差の和が非負で、ブロック全体の和は $0$」という不変条件を満たす。

実際、平均 $u>v$、長さ $l,r$ の隣接ブロックを併合し、平均を $w=(lu+rv)/(l+r)$ とする。左ブロック内の長さ $k$ の接頭部では、残差和は $k(u-w)\ge0$ だけ増える。左全体と右の長さ $k$ の接頭部では、元の非負残差和に

$$l(u-w)+k(v-w)=(r-k)(w-v)\ge0$$

が加わる。ゆえに不変条件は保たれる。終了時にはブロック平均が非減少で、異なるブロックの境界で累積残差が $0$ となるため、上の KKT 条件が成立する。したがって出力は最適解である。各要素は一度追加され、各併合でブロック数が一つ減るので、四則演算回数は $O(n)$ である。