【直觀詳解】拉格朗日乘法和KKT條件

2021-02-20 機器學習算法與自然語言處理

【閱讀時間】8min - 10mun

【內容簡介】直觀的解讀了什麼是拉格朗日乘子法,以及如何求解拉格朗日方程,並且給出幾個直觀的例子,針對不等式約束解讀了KKT條件的必要條件和充分條件

拉格朗日乘法(Lagrange multiplier)是一種在最優化的問題中尋找多元函數在其變量受到一個或多個條件的相等約束時的求局部極值的方法。這種方法可以將一個有 n 個變量和 k 個約束條件的最優化問題轉換為一個解有 n+k 個變量的方程組的解的問題

那麼如何求這個極值點呢?

設一個具體的例子,我們需要求下列問題

根據幾個不同的解帶入f(x,y)得到,2,-2,0,也就是我們需要的最大值,最小值,對應的直觀圖像解釋如下圖所示(非常直觀的展現約束和等高線的含義)

既然可以解決單約束,繼續思考一下多約束情況的直觀表現,假設我們的約束是兩條線,如下圖所示

和單約束的解決方法類似,我們畫出等高線圖,目的就是在約束線上找到一個點可以和等高線相切,所得的值實在約束範圍內的最大值或者最小值,直觀表示如下圖

解算方法是講單約束的擴展到多約束的情況,較為類似,可舉一反三

已經解決的在等式約束條件下的求函數極值的問題,那不等式約束條件下,應該如何解決呢?

這就需要引出KKT條件(Karush-Kuhn-Tucker Conditions),它是在滿足一些有規則的條件下,一個非線性規劃問題能有最優化解法的一個必要和充分條件

考慮以下非線性最優化問題,含有m個不等式約束,l個等式約束

總的來說,拉格朗日乘子法是一個工具(手段或方法),來解決在有約束情況的求函數極值的問題

原文地址:https://charlesliuyx.github.io

更多博文歡迎訪問原文連結

推薦閱讀:

精選乾貨|近半年乾貨目錄匯總

留給人類的時間不多了?現在不學機器學習更待何時!

【直觀詳解】什麼是PCA、SVD

          歡迎關注公眾號學習交流~         

相關焦點

  • 深入理解拉格朗日乘子法和KKT條件
    (Lagrange Multiplier) 和KKT條件是非常重要的兩個求取方法,對於等式約束的優化問題,可以應用拉格朗日乘子法去求取最優值;如果含有不等式約束,可以應用KKT條件去求取。KKT條件是拉格朗日乘子法的泛化。之前學習的時候,只知道直接應用兩個方法,但是卻不知道為什麼拉格朗日乘子法(Lagrange Multiplier) 和KKT條件能夠起作用,為什麼要這樣去求取最優值呢?本文將首先把什麼是拉格朗日乘子法(Lagrange Multiplier) 和KKT條件敘述一下;然後開始分別談談為什麼要這樣求最優值。一.
  • 直觀理解KKT條件
    KKT最優化條件是Karush[1939],以及Kuhn和Tucker[1951]先後獨立發表出來的。這組最優化條件在Kuhn和Tucker發表之後才逐漸受到重視,因此許多情況下只記載成庫恩塔克條件(Kuhn-Tucker conditions)庫恩塔克條件(Kuhn-Tucker conditions)是非線性規劃領域裡最重要的理論成果之一,是確定某點為極值點的必要條件。如果所討論的規劃是凸規劃,那麼庫恩-塔克條件也是充分條件。
  • 支持向量機(三):圖解KKT條件和拉格朗日乘子法
    前言支持向量機求解最優化參數的過程中需要用到拉格朗日乘子法和KKT條件,本文用清晰易懂的圖解法說明拉格朗日乘子法和
  • 如何搞定機器學習中的拉格朗日?看看這個乘子法與KKT條件大招
    一 前置知識本文引用地址:http://www.eepw.com.cn/article/201709/363864.htm  拉格朗日乘子法是一種尋找多元函數在一組約束下的極值方法,通過引入拉格朗日乘子,可將有m個變量和n個約束條件的最優化問題轉化為具有
  • 拉格朗日乘子法與KTT條件
    帶約束的優化過程應用非常普遍,拉格朗日乘子法以及其推廣KTT條件是凸函數求解極值時中常用的方法。
  • 一挑三 FJ vs KKT
    但是由於參與了美國的曼哈頓計劃(Manhattan Project),使得Karush本人對名利追求並不熱衷,而追求和平,他對Karush和Tucker的定理的命名權並不放在心上。 以至於KT條件在10年後才重命名為KKT條件。
  • 拉格朗日插值定理的理論基礎
    插值法裡面常用的就是拉格朗日插值、牛頓插值兩類,我們重點看看拉格朗日插值法。拉格朗日插值,是一種多項式插值,那多項式插值定理怎麼一回事呢?多項式插值定理拉格朗日插值本質上是多項式插值的一種,而多項式插值是什麼意思呢?這裡有個定理叫多項式插值定理,說的是咋個一回事呢?就是說假設我們已知有n個點,(x1,y1),(x2,y2),...
  • 變分法——歐拉-拉格朗日方程
    我們來看看當如果這個泛函在Y(x)=y(x)處取極值時,需要滿足什麼條件先來描述一下基礎條件:然後根據"變分法基本引理"(參見變分法基本引理)就可以導出歐拉-拉格朗日方程啦:需要注意的是,歐拉方程是泛函極值的必要條件,但不是充分條件,
  • 拉格朗日乘數法
    條件極值問題也可以化為無條件極值求解,但有些條件關係比較複雜,代換和運算很繁,而相對來說「拉格朗日乘數法」不需代換,運算簡單一點,這就是優勢。 上面說到:在利用偏導數求多元函數的極值時,若函數的自變量有附加條件,則稱之為條件極值。這時,可用拉格朗日乘數法求條件極值。具體方法如下: 設給定二元函數z=ƒ(x,y)和附加條件φ(x,y)=0,為尋找z=ƒ(x,y)在附加條件下的極值點,先做拉格朗日函數L(x,y)=ƒ(x,y)+λφ(x,y),其中λ為參數。
  • 大魔王拉格朗日的故事及拉格朗日中值定理
    20歲時,受歐拉的舉薦,拉格朗日被任命為普魯士科學院通訊院士。義大利、德國、法國三個國家的科學院,在數學、力學和天文學三個學科領域中都有歷史性的貢獻,拿破崙稱他為「數學科學高聳的金字塔」,是18世紀歐洲最偉大的數學家。
  • 從楊輝三角說起,體驗乘法公式應用魅力,挑戰趣味難題
    「楊輝三角」出現在楊輝編著的《詳解九章算法》一書中。楊輝,杭州錢塘人,中國南宋末年數學家,數學教育家,著作甚多。他編著的數學書共五種二十一卷,著有《詳解九章算法》十二卷(1261年)、《日用算法》二卷、《乘除通變本末》三卷、《田畝比類乘除算法》二卷、《續古摘奇算法》二卷。其中後三種合稱《楊輝算法》,朝鮮、日本等國均有譯本出版,流傳世界。
  • 拉格朗日乘數法介紹
    拉格朗日乘數法的基本思想  作為一種優化算法,拉格朗日乘子法主要用於解決約束優化問題,它的基本思想就是通過引入拉格朗日乘子來將含有n個變量和k個約束條件的約束優化問題轉化為含有(n+k)個變量的無約束優化問題。拉格朗日乘子背後的數學意義是其為約束方程梯度線性組合中每個向量的係數。
  • 通俗易懂 | SVM之拉格朗日乘子法
    在SVM中,將約束問題轉化成非約束問題採用到了拉格朗日乘子法。這個文章就講一下拉格朗日乘子法與KKT約束是怎麼回事。本人不是數學科班出身,但是也只能硬著頭皮講一講了。這個就是拉格朗日乘子法的直觀理解。KKT條件KKT的英文全稱:Karush-Kuhn-Tucker之前的拉格朗日的約束條件是等值的,現在可以通過KKT條件推廣到不等式。
  • 拉格朗日點和拉格朗日乘子法
    拉格朗日點指受兩大物體引力作用下,能使小物體穩定的點。一個小物體在兩個大物體的引力作用下在空間中的一點,在該點處,小物體相對於兩大物體基本保持靜止。在每個由兩大天體構成的系統中,按推論有5個拉格朗日點,但只有兩個是穩定的,即小物體在該點處即使受外界引力的攝擾,仍然有保持在原來位置處的傾向,每個穩定點同兩大物體所在的點構成一個等邊三角。
  • 矩陣的乘法在量子計算領域是一種基本操作
    矩陣的乘法在量子計算領域是一種基本操作,正是因為算法本身的簡單,矩陣乘法和導數結合非常容易。至於物理意義就是解一個能量問題,矩陣的結構就是基本原子或者分子電子的排列組合,基於一個組合態的結果,討論算符不知是不是可以算矩陣的非退化算符,即矩陣乘法不是一個主算符,有的只是一個導出算符而已。
  • 不等式專題之二元條件最值中的拉格朗日乘數法
    在均值不等式專題中有一類求最值的題目,題目給出了關於x,y的一個二元等式,讓求一個關於x,y式子的最值,此類問題的解法在高中階段一般有兩種做法,一種是利用等式關係,將目標式子轉化為求一元最值,另一種是根據所求式子,並對其變形,結合條件最後轉化為關於x,y的基本等式,第一種方法很直接
  • 拉格朗日乘子法
    這一篇先來介紹拉格朗日乘子法。 問題由來 在對函數優化時,如果沒有限制條件,一般直接對其求導,然後令導數為0,即可求解出極值點。但在更多的情況下,是有一些約束條件的。通常情況下,約束問題可以表示為: 也就是說,約束問題主要有2類。一類為不等式約束,另一類為等式約束。
  • 歐拉和拉格朗日筆下的三角級數以及重要的等式關係
    偉大的數學家歐拉從最一般的三角函數sinx^2+cosx^2=1公式出發,得到著名的棣莫弗定理以及正弦和餘弦的無窮級數,方法簡單明了直觀,接著法國數學家拉格朗日運用三角學中的複數性質,又得到一些重要級數等式,優美的思路值得大家學習借鑑。
  • 最小二乘法之加權最小二乘的應用
    因此我們迫切需要對每個點都定義一個權重,這就是今天我要介紹的加權最小二乘法。在介紹這個算法之前,先回答一個問題,上篇文章中,有網友私信問我為什麼那個參數方程要選取較小的特徵值與特徵向量:這個問題我在上篇文中只是提到了一下,最小距離的總和剛好是數據集矩陣的特徵值,但並沒有說明具體的原因,這裡給出一個更直觀的證明方法:
  • 題型解析:中值命題證明之拉格朗日中值定理
    -【分析】對於這個考題比較簡單,根據已知條件有非常直觀的一些結果.>階導數」可得(1) f(-x)=-f(x);(2) f(x)的導函數f』(x)為偶函數;(3) f(x)在[-1,1]上連續,可得f(0)=0;(4)由已知「f(1)=1」和(