首先我們定義一般形式的求解x的優(yōu)化問題：
- 表示優(yōu)化的目標函數(shù)，上述為最小優(yōu)化，實際上最大優(yōu)化可以改寫為的形式
- 表示第i個不等式約束
- 表示等式約束
1.?Lagrange對偶問題
上述優(yōu)化問題的拉格朗日Lagrange對偶法求解，是將上述帶約束的目標優(yōu)化問題改寫為如下無約束的Lagrange函數(shù)式子。
上述Lagrange函數(shù)式子存在如下對偶函數(shù)，其是Lagrange函數(shù)關于取最小值，即：
對偶函數(shù)是關于的函數(shù)，很顯然其是原來Lagrange函數(shù)式子的下界，假設優(yōu)化問題存在最優(yōu)解，當時，此時存在最優(yōu)目標大于對偶函數(shù)。
Lagrange對偶法即是通過最大化原問題Lagrange對偶函數(shù)，從而逼近原問題的下界來求解原問題最優(yōu)解，因為的參數(shù)遠小于原問題的求解參數(shù)，因此轉換為對偶問題后，求解更為簡單。
2. 強弱對偶性
接下來的問題是通過對偶函數(shù)得到下界同原問題的最優(yōu)解之間的差距是多少？當對偶函數(shù)得到下界同原問題的最優(yōu)解相等時，稱之為強對偶性，反之稱為弱對偶性。而這個差值稱之為最優(yōu)對偶間距。
Slater約束準則給出為強對偶性成立的條件：
- 原問題是凸問題
- 存在內點使得所有的不等式約束嚴格成立即，如果是仿射不等式時取等于也是可行的。
3. 如何轉換為對偶函數(shù)
因為對偶函數(shù)是Lagrange函數(shù)關于取最小值，假設是關于x的凸函數(shù)，且存在關于x的最小值，此時存在使得關于x的偏導數(shù)為0，則存在對偶函數(shù)為。
假設為對偶函數(shù)為也是關于可導，此時最優(yōu)值存在
此外最優(yōu)值要使對偶函數(shù)存在最大值，由于，因此：
上述五個條件構成了在Slater約束準則下求解優(yōu)化問題最優(yōu)解存在的KKT條件：
例子1：線性規(guī)劃問題
首先我們定義一個一般性的線性規(guī)劃問題，其中x是表示求解向量，該問題可解是指存在唯一解。
Lagrange函數(shù)式子表示為：
Lagrange函數(shù)僅當時，才是有界的，此時對偶函數(shù)為，否則為負無窮，因此原問題可以轉換為求解對偶問題的最大值，此時Slater約束準則，對偶問題的解也是原問題的最優(yōu)解。
例子2：最小二乘法
考慮以下問題：
Lagrange函數(shù)式子表示為：
Lagrange函數(shù)關于x是二階可導的凸函數(shù)，存在最小值的解：
此時對偶函數(shù)為下式，此時原問題被轉換為一個無約束的對偶問題的求解。
4. 最優(yōu)問題的轉換
接下來我們考慮更為通用的優(yōu)化問題形式，之前討論了不等式約束中的大于和小于可以通過變換符號進行調整，實際上我們可以通過新增求解變量將不等式約束轉換為等式約束：
文章來源：http://www.zghlxwxcb.cn/news/detail-432901.html
結合上述對偶問題的轉換，我們可以將通用的優(yōu)化問題形式轉換為等式約束問題，甚至無約束的問題，下一篇我們將介紹等式約束優(yōu)化問題和無約束優(yōu)化問題的通用求解方法。文章來源地址http://www.zghlxwxcb.cn/news/detail-432901.html
到了這里，關于優(yōu)化問題的拉格朗日Lagrange對偶法原理的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！
