對偶性 (最佳化)

在最优化理論中的對偶（duality）或對偶性原則（duality principle）是指最佳化問題可以用兩種觀點來看待的理論，兩種觀點分別是「原始問題」（primal problem）及「對偶問題」（dual problem）。對偶問題的解提供了原始問題（假設是最小化問題）的下限，不過一般而言，原始問題和對偶問題的最佳解不相同。兩個最佳解的差距為對偶間隙。若是凸優化問題，對偶間隙也稱為是卡鲁什-库恩-塔克条件。

對偶問題

一般而言「對偶問題」是指「拉格朗日對偶問題」（Lagrangian dual problem），不過也有其他的對偶問題，例如Template:Le和Template:Le。拉格朗日對偶問題是指在最小化問題上加上拉格朗日乘数，也就是在目標函數上加上對應限制條件的非負拉格朗日乘数，再求解可將原目標函數最小的原始變數值。此解會得到以拉格朗日乘数的函數表示的原始變數，稱為是「對偶變數」（dual variables），因此，新的問題就是要衍生對偶變數的限制下（包括非負的限制條件），找到可以使目標函數最大化的對偶變數。

一般而言，給定二個Template:Le的分隔Template:Le $(X,X^{*})$及$(Y,Y^{*})$，以及函數$f:X\to ℝ\cup \{+\mathrm{\infty }\}$，可以定義原始問題為找到$\hat{x}$使得$f(\hat{x})=\underset{x\in X}{\inf }f(x).$ 換句話說，若$\hat{x}$存在，$f(\hat{x})$是函數$f$的最小极值（minimum），也可以得到函數的最大下界（infimum）。

若有限制條件，可以整合到函數$f$中，方式是令$f=f+I_{\text{constraints}}$，其中$I_{\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{s}\mathrm{t}\mathrm{r}\mathrm{a}\mathrm{i}\mathrm{n}\mathrm{t}\mathrm{s}}$是在$X$上的適當函數，在限制條件上有最小值0，可以證明$\underset{x\in X}{\inf }\tilde{f}(x)=\underset{x\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{s}\mathrm{t}\mathrm{r}\mathrm{a}\mathrm{i}\mathrm{n}\mathrm{e}\mathrm{d}}{\inf }f(x)$。後者的條件很明顯，但不一定很方便可以符合示性函数（也就是說，滿足限制條件的$x$，$I_{\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{s}\mathrm{t}\mathrm{r}\mathrm{a}\mathrm{i}\mathrm{n}\mathrm{t}\mathrm{s}}(x)=0$，在其他情形，$I_{\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{s}\mathrm{t}\mathrm{r}\mathrm{a}\mathrm{i}\mathrm{n}\mathrm{t}\mathrm{s}}(x)=\mathrm{\infty }$）。因此可以將$\tilde{f}$延伸為擾動函數$F:X\times Y\to ℝ\cup \{+\mathrm{\infty }\}$使得$F(x,0)=\tilde{f}(x)$。

對偶間隙就是不等式

$\underset{y^{*}\in Y^{*}}{\sup }-F^{*}(0,y^{*})\le \underset{x\in X}{\inf }F(x,0),$

左側和右側的差。

其中$F^{*}$是二個變數的凸共轭，而$\sup$是上确界

線性規劃

Template:Main 线性规划問題是指损失函数和約束都是線性關係的最优化問題。原始問題中，目標函數是n個變數的線性組合，問題有m個約束，每一個都有上限，上限由n個變數的線性組合表示。其目的是要在滿足限制條件的情形下，最大化目標函數的值。其解是由n個值表示的向量，可以讓目標函數有最大值。

在對偶問題中，目標函數是m個值的線性組合，這些是原始問題中m個限制條件的上下限。有n個對偶限制條件，每一個的下限都是由m個對偶變數的線性組合所表示。

原始問題和對偶問題的關係

針對線性的最佳化問題，在原始問題中每一個符合限制條件的次佳點，都有一個方向（或方向的子空间），可以往目標函數增加的方向移動。若往這類的方向移動，稱為除去Template:Le和一個或多個限制之間的鬆弛量（slack）。候選解中不可行的值即為超過一個或多個限制的值。

在對偶問題中，會將對偶向量和限制條件相乘，這些限制條件會決定原始問題中限制條件的位置。在對偶問題中變動對偶向量類似在原始問題中調整上限。要找到最小的上限。也就是說，要將對偶向量最小化，以移除限制的候選位置和實際最佳解之間的鬆弛量（slack）。對偶向量中的不可行值是指哪些太低的值。這會讓候選解的一個或多個限制條件落在排除實際最佳解的位置。

在线性规划中探討對偶性的方程式中，會對上述直覺有型式化的敘述。

非線性規劃

非线性规划中的限制條件不一定是線性的，不過許多线性规划的原則還是適用。

為了確保可以簡單的識別非线性规划中的全域最大值，問題一般會要求函數要是凸函數，而且有緊緻的lower level sets。

由此可以看出卡鲁什-库恩-塔克条件的重要性。卡鲁什-库恩-塔克条件可以提供非線性規劃問題中識別局部最佳值的必要條件。也有一些額外的必要條件（約束規範，constraint qualifications）可以用來判斷可能有「最佳解」（是局部最佳解，但不一定是全域最佳解）的方式。

強拉格朗日原則：拉格朗日對偶Template:Anchor

考慮以下形式的非線性規劃：

$\begin{array}{cc}\text{minimize }& f_0(x)\\ \text{subject to }& f_i(x)\le 0,i\in \{1,\dots ,m\}\\ & h_i(x)=0,i\in \{1,\dots ,p\}\end{array}$

其定義域$𝒟\subset {ℝ}^n$有非空的內部。其拉格朗日函數$\mathrm{\Lambda }:{ℝ}^n\times {ℝ}^m\times {ℝ}^p\to ℝ$定義為

$\mathrm{\Lambda }(x,\lambda ,\nu )=f_0(x)+\sum _{i=1}^m{\lambda }_i{f}_i(x)+\sum _{i=1}^p{\nu }_i{h}_i(x).$

向量$\lambda$和$\nu$是有關此問題的「對偶變數」（dual variables）或拉格朗日乘數向量（Lagrange multiplier vectors）。拉格朗日對偶函數（Lagrange dual function）$g:{ℝ}^m\times {ℝ}^p\to ℝ$定義如下

$g(\lambda ,\nu )=\underset{x\in 𝒟}{\inf }\mathrm{\Lambda }(x,\lambda ,\nu )=\underset{x\in 𝒟}{\inf }(f_0(x)+\sum _{i=1}^m{\lambda }_i{f}_i(x)+\sum _{i=1}^p{\nu }_i{h}_i(x)).$

對偶函數g是凹函數，就算初始問題不是凸也會如此，因為是仿射函數的點狀最大下界。對偶函數提供初始問題最佳值$p^{*}$的下界：針對任意$\lambda \ge 0$及任意$\nu$，可以得到$g(\lambda ,\nu )\le p^{*}$。

若滿足約束規範（例如Template:Le），且原問題是凸，則可以得到Template:Le$d^{*}=\underset{\lambda \ge 0,\nu }{\max }g(\lambda ,\nu )=\inf f_0=p^{*}$。

凸問題

針對有不等式限制的凸最小化問題

$\begin{array}{cccc}& \underset{x}{\mathrm{minimize}}& & f(x)\\ & \mathrm{s}\mathrm{u}\mathrm{b}\mathrm{j}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{t}\mathrm{o}& & g_i(x)\le 0,i=1,\dots ,m\end{array}$

拉格朗日對偶問題為

$\begin{array}{cccc}& \underset{u}{\mathrm{maximize}}& & \underset{x}{\inf }(f(x)+\sum _{j=1}^m{u}_j{g}_j(x))\\ & \mathrm{s}\mathrm{u}\mathrm{b}\mathrm{j}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{t}\mathrm{o}& & u_i\ge 0,i=1,\dots ,m\end{array}$

其中目標函數是拉格朗日對偶函數。假設函數$f$ and $g_1,\dots ,g_m$ 連續可微，最大下界出現在梯度等於零的位置。問題

$\begin{array}{cccc}& \underset{x,u}{\mathrm{maximize}}& & f(x)+\sum _{j=1}^m{u}_j{g}_j(x)\\ & \mathrm{s}\mathrm{u}\mathrm{b}\mathrm{j}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{t}\mathrm{o}& & \mathrm{\nabla }f(x)+\sum _{j=1}^m{u}_j\mathrm{\nabla }{g}_j(x)=0\\ & & & u_i\ge 0,i=1,\dots ,m\end{array}$

稱為Wolfe對偶問題。此問題用計算的方式處理可能會很困難，因為目標函數在聯合變數$(u,x)$上不是凹。而且，一般而言，等式的限制條件$\mathrm{\nabla }f(x)+\sum _{j=1}^m{u}_j\mathrm{\nabla }{g}_j(x)$也是非線性的，因此Wolfe對偶問題一般而言會不會是凸最佳化問題。不論如何，Template:Le會成立。

歷史

依照喬治·伯納德·丹齊格所述，在丹齊格提出了線性規劃問題後，约翰·冯·诺伊曼就提出了線性規劃的對偶性定理的猜想。冯·诺伊曼注意到他使用了來自其博弈论中的資訊，並且猜想兩人零和的矩陣博弈和線性規劃等效。嚴謹的證明最早是由阿尔伯特·塔克和其團隊發表（丹齊格在Nering和塔克1993年著作中的前言）

相關條目

• 凸共轭
• 对偶 (数学)
• Template:Le

參考資料

書籍

• Template:Cite book
• Template:Cite book
• Template:Cite book
• Template:Cite book
• Template:Cite book
• Template:Cite book
• Template:Cite book
• Template:Cite book
• Template:Cite book
• Template:Cite book
• Template:Cite book
• Template:Cite book
• Template:Cite book
• Template:Cite book
• Template:Cite book
• Template:Cite book

論文

• Template:Cite journal
• Template:Cite journal
• Duality in Linear Programming Template:Wayback Gary D. Knott