最優化計算方法是運籌學、計算數學、機器學習和數據科學與大數據技術等專業的一門核心課程。最優化問題通常需要對實際需求進行定性和定量分析,建立恰當的數學模型來描述該問題,設計合適的計算方法來尋找問題的最優解,探索研究模型和算法的理論性質,考察算法的計算性能等多方面。最優化廣泛應用于科學與工程計算、數據科學、機器學習、人工智能、圖像和信號處理、金融和經濟、管理科學等眾多領域。本書將介紹最優化的基本概念、典型案例、基本算法和理論。通過本書的學習,掌握最優化的基本概念,最優性理論,典型的幾類最優化問題(如凸優化,無約束優化,約束優化,復合優化等等)的建模或判別,相關優化問題的基本計算方法,并能熟練調用基于MATLAB或Python等語言的典型優化軟件程序求解一些標準的優化問題,靈活運用所講授的算法和理論求解一些非標準的優化問題。達到鍛煉將實際問題建立合適最優化模型的能力,選擇合適的現有軟件包和算法的能力,遇到沒有現成算法自己實現簡單算法的能力。
//bicmr.pku.edu.cn/~wenzw/optbook.html
內容簡介
它們的主要區別是簡化版中不涉及一些復雜的概念、詳細的例子和證明等等。在第一章簡要介紹最優化基本概念之后,詳細版從四個方面進行講述。
基礎知識:第二章介紹最優化建模和算法中經常需要使用的一些基礎知識,包括范數、導數、凸集、凸函數、次梯度、共軛函數等。此外為了內容的完整性也在附錄部分簡要概述了一些基礎知識,其中線性代數包含矩陣、特征值、廣義逆、SMW公式、Schur補等,數值代數包括范數、方程組求解、矩陣分解、數值代數軟件包等,概率論包含隨機變量、期望、方差、條件期望、概率不等式等重要概念和結論。
優化建模:第三章闡述一些典型的優化建模方法,并以科學工程計算和機器學習中一些典型問題為例介紹如何建立優化模型。第四章給出了最優化問題的一些典型分類和判別技巧,如線性規劃、半定規劃、最小二乘問題、復合優化、矩陣優化、隨機優化等等。一個實際問題根據其側重點可以由不同的優化模型來描述,一種優化模型也可以對應很多不同的實際應用。
最優性理論:第五章介紹最優性理論,包括最優解的存在性和唯一性,無約束可微問題、無約束不可微問題、帶約束優化問題的一階或二階最優性條件,對偶理論,帶廣義不等式(如半定規劃問題)的對偶理論。
最優化算法:第六章介紹無約束優化算法,包括線搜索方法、梯度類算法、次梯度算法、牛頓類算法、信賴域算法、非線性最小二乘法。第七章介紹約束優化算法,包括罰函數法、增廣拉格朗日函數法及其在典型凸優化問題的主問題和對偶問題上的具體應用,線性規劃內點法。第八章介紹復合優化算法,包括近似點梯度法、Nesterov加速算法、近似點算法、分塊坐標下降法、對偶算法、交替方向乘子法、隨機優化算法。
本書主要概念基本配有詳細的例子來解釋。主要優化算法也都通過實際應用問題對算法細節進行詳細闡述,特別是在稀疏優化和邏輯回歸等等問題的典型場景下進行數值試驗,給出最優性度量與迭代步數關系等數值結果,相關程序也可以在本網頁下載。
本書特點
從優化建模和模型分類等不同側面闡述優化問題。考慮到優化問題大多來源于實際問題,本書的詳細版以一定篇幅介紹優化建模中的技術,包括壓縮感知、低秩矩陣恢復、回歸分析、邏輯回歸、支持向量機、相位恢復、字典學習、圖像處理、深度學習、強化學習等等,幫助讀者理解優化問題中每一部分的具體含義。此外,本書也詳細討論了若干種典型優化問題,包括線性規劃、最小二乘問題、復合優化問題、半定規劃、矩陣優化問題、隨機優化問題等等。著重介紹每種優化問題的特點,并列舉出大量的實例。
系統全面地講述了適用于大規模計算的一階優化算法。本書除了介紹一些經典的無約束和約束優化問題的算法外,強化了增廣拉格朗日函數法在凸問題中應用,特別著重講述了帶非光滑結構的復合優化問題的最優性條件和近年來發展起來的一階優化算法及相應理論,包括近似點梯度法、Nesterov加速算法、近似點算法、分塊坐標下降法、對偶算法、交替方向乘子法、隨機優化算法等等。因此,本書問題和算法廣泛覆蓋了常用的光滑和非光滑優化,凸優化和非凸優化,線性和非線性優化,確定性優化和隨機優化。 通過詳細的應用實例和高質量代碼實現強化對問題和算法的理解。本書中應用實例貫穿于各個章節中,在優化建模、優化問題舉例、最優性條件、優化算法章節加入了大量實際例子來幫助讀者理解相關內容。特別地,本書通過前面提到的一些重要實際應用問題對主要優化算法細節進行詳細闡述,在稀疏優化和邏輯回歸等問題的典型場景下進行數值試驗,給出最優性度量與迭代步數關系等數值結果。
統計學是關于可觀測現象的數學建模,使用隨機模型,以及分析數據:估計模型的參數和檢驗假設。在這些注釋中,我們研究了各種評估和測試程序。我們考慮它們的理論性質,并研究各種最優化的概念。
凸優化提供了一個統一的框架,以獲得數據分析問題的數值解決方案,并在充分理解的計算成本下,以可證明的統計保證正確性。
為此,本課程回顧了大數據之后在凸優化和統計分析方面的最新進展。我們提供了新興的凸數據模型及其統計保證的概述,描述了可擴展的數值求解技術,如隨機,一階和原對偶方法。在整個課程中,我們將數學概念運用到大規模的應用中,包括機器學習、信號處理和統計。
在整個課程中,我們將數學概念運用到大規模的應用中,包括機器學習、信號處理和統計。
//www.epfl.ch/labs/lions/teaching/ee-556-mathematics-of-data-from-theory-to-computation/
本課程包括以下主題
第一講:緒論。模型和數據的作用。最大似然公式。估計和預測的樣本復雜度界限。
第二講:計算的作用。優化算法的挑戰。最優測度。結構優化。梯度下降法。梯度下降的收斂速度。
第三講:收斂速度的最優性。加速梯度下降法。全部復雜性的概念。隨機梯度下降法。
第四講:簡潔的信號模型。壓縮傳感。估計和預測的樣本復雜度界限。非光滑優化對優化算法的挑戰。
第五講:近端算子介紹。近端梯度方法。線性最小化神諭。約束優化的條件梯度法。
第六講:時間-數據的權衡。方差減少以改進權衡。
第七講:深度學習的數學介紹。雙下降曲線和過度參數化。隱式規則化。
第八講:非凸優化中的結構。最優的措施。逃避鞍點。自適應梯度方法。
第九講:對抗性機器學習和生成式對抗性網絡(GANs)。Wasserstein GAN。極大極小優化的難點。
第十講: 原對偶優化- i:極大極小問題的基礎。梯度下降-上升法的陷阱。
第十一講: 原對偶優化- ii:額外梯度法。Chambolle-Pock算法。隨機非方法。
第十二講:原對偶III:拉格朗日梯度法。拉格朗日條件梯度法。
矩陣代數是數據分析和統計理論中最重要的數學領域之一。這本書的第一部分為統計中的應用提出矩陣代數的理論的相關方面。本部分從向量和向量空間的基本概念開始,接著介紹矩陣的基本代數性質,然后描述向量和矩陣在多元演算中的解析性質,最后討論線性系統解和特征分析中矩陣的運算。這部分基本上是獨立的。
本書的第二部分開始考慮在統計中遇到的各種類型的矩陣,例如投影矩陣和正定矩陣,并描述這些矩陣的特殊性質。第二部分也介紹了矩陣理論在統計中的一些應用,包括線性模型、多元分析和隨機過程。本部分說明了在本書第一部分中發展的矩陣理論。書的前兩個部分可以作為為統計學生的矩陣代數課程的文本,或作為在線性模型或多元統計的各種課程的補充文本。
這本書的第三部分涵蓋了數值線性代數。它以數值計算的基礎討論開始,然后描述精確和有效的算法因式分解矩陣,求解線性方程組,并提取特征值和特征向量。雖然這本書沒有捆綁到任何特定的軟件系統,它描述并給出了使用數字線性代數的現代計算機軟件的例子。這部分基本上是自包含的,盡管它假設有一些能力用Fortran或C編程和/或使用R/S-Plus或Matlab的能力。書的這一部分可以作為在統計計算中的一門課程的文本使用,或者作為強調計算的各種課程的補充文本。
這本書包括大量的練習,并在附錄中提供了一些解決方案。
James E. Gentle是喬治梅森大學計算統計學教授。他是美國統計協會(ASA)和美國科學促進會的會員。他曾在美國標準局擔任過幾個國家職務并擔任過美國標準局期刊的副主編以及其他統計和計算期刊的副主編。他是隨機數生成和蒙特卡羅方法,第二版,和計算統計元素的作者。
凸優化研究在凸集上最小化凸函數的問題。凸性,連同它的許多含義,已經被用來為許多類凸程序提出有效的算法。因此,凸優化已經廣泛地影響了科學和工程的幾個學科。
過去幾年,凸優化算法徹底改變了離散和連續優化問題的算法設計。對于圖的最大流、二部圖的最大匹配和子模函數最小化等問題,已知的最快算法涉及到對凸優化算法的基本和重要使用,如梯度下降、鏡像下降、內點方法和切割平面方法。令人驚訝的是,凸優化算法也被用于設計離散對象(如擬陣)的計數問題。同時,凸優化算法已經成為許多現代機器學習應用的中心。由于輸入實例越來越大、越來越復雜,對凸優化算法的需求也極大地推動了凸優化技術本身的發展。
這本書的目的是使讀者能夠獲得對凸優化算法的深入理解。重點是從第一性原理推導出凸優化的關鍵算法,并根據輸入長度建立精確的運行時間界限。由于這些方法的廣泛適用性,一本書不可能向所有人展示這些方法的應用。這本書展示了各種離散優化和計數問題的快速算法的應用。本書中所選的應用程序的目的是為了說明連續優化和離散優化之間的一個相當令人驚訝的橋梁。
目標受眾包括高級本科生、研究生和理論計算機科學、離散優化和機器學習方面的研究人員。
//convex-optimization.github.io/
第一章-連續優化和離散優化的銜接
我們提出了連續優化和離散優化之間的相互作用。最大流問題是一個激勵人心的例子。我們也追溯了線性規劃的歷史——從橢球法到現代內點法。最后介紹了橢球法在求解最大熵問題等一般凸規劃問題上的一些最新成果。
第二章 預備知識
我們復習這本書所需的數學基礎知識。這些內容包括多元微積分、線性代數、幾何、拓撲、動力系統和圖論中的一些標準概念和事實。
第三章-凸性
我們引入凸集,凸性的概念,并展示了伴隨凸性而來的能力:凸集具有分離超平面,子梯度存在,凸函數的局部最優解是全局最優解。
第四章-凸優化與效率
我們提出了凸優化的概念,并正式討論了它意味著什么,有效地解決一個凸程序作為一個函數的表示長度的輸入和期望的精度。
第五章-對偶性與最優性
我們引入拉格朗日對偶性的概念,并證明在一個稱為Slater條件的溫和條件下,強拉格朗日對偶性是成立的。隨后,我們介紹了拉格朗日對偶和優化方法中經常出現的Legendre-Fenchel對偶。最后,給出了Kahn-Karush-Tucker(KKT)最優性條件及其與強對偶性的關系。
第六章-梯度下降
我們首先介紹梯度下降法,并說明如何將其視為最陡下降。然后,我們證明了梯度下降法在函數的梯度是連續的情況下具有收斂時間界。最后,我們使用梯度下降法提出了一個快速算法的離散優化問題:計算最大流量無向圖。
第七章-鏡像下降和乘法權值更新
我們推出我們的凸優化的第二個算法-稱為鏡面下降法-通過正則化觀點。首先,提出了基于概率單純形的凸函數優化算法。隨后,我們展示了如何推廣它,重要的是,從它推導出乘法權值更新(MWU)方法。然后利用后一種算法開發了一個快速的近似算法來解決圖上的二部圖匹配問題。
第八章-加速梯度下降
提出了Nesterov的加速梯度下降算法。該算法可以看作是前面介紹的梯度下降法和鏡像下降法的混合。我們還提出了一個應用加速梯度法求解線性方程組。
第九章-牛頓法
IWe開始了設計凸優化算法的旅程,其迭代次數與誤差成對數關系。作為第一步,我們推導并分析了經典的牛頓方法,這是一個二階方法的例子。我們認為牛頓方法可以被看作是黎曼流形上的最速下降,然后對其收斂性進行仿射不變分析。
第十章 線性規劃的內點法
利用牛頓法及其收斂性,推導出一個線性規劃的多項式時間算法。該算法的關鍵是利用障礙函數的概念和相應的中心路徑,將有約束優化問題簡化為無約束優化問題。
第十一章-內點法的變種與自洽
給出了線性規劃中路徑遵循IPM的各種推廣。作為應用,我們推導了求解s-t最小代價流問題的快速算法。隨后,我們引入了自一致性的概念,并給出了多邊形和更一般凸集的障礙函數的概述。
第十二章 線性規劃的橢球法
介紹了凸優化的一類切割平面方法,并分析了一種特殊情況,即橢球體法。然后,我們展示了如何使用這個橢球方法來解決線性程序超過0-1多邊形時,我們只能訪問一個分離oracle的多邊形。
第十三章-凸優化的橢球法
我們展示了如何適應橢球法求解一般凸程序。作為應用,我們提出了子模函數最小化的多項式時間算法和計算組合多邊形上的最大熵分布的多項式時間算法。
這本書的第五版繼續講述如何運用概率論來深入了解真實日常的統計問題。這本書是為工程、計算機科學、數學、統計和自然科學的學生編寫的統計學、概率論和統計的入門課程。因此,它假定有基本的微積分知識。
第一章介紹了統計學的簡要介紹,介紹了它的兩個分支:描述統計學和推理統計學,以及這門學科的簡短歷史和一些人,他們的早期工作為今天的工作提供了基礎。
第二章將討論描述性統計的主題。本章展示了描述數據集的圖表和表格,以及用于總結數據集某些關鍵屬性的數量。
為了能夠從數據中得出結論,有必要了解數據的來源。例如,人們常常假定這些數據是來自某個總體的“隨機樣本”。為了確切地理解這意味著什么,以及它的結果對于將樣本數據的性質與整個總體的性質聯系起來有什么意義,有必要對概率有一些了解,這就是第三章的主題。本章介紹了概率實驗的思想,解釋了事件概率的概念,并給出了概率的公理。
我們在第四章繼續研究概率,它處理隨機變量和期望的重要概念,在第五章,考慮一些在應用中經常發生的特殊類型的隨機變量。給出了二項式、泊松、超幾何、正規、均勻、伽瑪、卡方、t和F等隨機變量。
專注于識別和解決應用中出現的凸優化問題。凸集、函數和優化問題。凸分析基礎。最小二乘、線性和二次規劃、半定規劃、極大極小、極值體積等問題。最優性條件,對偶理論,備選定理,及應用。內點法。應用于信號處理,統計和機器學習,控制和機械工程,數字和模擬電路設計,和金融。
本文采用了一種獨特的機器學習方法,它包含了對進行研究、開發產品、修補和玩耍所必需的所有基本概念的全新的、直觀的、但又嚴謹的描述。通過優先考慮幾何直觀,算法思維,和實際應用的學科,包括計算機視覺,自然語言處理,經濟學,神經科學,推薦系統,物理,和生物學,這篇文章為讀者提供了一個清晰的理解基礎材料以及實際工具需要解決現實世界的問題。通過深入的Python和基于MATLAB/ octave的計算練習,以及對前沿數值優化技術的完整處理,這是學生的基本資源,也是從事機器學習、計算機科學、電子工程、信號處理和數值優化的研究人員和實踐者的理想參考。其他資源包括補充討論主題、代碼演示和練習,可以在官方教材網站mlrefined.com上找到。
本書概述了現代數據科學重要的數學和數值基礎。特別是,它涵蓋了信號和圖像處理(傅立葉、小波及其在去噪和壓縮方面的應用)、成像科學(反問題、稀疏性、壓縮感知)和機器學習(線性回歸、邏輯分類、深度學習)的基礎知識。重點是對方法學工具(特別是線性算子、非線性逼近、凸優化、最優傳輸)的數學上合理的闡述,以及如何將它們映射到高效的計算算法。
//mathematical-tours.github.io/book/
它應該作為數據科學的數字導覽的數學伴侶,它展示了Matlab/Python/Julia/R對這里所涵蓋的所有概念的詳細實現。