二変数の凸区分線形整数最適化

概要

二変数の凸区分線形格子最適化

二つの整数parameter上の凸区分線形目的について、折れ目直線の交点から連続最小候補を作り、定数半径内に整数最適解があることを証明して有限格子点へ縮約する。

考え方

具体的に、正整数A,Bと定数e_1,…,e_4に対する

F(x,y)=max(|2Bx+e_1|,|2Ay+e_2|)+max(|2Ax+e_3|,|2By+e_4|)

を整数x,y上で最小化する。この係数の交差した形が、有限近傍へ絞る根拠になる。各絶対値とmaxは凸なのでFは凸区分線形であり、A,B>0だから遠方では増大し、最小値が存在する。

折れ目の交点を連続候補にする

折れ目は 2Bx+e_1=±(2Ay+e_2) と 2Ax+e_3=±(2By+e_4) の計四直線である。これらが平面を分け、各領域でFはaffineになる。

領域内部で両maxの選ぶ軸が違うなら、勾配は両座標に非零成分を持ち、最小点にならない。同じ軸なら勾配の大きさは2(A+B)または2|A-B|。A≠Bではやはり0にならない。一本だけの折れ目上でも、そのmaxの勾配は二軸の勾配を結ぶ線分で、もう一方の単一軸の勾配と打ち消せない。したがって二本以上が交わる点が連続最小候補となる。

A=Bでは平坦な領域・線分を持つことがあるが、Fは遠方で増大する。最小点集合の境界をたどると折れ目が交わる頂点へ到達でき、少なくとも一つの交点で最小値を取る。非平行な二直線の交点をすべて列挙してFを評価すれば、連続最小点z=(x_0,y_0)を選べる。同一直線や平行線は交点を作らず、他の組を調べる。

sublevel集合の辺方向を調べる

max(|u|,|v|)=max(u,-u,v,-v) と展開すると、Fは16個のaffine式の最大値になる。両項がxを選ぶ場合の法線はx軸、両項がyを選ぶ場合はy軸。一方がx、他方がyを選ぶ場合は、法線が (±2B,±2B) または (±2A,±2A) となる。

よってsublevel集合 P_K={F≤K} は、x,y,x+y,x-y のそれぞれに上下界を課す凸多角形である。辺の傾きは0,∞,1,−1に限られる。任意の係数を持つ二つのmaxならこの性質は失われる。

整数最適点が距離2以内にある理由

整数最小値をKとする。P_Kはzと少なくとも一つの整数点を含む。その整数点のうちzへのユークリッド距離が最小のqを選ぶ。|q_x-x_0|>2 と仮定し、座標反転により d_x=q_x-x_0>2 としてよい。

qからxを1減らすと、xの下界は破れない(zも満たしており余裕が2より大きい)。破り得るのはx+yまたはx-yの下界だけである。x+yの下界を破るなら、その余裕は1未満なので、zの実行可能性から d_x+d_y<1、つまり d_y=q_y-y_0<1-d_x<-1。

このとき代わりにqを(-1,+1)動かす。x+yは変わらず、yはzへ近付くのでyの上下界を保つ。x-yは2減るが、下界の余裕は少なくとも d_x-d_y>3 なので破れず、上界は改善する。他の制約も保ち、両座標がzへ近付くためqの選び方に矛盾する。

x-yの下界を破る場合は d_y>d_x-1>1 なので、(-1,-1)の移動で同様に矛盾する。どちらも破らなければ(-1,0)だけで距離を減らせる。座標を交換した場合も同じなので、結局 max(|q_x-x_0|,|q_y-y_0|)≤2。q∈P_Kの整数点は最適だから、半径2の近傍に整数最適解がある。

成立条件と計算量

連続最小点zを一つ選び、ceil(x_0-2)≤n≤floor(x_0+2)、ceil(y_0-2)≤m≤floor(y_0+2) の整数点を全評価する。各座標高々5個なので候補は高々25個。交点数も定数だから、この最適化部分はO(1)時間である。

交点は有理数として計算できる。負数のfloor/ceilや平行判定を正しく扱い、境界候補が浮動小数誤差で落ちないようにする。整数解を拡張Euclidで二parameterへ変換する段階があるなら、その費用O(log(A+B))は別に掛かる。

別の関数へ転用するときは、連続最小候補を列挙できることに加え、sublevel集合の法線が上の四方向になることを検査する。凸性だけから距離2は結論できない。この対象式と近傍保証はABC459 G公式解説に対応する。

問題一覧

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

前提・学習成果・出典

習得対象の目安: 橙色(2400–2799)。折れ目直線の交点から連続最小候補を作り、整数最適点が入る有限近傍を証明する。

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

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

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-two-variable-convex-lattice-optimization

習得する技能

  • 二変数の凸区分線形目的について折れ目直線の交点で連続最小候補を求め、定数距離内に整数最適点があることを証明して有限個の近傍格子点だけを評価できる。

前提と範囲

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

直接の前提単元: なし。

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

整数解を二つの自由parameterで表し、折れ目直線の交点から連続最小候補を作る。定数半径の格子点に整数最適解があることを証明して、大域探索を有限近傍の評価へ縮約する。

このUnitでは扱わないもの

  • 一変数の傾き単調性やternary searchだけで解く凸最適化、および連続最小点から整数近傍への保証を持たない一般の格子探索。

根拠