完整性約束中值的約束條件有哪些（優化淺談約束規範性條件）

2023-05-29 10:45:11

『運籌OR帷幄』原創

作者：門泊東吳

編者按：本文淺談了什麼是約束規範性條件(constraint qualification)，並列舉了一些常見的CQ和它們之間的關係。

看了之前公眾號推送的文章《【學界】關於KKT條件的深入討論》，忽然發現自己以前學的constraint qualification(簡稱CQ)的知識，因為太久不用，好多都不記得了；此處忽然又想起以前一個教授在課堂上說過的話，"真正理解透徹的東西，根本不用費心記憶，你忘了就代表你當時壓根兒就沒理解"，汗顏... 專門討論CQ的文章並不是很多，遂寫之，主要想通過這篇文章和大家一起溫故而知新，重新理解一下CQ到底在刻畫什麼？學藝不精，一知半(不)解，歡迎大家批評指正。

一、數學鋪墊：定義三個錐

可行方向錐和切線錐之間有下面兩個關係：(Proposition 4.6.2 in [1])

下面這張圖摘自[1]的4.6節，分別說明了這兩個關係。

二、局部最優解的必要條件

CQ和KKT條件的關係密不可分，正如王源在文章《【學界】關於KKT條件的深入探討》裡所述，CQ完善了KKT條件的嚴謹性，在滿足CQ的條件下，KKT條件才是帶約束的優化問題的局部最優解的必要條件，否則應該用Fritz John條件。我們先來簡單回顧一下KKT條件，考慮如下帶約束的優化問題：

(詳見文章《【學界】關於KKT條件的深入探討》中第3節的例子)，那有了CQ為什麼就可以避免這種情況呢？回到文章最開始的問題，所謂CQ，字面意思是約束的規範性條件，它究竟刻畫了什麼？

我們再來看看，局部最優解的必要條件還有哪些別的表述形式？Bertsekas在[1]的4.7節裡推導了對於具有三種不同性質(主要是目標函數的光滑性)的帶約束的優化問題的局部最優解的必要條件：Proposition 4.7.1-4.7.3，我們只簡單看一下Proposition 4.7.1。

接下來，我們試著從這個等價條件出發，看看如何引出CQ。重新看回到問題(CP)，第一步，先只考慮線性等式約束，即：

第二步，考慮一般的等式約束問題，即：

三、經典CQ和它們之間的關係

這一小節，我們來重溫一下一些常見的經典CQ。考慮如下帶約束的優化問題：

還有其他許許多多的CQ，推薦閱讀[3]，真的有好多，嗯，開卷有益。最後，用[3]裡面兩張有趣的圖來結束這一小節：第一張圖是一般情況下CQ之間的關係(誰implies誰)，第二張圖是約束集為凸的情況下CQ之間的關係。

這兩張圖裡，我們都可以觀察到，GCQ、ACQ確實在比較上方，說明比較弱；我們常用的SLCQ、LICQ、MFCQ都在比較下方，算是比較強的了。

四、寫在最後

像CQ這種很基礎的概念，作為優化領域的小學生，平時鑽研得比較少，即使碰到也多是用現成的理論，若有錯誤理解或疏漏，歡迎大家討論補充；在大牛們一些比較fundamental的工作裡，我也確實看到過他們自己定義一些新的CQ來fertilize他們的算法理論，對數學的要求蠻高的，可能越是具有奠基性的工作就越是先要從基礎下鏟子吧~

參考文獻：

[1] D. P. Bertsekas, A. Nedic and A. E. Ozdaglar, Convex Analysis And Optimization, Athena Scientific Belmont, 2003.

[2] J. V. Burke, Constraint Qualifications for Nonlinear Programming. Numerical Optimization Course Notes, AMath/Math 516, University of Washington, Spring Term 2012.

[3] D. W. Peterson, A Review of Constraint Qualifications in Finite-dimensional Spaces, SIAM Review, 15(3):639-654, 1973.