拉格朗日乘子法漏解的情況？

01-04

（首先說明一下，圖3有點筆誤，g(x)函數也就是t(x)函數）對拉格朗日乘子法，有些情況下我有點不解。演算法要求m個約束函數和n個變數之間的雅可比矩陣秩為m, 當秩為m，演算法是正確的（因為要麼是孤立點，要麼能確定隱函數），但是演算法不考慮秩小於m的情況，不是會漏解么？比如上面的t函數在實數集上連續可微，優化的目標函數f(x)是個非嚴格的凸函數，有2個滿足t(x)=0的點，x0,x1。但是在x1點，導數為0，故雅客比矩陣秩為0，演算法是找不到這點的，演算法找到的是x0點，而顯然x1點更好，而這流程完全按照教材（數學分析）來的，怎麼解釋這種漏解的情況呢？

你其實問到了一個最優化研究里的一個很重要，但是答案的細節又很微妙的問題。

首先如你所想，如果rank 不等於m，Lagrange方法或者說解KKT方程在理論上會失敗，這種退化而病態的情況是可能的。非線性優化理論的一個重要研究，就是弄清楚理論上什麼條件下可以避免這種病態情況，這方面的成果通常叫做KKT條件的約束規範constraint qualification。這方面的研究論文主要集中在上個世紀六七十年代，現在學習時可能都很少見，或者不太注意，教科書里也就是提一下約束規範條件這個概念。

之所以說這個問題的答案很重要而細節又很微妙，一方面是是因為最優條件不成立的病態情形都非常複雜，沒法完全弄清楚這些病態情形的機理或者對他們進行分類，所以學者們才花大量時間研究約束規範條件來避免病態情形。另一方面，這樣的病態案例只有教學意義，在實際問題中通常都不會出現。為什麼呢？因為這樣的情形都是不穩定的，細微的數據擾動就改變了輸出結果。而對於實際可用的數值演算法，必須要保證數值穩定性，否則就沒法應對舍入誤差。

最終導致了現在的情況: 通常學者們在研究時就是簡單地假定約束規範條件是成立的，換句話說就是規避這些病態情形。因為有大量的約束規範條件可以使用，不需要再詳究細節，而且這些規範情形已經足以覆蓋大多數實際問題。除非專門研究這些病態問題或者新的約束規範條件，否則大家就直接忽略這些病態情形。

我來多說一點有關constraint qualification 的吧！

因為Lagrange找的是滿足KKT條件的點。而KKT 並不是該點是最優解的充要條件，這是一個一階必要條件。也就是說只要是解，一定滿足KKT, 為什麼還有漏解？因為KKT條件有個前提啊，就是x 滿足CQ (constraint qualification).

先說說KKT怎麼來的。

最優化問題：Min f(x)

S.t. g(x)≤0, h(x)=0

解有限制條件的非線性最優化問題，首先找feasible set, 也就是滿足限制條件的點的集合。然後根據最優點的幾何意義，如果x是最優解(這裡我指極小), 起碼在feasible set里，每個方向都不能再下降了吧？所以有?f(x)"d≥0, d∈T(M,x). (T(M,x) 是Tangent cone, 簡單來說就是向這些方向走依然在feasible set里的方向集合。)

但是研究Tangent cone 是用極限定義的，不好算，很抽象啦，而且這個東西怎麼跟constraint condition g(x), h(x) 聯繫在一起？那就做linearized Tangent cone好了。定義是所有方向d, 使得?g(x)"d≤0, ?h(x)"d=0 的方向。但是這個集合其實是比Tangent cone 要大的，也就是說Linearized Tangent cone包含了Tangent cone. 如果它們相等那多好！所以如果他們相等，我們說這個點滿足ACQ(Abadie constraint qualification).

但是記得如何找最優解嗎？基本就是沿下降方向一直走啊，那麼就討論下降方向的集合好了。其實就相當於討論Tangent cone里方向的反方向不是嗎？於是我們研究Polar cone, 一個cone的Polar cone就是它裡面所有方向都相反的方向集合。(e.g. Polar cone of Tangent cone is T°(M, x)={v, v"d≤0,for all d∈T(M,x)} )

所以現在我們討論Tl°(g,h,x) (linearized Tangent cone的Polar cone) 和T°(M,x), 因為Tl 比 T 大，所以Polar cone 剛好是反過來的， T°大。如果他們相等，就叫做滿足GCQ( Guignade constraint qualification).

所有能推出GCQ的叫CQ.

然後， KKT 是建立在Farkas Lemma上的，而對於Farkas Lemma, CQ 是必須的。為什麼？因為Farkas Lemma說，以下兩個條件等價：

1. For all d, A"d≤0 and B"d=0, then C"d≤0.

2. 存在u,v, u≥0, s.t. c=Au+BC

現在把A,B 換成?g(x) 和?h(x) 看出來這個基本就是KKT條件了嗎？

為什麼KKT 是local solution 的必要條件？就是因為CQ 限制了方向，滿足CQ, 那麼Tl(g,h,x) 里的方向都不下降，所以這個點是局部最小。為什麼會少解，因為研究的是Polar cone 剛好反過來，Tl°小。

～～～～～～～～～～～～～～～～～～～～～～

當然有人說有沒有最優點的充分條件，有哦！只不過不是一階。

在討論充分條件之前，又有一個新的cone定義：

T+(g,h,x,λ)={d ∣?g(x)"d≤0 if λ =0, ?g(x)"d=0, if λ&>0, ?h(x)"d=0}

這裡的gi 只需要考慮使得gi(x)=0 的限制條件就好，也就是說下標i在Active set 里。也就是說?g(x)"d 和λ 至少一個要為零。

而局部最優點的充分條件是：除了KKT 要求的條件而外，還需要d"?xxL(x,λ,μ)d=0 for all d∈T+(g,h,x)/{0}

這裡的λ是KKT或者說解Lagrange 方程出來的。可以看出來T+ 更小。

有一些天生滿足CQ 的，還有一些簡單的方法判斷是否CQ。(比如LICQ, full rank 其實就是滿足了LICQ, 在只有等式約束的情況下) 此時對於所有滿足CQ 的點，如果二階充分條件成立，就是局部最優解。對於不滿足CQ的點，是不能用KKT二階充分條件的。由此看來，KKT的點會找多，而不是漏解。但是KKT 只能找到局部解，並不能保證全局最優。

現在來看題主的問題：

題主你最優化其實要分為兩個最優化問題看啊！

Min f(x)=-x

S.t t(x)=x^2+4x-4=0

g(x)=-x≤0

(按這樣的格式分兩個最優化問題啊！)

你這個不是一個優化問題可以解決的呀，你的不等式約束沒有用啊在你直接KKT的時候。

這樣兩個點都可以找到啊！

以上。

說明：

1. 手機打的，符號不太規範。上述符號都是向量，不只是一維。

2. " 是轉置啦。