【しっかり学ぶ数理最適化】1.1~1.5

2025年後期輪読会 #1 (10/9) しっかり学ぶ数理最適化 1章 京都大学 理学部 数理科学科 3回 千葉 一世 0

数理最適化：制約条件の下で目的関数を最大・最小化する解を求める最適化問題を通じて、 現実社会の問題を解決する手段 現実問題を数理最適化で解くには 最適化問題としての定式化・求解 結果の分析を行い現実的な解決策のために 定式化の再検討を繰り返していく。 例：必要な栄養素を満たしつつ、原料費最安を目指す トマト・人参・ほうれん草をx,y,z個として 最小化 400𝑥 + 250𝑦 + 1000𝑧 制約条件 10𝑥 + 25𝑦 + 30𝑧 ≥ 50 15𝑥 + 5𝑦 + 35𝑧 ≥ 60 5𝑥 + 80𝑦 + 40𝑧 ≥ 40 𝑥, 𝑦, 𝑧 ≥ 0 現実問題としては、美味しさ・品質なども考慮が必要で、他の原料の追加などの検討も 1

(x,y)という形式の二つの値の組のデータから、xとyの関係を近似する回帰問題 𝑦 = 𝑎𝑥 + 𝑏という一次式で表せる仮定して、データとの誤差を2乗誤差で考える場合を 最小二乗法と言い、以下の平均二乗誤差を最小化させる最適化問題になる。 𝑛 1 ෍ 𝑦𝑖 − 𝑎𝑥𝑖 + 𝑏 𝑛 2 𝑖=1 これは、a,bの連続2変数による最小値として解析的に解ける。 𝑛 𝜕𝑓 2 = − ෍ 𝑥𝑖 (𝑦𝑖 − 𝑎𝑥𝑖 − 𝑏) 𝜕𝑎 𝑛 𝑖=1 𝑛 𝜕𝑓 2 = − ෍ (𝑦𝑖 − 𝑎𝑥𝑖 − 𝑏) 𝜕𝑏 𝑛 𝑖=1 偏微分が全て0になる(a,b)を求めて、 このように、数学的に厳密に最適解が求まる場合もあるが、殆どの場合は上手くいかない アルゴリズムや数値計算で求める方法を考えていく。 2

最適化問題を一般的に表すと、目的関数 𝑓 𝑥 と制約条件を満たす集合を 𝑆 として、 最小化問題であれば、 ∀ 𝑥 ∈ 𝑆, 𝑓 𝑥 ∗ ≤ 𝑓 𝑥 を満たす最適解 𝑥 ∗ を求めていく。 変数𝑥の取る値を解・制約条件を満たす解を実行可能解・集合 𝑆 を実行可能領域と言う。 最適化問題を解くことは、一般に実行可能領域内の最適解を一つ見つけることを指すが、 複数存在し得る最適解を全て求めるという列挙問題もある。 制約付き最適化問題：制約条件がある 制約なし最適化問題：制約条件がない (つまりℝ𝑛 全体が実行可能領域など) 最適化問題は常に解けるとは限らず、主に以下の場合がある ① 実行不能：実行可能領域Sが空集合の場合 条件が厳しすぎて、制約を満たすものが一つもない状態 ② 非有界：際限なく大きく・小さくできてしまう場合 ③ 有界だが最適解が存在しない：ある値に限りなく近づけられるが、その値にはできない 数学的にはf(S)が開集合でinf, supは存在するがmin, maxが存在しない状態 ④ 最適解存在：有限値の最適値を取る最適解が存在 3

𝑥+𝑦 >5 2𝑥 + 𝑦 > 10 𝑥 > 0, 𝑦 > 0 𝑥+𝑦 >5 2𝑥 + 𝑦 < 7 𝑥 + 5𝑦 < 15 𝑥𝑦 < 1, 𝑦 < 10 2𝑥 + 𝑦 < 10 𝑥 + 3𝑦 < 15 𝑥 > 0, 𝑦 > 0 4

最適化問題で、最適解が存在しない場合は存在しないことまで示す必要がある。 また、最適解の存在が理論的に保証されていても、最適解を見つけることが困難な場合もある。 例：数学的に連続関数は有界閉区間上最大値・最小値を持つことが保証されており、 微分可能であるならば、増減表を考えて最大・最小値を求める方法まで分かっている。 しかし、 3 𝑥 5 −cos 𝑒 𝑥 +1 sin 𝑥+log 𝑥+2𝑥 など複雑すぎるものは到底計算できない。 最適解が存在しない・発見が困難な場合には、局所最適解を考える場合もある。 局所最適解𝑥 ∗ とは、𝑥 ∗ の近傍に制限した際に、最小・最大になっている解の事 対比的に全体の最適解を大域最適解と呼ぶ (つまり、関数の最小値と極小値の関係) 5

連続最適化：実数値変数など連続的に変化する最適化問題 線型計画問題：線形な目的関数と線形な等式・不等式制約 非線型計画問題：目的関数・制約条件に非線型関数を含む ２次計画問題：目的関数が二次関数で、線形の等式・不等式制約 6

離散最適化：整数・二値変数や、集合・順列・グラフなどの組合せ構造を持った最適化問題 (組合せ最適化) 整数計画問題：整数変数のみの線形計画問題 ２値整数計画問題：２値変数のみの整数計画問題 混合整数計画問題：整数・実数変数を両方含む線形計画問題 ネットワーク最適化問題：ネットワーク・グラフによる最適化問題 7