是否所有的優化問題都可以轉化成對偶問題？

01-11

最近在學凸優化的內容，感覺把原問題轉化成對偶問題的思路真的很神奇。雖然轉化後問題的對偶間隙不一定為0，求解最優結果不一定是原問題的最優結果，但是也畢竟算是提供了一種思路。通過乘以一些運算元，把不等式，等式約束拉入到目標函數中構建拉格朗日函數，就可以完成了轉化對偶問題的第一步。
我不是學數學出身的，但是感覺有些問題在轉化後表達式過於複雜，感覺轉化為對偶問題有些吃力，比如下面這個例子：

雖然用CVX工具可以很方便的對這一優化問題進行求解，但是轉化成對偶函數這一步就是比較困難的地方。如果想求解對偶問題，難點是不是就轉化成了如何將原函數的對偶函數按照標準轉換套路正確寫出來？而這一部分是需要自己在草稿紙上細緻推導演算的……
謝謝各位……

對所有實數域上的優化問題都有其對偶問題，三步曲如下（注意，f,g並不要求是凸的）。

注意不管f,g如何，弱對偶定理永遠是成立的（即v*&<=z*），所謂的能否轉化成對偶問題主要是指強對偶定理是否成立（即是否有v*=z*）。對線性規劃，滿足特定regularity條件（一般來說並不難）的半正定規劃或凸優化問題也是成立的。至於一些非凸問題或者整數規劃問題，雖然我們不再有強對偶定理，但是通過弱對偶定理我們往往能得到對原問題的一個下界（lower bound），這對於我們求解原問題有時會有非常大的增益（比如分支定界演算法，branch and bound）。實際上就算是凸問題，各種primal-dual演算法往往也比單純的primal方法要有效，比如dual-simplex一般認為比單純simplex要好，primal-dual interior point method和最近火起來的augmented Lagrangian method (ALM)都是因為實際implemetation中的優越性。由於與題主問題或許不太相關，所以就不多提了。只是想說，個人覺得對偶確實是優化中最最重要的概念。抽象來看都可看成和泛函里的Fenchel duality theorem相關（Fenchel"s duality theorem）。

作者：JohnnyLee

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

來源：知乎

著作權歸作者所有，轉載請聯繫作者獲得授權。

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

以下回答有重大漏洞，我在上面鏈接的原版本中已修改答案，希望大家多多指教。

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

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

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

依我現在的水平，我是這麼告訴自己的，我總結出我學的任何知識一般來說只有兩個作用：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的線性表達式，由於linear既是convec也是concave，一般很容易都能求。

謝邀。

對於題主給出的特殊問題，已經有人回答了。

回答一下『是否所有的優化問題都可以轉化成對偶問題』。對於有約束優化問題一般都是可以得到dual的，只不過得到的形式不一定是閉式的（比如對Lagrangian式無法最小化primal variable從而得到閉式的dual objective），而且不一定有用（比如dual gap不是0）。對於無約束優化問題，如果能夠合理得構造出約束（不影響目標函數的情況下），也可以有dual objective。

簡單回答，如果是Linear Programming，答案是可以；

如果是Nonlinear Programming，有duality gap，一般不可以；

如果是Integer或者Mixed Integer Linear Programming，一般不可以。

歡迎關注我的專欄：

[運籌帷幄]大數據和人工智慧時代下的運籌學 - 知乎專欄

就加一句…cvx可以直接定義各constriant的dual variable，很方便，不用寫兩個問題解。也不用在草稿紙上細緻推演。當然剛學LP的時候，自己在草稿紙上寫寫dual是個很好的練習方式。吐槽一下自己現在寫個dual還要看小表格，也是沒救。

%%begin cvx

n=size(A,2);

cvx_begin

variable x(n);

dual variable lambda;

maximize (sum(log(x))