数理最適化

神公開講座

以下めも

東工大の数理最適化テキスト

双対問題

第1回 最適化の概要、連続最適化：無制約最適化1

1-1 最適化問題の着眼点

３つの着眼点

1 何を決めていきたいか？ー決定変数

2 どうするのが理想的か？ー目的変数の最小化or最大化

3 まもるべき条件は何か？ー制約条件

1-2 最適化問題の例１：乗り換え案内

決定変数：各辺を使うか使わないか

目的関数：各辺の重みを足したものを最小化

制約条件：途中で途切れない

1-3 最適化問題の例2：配車計画

各トラックがどの配送先をどの順に訪れるのか

トラックの走行距離の総和を最小化

トラックの積載容量

配送時間帯の指定

運転手の労働条件など

1-4 最適化問題の例3 ：最適設計

コート掛け問題

設計領域をたくさんの小領域に分割し、それぞれの小領域の色を決定する

構造物の設計の過程に最適化を利用する

最適化問題として定式化すればあとはそれを解くだけで良い

それなので、直感では難しい問題でも解けることがある

1-5 最適化問題の例4 ：一変数の場合

最適化では多変数の場合に興味がある

グラフは書けないのが前提

コンピュータを用いて数値的に解く

1-6 最適化問題の分類

・連続最適化

無制約と制約付きがある

・離散最適化

ネットワーク計画、組み合わせ最適化、整数計画がある

1-7 無制約最適化の基本

局所最適解と大域最適解がある

1-8 最適解が同じ最適化問題

習慣上、最大かよりも最小化について考えることが多い

第2回 連続最適化：無制約最適化2

2-1 応用例(回帰分析)

2-2 多変数の場合

等高線から多変数の図について理解する

2-3 勾配とヘッセ行列、テイラー展開

勾配とヘッセ行列を定義する

勾配を縦ベクトルで書く習慣がある

2-4 多変数関数の例

コンピューターでプロットして説明していた

2-5 1次の最適性条件

xが局所最適解だとすると勾配がゼロベクトルとなる

2-6 勾配の意味

勾配は等高線に直交している

増えていく方向のベクトルが勾配

2-7 停留点

xがfの停留点であることと勾配が0になることは必要十分

2-8 対称行列の正定値性

2-9 正定値行列の例

第3回 連続最適化：無制約最適化3

3-1 最適性条件

前回の復習

3-2 2次の最適性条件

牛腸さんが言ってたようなこと

見えないf(x)をP^2と近似して考えればすぐ出る

3-3 最適性判定の例題、2×2行列の正定値性

3-4 最適性判定の例題

計算するだけ

3-5 2次関数の勾配とヘッセ行列

便利なので、覚えておく

計算のテクニック

3-6 数値解法：反復法の枠組み

これからは、最適解をどのように見つけるのか？という話をする

探索方向を決めるのは、いろんなバリエーションがあり、その違いが解法の違いにつながってくる

3-7 最急降下法

探索方向を勾配に-をつけたものにするというのが最急降下法である

3-8 ２次元の例、正確な直線探索

イメージを持つ

最小にするαをαkとするのが正確な直線探索という

3-9 最急降下法のアルゴリズム

3-10 実用的な直線探索

アルミホの条件を満たすαを見つけてαkとするのが実用的な直線探索である

第4回 連続最適化：無制約最適化4

4-1 最急降下法

4-2 最急降下法の例題

イメージを膨らませる

4-3 最急降下法のアルゴリズムの実行例

収束するまで繰り返すとどんなようになるのかをPCで確認する

4-4 最急降下法の長所と短所

最急降下法 + 実用的な直線探索

→x0をどう選んでも局所最適解に収束する

これを大域的収束性という

必ず大域最適解が得られるという意味ではない

どの局所最適解が得られるかは、初期点に依存

収束が遅いという欠点がある

4-5 ニュートン法

次は反復回数をどう小さくするかということを考えていく

最急降下法と探索方向の決め方が異なる

簡単にいうとテイラー展開の２次の項まで見て小さくすることを考えるのがNewton法

最急降下法は一次近似した関数を見ている

ニュートン法は２次近似した関数を見ている

4-6 ニュートン法の例題

4-7 ニュートン法の長所と短所

ニュートン法は収束が早い

二次関数であれば１反復で収束する

ニュートン方程式を解く手間が必要

f(xk+1)が小さくなるとは限らないので局所最適解にすら収束するとは限らない

4-8 降下方向

なんとか正定値にしたいというのが準ニュートン法

第5回 連続最適化：無制約最適化5,制約付き最適化1

5-1 準ニュートン法

最急降下法とニュートン法の良いとこどりをしようとした

fの二階微分をあるBkで近似しようとした

5-2 ヘッセ行列の近似の仕方：正定値対称

Bkを正定値対象とするとdkはfのxkにおける降下方向

5-3 ヘッセ行列の近似の仕方：セカント条件

Bkを単位行列にすると最急降下法になってしまう

5-4 ヘッセ行列の近似の仕方：注意点、BFGS公式

Bk+1を決めるときは、xkとxk+1は既知

上の１と２だけではBk+1は一意には決まらない→様々な公式がある

5-5 準ニュートン法の例、無制約最適化の数値解法の比較

PCで動き方を見る

5-6 収束速度

1次収束と2次収束

5-7 最急降下法の加速法

5-8 制約付き最適化の基本

5-9 等式制約のみの場合

g=0上の点で、目的関数と勾配が同じ向きになっているのが最適解でありそうなことが図を書けばわかる

5-10 ラグランジュの乗数法

これが多制約、多変数のときに同じことが成り立つ

これがラグランジュ乗数法である

第6回 連続最適化：制約付き最適化2

6-1 ラグランジュ乗数法、制約想定

6-2 ラグランジュ乗数法の証明の概略1

陰関数定理を使う

実行可能解の中で少し動いて目的関数値がどのように変化するのかを観察する

6-3 ラグランジュ乗数法の証明の概略2

線形代数の知識を用いる

6-4 不等式制約を持つ場合

6-5 最適性条件の観察

=のときはラグランジュの未定乗数法と同じ

不等号のときは、最適解ではラグランジュ乗数が正のときであると図でわかる

h1とh2がどちらも非有効である場合はh1とh2のgradの一次結合でfが表せるはず

6-6 KKT条件

１〜３の考察で分かったことをまとめてみる

最後の式が等式制約を違う場合

これは有効、非有効から生じている

相補性条件という

非常によく出てくるので重要である

最適解の性質はKKT条件で決まってくる

6-7 ラグランジュ関数

ラグランジュ関数は6-6の式を覚え方とも取れるが、実は双対問題を解くときに使うという深いことがある

6-8 一般の制約付き最適化問題の解法

・逐次2次計画

2次計画問題で、近似することを繰り返す

2次計画問題は後でやる

・内点法：後で線型計画のところでやる

pythonでpyOptを使うなど、現にあるパッケージを使えば良い

自分でアルゴリズムを書く必要はない

第7回 凸計画1

7-1 凸計画の導入

前回は、最適解がKKT条件でかけることが分かった

KKT条件は局所最適解が満たすべき条件であった

一般に大域的最適解の保証は困難であるが

ある性質を満たしているときに保証できることがある

それが凸計画である

大域的最適解を求めやすい問題のクラスである

7-2 凸関数の定義

7-3 凸関数の例

二次関数や、折れ線やその組み合わせ、直線、

三次関数はダメ

7-4 凸関数の特徴づけ

7-5 凸集合

7-6 凸集合の例

全空間や一次不等式何本かで定義される多面体

凸集合の共通部分は凸

7-7 凸計画問題の基本

凸は非線型も含んでいる

7-8 線型計画問題の基本

凸計画問題の一種である

大規模でも容易に解ける

どんなLPも等式標準形に変形できるので、上の形に限定して議論して良い

7-9 等式標準形への変形例

7-10 線型計画問題の実行可能領域と最適解

一般にLPの実行可能領域は多面体で、その最適解はどこかの頂点である

頂点の数は有限個なので、ある頂点から出発して、目的関数が減る方向の隣の頂点に移動することを考える

それを繰り返すと、最適解が求まる

これが単体法と呼ばれる方法

7-11 線型計画問題の例

一次式しか扱えないのは条件が厳しいと思われるが、一見一次式には見えない問題も工夫をして線型計画問題に直すことができる

第8回 凸計画2

8-1 線型計画

要するに線型計画問題に帰着させれば簡単！

8-2 線型計画問題の例：絶対値の和

上界を考えるということをよくやる

8-3 基底追跡

上記は基底追跡という名前の問題

8-4 線型計画問題の例：いくつかの一次関数の最大値

8-5 線型計画問題の例：多面体のChebyshev中心

8-6 CVXPYによる線型計画問題の解き方

8-7 線型計画の双対性

主問題と双対問題は相対的である

というのも双対問題の双対問題は主問題である

8-8 線型計画の強双対性

不等号で双対問題の話をしていたが、実は等号で成り立ち、これを強双対性という

8-9 線型計画の最適性条件

この４つの条件を満たすxとyを見つければ、xは主問題の最適解、yは双対問題の最適解となる

8-10 内点法

どうやって最適解を見つけるのか？

単体法と並んでよく使われる線型計画の解き方

要するに4つの条件を満たす点を見つければ良い

上２行は線型なので、簡単

相補性条件は非線型なので扱うのが難しい

内点法では、扱いにくいところを変形する

μを動かすと、枝分かれしない曲線となることを示すことができる

線形近似を考える

第9回 凸計画3

9-1 ２次計画の基本

二次の目的関数を持っている問題

制約も二次式の時があるが、この講義では制約は一次式とする

Q：n次対称、半正定値

Q=0の場合が線型計画である

二次計画にも双対定理が成り立ち、似たような最適条件や効率よく解ける方法がある

9-2 回帰分析：最小二乗法

二次計画の理論はやらないことにする

今回は二次計画の応用例を考えていく

9-3 回帰分析：RIdge,Lasso解析

9-4 CVXPYによる二次計画問題の解き方

9-5 SVM：基本、直線での分離可能性

9-6 SVM：分離可能な場合

これは二次計画

これを解くことで分離可能なときは二次計画を解けば簡単にSVMが解ける

9-7 SVM：分離不可能な場合

9-8 確率線型計画

パレート最適化という

何を選ぶかは価値観が入ってくる

世の中の多くの決定問題はこのような形式になっている

9-9 半正定値計画

半正定値計画は凸計画となる

9-10 半正定値計画の応用例

固体の釣り合い形状は一般に変分原理により求められる

応力テンソルは常に半正定値→半正定値計画で定式化できる

半正定値計画問題を解くことで変形形状が求められる

このほかにもロバスト最適化、制御、データマイニング、計算化学、非凸な最適化問題の緩和などいろいろ応用がある

第10回 ネットワーク計画1

10-1 最短路問題

今回からは離散的な最適化問題を扱う

10-2 最適性の原理

最短路の途中の路は、その中の最短路

つまり、sから各点までの最短路を近い順に確定していける

10-3 ダイクストラ法1

隣接する点の数字をどんどん更新していく

10-4 ダイクストラ法2

2^nを列挙は無理なので、ダイクストラを使う

10-5 グラフ

10-6 木

木は連結で、閉路を持たないグラフである

連結と閉路は読んで字のごとく

10-7 全域木、カット

Gの全域木はGの部分グラフで、Vの全てを持つ木

全域木の性質として、

・辺は|V-1|

・辺を１本追加すると閉路ができる

・辺を１本取り除くと２つの連結成分に分解する

Gのカットについて

カットは、頂点を２つの集合に分けたときの概念

カットは辺の集合

SとV-Sを繋いでる辺の集合である

10-8 最小全域木

重みの総和が最小の全域木を考える

最小木はある性質を持っており、その性質を使えばこの問題が解決する

Gのカットの重み最小の辺を考える

その重み最小の辺は最小木に含まれる

これが任意のSの選び方について成り立つ

10-9 最小木の性質の証明

全域木に辺を１つ追加すると閉路ができる

閉路のカットを考えると必ず2本以上の辺をとおる

10-10 プリムのアルゴリズム

この性質を利用して最小木問題を解く方法として２つぐらいよく知られた方法がある

１つ目がプリム法である

第11回 ネットワーク計画2、組み合わせ最適化1

11-1 最小木問題

前回の復習

11-2 クラスカルのアルゴリズム

・重みの小さい辺から順に採用

・閉路ができるときはその辺をスキップする

これだけ

Gの中での重みが最小の辺は、必ずどんなカットの中でも重みが最小

どんなカットの中で重みが最小の辺は最小木に含まれるので、これは最小全域木2に入る

このようなアルゴリズムと貪欲法という

良い要素から順に採用して解を構築するのが貪欲法

11-3 NetworkXによるネットワーク計画問題の解き方

NetworkXというPythonのライブラリを使うと、ネットワーク計画問題が簡単に解ける

11-4 階層的クラスタリング

最小木の応用である

似たもの同士のグループに分けることをクラスタリングという

クラスター間の距離を最大化したい

11-5 階層的クラスタリング：クラスカルのアルゴリズムによる解法

実は上記のような問題はクラスカルのアルゴリズムで解ける

11-6 組み合わせ最適化：巡回セールスマン問題

問題

ちょうど一回ずつ通って元に戻る重み最小の閉路は？

これは、N!通りあるのでまず全探索は無理ゲー

11-7 巡回セールスマン問題：貪欲算法の適用例

クラスカルのような貪欲法をやれば最適解が求まるのではないか？と思うが、そうでもない

nearest neighborとよばれるまだ訪れていない最も近い頂点に移動するものは最適解にはならない

巡回セールスマン問題は厳密に解くのは難しい難問題とされている

11-8 巡回セールスマン問題：近似解法

厳密に解くのは難しいので、近似解法を考えていく

仮定として、重みが三角不等式を満たすことを仮定する

11-9 巡回セールスマン問題：近似比

これはある閉路を見つけただけに見えるが、ある精度保証ができる

また、簡単である

より１に近い解法がいくつか考えられている

近似比が2の近似解法のことを2-近似解法という

第12回 組み合わせ最適化の近似解法2、整数計画1

12-1 最遠点クラスタリング

似たもの同士は同じクラスター内＝各くらすたーは小さい

つまりクラスタ内で一番遠い距離の点同士の距離が小さいことを目指す

12-2 最遠点クラスタリング：近似解法(farthest-first traversel)

各クラスターの代表点を順番に決めていくアルゴリズムである

12-3 最遠点クラスタリング：近似比

新しい代表点を作り、最も近い座標点までの距離をδとおく

12-4 最遠点クラスタリング：近似比の説明

気になったら動画を見返す

12-5 ナップサック問題

これは整数計画というものでかける

変数が整数になっている計画問題は整数計画という

12-6 サップサック問題：具体例

厳密解は後でやるが、今は先に近似解法をやる

x^lpは整数計画の解ではないが、一応書いておく

これはある意味貪欲算法である

12-7 ナップサック問題：緩和問題の解

12-8 ナップサック問題：近似解法

そもそもナップサックに入らないものは除外しておく

12-9 整数計画

線型計画+整数制約

x1,,,xnが0か1の時、0-1計画という

0,1に限っても十分表現力がある

連続変数も含むときは、混合整数計画という

12-10 連続緩和問題

実は緩和問題では、厳密解を求めるためにつける

分枝限定法という

第13回 整数計画2

13-1 整数計画

整数計画を解く時の道具として使われるものとして緩和問題がある

13-2 連続緩和問題

離散的なものがあると問題が難しくなるので、0~1の間という風に緩和する

13-3 分枝限定法1

緩和問題を利用する厳密解法

13-4 分枝限定法2

13-5 分枝限定法3

それより下に、最適解があるはずないので調べる必要はない

緩和問題から、調べる範囲を絞ることでしらみつぶしをするのが分枝限定法

13-6 分枝限定法の注意点

・限定操作ができるのかは、分枝をたどる順番に依存する

最終的に解かなければいけない線型計画問題の数は変わる

一般には、小数になる変数は１つだけではない

13-7 ソルバーによる整数計画問題の解き方

整数計画問題は、ソルバーを利用すれば良い

分枝限定法や切除平面法を実装した良いソルバーがたくさんある

13-8 整数計画の応用例：部屋割り問題1

整数計画を使ってどのような問題を表現できるのかを講義して終わりにする

整数計画は、記述能力が高く、組み合わせの性質を持っているいろんな問題を解くことができる

組み合わせ最適化の問題の多くは整数計画をつかって記述することができる

部屋割を決める問題を考える

溢れる人を最小化したい

13-9 整数計画の応用例：部屋割り問題2

数理計画法

組み合わせ最適化

最小木問題、巡回セールスマン問題など

解きやすい問題の場合

→多項式時間アルゴリズムを構築

解きにくい問題の場合

・最適解が必要

→分枝限定法、動的計画法

・ある程度良い解であれば十分

→精度保証付き近似アルゴリズム、ヒューリスティックス

動的計画法：同一の部分問題を繰り返し解かない

分枝限定法：ある部分問題から最適解が得られないことがわかったらその部分問題は無視する

分枝限定法

分枝操作によりたくさんの部分問題が生成

解く必要のない部分問題が検出されたらさらなる分枝操作をストップ

暫定解の保持と緩和問題の利用により無駄をチェック

緩和問題とは、元の数理計画問題の制約条件の一部を緩和して得られる問題

例えば、連続ナップサック問題は線形計画問題なので多項式時間で解ける

緩和問題は元の問題よりときやすく、緩和問題の最適値は元の問題の最適値の上界

緩和問題の最適解を修正することにより元の問題の実行可能解を作ることが可能なケースが多い

分枝限定法の検討事項

・部分問題の探索法

・限定操作のやり方

・分枝操作のやり方

整数計画による定式化入門

ネットワーク最適化

最小木問題

最短路問題

最大流問題

最小費用流問題

割り当て問題

60分で数理最適化

関数解析と最適化

リーマン多様体上の最適化―特異値分解の例を通して―

数理最適化ことはじめ

実務につなげる数理最適化

pulp

Googleの数理最適化ツールOR-Toolsを使ってみる