最適化の基礎

最適化の基礎

線形計画法,非線形計画法,組合せ最適化問題を扱う。また,機械学習の重要性に配慮し,データ解析と最適化の関連に言及した。

ジャンル
発行年月日
2018/03/20
判型
A5
ページ数
140ページ
ISBN
978-4-339-02884-3
最適化の基礎
在庫あり

定価

1,980(本体1,800円+税)

カートに入れる

電子版を購入

購入案内

  • 内容紹介
  • まえがき
  • 目次
  • 著者紹介

本書では,線形計画法,非線形計画法,組合せ最適化問題の3種類の最適化を扱うが,大学3年への講義を念頭において,数理計画法におけるシンプレックス法,非線形計画法におけるラグランジュの未定乗数法,組合せ最適化におけるメタ戦略といった代表的な手法はもちろんだが,それらを裏付ける数学的定理についても,過不足なく,過度に詳細な記述にならないように配慮しつつ記述した。特に5章「最適化のデータ解析への応用」は,昨今のビッグデータ解析をはじめとした機械学習における重要性に配慮し,データ解析と最適化の関連を理論面から言及したものとして,本書の大きな特徴となっている。

本書は,筑波大学理工学群工学システム学類3年を対象として開講している「システム最適化」において,筆者らが用いてきたテキストを補筆したものである。1章から3章は遠藤が,4章から6章は宮本が担当した。

最適化の分野は長い歴史をもち,多くの研究が行われている。本書では,線形計画法,非線形計画法,組合せ最適化問題の3種類の最適化を扱うが,これらに関しても,理論面・実用面ともに非常に深化しており,関連文献も数多い。そこで本書では,前述のように大学3年への講義を念頭において,数理計画法におけるシンプレックス法,非線形計画法におけるラグランジュの未定乗数法,組合せ最適化におけるメタ戦略といった代表的な手法はもちろんだが,それらを裏付ける数学的定理についても,過不足なく,過度に詳細な記述にならないように配慮しつつ記述した。特に5章は,昨今のビッグデータ解析をはじめとした機械学習における重要性に配慮し,データ解析と最適化の関連を理論面から言及したものとして,本書の大きな特徴となっている。

本書の章末問題には解答がついていない。これは,講義での演習として出題するため,という理由もあるが,わからなければ何回も本書を読み直して,解けるまで考えてほしいからである。解答がわからないと解く気がしない,ということはあろうが,本書を読めば解ける問題ばかりなので,ぜひ取り組んでほしい。

本書を執筆するにあたり,適切なご助言をいただいただけでなく,執筆の遅れに対して忍耐強く接してくださったコロナ社に心から感謝する。

2018年1月 遠藤靖典・宮本定明

1. 最適化
1.1 「最適化」の意味
1.2 最適化問題の記述
 1.2.1 記号
 1.2.2 最適化問題の記法
 1.2.3 大域的最適解と局所的最適解
 1.2.4 数理計画法
1.3 最適化問題の分類と数学との関連
章末問題

2. 線形計画法
2.1 生産計画問題と栄養問題
2.2 図的解法
2.3 標準形と行列表現
 2.3.1 標準形への変換
 2.3.2 等式標準形の行列形式による表現
2.4 線形計画法の基本定理
 2.4.1 基本定理
 2.4.2 基本定理の幾何学的考察
2.5 シンプレックス法
2.6 2段階法
2.7 双対性
 2.7.1 双対性の基本定理
 2.7.2 双対性の解釈
2.8 内点法
章末問題

3. 非線形計画法
3.1 凸集合と凸関数
3.2 最適化における凸関数の意義
3.3 2次形式
3.4 微分可能な関数の最適性と凸性の判定条件
3.5 制約のある問題における最適性の必要条件
3.6 非線形最適化のための計算法
 3.6.1 非線形方程式の近似解法
 3.6.2 区間縮小法による1次元探索
 3.6.3 最急降下法
章末問題

4. 組合せ最適化問題
4.1 重み付きグラフ
 4.1.1 最短路問題
 4.1.2 最小木問題
 4.1.3 アルゴリズムの考え方
4.2 発見的解法とメタ戦略
 4.2.1 グリーディアルゴリズム
 4.2.2 メタ戦略
 4.2.3 メタ戦略の諸手法
章末問題

5. 最適化のデータ解析への応用
5.1 線形回帰
 5.1.1 回帰直線
 5.1.2 多次元の場合
5.2 主成分分析
5.3 自動分類
 5.3.1 線形分離できない場合
 5.3.2 カーネル関数を用いた非線形分類境界
5.4 クラスター分析
 5.4.1 K-meansと交互最適化
 5.4.2 Fuzzy K-means法
章末問題

6. 補足:NP完全性について

引用・参考文献
索引

遠藤 靖典(エンドウ ヤスノリ)

宮本 定明(ミヤモト サダアキ)