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