幾何・凸最適化

概要

座標・向き・円環順序から凸包と半平面へ進み、幾何的な実行可能領域を表す。直線包絡を幾何と関数の橋渡しとして学ぶ。凸性の節では一次元の最適化から限界値選択・slope trickへ進み、比率目的を単調判定へ変換するfractional programmingを学ぶ。その後、順序制約のPAV、個数制約を罰則へ移すAliens trick、遷移行列のMonge性を扱う。最後に二変数の凸区分線形整数最適化で、連続的な候補と整数格子の近傍保証を組み合わせる。DP・データ構造・数論の道具がどの条件で再利用できるかを確認する。

幾何・凸最適化への変換

配置・距離・目的関数を幾何predicateや凸構造へ変換する。

考え方

座標の問題では、まず距離や位置関係を式へ直し、その式を扱いやすくする座標を探す。例えば二点 (0,0)(0,0) と (1,2)(1,2) のマンハッタン距離(各座標の差の絶対値の和)は ∣1∣+∣2∣=3|1|+|2|=3 である。ここで新しい座標を u=x+y, v=x−yu=x+y,\ v=x-y と置くと、二点は (0,0)(0,0) と (3,−1)(3,-1) に移り、距離は max⁡(∣3∣,∣−1∣)=max⁡(3,1)=3\max(|3|,|-1|)=\max(3,1)=3 と求まる。

これはこの二点だけの偶然ではない。二点の座標差を Δx,Δy\Delta x,\Delta y、変換後の差を Δu,Δv\Delta u,\Delta v とすると、

∣Δx∣+∣Δy∣=max⁡(∣Δu∣,∣Δv∣)|\Delta x|+|\Delta y|=\max(|\Delta u|,|\Delta v|)

が成り立つ。元の二つの差が同符号なら和の絶対値が、異符号なら差の絶対値が左辺と一致し、もう片方はそれを超えないからである。一点からの距離がある上限以下という条件は、変換後には u,vu,v それぞれの区間条件になる。斜めの境界を持つ領域を、軸に平行な長方形として扱える。

ただし、元が整数格子の問題なら、変換先の整数点をすべて使ってよいわけではない。逆変換は

x=u+v2,y=u−v2x=\frac{u+v}{2},\qquad y=\frac{u-v}{2}

なので、整数の u,vu,v が元の整数点に戻る条件は、両者の偶奇が同じことである。例えば (u,v)=(1,0)(u,v)=(1,0) は (x,y)=(1/2,1/2)(x,y)=(1/2,1/2) へ戻り、元の格子点ではない。距離の式と一緒に、実行可能な点の条件も移す。この判定や変換を詳しく学ぶ入口が幾何の基本判定と座標変換である。

式へ直した後は、何の構造を利用するかを分けて考える。点集合の内部候補を捨てられるなら凸境界・半平面制約へ、選ぶ値を動かしたときの費用の増減に規則があるなら凸性・傾き・限界費用へ進む。領域が凸であることと、そこで最小化する関数が凸であることは別の性質であり、使える候補削減も異なる。

成立条件と計算量

変換後の式が元の条件と同値かを確かめる。上の変換では、距離の条件に加えて整数座標の偶奇条件を保つ必要がある。一般の最適化でも、連続最適解を丸めれば整数最適解になるとは限らない。

固定長整数の演算を定数時間と数えれば、一点の座標変換は O(1)O(1)、NN 点全体では O(N)O(N) 時間である。その後の整列・領域内の集計・最適化には別の費用がかかるため、変換だけの計算量で解法全体を評価しない。外積の積や座標の和・差が収まる整数幅、境界を含むか、浮動小数点の誤差も確認する。各子単元で、候補を捨てる根拠と必要な操作の費用を対応させる。

章の構成

項目は各章の読書順に並べています。親子関係は順序と独立しているため、階層を字下げで表さず、子Unitには「概念上の親」を示します。導入項目は関連手法の見取り図で、発展的なUnitは対象色を目安に後から戻って学べます。

問題一覧

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

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

関連問題

前提・学習成果・出典

導入対象の目安: 水色(1200–1599)。座標と向きによる判定から、凸な境界・関数の最適化へ進む入口。

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

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-chapter-geometry-optimization

習得する技能

  • 配置・距離・目的関数を幾何predicateや凸構造へ変換する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

前提と範囲

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

直接の前提単元: なし。

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

orientationなどの幾何predicateから凸境界・傾き・dual penaltyへ進み、候補を構造的に削減する。

このUnitでは扱わないもの

  • なし

根拠