一些疑惑的最優化問題，希望大神幫忙解答一下，非常感謝！？

01-11

1、非線性規劃問題有對偶問題嗎
2、無論原問題形式如何，其對偶問題都是一個凸優化問題嗎
3、非凸問題有哪些轉化為凸問題的方法呢
4、convex是向下凸，所以凸優化問題就是求解minimum目標函數的問題嗎，那數學模型設定的是maximum目標函數，需要轉化為對偶問題來做嗎

各位！各位！！！非常感謝 @Olivia Zhang！！！我在第一次寫的時候就覺得哪裡解釋的不對勁，但是當時自己懶癌犯了，也沒有細究，所以導致了可能誤導了很多人，在此表示深深的歉意，當然我第一次除了第三個picture里有一些地方說的不對，其他地方應該還是暫時沒問題的。如果各位有興趣請看我下面的勘誤版本。再次感謝 @Olivia Zhang 。

----------------------------------------------------------------------------------------

最初版，看不出錯誤的請看我下面的勘誤版，大家一起學習！

----------------------------------------------------------------------------------------

我來說說我的個人愚見吧！

首先，我想說一下我的個人理解：為什麼要把對偶問題引入！！！！

依我現在的水平，我是這麼告訴自己的，我總結出我學的任何知識一般來說只有兩個作用：1. 直接解決問題的方法。 2. 簡化解決問題的方法（找一個新問題的解，證明新問題的解逼近原問題）。

而我總結出來的就是對偶問題很明顯就是第二種作用。首先，其實你實際做research能formulate出一個Optimization的問題就已經是初步成功了（比如machine learning中的很多方法，以SVM：support vector machine為例），最後我們無非要找的是方程在最大值或最小值時的解。

這時候你可以向你高中時如何解決這個問題的，就是找極值點嘛，然後再判斷導數在極值點兩邊極限的正負去判斷是極大值還是極小值。如果要是一元二次方程極大值就是最大值，極小值就是最小值。實際上optimization我覺得就是一個在多維空間中的找極大/小值（最大/小值）的問題，和高中求極值只有兩點不同：一，從一位轉向了多維（僅僅只是求導和運算不同，你需要的是矩陣求導和運算）。二，從無限制條件到有某些邊界條件（就是類似你初中是學過的線性規劃的那種條件）。

現在問題就來了，由於有了邊界條件，所以我們沒辦法像高中那樣去做目標函數的導數然後讓它等於0去求解極值，因為它們不一定滿足限制條件，而這個限制條件往往十分噁心，是很多很大的不等式（一個優化問題可能有n個限制條件，n可以無限大）。所以這真的是很尼瑪噁心人。人類就要思索我能不能把這些條件去除了並且還不影響（或基本不影響）原來的最優解呢？（此處表達一下我對為人類做出貢獻的人的敬意）於是乎！！！對偶方法應運而生！！！！

我們給每一個特別尼瑪複雜的不等式限制條件附加一個lagrangian multiplier（alpha_1吧，下標代表第一個constraint的lagrangian multiplier），這個乘子就是一個很簡單的變數。所以對n個不等式，我們就有n個乘子，這n個乘子就引入了一個新的變數vector alpha（這是一個向量變數裡面包含了從alpha_1到alpha_n）。現在聰明的思想就出來了，我們就是要把原問題轉化為可以對原變數直接求導的問題，然後再解決變數只有拉格朗日乘子的問題。

我隨便來舉個例子：

所以，最終我們可以直接利用高中的方法先把最內層的x的最大值求出來，因為此時x已經沒有了限制條件，直接對x求偏導然後等於0，用alpha表示的x的最優解帶入到原目標函數，最終得到一個完全是constraint lagrangian multiplier為變數的優化問題，此優化問題已經十分好做了，因為此時：第一，只有一個變數（alpha vector）。第二，此變數的constraint十分簡單為&>0。

（今天太晚了，我要趕緊從實驗室回家了，不然就被老黑鮑菊了，小弟才疏學淺，此次僅為拋磚引玉，希望大家一起討論，共同學習，祝所有人好！）

---------------------------------------------------------

（上面有大錯！！！！）

---------------------------------------------------------

大家請看我的上面最後一個照片里的分析！裡面有一個很大的問題。我的原句：由於我們加了一個恆為負的數。此舉實際上有一個前提條件就是 $alpha_i>0<br />$ 和 $B_i x-y_i<0$ (x代表上面的x下劃線)，然後我就直接做了 $frac{partial }{partial x} x^TAx + bx^Ty + sum_{i=1}^{n}alpha_i(B_ix-y_i)$ ，這樣做實際上無法保證 $B_i x-y_i<0$ ，因為上面求導的時候已經默認了x的domain為全體實數，所以 $B_i x-y_i>0$ 也會存在，因此上面的分析「恆為負」是錯的！！！！

而實際上上面的例子我舉的壓根兒就不對！因為當目標函數是Maximize的時候問』題三的值『恆小於』問題二的值『是不對的！！！是不對的！！！！！是不對的！！！！！！（重要的事情說三遍）（因為maximize只能找到一個橫比它大的問題，這裡感謝細心的 @又紅又正的糾正，具體的描述大家可以先看Minimize的，最後我會說maximize的情況。）

我這個人就有個臭毛病，我自認為自己掌握了某些小問題的本質之後，教別人的時候一定會跟課本里反著來，課本里如果用東講的，我教別人的時候一定是自己瞎創一個西的例子，因為我覺得只有把一個條件完全不同的例子用相同的方法分析清楚，這樣才能把我們的注意力從問題本身牽引出來，而去更好的看待問題本身所反映出的一個更general的point。而當我學的二把刀的時候，就會忽略一些條件的重要性，只有像 @Olivia Zhang 這麼認真的同學給我指出矛盾點的時候，我才能意識到我的錯誤，從而對知識再加深一次認識，再次感謝。我裝逼失敗不要緊，但我怕我的答案誤人子弟，將大家帶入一個更混亂的知識體系，在此我深感歉意。
我覺得大家現在應該知道了我把哪裡給改了，對！課件里的原問題基本都是Minimize但我卻改成Maximize了！！！這就把問題弄得大大的不同了，我下面會詳細講為什麼一定要minimize，我先要強調一下結論：只有當minimize一個目標函數的時候，我們才能引入lagrangian並得到一個不論lagrangian multiplier取何值時都會使新的目標函數（lagrangian）小於原目標函數的解。

-----------------------------------------

詳細的解釋和分析

-----------------------------------------

大家見過的形式都是

$Problem I egin{align} underset{x}{ ext{minimize}} f_0(x)\ ext{subject to} f_i(x)leq0, i =1,...,m\ h_j(x)=0, j=1,...,p end{align}$

(上面為直接引用Stanford Boyd課件的原形式http://stanford.edu/class/ee364a/lectures/duality.pdf)

我們為了想去除Problem I中的m+p個噁心的條件，但是我們還想盡量能夠找到滿足這m+p個條件的Problem I的最小的 $f_o(x)$ 的值，所以我們引入了lagrangian multiplier，我們相用dual problem（沒有對x的條件的一個problem II）的解去逼近Problem I的解。

對於 $f_i(x)leq0$ 我們引入 $lambda_igeq0$ ,我標記這個為條件一；

對於 $h_j(x)=0$ 我們引入 $u _j$ ,這個拉格朗日乘子沒有任何的條件，我標記這個為條件二。

現在我們來formulate problem II:

$Problem II egin{align} underset{x}{ ext{minimize}} L(x,lambda, u)\ ext{subject to} lambda_igeq0, i =1,...,m\ end{align}$

where $L(x,lambda, u) = f_0(x)+sum_{i=1}^{m}lambda_if_i(x)+sum_{j=1}^{p} u_jh_j(x)$

我假設problem I的最優解為 $ar{x}$ （這個 $ar{x}$ 是同時滿足 $f_0(x)$ 的domain和problem I中的constraints的條件的一個值），下一步我要為大家解釋為什麼probelm I 中的最小值會恆大於problem II中的最小值。

首先Problem I的最小值為將最優解 $ar{x}$ 帶入到目標函數的值，即 $f_0(ar{x})$ 。

然後我們再表示problem II的最小值為 $ext{inf}_{xinmathcal{D}}L(x,lambda, u)$ （由於此時在problem II中，x已經沒有了contraint的條件所以我們只要從L(.)這個function的domain裡面選一個讓目標函數最小的x就行了，即為對x求偏導=0，再代入回去）

現在我們要證明的是為什麼problem II的結果會永遠小於problem I的結果，即我們要證明不論 $lambda$ 和 $u$ 取什麼值， $f_0(ar{x})geq ext{inf}_{xinmathcal{D}}L(x,lambda, u)$ 這個式子總是成立的。在這個分析里這個目標函數的形式是Minimize這個條件就必不可少了。

這個證明的trick就在於我們要借用一個中間的量 $L(ar{x},lambda, u)$ ！！！！！

我們發現如果我們證明了 $f_0(ar{x})geq L(ar{x},lambda, u)$ 和 $L(ar{x},lambda, u)geq ext{inf}_{xinmathcal{D}}L(x,lambda, u)$ 同時成立，那麼原不等式就一定成立。

我們先看第一個不等式為什麼成立呢？這個是我原來錯誤答案中第三個圖片的解釋的東西，也就是Problem I的最優解是一定滿足problem I 中constraint的條件的，所以可以保證 $lambda_if_i(ar{x})leq0$ 和 $u_jh_j(ar{x})=0$ ，所以 $L(ar{x},lambda, u)$ 相當於在 $f_0(ar{x})$ 的基礎上加了一個負數和0，所以 $L(ar{x},lambda, u)$ 一定小於 $f_0(ar{x})$ 。

我們再看一下第二個不等式，這個是很明顯成立的，因為 $ext{inf}_{xinmathcal{D}}L(x,lambda, u)$ 本身就代表了所有x可能取值的最小值，所以一定小於等於當 $x=ar{x}$ 的情況。這個inf是從哪裡來的呢，就是應為problem I本身是個Minimization的問題，所以Problem II也是minimization的，所以Problem II的最優化的解是inf lagrangian的解。

綜上，我們可以從 $f_0(ar{x})overset{1}{geq} L(ar{x},lambda, u)overset{2}{geq} ext{inf}_{xinmathcal{D}}L(x,lambda, u)$ 得到 $f_0(ar{x})geq ext{inf}_{xinmathcal{D}}L(x,lambda, u)$ 。1成立是因為lagrangian multiplier的設定，2成立時因為原問題是Minimize的形式，二者綜合到一起我們才得出：不論 $lambda$ 和 $u$ 取什麼值，problem II的解一定小於等於problem I的解，由於我們想要找到一個最逼近Problem I的最優解的Problem II的解，而這個difference最小的就是找到 $ext{inf}_{xinmathcal{D}}L(x,lambda, u)$ 關於 $lambda$ 和 $u$ 的最大值（原課件裡面用 $g(lambda, u)$ 來表示 $ext{inf}_{xinmathcal{D}}L(x,lambda, u)$ ，由於x此時以並非變數），所以最後最逼近Problem I的解（ $f_0(ar{x})$ ）為一個用Problem II的解裡面的一個最大值，即為 $underset{lambda, u}{ ext{max}} g(lambda, u)$ 或 $underset{lambda, u}{ ext{max}} ext{inf}_{xinmathcal{D}} L(x,lambda, u)$ 。

以上即為為什麼要引入dual problem，歸根究底是為了簡化問題的同時還想盡量保持解的正確性（注意此時我們看的是Objective function的最終值的正確性，x的正確性，所以可能兩個不同問題的x會差的比較遠，但是x帶入到兩個Objective function中，會讓兩個function的值很接近），而dual problem與original problem的最優解之間的差異就叫做duality gap或者duality。

Weak duality就是上面的例子。但通常人們想讓簡化問題的同時，正確性還保持不變，所以就對convex的問題加以研究，因為convex才有Inf，而且還好分析（主要還是由於相對其他情況比較容易），所以就有衍生出一個概念叫constraint qualification，就是看滿足在convex情況下如果才能保證我們最後的逼近解等於原解（slater"s constraint qualification），我上面給的boyd的課件里都有說，大家有興趣可以看一下。

最後再多說一句，我第一次的那個例子也是可以做的，只要把原來的Maximize改成minimize 負就可以了，但是要滿足-A是正定的矩陣，後面大家應該都會了。或者大家可以直接用maximize做，只不過把加上lagrangian變成減法，然後把不等式的方向變成相反。

1. 是，都有對偶問題

2. 是，對偶問題一定是convex的，但問題是duality gap一般不為0，而且對偶問題一般沒有closed form expression.

3. 轉化的方法取決於問題的結構和"轉化"的定義。一般來說NP-hard問題是不可能reformulate成凸問題的(除非證明P=NP)。對於具體結構的優化問題，轉化方法不一樣。比如對於geometric programming, 每個問題都可以reformulate成一個convex problem. 但是對於quadratic constrained quadratic programm(QCQP), 只能用semidefinite relaxation去近似得到一個convex problem，這個convex problem的解是原問題的一個lower bound. 還有比如對於difference of convex之類的問題，可以通過求解一系列的convex問題來得到原問題的一個stationary point (majorize-minimization). 具體的方法太多，就不展開了。

4. maximize f(x)等效於minimize -f(x)，所以對於maximization problem可以直接寫出minimization的形式。

最後建議題主先讀下Boyd的convex optimization來補充下基本知識。