An Introduction to Optimization: With Applications to Machine Learning（最適化入門：機械学習への応用）

引用

Chong, E. K. P., Lu, W.-S., & Żak, S. H. (2023). An Introduction to Optimization: With Applications to Machine Learning (5th ed.). Wiley.

章の要約

本書は5部31章からなり、約670ページで、参考文献と索引が付く。出版社によれば、各章のあとにはMATLABの演習と練習問題が置かれている。同じく出版社によれば、第5版ではラグランジュ双対性の章が加わり、行列ゲーム、射影勾配法、機械学習の扱いが拡充された。

第I部（第1–5章）：数学の復習

第1章「証明の方法と記法」は、真理値表、ド・モルガンの法則、条件文と双条件文、直接法・対偶・背理法・帰納法による証明、集合の記法をわずか数ページで紹介する。第2章「ベクトル空間と行列」は、ベクトルと行列、階数、連立1次方程式、内積とノルムを扱う。第3章「変換」は、線形変換、固有値と固有ベクトル、直交射影、2次形式、行列ノルムを扱う。第4章「幾何学の概念」は、線分、超平面と線形多様体、凸集合、近傍、多面体を扱う。第5章「微積分の要素」は、数列と極限、微分可能性、導関数行列、微分の規則、等位集合と勾配、テイラー級数を扱う。

第II部（第6–14章）：制約なし最適化

第6章「集合制約付き・制約なし最適化の基礎」は、集合制約付き問題と制約なし問題、および局所的最小点の条件を導入する。第7章「1次元探索法」は、黄金分割法、フィボナッチ法、二分法、ニュートン法、割線法、区間の括り出し、多次元最適化での直線探索を扱う。第8章「勾配法」と第9章「ニュートン法」は、最急降下法とニュートン法を解析とともに示し、レーベンバーグ–マルカート修正と非線形最小2乗法も扱う。第10章「共役方向法」と第11章「準ニュートン法」は、共役勾配法、ランク1修正、DFP法、BFGS法を扱う。第12章「連立1次方程式を解く」は、最小2乗、逐次最小2乗、最小ノルム解、カチマルツ法を扱う。第13章「制約なし最適化とニューラルネットワーク」は、単一ニューロンの学習と誤差逆伝播法を扱う。第14章「大域的探索アルゴリズム」は、ネルダー–ミード法、焼きなまし法、粒子群最適化、遺伝的アルゴリズムを扱う。

第III部（第15–19章）：線形計画法

第15章「線形計画法入門」は、簡単な歴史、簡単な例、2次元の線形計画、凸多面体、標準形、基底解を扱う。第16章「シンプレックス法」は、行基本変形、標準拡大行列、シンプレックス法、行列形式、2段階法、改訂シンプレックス法を展開する。第17章「双対性」は、双対線形計画、その性質、行列ゲームを扱う。第18章「非シンプレックス法」は、ハチヤン法、アフィンスケーリング法、カーマーカー法を扱う。第19章「整数線形計画法」は、単模行列とゴモリの切除平面法を扱う。

第IV部（第20–25章）：非線形制約付き最適化

第20章「等式制約をもつ問題」は、接空間と法空間、ラグランジュ条件、2次条件、線形制約のもとでの2次関数の最小化を扱う。第21章「不等式制約をもつ問題」は、カルーシュ–クーン–タッカー条件と2次条件を扱う。第22章「凸最適化問題」は、凸関数、凸最適化問題、半正定値計画法を扱う。第23章「ラグランジュ双対性」（この版で新設）は、主問題と双対問題の対、双対性の一般的性質、強双対性、凸の場合を扱う。第24章「制約付き最適化のアルゴリズム」は、射影、射影勾配法とその収束、ラグランジュ型アルゴリズム、ペナルティ法を扱う。第25章「多目的最適化」は、パレート解、パレートフロントの計算、単一目的問題への帰着、不確実な線形計画問題を扱う。

第V部（第26–31章）：機械学習における最適化

第26章「機械学習の問題と特徴量エンジニアリング」は、データの正規化、勾配方向ヒストグラム、主成分分析と線形オートエンコーダを扱う。第27章「確率的勾配降下法アルゴリズム」は、確率的勾配降下法と分散低減型の変種を扱う。第28章「線形回帰とその変種」は、最小2乗回帰、交差検証、正則化を扱う。第29章「分類のためのロジスティック回帰」は、2値分類と多カテゴリ分類を扱う。第30章「サポートベクターマシン」は、ヒンジ損失、2値および多カテゴリ分類、カーネルトリックを扱う。第31章「K平均法クラスタリング」は、アルゴリズム、K-means++による初期化、変種、ベクトル量子化による画像圧縮を扱う。

主要概念

第I部：数学の復習

• 証明の方法：直接法、対偶、背理法、帰納法。
• 2次形式：後に2次条件を述べるために使う行列の道具。
• 凸集合と多面体：線形計画法と凸最適化の土台となる幾何。
• 勾配とテイラー級数：局所的最小点の条件の背後にある微積分。

第II部：制約なし最適化

• 局所的最小点の条件：第6章の1次条件と2次条件。
• 最急降下法、ニュートン法、準ニュートン法：反復アルゴリズムの主な系統で、第8–11章で解析により比較される。
• 共役勾配法：2次の問題のために設計され、非2次の問題へ拡張された方法。
• 誤差逆伝播法：ニューラルネットワークの学習のための勾配計算。

第III–IV部：線形・非線形の制約付き最適化

• シンプレックス法と基底解：多面体の頂点の間を移動すること。
• 双対性：線形計画の双対と、新設の第23章では非線形計画のラグランジュ双対。
• カルーシュ–クーン–タッカー条件：不等式制約に対する1次の条件。
• パレートフロント：多目的問題におけるトレードオフ解の集合。

第V部：機械学習

• 確率的勾配降下法：目的関数全体ではなくサンプルから更新すること。
• ロジスティック回帰とサポートベクターマシン：最適化によって学習される分類器。
• K平均法クラスタリング：割り当てと中心の更新を繰り返すクラスタリング。

批判的分析

長所

• 自己完結した準備。 第I部は、最適化の章が始まる前に必要な線形代数、幾何、微積分を復習するので、知識に穴のある読者も本書の中でそれを埋められる。
• 広く整然とした範囲。 1冊で、制約なしの方法から線形計画法、非線形制約付き問題、機械学習まで進む。出版社は、本書を1学期または2学期の学部上級〜大学院初年次の課程向けとして提示している。
• 計算面の支援。 出版社は各章のあとのMATLABの演習と例題を謳っている。著者のページには、アルゴリズムのMファイル、第V部のデータセットとコード、Paul Atzberger とUCSBの学生たちによるいくつかのアルゴリズムのPythonコードへのリンクがある。
• 旧版の書評からの称賛。 裏表紙は、第3版についての MAA Reviews の言葉を引き、本書は読者を学習の道筋に沿って導き、例が明快に述べられ、細部に注意が払われていると述べている。

短所

• 解答集は教員のみ。 解答集は本書を採用した教員だけが入手できるので、独習者は解答なしで取り組むことになる。
• 部分的に深さより幅広さ。 目次からは、いくつかの話題の扱いが簡潔であることがうかがえる。半正定値計画法は第22章の1節にすぎず、整数計画法は3節からなる章である。凸最適化を十分に学びたい読者は、専門の教科書が必要になる。
• ニューラルネットワークは基礎どまり。 第13章（単一ニューロンの学習と誤差逆伝播法）に現れるだけで、機械学習の部には回帰、ロジスティック回帰、サポートベクターマシン、K平均法が挙がっており、深層ネットワークの構造は挙がっていない。
• 1つの課程には長い本。 31章、約670ページあるので、課程では何を省くかを選ぶ必要がある。

コースにおける位置づけ

最適化と応用数学のリストのなかで、Chong、Lu、Żak は標準的なシラバスを扱う一般的な教科書である。Guenin、Könemann、Tunçel の A Gentle Introduction to Optimization は、線形代数の最初の課程だけを前提に、問題の定式化とシンプレックス法に基づく、より穏やかな最初の課程である。Boyd と Vandenberghe の Convex Optimization は、凸問題と双対性が主題になったときの厳密な次の一冊で、本書の第22・23章がその橋渡しになる。

リストの他の本はより広い。Ostaszewski の Advanced Mathematical Methods は線形代数と微積分を応用とともに論じ、Jacques の Mathematics for Economics and Business は最適化を経済の文脈に置き、Goriely の Applied Mathematics: A Very Short Introduction は応用数学者の仕事ぶりについての専門的でない概観である。

本書の使い方

出版社は、本書を最適化の理論と方法についての1学期または2学期の学部上級〜大学院初年次の課程向けとし、数学、オペレーションズ・リサーチ、電気工学、経済学、統計学、経営学の研究者や実務家のための参考書でもあるとしている。当サイトは前提条件として、多変数の微積分と線形代数を挙げている。

実用的な計画は次のとおりである。

• 1学期の課程の中核： 制約なし最適化の第6–11章、線形計画法の第15–17章、制約付き最適化の第20・21章。
• 発展： 現代的な理論へ進む読者のための凸最適化の第22章とラグランジュ双対性の第23章。第12–14章と第18–19章は選択として扱う。
• 機械学習の道筋： 第V部への準備として適切なのは、勾配法、最小2乗、誤差逆伝播法を扱う第6–9章、第12章、第13章である。
• 演習： 著者のページにあるMATLABやPythonのコードを使って演習に取り組む。第I部は通読せず、復習として使う。