本書旨在介紹常見的非線性最優(yōu)化的理論與算法,以及深度學(xué)習(xí)中的優(yōu)化算法。全書側(cè)重對優(yōu)化原理的直觀理解和優(yōu)化算法的步驟設(shè)計和流程構(gòu)建,并通過大量案例對所介紹的算法進行了編程實現(xiàn)。書中提供的大量編程代碼可以為需要使用非線性最優(yōu)化解決實際問題的工程技術(shù)人員進行二次開發(fā)提供基礎(chǔ),也可以為致力于學(xué)習(xí)最優(yōu)化理論與算法的讀者進行編程練手提供參考。
除第1章介紹的基礎(chǔ)知識外,全書內(nèi)容可以分為4部分。第一部分介紹一維搜索理論與算法,第二部分介紹無約束最優(yōu)化理論與算法,第三部分介紹約束最優(yōu)化理論與算法,第四部分介紹的深度學(xué)習(xí)中的優(yōu)化算法。本書可以作為理工科大學(xué)相關(guān)專業(yè)研究生的學(xué)位課教材,也可以作為數(shù)據(jù)科學(xué)、人工智能、機器學(xué)習(xí)相關(guān)專業(yè)高年級本科生的選修課教材,還可以作為相關(guān)領(lǐng)域?qū)W術(shù)研究人員、工程技術(shù)人員的參考資料。
本書注重優(yōu)化算法設(shè)計,突出算法流程實現(xiàn),并提供大量實踐案例,呈現(xiàn)完整編程實現(xiàn)
最優(yōu)化是運籌學(xué)與控制論二級學(xué)科下的一個重要研究方向,它研究如何在眾多可行方案中找到滿足約束條件的最優(yōu)方案,并計算最優(yōu)方案所需要的成本或收益。本書主要介紹目標函數(shù)和約束函數(shù)均為連續(xù)函數(shù)的非線性最優(yōu)化問題,這類問題在學(xué)術(shù)研究和實際應(yīng)用中普遍存在,學(xué)習(xí)和研究它具有重要的理論意義和應(yīng)用價值。
本書主要內(nèi)容包括四部分。第一部分介紹一維搜索理論與算法,包括第1章和第2章,主要內(nèi)容有試探法、函數(shù)逼近法和非精確線搜索法。一維搜索算法是所有其他搜索算法的基礎(chǔ)。第二部分介紹無約束最優(yōu)化理論與算法,包括第3章和第4章,主要內(nèi)容有無約束最優(yōu)性條件、基于梯度的下降方法和基于函數(shù)值估計的直接法。無約束最優(yōu)化是后續(xù)約束最優(yōu)化的基礎(chǔ)。第三部分介紹約束最優(yōu)化理論與算法,包括第5~8章,主要內(nèi)容有無約束最優(yōu)性條件、可行方向法、罰函數(shù)法和二次規(guī)劃。第四部分介紹深度學(xué)習(xí)中的優(yōu)化算法,包括第9章,深度學(xué)習(xí)中的優(yōu)化方法是最優(yōu)化在近年來的重要新發(fā)展方向,對深度學(xué)習(xí)的發(fā)展有重要的促進作用。
非線性最優(yōu)化是我從碩士到博士,再到參加工作以來一直都在研究的一個領(lǐng)域。在研究生期間,雖然研究得非常深入,但其內(nèi)容僅僅局限于所從事的研究課題,并未從整體上對最優(yōu)化理論與算法進行非常深入的學(xué)習(xí)。參加工作以后,由于開設(shè)課程的需要,我開始全面學(xué)習(xí)非線性最優(yōu)化。我驚訝地發(fā)現(xiàn),非線性最優(yōu)化是如此博大精深,以至于就算窮盡畢生精力也不一定能窺得其全貌,更別說完全掌握了。最優(yōu)化理論與算法無論是對非專業(yè)學(xué)生還是對專業(yè)學(xué)生都有相當難度,主要原因有二,一是它用到了大量綜合性較強的數(shù)學(xué)知識,二是算法設(shè)計和編程實現(xiàn)對邏輯思維和動手能力要求非常高。我先為計算機專業(yè)的研究生開設(shè)了最優(yōu)化理論與算法課程,后來隨著我院數(shù)學(xué)一級學(xué)科開始招研究生,又給數(shù)學(xué)類的研究生開設(shè)了本課程。從教學(xué)的反饋來看,學(xué)生普遍對大量的數(shù)學(xué)推導(dǎo)過程望而卻步,不能直觀地理解定理和算法的精髓,以至于在算法設(shè)計環(huán)節(jié)難以厘清算法邏輯,更別說編程實現(xiàn)了。后來在疫情期間,我又將該課程錄制成視頻,分享到B站,沒想到的是,視頻受到了B站網(wǎng)友的熱烈追捧,很快躍升為同類課程排行榜首位,點擊量超過了30萬次,對于一個非常小眾的課程來講,這算是不小的成就了。究其原因,我認為是因為我在講授中重在通過一些圖形和案例來講解原理,而非滿篇晦澀難懂的證明。同時,我比較注重對算法的實現(xiàn),每種算法都至少通過一個案例進行編程實現(xiàn)。算法的編程實現(xiàn)需要讀者對細節(jié)非常精細地進行理解,這非常有助于初學(xué)者理解理論知識,通過案例實現(xiàn)的方式也讓工程技術(shù)人員真實地看到了優(yōu)化應(yīng)該如何用在工程實踐中。受此鼓舞,我決定再進一步,將我的授課講義整理成書出版,而編寫的思路就是重理解、重實踐、輕證明。
我從2022年暑假開始動筆寫這本書,由于工作比較忙,每天只能在早上和晚上各抽出不到1小時時間來撰寫書稿,進度非常緩慢。后來我受學(xué)校選派,到了涼山州布拖縣地洛鎮(zhèn)依子村從事鄉(xiāng)村振興幫扶工作,駐村工作雖然辛苦,但工作內(nèi)容相對單一,也少了很多雜七雜八的事務(wù),加上騰出了陪伴家人的時間,才有了更多的時間來進行寫作,進度快了許多,所以實際上,本書有70%的內(nèi)容是在偏遠的山區(qū)村落完成的。
要感謝駐村工作這段經(jīng)歷,雖然名義上是去幫扶當?shù)匕l(fā)展,但我在這一段經(jīng)歷中所獲得的遠比我所付出的更多。我和同去的另外兩位學(xué)校同事共同努力,為村上修補了道路,為孩子們裝修了圖書室,為村民修建了飲水灌溉設(shè)施,為村子產(chǎn)業(yè)發(fā)展打造了蔬菜基地,為先天腿疾兒童送去了電動輪椅,為事實無人撫養(yǎng)兒童募捐學(xué)費、生活費。這些工作不僅讓我對中國的農(nóng)村更加了解,也讓我感受到了幫助一個地方發(fā)展和幫助別人解決困難的巨大成就感,更讓我理解了黨中央脫貧攻堅、鄉(xiāng)村振興重大行動的偉大意義。駐村期間,我常常被當?shù)卮迕翊緲愕拿耧L(fēng)所感動,和他們結(jié)下了深厚的友誼,他們見證了我的成長,也見證了這本書的誕生。
要感謝我的恩師吳至友教授,Adil Bagirov教授和在我求學(xué)道路上無私幫助過我的白富生、趙克全、吳昌質(zhì)、杜學(xué)武等教授,是他們成就了現(xiàn)在的我。感謝母校重慶師范大學(xué)的栽培,曾經(jīng)就讀的數(shù)學(xué)科學(xué)學(xué)院如今發(fā)展蒸蒸日上,我等均以畢業(yè)于重慶師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院而自豪,希望有一天學(xué)院也能以培養(yǎng)了我等而驕傲。
要感謝我的本科學(xué)生楊佳鑫同學(xué),本書第9章的內(nèi)容主要來自由我指導(dǎo)的她的本科畢業(yè)論文,她提出的方法現(xiàn)已在國際學(xué)術(shù)期刊上正式發(fā)表,也編入了本書最后一節(jié)。我始終認為能夠碰到幾個優(yōu)秀的學(xué)生是作為老師的一生之幸,而楊佳鑫便是其中之一。感謝本書責(zé)任編輯趙佳霓,她在本書的編寫、校對和排版過程中做了大量細致的工作,沒有她的幫助,本書不可能順利出版。
特別地,要感謝我的家人,尤其是愛妻文靜,在我駐村工作期間,她不僅要全職工作,還要照顧兩個孩子和偶爾負責(zé)我的后勤,這其中的艱辛,我是很難體會的。兩個小天使也是我寫作的強大動力,雖然他們不再像上一本書寫作期間那樣時不時詢問: 爸爸,你的書寫得怎樣了?但是他們用在學(xué)校中的實際表現(xiàn)告訴我: 爸爸,你小心被我們拍在沙灘上哦。為了不那么快地被他們拍在沙灘上,我當然只有一刻也不能停下前進的腳步了。
本書的出版得到了國家自然科學(xué)基金面上項目(項目編號: 12371258)的資助,特此感謝。
最后,由于個人能力有限,書中難免有疏漏之處,還望讀者批評指正,不勝感激。
龍強
2025年1月
于涼山州布拖縣地洛鎮(zhèn)依子村
龍強,博士,副教授,碩士生導(dǎo)師;就職于西南科技大學(xué)數(shù)理學(xué)院數(shù)據(jù)科學(xué)系,中國運籌學(xué)會終生會員;主要從事最優(yōu)化理論與算法、機器學(xué)習(xí)算法研究;在國際國內(nèi)學(xué)術(shù)期刊上發(fā)表論文20余篇,獲批國家發(fā)明專利3項,主持和參與國家自然科學(xué)基金4項,參與國家社會科學(xué)基金1項,出版圖書《深度強化學(xué)習(xí)理論與算法》,講授深度強化學(xué)習(xí)算法設(shè)計與分析最優(yōu)化理論與算法線性代數(shù)與矩陣分析等課程。
趙克全 博士,教授,博士生導(dǎo)師,就職于重慶師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院,中國運籌學(xué)會理事、中國系統(tǒng)工程學(xué)會理事、中國運籌學(xué)會數(shù)學(xué)規(guī)劃分會常務(wù)理事、中國運籌學(xué)會科普工作委員會副主任,重慶市運籌學(xué)學(xué)會秘書長。主要從事最優(yōu)化理論與方法、電力系統(tǒng)運行可靠性的數(shù)學(xué)模型與優(yōu)化算法研究。主持國家重點研發(fā)計劃項目、國家自然科學(xué)基金面上項目等國家級項目6項,主持重慶市高校創(chuàng)新研究群體、重慶英才計劃創(chuàng)新領(lǐng)軍人才等省部級項目11項。講授數(shù)學(xué)分析運籌學(xué)泛函分析最優(yōu)化基礎(chǔ)等課程。
第1章緒論(270min)
1.1最優(yōu)化概述
1.2最優(yōu)化問題的模型及分類
1.2.1最優(yōu)化問題的標準模型
1.2.2最優(yōu)化問題的分類
1.3最優(yōu)化問題舉例
1.4數(shù)學(xué)預(yù)備知識
1.4.1向量范數(shù)
1.4.2方陣范數(shù)
1.4.3序列的極限
1.4.4梯度、海森矩陣、泰勒展式
1.4.5雅可比矩陣、鏈式法則
1.5凸集與凸函數(shù)
1.5.1凸集
1.5.2典型的凸集
1.5.3凸集分離定理
1.5.4凸函數(shù)
1.5.5凸函數(shù)的判定
1.5.6凸函數(shù)的性質(zhì)
1.5.7凸規(guī)劃
第2章一維搜索(306min)
2.1優(yōu)化問題的基本框架
2.2一維搜索的概念
2.3一維優(yōu)化的最優(yōu)性條件
2.4算法的收斂性
2.4.1算法收斂的定義
2.4.2收斂速度
2.4.3實用收斂準則
2.5試探法
2.5.1單峰函數(shù)
2.5.2黃金分割法
2.5.3斐波那契法
2.5.4試探法案例
2.6函數(shù)逼近法
2.6.1牛頓法
2.6.2割線法
2.6.3拋物線法
2.6.4函數(shù)逼近法案例
2.7非精確一維搜索
2.7.1ArmijoGoldstein步長準則
2.7.2WolfPowell步長準則
2.7.3簡單準則和后退法
2.7.4非精確一維搜索案例
第3章無約束優(yōu)化的梯度方法(295min)
3.1無約束優(yōu)化的最優(yōu)性條件
3.1.1下降方向
3.1.2一階必要條件
3.1.3二階必要條件
3.1.4二階充分條件
3.1.5充要條件
3.1.6最優(yōu)性條件應(yīng)用案例
3.2最速下降法
3.2.1最速下降方向
3.2.2最速下降法
3.2.3最速下降法案例
3.2.4最速下降法的收斂性
3.3牛頓法
3.3.1基本原理
3.3.2牛頓法的算法步驟和流程
3.3.3牛頓法的改進
3.3.4牛頓法案例
3.4共軛梯度法
3.4.1共軛方向
3.4.2二次函數(shù)的共軛梯度法
3.4.3一般函數(shù)的共軛梯度法
3.4.4共軛梯度法案例
3.5擬牛頓法
3.5.1對稱秩1(SR1)校正法
3.5.2DFP校正法
3.5.3BFGS校正法
3.5.4擬牛頓法案例
第4章無約束優(yōu)化的直接方法(163min)
4.1探測搜索
4.1.1探測搜索算法
4.1.2探測搜索案例
4.2交替方向法
4.2.1交替方向法原理
4.2.2交替方向法案例
4.3HookeJeeves方法
4.3.1HookeJeeves方法簡介
4.3.2HookeJeeves方法的案例
4.4Rosenbrock方法
4.4.1Rosenbrock方法簡介
4.4.2Rosenbrock方法的案例
4.5Powell方法
4.5.1Powell方法簡介
4.5.2Powell方法的案例
4.6單純形法
4.6.1單純形
4.6.2單純形迭代
4.6.3單純形法停止準則
4.6.4單純形法的算法步驟和流程
4.6.5單純形法的案例
第5章約束優(yōu)化問題的最優(yōu)性條件(311min)
5.1約束優(yōu)化問題最優(yōu)性條件的基本思想
5.1.1下降方向
5.1.2可行方向
5.1.3幾何描述
5.2不等式約束優(yōu)化問題的一階最優(yōu)性條件
5.2.1用積極約束表達的幾何最優(yōu)性條件
5.2.2Fritz John條件
5.2.3KarushKuhnTucker(KKT)條件
5.3一般約束優(yōu)化問題的一階最優(yōu)性條件
5.3.1幾何最優(yōu)性條件
5.3.2Fritz John必要條件
5.3.3KKT必要條件
5.4對偶問題及鞍點最優(yōu)性條件
5.4.1拉格朗日對偶問題
5.4.2對偶定理
5.4.3鞍點最優(yōu)性條件
第6章可行方向法(203min)
6.1Zoutendijk可行方向法
6.1.1線性約束情形
6.1.2非線性約束情形
6.2Rosen梯度投影法
6.2.1投影和投影矩陣
6.2.2Rosen的算法步驟和流程
6.3FrankWolfe方法
6.3.1FrankWolfe方法原理
6.3.2FrankWolfe方法的算法
第7章罰函數(shù)法(164min)
7.1外點罰函數(shù)法
7.1.1基本思想
7.1.2算法原理
7.1.3算法步驟
7.2內(nèi)點罰函數(shù)法
7.2.1基本思想
7.2.2算法原理
7.2.3算法步驟
7.3乘子法
7.3.1算法思想
7.3.2只含等式約束的乘子法
7.3.3只含不等式約束的乘子法
第8章二次規(guī)劃問題(183min)
8.1基本性質(zhì)
8.2只含等式約束的二次規(guī)劃問題
8.2.1變量消去法
8.2.2拉格朗日法
8.3積極約束法
8.3.1基本思想
8.3.2算法原理
8.3.3算法步驟
8.4路徑跟蹤法
8.4.1松弛KKT條件
8.4.2求解松弛KKT條件
8.4.3路徑跟蹤法算法流程
第9章機器學(xué)習(xí)中的最優(yōu)化方法
9.1機器學(xué)習(xí)中的優(yōu)化問題
9.2梯度下降算法
9.2.1標準梯度下降算法
9.2.2隨機梯度下降算法
9.2.3Minibatch梯度下降算法
9.3對搜索方向的改進
9.3.1Momentum算法
9.3.2Nesterov Momentum算法
9.4對學(xué)習(xí)率的改進
9.4.1Adagrad算法
9.4.2RMSprop算法
9.5結(jié)合搜索方向和學(xué)習(xí)率的改進
9.5.1Adam算法
9.5.2Nadam算法
9.5.3Amsgrad算法
9.6NewAdam算法
參考文獻