1. 從“線性”到“非線性”為什么說非線性規(guī)劃是建模的靈魂如果你接觸過數(shù)學(xué)建模大概率是從線性規(guī)劃開始的。目標(biāo)函數(shù)是線性的約束條件也是線性的用單純形法或者內(nèi)點(diǎn)法總能找到一個(gè)最優(yōu)解整個(gè)過程清晰、可控甚至有些“優(yōu)雅”。但當(dāng)你真正面對(duì)一個(gè)實(shí)際的工程、經(jīng)濟(jì)或科研問題時(shí)你會(huì)發(fā)現(xiàn)現(xiàn)實(shí)世界幾乎處處都是“彎”的。成本函數(shù)不是簡(jiǎn)單的單價(jià)乘以數(shù)量它可能包含折扣、規(guī)模效應(yīng)物理規(guī)律里充滿了平方、指數(shù)和對(duì)數(shù)資源分配中投入和產(chǎn)出往往不是簡(jiǎn)單的正比關(guān)系。這時(shí)候線性規(guī)劃那張“直來直去”的網(wǎng)就兜不住這些“彎彎繞繞”的現(xiàn)實(shí)了。非線性規(guī)劃處理的正是這些“彎”的問題。它的目標(biāo)函數(shù)或約束條件中至少有一個(gè)是非線性的。這聽起來只是數(shù)學(xué)形式上的一個(gè)微小變化但帶來的卻是求解難度和理論深度的指數(shù)級(jí)躍遷。線性規(guī)劃的可行域是凸多面體最優(yōu)解總在頂點(diǎn)上我們可以沿著邊界“爬”過去。而非線性規(guī)劃的可行域可能是一個(gè)奇形怪狀的曲面最優(yōu)解可能藏在某個(gè)“山谷”的谷底或者“山脊”的鞍點(diǎn)上你甚至無法確定找到的是局部最優(yōu)還是全局最優(yōu)。可以說從線性到非線性是從“理想實(shí)驗(yàn)室”走向“復(fù)雜現(xiàn)實(shí)世界”的關(guān)鍵一步也是數(shù)學(xué)建模從“解題”到“解決實(shí)際問題”能力躍升的核心標(biāo)志。我見過太多同學(xué)在建模比賽中套用線性模型去擬合明顯非線性的數(shù)據(jù)結(jié)果雖然能跑出個(gè)結(jié)果但解釋力蒼白預(yù)測(cè)效果一塌糊涂。也見過一些有經(jīng)驗(yàn)的建模者一上來就試圖用最復(fù)雜的非線性優(yōu)化器卻因?yàn)閷?duì)問題本質(zhì)理解不深、模型設(shè)置不當(dāng)導(dǎo)致算法不收斂或者陷入局部最優(yōu)的泥潭。非線性規(guī)劃不是工具箱里最炫的那把錘子見到什么都想敲一下它更像是一把需要精心調(diào)試的手術(shù)刀用對(duì)了地方能精準(zhǔn)地剖析問題核心用錯(cuò)了反而會(huì)傷及模型自身。這篇文章我想和你深入聊聊非線性規(guī)劃在數(shù)學(xué)建模中的實(shí)戰(zhàn)應(yīng)用。我們不追求面面俱到的理論推導(dǎo)那是教科書的事而是聚焦于一個(gè)建模者最關(guān)心的幾個(gè)問題我手上的這個(gè)問題到底該不該用非線性規(guī)劃如果用有哪些主流的模型類型和求解思路在具體求解時(shí)那些主流的求解器比如 MATLAB 的fmincon, Python 的SciPy.optimize內(nèi)部到底在干什么我該如何設(shè)置選項(xiàng)才能讓它更聽話更重要的是當(dāng)算法報(bào)錯(cuò)或不收斂時(shí)我該如何像偵探一樣一步步排查問題所在這些經(jīng)驗(yàn)很多是你在標(biāo)準(zhǔn)教材和官方文檔里找不到的卻是在實(shí)戰(zhàn)中決定成敗的關(guān)鍵。2. 問題識(shí)別與模型構(gòu)建什么樣的“彎”值得用非線性規(guī)劃去“掰直”動(dòng)手之前先診斷。不是所有帶平方項(xiàng)的問題都需要?jiǎng)佑梅蔷€性規(guī)劃。構(gòu)建一個(gè)有效的非線性規(guī)劃模型第一步是準(zhǔn)確識(shí)別問題的非線性特征并判斷其復(fù)雜程度。2.1 非線性來源的三大類型根據(jù)我的經(jīng)驗(yàn)建模中的非線性主要來自以下三個(gè)方面它們的處理策略也各不相同第一類本質(zhì)非線性。這是最典型、也最必須使用非線性規(guī)劃的情況。問題的物理、經(jīng)濟(jì)或社會(huì)規(guī)律本身就用非線性方程描述。例如工程優(yōu)化結(jié)構(gòu)設(shè)計(jì)中應(yīng)力與尺寸的關(guān)系如梁的撓度與截面慣性矩呈倒數(shù)或高次方關(guān)系電路設(shè)計(jì)中功耗與電壓、頻率的非線性關(guān)系。經(jīng)濟(jì)學(xué)模型柯布-道格拉斯生產(chǎn)函數(shù)Y A * L^α * K^β其中產(chǎn)出Y與勞動(dòng)力L和資本K是指數(shù)關(guān)系α, β 為彈性系數(shù)。效用函數(shù)也常是非線性的如對(duì)數(shù)效用函數(shù)Uln(c)。數(shù)據(jù)擬合與機(jī)器學(xué)習(xí)當(dāng)你用非線性函數(shù)如指數(shù)衰減y a * exp(-b*x)、S型生長(zhǎng)曲線y L / (1 exp(-k*(x-x0)))去擬合數(shù)據(jù)時(shí)擬合過程本身就是一個(gè)最小化誤差平方和的非線性優(yōu)化問題。對(duì)于這類問題非線性規(guī)劃是唯一的選擇。我們的任務(wù)是把這些自然規(guī)律準(zhǔn)確地翻譯成數(shù)學(xué)語(yǔ)言。第二類由決策邏輯引入的非線性。問題本身可能可以用分段線性或離散模型描述但為了建模或求解的方便我們引入了非線性。最經(jīng)典的例子是固定成本問題。 假設(shè)你要開一家工廠有固定建設(shè)成本F以及可變生產(chǎn)成本c乘以產(chǎn)量x?？偝杀綜(x)是這樣的如果x 0則C F c*x如果x 0則C 0。這是一個(gè)包含“如果-那么”邏輯的非線性關(guān)系。為了在連續(xù)優(yōu)化框架內(nèi)處理它我們常引入一個(gè)0-1變量y和一個(gè)大M值將模型轉(zhuǎn)化為一個(gè)混合整數(shù)線性規(guī)劃。但有時(shí)我們也會(huì)用一些連續(xù)的非線性函數(shù)如光滑的近似函數(shù)來逼近這個(gè)跳躍這就導(dǎo)出了一個(gè)非線性規(guī)劃問題。選擇哪種方式取決于你擁有的求解器和對(duì)精度的要求。第三類“偽”非線性或可線性化的非線性。有些非線性形式可以通過巧妙的數(shù)學(xué)變換轉(zhuǎn)化為線性問題。這是建模中最體現(xiàn)“藝術(shù)性”的地方。比例形式目標(biāo)函數(shù)為(c^T x) / (d^T x)。這看似非線性但如果你令t 1 / (d^T x),y t * x在一定的假設(shè)下如分母恒正可以轉(zhuǎn)化為線性規(guī)劃。這在一些效率評(píng)價(jià)模型如DEA中很常見。多項(xiàng)式目標(biāo)函數(shù)線性約束如果目標(biāo)函數(shù)是二次的而約束是線性的那就是二次規(guī)劃它有非常成熟和高效的專門算法如內(nèi)點(diǎn)法、有效集法通常比通用的非線性規(guī)劃求解器更快更穩(wěn)定。不要把二次規(guī)劃問題盲目地交給通用非線性求解器。提示在構(gòu)建模型前花點(diǎn)時(shí)間分析一下非線性的結(jié)構(gòu)。問問自己這個(gè)非線性是問題固有的還是我引入的它能否通過變量替換、線性化技巧或分段逼近來簡(jiǎn)化這一步的思考可能為你節(jié)省大量的求解時(shí)間和調(diào)試精力。2.2 模型的標(biāo)準(zhǔn)形式與關(guān)鍵要素一個(gè)非線性規(guī)劃模型通常寫成以下形式Minimize f(x) Subject to: g_i(x) ≤ 0, i 1, ..., m (不等式約束) h_j(x) 0, j 1, ..., p (等式約束) x in R^n (決策變量)其中f(x),g_i(x),h_j(x)中至少有一個(gè)是非線性函數(shù)。在構(gòu)建這個(gè)模型時(shí)有幾個(gè)極易踩坑的細(xì)節(jié)決策變量的尺度與范圍這是影響求解器性能的頭號(hào)因素。假設(shè)你的變量x1代表距離可能值在0到1000之間x2代表百分比在0到1之間。它們的數(shù)量級(jí)相差千倍。對(duì)于基于梯度的算法這會(huì)導(dǎo)致 Hessian 矩陣或它的近似的條件數(shù)很大變得“病態(tài)”使得算法收斂極慢甚至數(shù)值不穩(wěn)定。最佳實(shí)踐是在模型內(nèi)部對(duì)變量進(jìn)行縮放讓所有變量都在相近的數(shù)量級(jí)上比如都在[0, 1]或[-1, 1]附近。在求解得到結(jié)果后再縮放回去。約束的寫法與可行性一個(gè)常見的錯(cuò)誤是寫出矛盾的或者過于“緊”的約束使得可行域非常小甚至為空。例如如果你有一個(gè)等式約束h(x) sin(x) cos(x) - 1.5 0但sin(x)cos(x)的值域是[-√2, √2]最大也就約1.414永遠(yuǎn)不可能等于1.5這就導(dǎo)致問題不可行。求解器會(huì)報(bào)錯(cuò)但你可能需要花很長(zhǎng)時(shí)間才能發(fā)現(xiàn)是這個(gè)等式約束“逼死”了模型。對(duì)于非線性約束在建模時(shí)就要心里有數(shù)估算一下約束函數(shù)的大致范圍。初始點(diǎn)的選擇對(duì)于非線性規(guī)劃特別是非凸問題初始點(diǎn)x0的選擇至關(guān)重要。它決定了算法從哪開始“下山”最終會(huì)落入哪個(gè)“山谷”局部最優(yōu)解。一個(gè)好的初始點(diǎn)應(yīng)該盡可能可行至少滿足大多數(shù)約束特別是等式約束。對(duì)于fmincon你可以使用‘InitBarrierParam’或?qū)ｉT的兩階段方法先找一個(gè)可行點(diǎn)?；谖锢砘驑I(yè)務(wù)意義如果你在優(yōu)化一個(gè)工程系統(tǒng)可以用一個(gè)已知的、合理的參數(shù)配置作為起點(diǎn)。多起點(diǎn)策略當(dāng)懷疑問題有多個(gè)局部最優(yōu)解時(shí)一個(gè)非常實(shí)用的技巧是從多個(gè)隨機(jī)初始點(diǎn)分別運(yùn)行求解器然后選擇最好的結(jié)果。這雖然增加了計(jì)算量但能大大提高找到全局最優(yōu)或至少是更好局部最優(yōu)的概率。3. 求解器黑盒揭秘fmincon與scipy.optimize.minimize里發(fā)生了什么大多數(shù)建模者不會(huì)自己去實(shí)現(xiàn)優(yōu)化算法而是調(diào)用成熟的求解器。但把求解器當(dāng)“黑盒”用和了解其內(nèi)部大概的原理并據(jù)此調(diào)整參數(shù)效果天差地別。我們以兩個(gè)最常用的工具為例。3.1 MATLABfmincon算法選擇與核心選項(xiàng)fmincon提供了多種算法默認(rèn)是‘interior-point’內(nèi)點(diǎn)法。選擇哪種算法取決于你的問題特征‘interior-point’(內(nèi)點(diǎn)法)這是目前處理中大規(guī)模非線性規(guī)劃特別是帶有不等式約束最魯棒、最通用的算法之一。它的思想是從可行域內(nèi)部出發(fā)用一個(gè)障礙函數(shù)將約束邊界“推開”形成一條從內(nèi)部通向最優(yōu)解的中心路徑。它對(duì)于病態(tài)問題和初始點(diǎn)選擇相對(duì)不敏感是“開箱即用”的首選。但它的每次迭代計(jì)算量較大?！畇qp’(序列二次規(guī)劃)該方法在每一步迭代中用原問題的拉格朗日函數(shù)的二階近似二次規(guī)劃子問題來尋找搜索方向。它對(duì)于光滑的非線性問題非常有效尤其是當(dāng)最優(yōu)解位于約束邊界上時(shí)收斂速度可能很快。但它對(duì)函數(shù)的平滑性要求高如果梯度或Hessian計(jì)算不準(zhǔn)確例如用數(shù)值差分近似性能會(huì)下降。‘a(chǎn)ctive-set’(有效集法)更適合中小規(guī)模問題或者你知道哪些約束在最優(yōu)解處是“活躍”取等號(hào)的。它顯式地維護(hù)一個(gè)活躍約束集并在該集合確定的子空間內(nèi)搜索。對(duì)于線性約束或接近線性的約束效果很好。關(guān)鍵選項(xiàng)調(diào)試心得OptimalityTolerance(最優(yōu)性容差)和StepTolerance(步長(zhǎng)容差)這兩個(gè)是決定算法何時(shí)停止的主要條件。OptimalityTolerance基于一階最優(yōu)性條件KKT條件的違反程度StepTolerance看迭代點(diǎn)的移動(dòng)距離。如果結(jié)果看起來“差不多”但沒完全收斂可以適當(dāng)放寬這些容差如從1e-6放到1e-4。但要注意放寬太多會(huì)損失精度。MaxIterations(最大迭代次數(shù))和MaxFunctionEvaluations(最大函數(shù)計(jì)算次數(shù))如果求解器因達(dá)到最大迭代次數(shù)而停止首先檢查輸出的迭代信息。如果目標(biāo)函數(shù)值還在明顯下降那就增加這個(gè)限制。如果已經(jīng)很久沒變化了那可能是陷入了局部最優(yōu)或遇到了數(shù)值困難增加迭代次數(shù)也沒用。SpecifyObjectiveGradient和SpecifyConstraintGradient這是性能提升的關(guān)鍵如果你能為目標(biāo)函數(shù)和約束函數(shù)提供解析梯度甚至Hessian求解器的速度和穩(wěn)定性會(huì)有質(zhì)的飛躍。數(shù)值差分默認(rèn)不僅慢而且在變量尺度差異大或函數(shù)不平滑時(shí)誤差很大。在建模階段多花點(diǎn)時(shí)間推導(dǎo)和編碼梯度函數(shù)絕對(duì)是值得的投資。CheckGradients(梯度檢查)當(dāng)你第一次提供自定義的梯度函數(shù)時(shí)務(wù)必開啟這個(gè)選項(xiàng)。求解器會(huì)用數(shù)值差分法和你提供的解析梯度進(jìn)行對(duì)比幫你發(fā)現(xiàn)梯度代碼中的錯(cuò)誤。這是避免“垃圾進(jìn)垃圾出”的重要防線。3.2 Pythonscipy.optimize.minimize方法生態(tài)與適用場(chǎng)景SciPy 的minimize函數(shù)提供了一個(gè)算法“超市”其中處理約束非線性規(guī)劃的主要方法是‘SLSQP’和‘trust-constr’。method‘SLSQP’這是 SciPy 中最常用的序列二次規(guī)劃法實(shí)現(xiàn)。它和 MATLAB 的‘sqp’類似適合中小規(guī)模、光滑的問題。它的接口直觀約束可以分別以字典形式傳入constraints參數(shù)。一個(gè)實(shí)戰(zhàn)技巧是對(duì)于不等式約束g(x) 0SciPy 要求你同時(shí)提供約束函數(shù)fun和它的雅可比矩陣jac即梯度。同樣提供解析雅可比能極大提升性能。method‘trust-constr’這是一個(gè)基于信賴域方法的求解器比SLSQP更魯棒尤其擅長(zhǎng)處理病態(tài)問題和非線性約束。它有兩種子方法‘tr_interior_point’內(nèi)點(diǎn)法和‘eq_interior_point’。如果你的問題用SLSQP難以收斂可以嘗試切換到‘trust-constr’。SciPy 使用中的“坑”與技巧變量邊界minimize的bounds參數(shù)只接受元組列表如[(0, None), (-1, 1)]表示第一個(gè)變量非負(fù)第二個(gè)變量在-1到1之間。None表示無界。務(wù)必正確設(shè)置邊界這能顯著縮小搜索空間幫助求解器。約束字典的格式constraints是一個(gè)字典列表。每個(gè)字典必須有‘type’(‘eq’ 或 ‘ineq’) 和‘fun’。對(duì)于‘ineq’類型fun(x) 0才是標(biāo)準(zhǔn)形式這和你模型中的g(x) 0是相反的你需要做一個(gè)轉(zhuǎn)換constraint_fun lambda x: -g(x)。這是一個(gè)非常常見的錯(cuò)誤來源。回調(diào)函數(shù)callback這是一個(gè)強(qiáng)大的調(diào)試工具。你可以定義一個(gè)回調(diào)函數(shù)在每次迭代時(shí)被調(diào)用打印出當(dāng)前變量值、目標(biāo)函數(shù)值等。這對(duì)于觀察算法進(jìn)展、判斷是否陷入循環(huán)或發(fā)散至關(guān)重要。結(jié)果對(duì)象解析求解返回的result對(duì)象包含豐富信息。result.success是布爾值表示是否成功。result.message會(huì)告訴你終止原因。result.fun是最優(yōu)值result.x是最優(yōu)點(diǎn)。一定要檢查result.success不要只看result.x就以為萬事大吉。4. 實(shí)戰(zhàn)調(diào)試當(dāng)求解器報(bào)警或不收斂時(shí)你的排查清單“求解失敗”是建模常態(tài)。一個(gè)成熟的建模者價(jià)值往往體現(xiàn)在快速定位和解決這些失敗的能力上。下面是我總結(jié)的一個(gè)排查流程你可以像查手冊(cè)一樣對(duì)照使用。4.1 第一步讀懂求解器的“遺言”——終止信息這是診斷的第一步也是最直接的一步。不同的信息指向不同的問題根源?！甃ocal minimum possible’或‘Positive directional derivative’這通常意味著求解器認(rèn)為它找到了一個(gè)駐點(diǎn)梯度為零但無法確認(rèn)是最小值可能是鞍點(diǎn)?；蛘哐刂阉鞣较蚰繕?biāo)函數(shù)不再下降。這強(qiáng)烈暗示1) 初始點(diǎn)不好算法一開始就困在了平坦區(qū)域或鞍點(diǎn)2) 梯度信息可能不準(zhǔn)確如果用的是數(shù)值梯度3) 問題本身非凸且當(dāng)前點(diǎn)是一個(gè)局部駐點(diǎn)但不是全局最優(yōu)。對(duì)策更換初始點(diǎn)提供解析梯度或嘗試多起點(diǎn)策略?！甋olver stopped prematurely’/‘Maximum iterations exceeded’迭代次數(shù)用完了。檢查最終的目標(biāo)函數(shù)值是否還在下降。如果還在快速下降簡(jiǎn)單增加MaxIterations。如果已經(jīng)很久比如最后幾十次迭代變化小于StepTolerance那可能是收斂速度很慢需要檢查變量尺度、或者考慮使用更強(qiáng)大的算法如從SLSQP切換到trust-constr?！瓹onstraints are not satisfied’/‘Infeasible constraints’約束無法滿足。這是最棘手的情況之一。首先手動(dòng)驗(yàn)證你的初始點(diǎn)x0是否滿足約束。用一個(gè)簡(jiǎn)單的腳本計(jì)算所有約束函數(shù)在x0處的值。如果初始點(diǎn)就不可行對(duì)于某些算法如內(nèi)點(diǎn)法可能還能工作但會(huì)困難很多。你需要提供一個(gè)更好的初始點(diǎn)或者放松一些約束如果業(yè)務(wù)允許。其次檢查約束是否可能互相矛盾。對(duì)于非線性約束可以嘗試?yán)L制約束函數(shù)的圖像看看是否存在可行域?！甆aN or Inf function value encountered’在計(jì)算目標(biāo)或約束時(shí)出現(xiàn)了非數(shù)值NaN或無窮大Inf。這通常是因?yàn)樵诘^程中變量值進(jìn)入了函數(shù)的未定義域。例如對(duì)數(shù)函數(shù)log(x)要求x0但算法試探步可能讓x暫時(shí)為負(fù)。解決方法是為變量設(shè)置合理的邊界 (bounds)或者在你的函數(shù)定義中加入保護(hù)性判斷如if x 0: return a_large_penalty_value但這會(huì)引入不連續(xù)可能影響基于梯度的算法。4.2 第二步可視化與敏感性分析——讓問題“現(xiàn)形”對(duì)于中低維度問題變量數(shù) 3可視化是無可替代的調(diào)試工具。繪制目標(biāo)函數(shù)等值線/面對(duì)于二維問題你可以繪制目標(biāo)函數(shù)f(x1, x2)的等值線圖。同時(shí)在圖上畫出約束邊界g(x1,x2)0的線。這樣可行域和最優(yōu)解的可能位置一目了然。你可以把你的初始點(diǎn)x0和求解器返回的“最優(yōu)解”x_opt都標(biāo)在圖上。如果x_opt看起來不在可行域內(nèi)或者遠(yuǎn)離等值線的中心那肯定出了問題。繪制迭代路徑如果你的求解器支持輸出每次迭代的中間點(diǎn)可以通過回調(diào)函數(shù)實(shí)現(xiàn)把這些點(diǎn)連成線畫在等值線圖上。你可以看到算法是如何“行走”的它是直奔山谷而去還是在山脊上徘徊迭代點(diǎn)是否在可行域邊界反復(fù)橫跳這能幫你判斷算法的行為是否正常。單變量敏感性分析對(duì)于多變量問題可以固定其他變量為某個(gè)合理值比如初始點(diǎn)或當(dāng)前解只變化一個(gè)變量觀察目標(biāo)函數(shù)和關(guān)鍵約束的變化曲線。這能幫你理解每個(gè)變量的影響并發(fā)現(xiàn)可能導(dǎo)致函數(shù)值突變或不可行的區(qū)域。4.3 第三步簡(jiǎn)化問題與分步驗(yàn)證——隔離故障當(dāng)問題復(fù)雜時(shí)采用“分治法”先去掉所有約束求解無約束問題用fminunc(MATLAB) 或minimize(method‘BFGS’)(SciPy) 求解。如果能順利求解說明目標(biāo)函數(shù)本身和優(yōu)化算法基本沒問題。如果無約束都求不出來那問題很可能出在目標(biāo)函數(shù)的定義如非光滑、導(dǎo)數(shù)不連續(xù)或尺度上。逐步添加約束先加上簡(jiǎn)單的邊界約束然后加線性約束最后再加非線性約束。每加一步都重新求解。當(dāng)加入某個(gè)約束后求解失敗那么這個(gè)約束就是“嫌疑犯”。集中精力檢查這個(gè)約束的公式和可行性。驗(yàn)證梯度/雅可比矩陣如果你提供了解析導(dǎo)數(shù)務(wù)必用求解器的檢查功能或自己編寫一個(gè)小的有限差分檢查程序?qū)Ρ冉馕鲋岛蛿?shù)值近似值。一個(gè)錯(cuò)誤的梯度會(huì)讓基于梯度的算法完全迷失方向?？s放變量如前所述如果變量尺度差異巨大如x1 ~ 1000,x2 ~ 0.001在求解前進(jìn)行線性縮放x_scaled (x - lb) ./ (ub - lb)或其他方式讓所有變量大致在[0,1]或[-1,1]區(qū)間。在求解器得到x_scaled_opt后再變換回原空間x_opt。5. 超越局部最優(yōu)全局優(yōu)化策略初探非線性規(guī)劃求解器找到的通常是局部最優(yōu)解。對(duì)于非凸問題局部最優(yōu)可能和全局最優(yōu)相差甚遠(yuǎn)。在數(shù)學(xué)建模中尤其是比賽或?qū)嶋H決策中滿足于一個(gè)局部最優(yōu)解可能是危險(xiǎn)的。以下是一些實(shí)用的策略多起點(diǎn)優(yōu)化這是最直接、最常用的啟發(fā)式方法。從多個(gè)幾十個(gè)、上百個(gè)隨機(jī)初始點(diǎn)分別運(yùn)行局部?jī)?yōu)化器然后收集所有找到的局部最優(yōu)解取其中目標(biāo)函數(shù)值最好的那個(gè)。雖然不能保證找到全局最優(yōu)但能顯著提高找到更好解的概率。在 MATLAB 中你可以用GlobalSearch或MultiStart類來自動(dòng)化這個(gè)過程。在 Python 中可以寫一個(gè)循環(huán)結(jié)合numpy.random生成隨機(jī)初始點(diǎn)然后調(diào)用minimize。使用全局優(yōu)化算法對(duì)于變量不多比如小于10維但高度非凸的問題可以考慮專門的全局優(yōu)化算法。例如模擬退火 (simulated annealing)靈感來自冶金學(xué)通過引入“溫度”參數(shù)允許偶爾接受比當(dāng)前解差的解從而有機(jī)會(huì)跳出局部最優(yōu)的“深坑”。SciPy 中有basinhopping函數(shù)它結(jié)合了局部搜索和隨機(jī)跳躍就是一種改進(jìn)的模擬退火。差分進(jìn)化 (differential evolution)這是一種基于種群的隨機(jī)搜索算法不依賴于梯度信息對(duì)函數(shù)的連續(xù)性、可微性要求很低非常適用于復(fù)雜、多峰的函數(shù)。SciPy 的differential_evolution函數(shù)非常強(qiáng)大對(duì)于有邊界約束的問題往往是首選全局優(yōu)化器。遺傳算法 (genetic algorithms)另一種經(jīng)典的種群算法通過選擇、交叉、變異來進(jìn)化解。有很多優(yōu)秀的第三方庫(kù)如DEAP可以實(shí)現(xiàn)。問題重構(gòu)與凸松弛這是一項(xiàng)更高階的技巧。如果可能嘗試將原非凸問題松弛為一個(gè)凸問題。凸問題的局部最優(yōu)就是全局最優(yōu)。求解松弛問題可以得到原問題全局最優(yōu)解的一個(gè)下界對(duì)于最小化問題。這個(gè)下界本身就有價(jià)值同時(shí)松弛問題的最優(yōu)解有時(shí)也能為原問題提供一個(gè)高質(zhì)量的初始點(diǎn)。例如某些特殊的非凸二次約束可以通過半定規(guī)劃SDP進(jìn)行松弛。在實(shí)際建模中我通常采用一種混合策略先使用differential_evolution進(jìn)行全局探索將其找到的最好解作為局部?jī)?yōu)化器如SLSQP或trust-constr的初始點(diǎn)進(jìn)行精細(xì)的局部搜索。這樣既能利用全局算法的逃逸能力又能利用局部算法的高精度和快速收斂性。非線性規(guī)劃是數(shù)學(xué)建模從青澀走向成熟的一道分水嶺。它要求你不僅會(huì)寫方程、會(huì)調(diào)庫(kù)更要理解問題背后的結(jié)構(gòu)懂得與求解器“溝通”具備系統(tǒng)性的調(diào)試和診斷能力。這個(gè)過程充滿挑戰(zhàn)但當(dāng)你成功地將一個(gè)復(fù)雜的現(xiàn)實(shí)問題通過非線性模型刻畫并求解出來那種精準(zhǔn)刻畫世界運(yùn)行規(guī)律的成就感是無可替代的。希望這些從實(shí)戰(zhàn)中摸爬滾打出來的經(jīng)驗(yàn)?zāi)軒湍闵僮咝澛犯孕诺孛鎸?duì)建模中那些“彎彎繞繞”的挑戰(zhàn)。記住每一個(gè)報(bào)錯(cuò)信息都不是終點(diǎn)而是通往更深刻理解的線索。