一次元凸・単峰最適化
概要
値を一つ動かしたときに、目的関数が増えるか減るかを調べる。整数では隣り合う値の差、連続では導関数や二点の値の比較を使い、最小点が残る側へ探索区間を縮める。
考え方
単変数の関数を最小化するとき、値をすべて調べる代わりに「右へ動くと改善するのはどこまでか」を考える。まず探索区間を決め、その区間全体で改善方向が一度だけ切り替わる根拠を示す。凸性はそのための十分条件であり、どんな関数にも二分探索や三分探索を使えるわけではない。
整数では「一つ増やす差額」の符号を探す
説明用の小例として、整数 を で動かし、 を最小化する。隣への差額を と定義すると、次のようになる。最後の点には右隣がないので、差分を定義しない。
| 0 | 1 | 2 | 3 | 4 | |
|---|---|---|---|---|---|
| 4 | 1 | 0 | 1 | 4 | |
| −3 | −1 | 1 | 3 | — |
差分が負なら右隣の方が安く、正なら右隣の方が高い。この例では が非減少なので、一度非負になれば、その先で再び負にはならない。初めて非負になる までは右へ進むほど安く、それ以降は安くならない。従って最小点は2である。関数値そのものは単調ではないが、判定 は単調なので二分探索できる。
一般に、整数区間 上で差分が非減少である性質を離散凸性という。 なら差分を調べる範囲は である。初めて となる位置を探し、見つからなければ を返す。実装では を「該当する差分がない場合の返り値」として扱い、 を評価しない。この手順は最小点のうち最も左のものを返す。
端や同値でも、この規約を変える必要はない。
- 同じ二次関数を に制限すると、最初の差分が既に正なので を返す。
- に制限すると、差分がすべて負なので を返す。
- 零差分は「右へ一つ進んでも費用が変わらない」を意味する。例えば を で考えると、関数値は 、差分は である。最初の非負差分の位置1を返し、最小点は1、2、3である。零差分の区間の右隣の点まで同じ最小値になる。
- なら候補は一点しかない。差分を作らず、その点を返して必要なら関数値を一回評価する。
連続最小点から整数候補を絞る
実数上の凸関数の最小点を とすると、その左では非増加、右では非減少である。そのため整数候補は と に絞れる。探索域が整数区間 なら、域外の候補を除き、端点も比べる。例えば では であり、 と から2を選ぶ。域が なら両候補とも域外で、右端1が最適になる。
ここで必要なのは、丸めた二候補の関数値を比較することである。一般の凸関数は左右対称ではないため、実数最小点に距離が近い整数を選ぶだけでは足りない。また、多変数凸関数を座標ごとに丸めても、総和などの制約や最適性は保証されない。
ABC224 G「Roll or Increment」の解説では、振り直し後に受け入れる出目の個数を として、期待費用を
へ整理する。ここで は一回の加算費用、 は一回の振り直し費用、 はサイコロの面数である。正の実数上の最小点 を求めた後、整数条件と端点に戻るのがこの単元との接続になる。受け入れる範囲への帰着や、振り直さず目標へ進む場合との比較は問題の解説で確認する。
連続三分探索で残す区間
最小点を式で解けなくても、区間 で凸性を示せれば、二点の評価から区間を縮められる。三分点を
とする。 なら最小点を含む を残し、逆なら を残す。例えば前者では二点の間の傾きが負なので、凸性により より左に最小点を探す必要がない。等しい場合も、凸性の下では に最小点がある。
各回で区間長が定数率で減る。整数で三分探索する場合は、区間が狭くなると三分点が同じになり更新が止まるので、残りの少数候補を直接列挙する。差分の符号を判定できるなら、先ほどの二分探索の方が境界を明確に扱いやすい。
凸性より弱い単峰性だけを使う場合は、等値の扱いを別に確認する。例えば値が と並ぶ関数では、途中の二点が等しくても、その間に最小点があるとは限らない。平坦な非最小区間を許して「等しいから中央だけを残す」とすると、最小点を捨てることがある。
ここまでは一つの変数をどこまで増やすかを差分で決めた。分離凸・凹の単調限界値選択では、同じ差分を複数の変数について作る。総資源量が固定されているため、符号で止める代わりに「どの変数の次の一単位が最も安いか」を比べる。
成立条件と計算量
整数区間の幅を とすると、差分二分探索は 回の関数評価で済む。差分の評価に二回の関数評価が必要なら、その費用も含める。連続三分探索は初期幅 を必要幅 まで縮めるのに、 なら 回かかる。関数評価一回の時間を掛けたものが全体の時間であり、探索自体の追加空間は である。必要な関数値の誤差から探索幅や反復数を決め、浮動小数点の丸めにも注意する。
整数では端点・零差分・一点の探索域を、連続では凸性または採用する単峰性の定義と等値時の規則を確認する。二分探索用の差分の単調性も、三分探索で区間を捨てる根拠も、探索する区間全体で必要である。
問題一覧
- ABC224 G「Roll or Increment」 公式問題
技能・出典
主題: 一次元凸・単峰最適化(差分/導関数の単調性または単峰性を証明し、連続解近傍・ternary search・整数境界で最適点を求める。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: 一次元凸・単峰最適化
- ABC314 Ex「Disk and Segments」 公式問題組合せ: 幾何の基本判定と座標変換
技能・出典
主題: 一次元凸・単峰最適化(差分/導関数の単調性または単峰性を証明し、連続解近傍・ternary search・整数境界で最適点を求める。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 幾何の基本判定と座標変換(幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。)。主タグ: 一次元凸・単峰最適化 / 補助タグ: 幾何の基本判定・配置・座標変換
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
関連問題
他の主題と組み合わせる問題を読む
以下はこのUnitのOutcomeを追加で学ぶ技能または既習技能として参照する、別のUnitを主題とする問題です。
- ABC229 G「Longest Y」 公式問題主題: 単調境界を証明して探索する
技能・出典
主題: 単調境界を証明して探索する(判定の単調性を証明し、二分探索の成功側・失敗側を設定できる。)。既習技能: 一次元凸・単峰最適化(差分/導関数の単調性または単峰性を証明し、連続解近傍・ternary search・整数境界で最適点を求める。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: 単調境界探索 / 補助タグ: 一次元凸・単峰最適化
- ABC240 F「Sum Sum Max」 公式問題主題: 整数境界と同値区間を正確に分ける
技能・出典
主題: 整数境界と同値区間を正確に分ける(圧縮block内の一次・二次式や操作列の累積境界を閉形式にし、極値・順位・個数を求められる。)。既習技能: 一次元凸・単峰最適化(差分/導関数の単調性または単峰性を証明し、連続解近傍・ternary search・整数境界で最適点を求める。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: 整数境界・同値区間分割 / 補助タグ: 一次元凸・単峰最適化
- ABC263 G「Erasing Prime Pairs」 公式問題主題: 最大流・最小カット
技能・出典
主題: 最大流・最小カット(選択・排反・closure・頂点容量をcapacity networkへ写し、残余グラフとmax-flow min-cut定理から最適値とcut側を復元する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 一次元凸・単峰最適化(差分/導関数の単調性または単峰性を証明し、連続解近傍・ternary search・整数境界で最適点を求める。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: 最大流・最小カット / 補助タグ: 一次元凸・単峰最適化
- ABC330 F「Minimize Bounding Square」 公式問題主題: 単調境界を証明して探索する
技能・出典
主題: 単調境界を証明して探索する(判定の単調性を証明し、二分探索の成功側・失敗側を設定できる。)。既習技能: 一次元・二次元累積和と差分で区間情報を線形化する(prefix配列またはprefix変数を置き、区間和を二つのprefix値の差で表現できる。多次元の直方体は2^D隅の包除で取得し、一括加算は端点差分へ変換できる。) / 一次元凸・単峰最適化(差分/導関数の単調性または単峰性を証明し、連続解近傍・ternary search・整数境界で最適点を求める。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: 単調境界探索 / 補助タグ: 一次元凸・単峰最適化、累積和・差分配列
- ABC462 E「Alternating Costs」 公式問題主題: 同値な状態を正規化する
技能・出典
主題: 同値な状態を正規化する(対称操作で同値な状態の標準形と不変量を選べる。)。既習技能: 一次元凸・単峰最適化(差分/導関数の単調性または単峰性を証明し、連続解近傍・ternary search・整数境界で最適点を求める。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: 状態・配置の正規化 / 補助タグ: 一次元凸・単峰最適化
前提・学習成果・出典
習得対象の目安: 青色(1600–1999)。単峰性や差分の単調性を証明し、三分探索・整数境界で最適点を求める。
対象色の読み方は本書の読み方を参照してください。
概念上の親: 凸性・傾き・限界費用・slope trick。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。
Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-basic-convex-optimization
一次元凸・単峰最適化
習得する技能
- 差分/導関数の単調性または単峰性を証明し、連続解近傍・ternary search・整数境界で最適点を求める。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
前提と範囲
共通前提: prereq-abc-advanced-v1 (1.0.0)。
直接の前提単元: なし。
このUnitを直接前提とする単元: isotonic regression・PAV、Lagrangian relaxation・Aliens trick、分離凸・凹の単調限界値選択、slope trick。
差分/導関数の単調性または単峰性を証明し、連続解近傍・ternary search・整数境界で最適点を求める。その発動条件と正当化原理を比較可能な独立教材として学ぶ。
このUnitでは扱わないもの
- 一次元凸・単峰最適化の発動条件・不変量を使わず、実装部品だけを偶然共有する解法。