卡鲁什-库恩-塔克条件
在數學中,卡鲁什-库恩-塔克条件(英語:Karush-Kuhn-Tucker Conditions,常見別名:Kuhn-Tucker,KKT條件,Karush-Kuhn-Tucker最優化條件,Karush-Kuhn-Tucker條件,Kuhn-Tucker最優化條件,Kuhn-Tucker條件)是在满足一些有规则的条件下,一個非線性規劃問題能有最優化解法的一個必要條件。這是一個使用广义拉格朗日函数的结果。
考慮以下非線式最優化問題:
是需要最小化的函數,是不等式約束,是等式約束,和分別為不等式約束和等式約束的數量。
不等式約束問題的必要和充分條件初見於威廉·卡鲁什的硕士論文[1],之後在一份由哈羅德·W·庫恩及阿爾伯特·W·塔克撰寫的研究生論文[2]出現後受到重視。
必要條件编辑
假設有目標函數,即是要被最小化的函數 ,約束函數 及 。再者,假設他們都是於 這點是连续可微的,如果 是一局部极小值,那麼將會存在一组所谓乘子的常数 , 及 令到
- 。
正則性條件或約束規範编辑
於上述必要和充分條件中,dual multiplier 可能是零。當 是零時,這個情況就是退化的或反常的。因此必要和充分條件會將約束的幾何特性而不是將函數自身的特點納入計算。
有一定數量的正則性條件能保證解法不是退化的(即 ),它們包括:
- 線性獨立約束規範(Linear independence constraint qualification,LICQ):有效不等式約束的梯度和等式約束的梯度於 線性獨立。
- Mangasarian-Fromowitz約束規範(Mangasarian-Fromowitz constraint qualification,MFCQ):有效不等式約束的梯度和等式約束的梯度於 正線性獨立。
- 常秩約束規範(Constant rank constraint qualification、CRCQ):考慮每個有效不等式約束的梯度子集和等式約束的梯度,於 的鄰近區域的秩(rank)不變。
- 常正線性依賴約束規範(Constant positive linear dependence constraint qualification,CPLD):考慮每個有效不等式約束的梯度子集和等式約束的梯度,如果它們於 是正線性依賴,那麼它們於 的鄰近區域也是正線性依賴。(如果存在 not all zero令到 ,那麼 是正線性依賴)
- 斯萊特條件(Slater condition):如果問題只包含不等式約束,那麼有一點 令到 for all
雖然MFCQ不等同於CRCQ,但可證出LICQ⇒MFCQ⇒CPLD,LICQ⇒CRCQ⇒CPLD。於實際情況下,較弱的約束規範會被傾向使用,這是因為較弱的約束規範能提供較強的最優化條件。
充分條件编辑
假設目標函數 及約束函數 皆為凸函數,而 是一仿射函數,假設有一可行點 ,如果有常數 及 令到
那麼 這點是一全局极小值。
註釋编辑
- ^ W. Karush. Minima of Functions of Several Variables with Inequalities as Side Constraints. M.Sc. Dissertation. Dept. of Mathematics, Univ. of Chicago, Chicago, Illinois. 1939..此論文可於以下網址得到:http://wwwlib.umi.com/dxweb/details?doc_no=7371591[失效連結] (需付費)
- ^ Kuhn, H. W.; Tucker, A. W. Nonlinear programming. Proceedings of 2nd Berkeley Symposium. Berkeley: University of California Press: 481–492. 1951.
參考文獻编辑
- Avriel, Mordecai (2003). Nonlinear Programming: Analysis and Methods. Dover Publishing. ISBN 0-486-43227-0.
- R. Andreani, J. M. Martínez, M. L. Schuverdt, On the relation between constant positive linear dependence condition and quasinormality constraint qualification. Journal of optimization theory and applications, vol. 125, no2, pp. 473-485 (2005).
🔥 Top keywords: Baike: 首页Special:搜索胖猫跳江事件背着善宰跑九龍城寨之圍城逆天奇案2璩静淚之女王歌手2024Energy (組合)新生 (网络剧)习近平匈牙利邊佑錫劉俊謙 (香港)金智媛神耆小子塞尔维亚金秀賢 (男演員)母亲节猩球崛起:王國誕生九龍寨城馴鹿寶貝家族榮耀之繼承者Seventeen (組合)六四事件不夠善良的我們张维为楊佩潔TripleS支配物种庆余年郭葦昀洪若潭命案金惠奫2024年英雄联盟季中邀请赛春色寄情人BABYMONSTER笑看風雲乘風2024排球少年!!角色列表破墓徐巧芯中华人民共和国中華民國打天下2WIND BREAKER—防風少年—习明泽排球少年!!彭丽媛磁暴ILLIT贾斯汀·比伯逆天奇案BOYNEXTDOOR猿人爭霸戰:猩凶革命張書偉我的婆婆怎麼那麼可愛我獨自升級怪獸8號謝坤達IVE (組合)與鳳行關於我轉生變成史萊姆這檔事角色列表黃道十二宮福建號航空母艦虽然不是英雄葉乃文五月天張員瑛草榴社区張文傑2024年花蓮地震极光香緹·摩爾迷宮飯呂家愷搜查班長1958日本劉德華海莉·鮑德溫蕭景鴻越位 (足球)葬送的芙莉蓮周處除三害 (電影)毛泽东願榮光歸香港林峯周雨彤伍允龍羅毓儀香港Baike: 分類索引沒有秘密猩球崛起:終極決戰角質層唐振剛柯佳嬿文化大革命