1. 從“摸著石頭過河”到“有路可走”Zoutendijk可行方向法的核心思想在優(yōu)化問題的世界里我們常常扮演著探險家的角色。想象一下你站在一個崎嶇不平的山谷中四周是濃霧你的目標是找到最低點。你只能看清腳下很小一片區(qū)域每走一步都要判斷往哪個方向走既能保證自己不掉下懸崖滿足約束條件又能最快地下降高度降低目標函數(shù)值這就是約束優(yōu)化問題的核心困境。而Zoutendijk可行方向法就是為這種困境提供的一套系統(tǒng)性的“探路”策略。它不是一個具體的算法而是一類算法的理論框架其核心思想是在每一步迭代中找到一個方向這個方向不僅能讓你目標函數(shù)值下降還能保證你至少在當前點附近的一小步內(nèi)不會“越界”違反約束。這個方向就叫做“可行下降方向”。為什么這個方法重要因為在工程、經(jīng)濟、機器學習等幾乎所有需要做決策的領(lǐng)域我們面對的問題幾乎都帶有約束。比如設(shè)計一個結(jié)構(gòu)材料用量目標函數(shù)要最小但強度、剛度約束必須達標投資組合要收益最大但風險約束不能超過某個閾值。早期的很多方法比如罰函數(shù)法是把約束“軟化”通過懲罰項把約束問題轉(zhuǎn)化為無約束問題但這容易導致數(shù)值不穩(wěn)定或者解不精確?？尚蟹较蚍▌t不同它從一開始就尊重約束的“硬邊界”試圖在可行域的“圍墻”內(nèi)找到一條通往最優(yōu)點的路徑。Zoutendijk在1960年系統(tǒng)性地提出了尋找這類方向的條件和算法框架使得“可行方向法”從一種直覺變成了一套可以嚴格分析和實現(xiàn)的數(shù)學工具。簡單來說Zoutendijk可行方向法回答了兩個關(guān)鍵問題第一在給定點什么樣的方向才是“合法”的可行下降方向第二如何系統(tǒng)地找到這樣的方向理解了這兩個問題你就抓住了這個方法的靈魂。它不是最快的也不是萬能的但在處理中等規(guī)模、非線性程度較高的約束問題時它提供了一種直觀且理論上可靠的思路。接下來我們就深入這個“探路”過程看看每一步具體是怎么走的。2. 可行下降方向的數(shù)學定義什么方向才是“好”方向要理解Zoutendijk可行方向法必須先嚴格定義什么是“可行下降方向”。這不僅僅是字面意思而是有精確的數(shù)學刻畫。我們考慮一個一般的非線性規(guī)劃問題最小化 f(x) 滿足于 g_i(x) ≤ 0, i 1, 2, ..., m h_j(x) 0, j 1, 2, ..., p其中x 是決策變量向量f(x) 是目標函數(shù)g_i(x) 是不等式約束h_j(x) 是等式約束。假設(shè)我們現(xiàn)在位于一個可行點 x_k即滿足所有約束的點。我們想找一個移動方向 d_k。這個方向要滿足兩個基本要求1. 可行性要求至少局部可行沿著方向 d_k 走一個足夠小的步長 α 0新點 x_k α d_k 仍然滿足所有約束。注意這里強調(diào)的是“局部”和“足夠小”。對于等式約束 h_j(x)0這要求方向 d_k 必須與約束曲面的切平面平行即 ?h_j(x_k)^T d_k 0。對于在 x_k 處“起作用”的不等式約束即 g_i(x_k) 0 的那些約束方向 d_k 不能指向約束外部即 ?g_i(x_k)^T d_k ≤ 0。對于那些 g_i(x_k) 0 的約束由于點在內(nèi)點稍微移動一下通常不會立刻越界所以暫時沒有嚴格要求。滿足這些條件的方向稱為在 x_k 處的可行方向。2. 下降性要求沿著方向 d_k 走目標函數(shù)值應(yīng)該減少。從一階泰勒展開來看這要求目標函數(shù)在該方向的導數(shù)即方向?qū)?shù)為負?f(x_k)^T d_k 0。同時滿足以上兩個條件的方向 d_k就稱為在點 x_k 處的可行下降方向。這里有一個非常關(guān)鍵且容易混淆的概念起作用約束集。在點 x_k我們把所有等式約束和所有取等號的不等式約束即 g_i(x_k)0的集合稱為起作用約束集。尋找可行方向時主要需要考慮的就是這些起作用約束因為它們像“墻壁”一樣擋在了當前點的邊界上。那些嚴格滿足的不等式約束g_i(x_k) 0當前點離它們的邊界還有距離在尋找方向時暫時可以“忽略”這大大簡化了問題的復雜度。注意在實際數(shù)值計算中判斷一個約束是否“起作用”需要設(shè)置一個容差ε。因為浮點數(shù)計算有誤差我們通常認為當 |g_i(x_k)| ε 時該約束就是起作用的。這個ε的選擇很關(guān)鍵太小會漏掉一些臨界約束太大會把無關(guān)約束加進來影響方向搜索的效率。通常ε取 1e-6 到 1e-8 之間需要根據(jù)問題的尺度調(diào)整。那么如何系統(tǒng)地找到一個滿足 ?f(x_k)^T d_k 0 且對于所有起作用約束有 ?g_i(x_k)^T d_k ≤ 0, ?h_j(x_k)^T d_k 0 的方向呢這引出了下一個核心環(huán)節(jié)通過求解一個子優(yōu)化問題來生成這個方向。3. 方向?qū)ふ易訂栴}把找方向轉(zhuǎn)化為另一個優(yōu)化知道了好方向的標準下一步就是如何計算它。Zoutendijk法的巧妙之處在于它將“尋找可行下降方向”這個問題本身轉(zhuǎn)化為了一個線性或二次規(guī)劃問題來求解。這是整個算法的計算核心。最經(jīng)典的一種構(gòu)造方法是利用線性近似。在當前迭代點 x_k我們將目標函數(shù)和起作用約束進行一階泰勒展開我們希望 ?f(x_k)^T d 0 下降對于起作用的不等式約束 i ∈ I_k (I_k是起作用集)希望 ?g_i(x_k)^T d ≤ 0 可行對于等式約束 j希望 ?h_j(x_k)^T d 0 可行為了得到一個良定的優(yōu)化問題我們通常不會直接要求 ?f(x_k)^T d 0而是希望這個內(nèi)積盡可能小即下降得盡可能快。同時為了處理約束的可行性我們引入一個松弛變量。這就形成了著名的Zoutendijk可行方向法子問題也稱為線性化方向?qū)ふ覇栴}最小化 z 滿足于 ?f(x_k)^T d ≤ z ?g_i(x_k)^T d ≤ z, 對于所有 i ∈ I_k ?h_j(x_k)^T d 0, 對于所有 j -1 ≤ d_l ≤ 1, l 1, 2, ..., n (規(guī)范化約束防止方向向量無限大)其中z 是一個輔助變量代表了“不可行度”或“上升度”的一個上界。我們最小化 z就是希望所有起作用約束的線性化違反量?g_i^T d和目標函數(shù)的上升量?f^T d的最大值盡可能小最好是負數(shù)。對這個子問題的解讀如果求得的最優(yōu)值 z_k* 0那么至少存在一個方向 d_k*使得 ?f(x_k)^T d_k* ≤ z_k* 0且對于所有起作用約束 ?g_i(x_k)^T d_k* ≤ z_k* 0。這意味著 d_k* 不僅是一個下降方向?f^T d 0而且對于所有起作用約束它都是一個“嚴格可行”方向?g_i^T d 0。注意即使對于 ?g_i^T d 0 的約束沿著 d 走也不會立即違反它二階項才會起作用但通常我們會認為 z_k* 0 時得到的才是“好用”的方向。如果求得的最優(yōu)值 z_k* 0那么說明找不到一個能同時讓目標函數(shù)和所有起作用約束都得到改善即值變小的方向了。這個時候當前點 x_k 很可能已經(jīng)滿足一階必要條件即Kuhn-Tucker條件是一個駐點可能是局部最優(yōu)點。算法可以在此停止。求解這個線性規(guī)劃問題我們就能得到一個候選方向 d_k。這個子問題規(guī)模不大變量是d和z約束是起作用的那些約束加上規(guī)范化約束可以用標準的線性規(guī)劃算法如單純形法高效求解。這是Zoutendijk法在計算上的一個優(yōu)勢。實操心得在編程實現(xiàn)時規(guī)范化約束-1 ≤ d_l ≤ 1非常重要。沒有它如果目標函數(shù)梯度?f和約束梯度線性相關(guān)子問題可能產(chǎn)生無界解即讓d的模長趨于無窮來使z趨于負無窮這在數(shù)值上是沒有意義的。規(guī)范化約束將搜索方向限制在一個超立方體內(nèi)保證了子問題總有有限解。也有人使用球形約束 ||d|| ≤ 1但線性約束更容易被線性規(guī)劃求解器處理。4. 步長選取策略走多遠才算合適找到了一個可行的下降方向 d_k就像知道了該往哪個方向邁步。接下來最關(guān)鍵的問題是這一步該邁多大步長 α 的選擇是迭代優(yōu)化算法的靈魂直接影響到收斂速度和穩(wěn)定性。在可行方向法中步長選取必須兼顧兩點充分下降和保持可行。1. 充分下降目標函數(shù)減少我們希望步長 α 能使目標函數(shù)值有足夠的下降通常采用Armijo型線搜索或其變種。即尋找一個 α使得f(x_k α d_k) ≤ f(x_k) c1 * α * ?f(x_k)^T d_k其中c1 是一個小常數(shù)通常取 1e-4 左右。這個條件被稱為“充分下降條件”它保證了每一步迭代函數(shù)值下降的量至少是線性預測下降量α ?f^T d的一個比例。由于 ?f^T d 0這確保了下降。2. 保持可行不違反約束這是約束優(yōu)化區(qū)別于無約束優(yōu)化的關(guān)鍵。步長 α 必須保證新點x_{k1} x_k α d_k仍然在可行域內(nèi)。由于我們的方向 d_k 是基于線性近似找到的可行方向它只能保證在無窮小的步長下是可行的。對于有限的步長非線性約束可能會被違反。因此我們需要一個可行性線搜索。最常用的方法是最大可行步長搜索。即找到滿足所有約束的最大步長 α_maxα_max sup { α 0 | g_i(x_k α d_k) ≤ 0, h_j(x_k α d_k) 0, 對于所有 α ∈ [0, α] }然后在實際的步長選擇中我們?nèi)ˇ? min(α_max, α_s)其中 α_s 是通過充分下降條件確定的步長。有時為了保守起見會再乘以一個安全系數(shù) β (比如0.9或0.99)即α β * min(α_max, α_s)。如何計算 α_max對于每個約束我們都可以近似地求解方程g_i(x_k α d_k) 0來得到一個臨界步長 α_i。對于等式約束則是|h_j(x_k α d_k)| δδ是一個小容差。所有這些臨界步長中的最小值就是 α_max 的估計。在實際操作中我們通常使用回溯法從一個初始步長如1或由二次插值估計的步長開始不斷乘以一個衰減因子如0.5直到新點滿足所有約束。踩坑實錄步長選取是可行方向法最容易出問題的地方。我曾在處理一個化學過程優(yōu)化問題時因為約束函數(shù)非?！岸盖汀卑礃藴蔄rmijo搜索得到的步長雖然滿足了充分下降條件但迭代點總是“撞”到約束邊界上導致后續(xù)方向?qū)ふ易訂栴}變得病態(tài)梯度幾乎平行算法停滯。后來改為兩階段搜索先做一個快速的可行性回溯找到一個滿足所有約束的步長上界 α_feasible然后在這個區(qū)間 [0, α_feasible] 內(nèi)再進行標準的Armijo-Wolfe條件搜索尋找最優(yōu)步長。這樣雖然每次迭代成本稍高但穩(wěn)定性和收斂性大大提升。另一個常見問題是當?shù)c非常接近約束邊界時最大可行步長 α_max 可能非常小導致進展緩慢。這時算法實際上是在沿著邊界“蠕動”。這正是算法接近最優(yōu)解通常是邊界上的點的征兆。此時檢查方向?qū)ふ易訂栴}的解 z_k* 是否接近零是判斷收斂的一個好方法。5. 算法流程與收斂性從理論到實踐的閉環(huán)將方向?qū)ふ液筒介L選取組合起來就得到了Zoutendijk可行方向法的基本算法框架。讓我們梳理一下一個完整的迭代步驟算法步驟初始化給定一個初始可行點 x_0設(shè)置迭代計數(shù)器 k0收斂容差 ε 0。確定起作用約束集在當前點 x_k識別所有等式約束和滿足 |g_i(x_k)| ≤ ε 的不等式約束構(gòu)成起作用約束集 I_k。求解方向?qū)ふ易訂栴}構(gòu)建并求解上一節(jié)所述的線性規(guī)劃子問題得到最優(yōu)方向 d_k 和最優(yōu)值 z_k*。收斂性檢查如果 |z_k*| ε則算法終止x_k 被視為一個近似駐點。否則繼續(xù)。步長搜索沿方向 d_k 進行受約束的線搜索找到一個步長 α_k 0使得新點 x_{k1} x_k α_k d_k 滿足可行性x_{k1} 是可行點。充分下降滿足Armijo條件或類似的下降條件。更新迭代點令 x_{k1} x_k α_k d_k k k1返回步驟2。收斂性分析Zoutendijk法的收斂性理論是優(yōu)美的但前提是滿足一些條件。在一定的約束規(guī)格下如MFCQ約束品性如果算法產(chǎn)生的迭代點列有極限點那么這個極限點必然滿足一階最優(yōu)性條件KKT條件。簡單來說如果算法能一直找到可行的下降方向并不斷下降最終“無路可走”z_k* → 0時找到的點就是臨界點。然而理論上的收斂不等于實踐中的高效。這里有三個常見的實踐陷阱Maratos效應(yīng)這是一個經(jīng)典現(xiàn)象。當最優(yōu)解位于約束邊界上且目標函數(shù)的等高線在邊界處曲率很大時單純沿可行下降方向走即使步長很小也可能導致新點嚴重違反約束因為線性近似誤差大。這會導致可行性回溯步長極小算法進展如蝸牛。解決Maratos效應(yīng)需要引入二階校正步即在得到主迭代點后沿一個近似切向的方向做一個小的校正以重新拉回到可行域并保持超線性收斂速率。這類似于SQP序列二次規(guī)劃的思想。起作用約束集的識別錯誤由于浮點誤差錯誤地將一個非起作用約束納入I_k或漏掉一個起作用約束會導致尋找的方向根本不可行或者錯過真正的下降方向。穩(wěn)健的實現(xiàn)必須有一個可靠的、基于容差的起作用集識別策略并且在迭代中可能需要動態(tài)調(diào)整這個容差。子問題的不可行或退化方向?qū)ふ易訂栴}本身可能無解盡管在約束品性下通常有解或者解不唯一退化。這需要求解器具有良好的數(shù)值穩(wěn)定性并且算法要有應(yīng)對策略比如輕微擾動梯度或引入正則化項。在我實現(xiàn)的幾個求解器中一個提升魯棒性的技巧是采用“彈性模式”。當標準方向?qū)ふ易訂栴}無解或求解困難時暫時放寬可行性要求在子問題的約束中引入彈性變量并加以懲罰先求得到一個“大致可行”的下降方向把迭代點拉到一個更好的區(qū)域再恢復嚴格模式。這相當于在“死胡同”里給自己一個臨時的小出口。6. 與其他約束優(yōu)化方法的對比何時該用可行方向法優(yōu)化算法工具箱里有很多工具Zoutendijk可行方向法只是其中之一。了解它的長處和短處才能知道在什么場景下該用它。我們把它和幾個主流方法做個對比。1. 與罰函數(shù)法/增廣拉格朗日法對比罰函數(shù)法將約束 violation 作為懲罰項加到目標函數(shù)中轉(zhuǎn)化為無約束問題。優(yōu)點是概念簡單可以利用成熟的無約束優(yōu)化算法。缺點是懲罰參數(shù)需要精心選擇太小則約束不被尊重太大則問題病態(tài)數(shù)值困難。且最終解可能只是近似可行。增廣拉格朗日法比純罰函數(shù)法更優(yōu)通過引入拉格朗日乘子估計降低了懲罰參數(shù)的需要收斂性更好。可行方向法 vs 它們可行方向法從始至終保持迭代點的可行性這對于某些“硬約束”如物理限制、安全邊界絕對不能違反的場景是巨大優(yōu)勢。罰函數(shù)類方法在迭代中間點可能是不可行的。然而可行方向法需要每一步都求解一個子優(yōu)化問題線性/二次規(guī)劃計算成本通常高于一次無約束優(yōu)化迭代。當約束很多時識別起作用集和求解子問題可能成為瓶頸。2. 與序列二次規(guī)劃SQP對比SQP當前最強大的非線性約束優(yōu)化方法之一。它在每一步迭代中利用目標函數(shù)和約束的二階信息Hessian矩陣構(gòu)造一個二次規(guī)劃子問題同時求解下一步的迭代方向和拉格朗日乘子更新。具有超線性收斂速度。可行方向法 vs SQPZoutendijk法通常只利用一階信息梯度可以看作是SQP的一階近似簡化版。SQP的二次規(guī)劃子問題比可行方向法的線性規(guī)劃子問題包含更多信息因此收斂更快、更穩(wěn)健尤其是接近解時。但SQP需要計算或近似二階導數(shù)實現(xiàn)更復雜每個子問題求解成本也更高?？尚蟹较蚍▽崿F(xiàn)更簡單對于中等規(guī)模、導數(shù)計算成本高的問題有時是一個不錯的折中選擇。3. 與內(nèi)點法對比內(nèi)點法通過引入障礙函數(shù)迫使迭代點始終在可行域內(nèi)部并從內(nèi)部逼近邊界上的最優(yōu)解?，F(xiàn)代內(nèi)點法非常強大尤其對于大規(guī)模稀疏問題。可行方向法 vs 內(nèi)點法可行方向法是“邊界巡游”法迭代點可以在可行域內(nèi)部也可以在邊界上。內(nèi)點法則始終在內(nèi)部。對于最優(yōu)解在邊界的問題內(nèi)點法需要迭代很多步來無限接近邊界而可行方向法可以早早地“貼”著邊界走。內(nèi)點法在處理不等式約束時非常統(tǒng)一而可行方向法需要顯式處理起作用集。對于問題規(guī)模非常大時內(nèi)點法因其多項式時間復雜度和處理稀疏性的能力往往更受青睞。適用場景總結(jié)考慮使用Zoutendijk可行方向法問題規(guī)模中等變量和約束在幾百到幾千量級。函數(shù)和約束的梯度可計算但二階導數(shù)難以獲得或計算代價高。保持迭代點可行性至關(guān)重要例如在線控制、實時優(yōu)化。需要一個相對簡單、易于理解和實現(xiàn)的算法原型。可能不適合超大規(guī)模稀疏問題考慮內(nèi)點法或現(xiàn)代SQP。需要極高收斂速度的問題考慮利用二階信息的SQP或內(nèi)點法。約束非常復雜或非光滑導致可行方向難以定義或?qū)ふ摇?. 一個數(shù)值案例手把手實現(xiàn)與調(diào)試理論說得再多不如看一個實際的例子。我們考慮一個經(jīng)典測試問題——Rosenbrock函數(shù)帶圓盤約束最小化 f(x, y) (1-x)^2 100*(y-x^2)^2 滿足于 g(x, y) x^2 y^2 - 2 ≤ 0初始點取可行域內(nèi)的 (0.5, 0.5)。目標是最小化Rosenbrock函數(shù)其無約束最優(yōu)解在(1,1)但該點不滿足約束約束是一個半徑為√2的圓盤。手動迭代幾步理解過程初始點 x0 (0.5, 0.5):f (0.5)^2 100*(0.5-0.25)^2 0.25 100*0.0625 6.5。g 0.250.25-2 -1.5 0約束不起作用。梯度?f (-2*(1-x) - 400x(y-x^2), 200*(y-x^2)) ( -1 - 4000.5(0.5-0.25), 200*(0.5-0.25) ) ( -1 - 50, 50 ) (-51, 50)。?g (2x, 2y) (1, 1)。起作用集 I {} (空集因為g0)。方向子問題簡化為最小化 z滿足 ?f^T d ≤ z且 -1 ≤ d_x, d_y ≤ 1。由于沒有起作用約束最優(yōu)方向就是負梯度在規(guī)范化盒子上的投影。為最小化 ?f^T d -51d_x 50d_y應(yīng)讓d_x盡可能大d_y盡可能小。在[-1,1]限制下取 d0 (1, -1)。此時 z0* ?f^T d0 -511 50(-1) -101 0。這是一個下降方向。步長搜索沿 d0(1,-1) 搜索。需要保證新點可行g(shù)(x0α d0) (0.5α)^2 (0.5-α)^2 - 2 ≤ 0。化簡得 2*(0.25 α^2) - 2 0.5 2α^2 - 2 2α^2 - 1.5 ≤ 0 α^2 ≤ 0.75 α ≤ √0.75 ≈ 0.866。這是最大可行步長 α_max。同時進行Armijo搜索。從α1開始但1 0.866不可行?；厮莸溅?.866檢查下降條件。計算 f(x00.866*d0)f(1.366, -0.366) ≈ 很大因為y遠偏離x^2。可能不滿足充分下降條件。需要更精細的線搜索在[0, 0.866]內(nèi)找到滿足Armijo條件的步長。假設(shè)我們通過回溯找到 α0 0.5。新點 x1 (0.5, 0.5) 0.5*(1, -1) (1.0, 0.0)。第一次迭代后 x1 (1.0, 0.0):f 0 100*(0-1)^2 100。g 1 0 - 2 -1 0仍不起作用。?f (-2*(0) - 4001(0-1), 200*(0-1)) (400, -200)。?g (2, 0)。起作用集 I 仍為空。方向子問題最小化 z滿足 400d_x -200d_y ≤ z規(guī)范化約束。為最小化 z應(yīng)讓 d_x 盡可能小d_y 盡可能大。取 d1 (-1, 1)。z1* 400*(-1) -200*(1) -600 0。從這個簡單的手動計算可以看出算法正在試圖逃離Rosenbrock函數(shù)的“香蕉谷”底部(1,1)因為該點不可行同時向約束邊界移動。如果繼續(xù)迭代最終會收斂到約束邊界上的某個點該點滿足目標函數(shù)梯度與約束梯度共線KKT條件。編程實現(xiàn)的關(guān)鍵代碼結(jié)構(gòu)Python偽代碼風格import numpy as np from scipy.optimize import linprog # 用于求解線性規(guī)劃子問題 def zoutendijk_optimize(f, grad_f, g_list, grad_g_list, x0, max_iter100, tol1e-6): Zoutendijk可行方向法簡單實現(xiàn) f: 目標函數(shù) callable grad_f: 目標函數(shù)梯度 callable g_list: 不等式約束函數(shù)列表 [g1, g2, ...] grad_g_list: 對應(yīng)梯度列表 [grad_g1, grad_g2, ...] x0: 初始可行點 x np.array(x0, dtypefloat) n len(x) for k in range(max_iter): # 1. 計算當前點的函數(shù)值和梯度 f_val f(x) grad_f_val grad_f(x) # 2. 識別起作用約束集 (基于容差) active_indices [] active_gradients [] for i, g_func in enumerate(g_list): if g_func(x) -tol: # 接近或違反邊界 active_indices.append(i) active_gradients.append(grad_g_list[i](x)) # 3. 構(gòu)造并求解線性規(guī)劃子問題 # 變量: [d_1, d_2, ..., d_n, z] c np.zeros(n 1) # 目標函數(shù)系數(shù) c[-1] 1 # 最小化 z # 約束: A_ub [d; z] b_ub A_ub [] b_ub [] # 目標函數(shù)梯度約束: grad_f^T d - z 0 row list(grad_f_val) [-1] A_ub.append(row) b_ub.append(0) # 起作用約束梯度約束: grad_g_i^T d - z 0 for grad_g in active_gradients: row list(grad_g) [-1] A_ub.append(row) b_ub.append(0) # 規(guī)范化約束: -1 d_i 1 轉(zhuǎn)化為 d_i 1 和 -d_i 1 for i in range(n): row_pos [0]*n [0] row_pos[i] 1 A_ub.append(row_pos) b_ub.append(1) row_neg [0]*n [0] row_neg[i] -1 A_ub.append(row_neg) b_ub.append(1) A_ub np.array(A_ub) b_ub np.array(b_ub) # 求解線性規(guī)劃 res linprog(c, A_ubA_ub, b_ubb_ub, bounds(None, None)) if not res.success: print(f迭代 {k}: 方向子問題求解失敗) break d res.x[:-1] z_star res.x[-1] # 4. 收斂性檢查 if abs(z_star) tol: print(f收斂于迭代 {k} z* {z_star}) break # 5. 步長搜索 (帶可行性回溯的Armijo搜索) alpha 1.0 # 初始步長 beta 0.5 # 回溯因子 c1 1e-4 # Armijo參數(shù) max_backtrack 20 for _ in range(max_backtrack): x_new x alpha * d # 檢查可行性 feasible all(g(x_new) tol for g in g_list) # 簡化檢查 # 檢查充分下降條件 if feasible and f(x_new) f_val c1 * alpha * np.dot(grad_f_val, d): break alpha * beta else: print(f迭代 {k}: 步長搜索失敗) break # 6. 更新迭代點 x x_new print(f迭代 {k}: x {x}, f {f(x)}, alpha {alpha}, z* {z_star}) return x調(diào)試經(jīng)驗實現(xiàn)時最大的坑在于起作用集識別和線性規(guī)劃求解的數(shù)值穩(wěn)定性。對于起作用集我通常會維護兩個容差一個寬松的容差用于初步識別候選起作用集如1e-4然后在構(gòu)建子問題時對于這些候選約束再檢查其梯度是否線性相關(guān)嚴重。如果發(fā)現(xiàn)梯度矩陣接近奇異說明約束可能冗余或子問題病態(tài)此時需要采用“激活集”策略只選擇一個線性無關(guān)的子集。此外scipy.optimize.linprog默認使用單純形法或內(nèi)點法對于小規(guī)模問題沒問題但自己實現(xiàn)時子問題的系數(shù)矩陣A_ub可能因為梯度數(shù)量級差異巨大而導致數(shù)值問題對梯度進行適當?shù)目s放比如除以各自的范數(shù)有時能顯著提高穩(wěn)定性。這個簡單的例子和代碼框架展示了Zoutendijk法的核心邏輯。在實際復雜問題中你需要加入更多的技巧如二階校正、彈性模式、更復雜的線搜索等才能讓它成為一個魯棒的求解器。但無論如何理解這個基本框架是駕馭更高級約束優(yōu)化算法的基礎(chǔ)。它教會我們的是一種在約束邊界上“謹慎探索”的哲學這種思想在很多現(xiàn)代算法中依然閃耀著光芒。