凸性・傾き・限界費用・slope trick

概要

目的関数の値そのものに加え、「変数を一つ増やすと値がいくつ変わるか」を調べる。その差分が単調なら、最適点の探索や資源配分に使える。関数全体を更新する問題では、傾きが変わる点を保持する方法へ進む。

考え方

整数区間上の関数 ff に対し、一つ右へ動いたときの値の変化を

Δf(x)=f(x+1)−f(x)\Delta f(x)=f(x+1)-f(x)

と置く。この差分が xx とともに非減少となることを、ここでは離散凸性と呼ぶ。小例として f(x)=(x−2)2f(x)=(x-2)^2 を、整数 x=0,1,2,3,4x=0,1,2,3,4 で計算する。

xxf(x)f(x)次の整数への差分 Δf(x)\Delta f(x)
0044−3-3
1111−1-1
220011
331133
4444—(区間の右端)

差分は −3,−1,1,3-3,-1,1,3 と増えている。負の間は右へ進むと値が減り、正になると値が増えるので、最初に差分が非負になる x=2x=2 が最小点である。この例では Δf(x)=2x−3\Delta f(x)=2x-3 と展開しても、非減少であることを確かめられる。

差分の単調性を見つけた後は、問題が何を求めるかで使い方を選ぶ。

  • 一つの変数の最適点を求めたいなら、一次元凸・単峰最適化へ進む。値や差分を必要な位置で計算できれば、上の表を全範囲に作らず、差分の符号が変わる位置を二分探索できる。
  • 複数の対象へ合計量を決めて資源を配りたいなら、分離凸・凹の単調限界値選択へ進む。費用が対象ごとの和に分かれ、各対象に上下限だけがある場合、一単位を足す差分が次の限界費用となる。各対象の次の費用のうち最小のものから配れば、各列の先頭から必要個数を選べる。利益の最大化では、差分が非増加となる凹関数を対称に扱う。
  • DPなどで、後の操作に備えて費用関数全体を更新したいなら、slope trickへ進む。区分線形凸関数を保つ遷移では、各座標の値を並べる代わりに傾きが変わる折れ点を保持できる。上の二乗関数をそのままこの表現で扱うという意味ではなく、実際の遷移が区分線形性と凸性を保つことを確認する。
  • 変数間に値の昇順などの順序制約があるなら、独立に資源を配る方法では扱えない。isotonic regression・PAVで、順序に違反する隣接部分をまとめる理由を学ぶ。

成立条件と計算量

差分が非減少な整数区間では、ある点から右へ進む値の変化は、その右側の差分の和になる。最初の差分が非負なら、それ以降を足しても値は下がらない。同様に、左側の差分が非正なら、左へ戻っても値は下がらない。したがって、両隣への移動で改善しない点は区間全体の最小点である。差分が 00 なら隣の点も同値で、最小点が複数になることもある。差分がすべて負なら右端、すべて正なら左端が最小で、一点だけの区間には差分がない。

小さい表は意味を確認する例であり、一般の入力での凸性の証明にはならない。差分の式や遷移の性質から単調性を示す。ABC224 Gの公式解説では、戦略を一変数に絞って費用の期待値を式にし、その凸性から整数の候補を減らしている。図が滑らかに見えることだけを根拠に探索へ進まない。

整数区間 [L,R][L,R] の要素数を U=R−L+1U=R-L+1 とし、一回の関数評価に TT 時間かかるなら、差分の符号を二分探索する費用は O(Tlog⁡U)O(T\log U) 時間である(U=1U=1 では一回の評価)。一方、限界費用を一単位ずつ配る方法は配る総量にも、slope trickは生成する折れ点の総数と更新方法にも依存する。差分の単調性は正しさの根拠であり、全体の計算量は評価・選択・更新の操作数を数えて求める。

下位単元

問題一覧

この単元に直接配置する問題はありません。下位単元または関連問題を参照してください。

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

関連問題

前提・学習成果・出典

導入対象の目安: 青色(1600–1999)。差分の単調性を入口に、凸関数の選択・合成・制約付き最適化を見渡す。

対象色の読み方は本書の読み方を参照してください。

概念上の親: 幾何・凸最適化。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-discrete-convex

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: なし。

このUnitを直接前提とする単元: なし。

このUnitでは扱わないもの

  • 真偽値の単調境界探索と、交換論だけで決まる貪欲順。

根拠