線性空間的對偶空間和優化里的拉格朗日對偶有什麼關係？

01-05

這兩個概念是非常有關係的。不過，要搞清楚這層關係，這個問題會變得非常深刻，對此很多著名的凸分析書都有很深入的闡述，比如R.T. Rockafellar的Convex Analysis 30章就寫的非常清楚。

http://www.convexoptimization.com/TOOLS/ConvexAnalysis.pdf

下面我給一個更intuitive的闡釋。

首先解釋為什麼在數學程度更輕的教材里我們一般看不到這兩者的關係。因為在一般的application當中（比如 $mathbb{R}^n$ 中的連續優化問題），我們考慮的problem domain（稱作 $Y$ ）都是完備的內積空間（希爾伯特空間），所以這個時候考慮拉格朗日函數裡面那個 $lambda$ 應該屬於 $Y$ 的對偶空間 $Y^*$ 沒有什麼意義，因為根據Riesz表示定理（Riesz representation theorem） $Y$ 和 $Y^*$ 是同構的。所以在這種情況下，「對偶空間」這個概念確實是多餘的。

然而從純粹數學的角度來說這種情況也只是所有情況中的一個特例。為此，不失一般性，我們考慮如下情況：讓 $Y$ 是一個有限維的在 $mathbb{R}$ 中的向量空間（不必是內積空間）。

順便先指出，凸分析里對對偶問題的核心思路其實是把一個凸集（convex set）用它的支撐超平面（hyperplanes）來表示。注意，對閉凸集（closed convex sets）來說二者可以說是等價的，因為任何一個閉凸集 $C$ 都是包含它的所有半平面（halfspaces）的交集（Theorem 11.5 in R.T. Rocafellar）。實際上這便是對集合 $C$ 的「對偶表示」。

接下來我們考慮一個真正的優化問題，即在域 $Y$ 上我們希望最小化一個凸函數 $f$ （注意，凸函數的epigraph是一個凸集）。根據上一段的討論，對偶問題的核心思路是考慮函數 $f$ 在 $Y$ 上的一個線性majorization $langle lambda,x angle - alpha$ , $lambdain Y^*$ . 注意如果給定一個固定的 $lambda$ ，我們可以選取一個「最好」的 $alpha$ :

$f(x)geq langle lambda, x angle-alpha, forall~xin Y Leftrightarrow alphageq suplimits_{xin Y} ( langle lambda, x angle-f(x))$

所以顯然我們可以選擇

$alpha=f^*(lambda)= suplimits_{xin Y} ( langle lambda, x angle-f(x))$ .

注意對任意 $lambda$ ， $alpha$ 不一定是有限的（可能趨於無窮），這種情況下對偶問題會不well-defined，會需要一些專門的regularity條件和其它討論，這裡暫且不表。只是指出實際上 $f^*(lambda)$ 實際上是 $f$ 的共軛函數（conjugate function），不了解這個定義intuition的同學可以看一下下圖這張非常直觀的解釋（圖來自Stephen Boyd的那本凸優化）。共軛函數有很多很有趣的性質，比如如果f是convex且closed的（closed表示它的epigraph是閉的）那麼 $f^{**}=f$ (這個證明的實質和Theorem 11.5是一樣的，你發現了么？)，而如果沒有convex和closed這個條件一般來說 $f^{**} = cl f$ .

注意 $f^*(lambda)$ 是定義在 $Y^*$ 上的，所以我們已經看到了對偶空間在優化理論中描述「對偶」的作用。接下來我們說明如何進一步推導出其和拉格朗日對偶的關係（我們先推導一個一般情況的）。注意在優化理論中，對偶問題是通過對原問題進行擾動（perturb）才得到的（對於這一點，不僅R.T. Rockafellar凸分析的30章寫的很好，A. Shapiro有本Perturbation Analysis of Optimization Problems整本書都在闡述這一核心思想），而不同的擾動方式會得到不同形式的對偶問題，這也是我們常看到等價的原問題會有不同的對偶形式的原因。為了說明這一點，我們考慮如下優化問題(記作原問題 $extbf{P}$ ): $min_{xin C} phi(x,0)$ ，其中 $phi:C imes D ightarrow mathbb{R}$ 是凸的。

對任意 $yin D$ ，原問題 $extbf{P}$ 的擾動問題定義為 $min_{xin C} phi(x,y)$ 。接著定義函數 $h(y)=inf_{xin C}phi(x,y)$ ，則顯然原問題 $extbf{P}$ 等價於估計 $h(0)$ 的值。注意根據共軛函數的定義我們有 $h(0)geq h^{**}(0)$ 而且滿足一些特定的regularity條件我們就有等號成立（比如 $h$ 在0點處有次梯度，這對凸函數來說是trivial的）。

由此，我們定義對偶問題 $extbf{D}$ 為估計 $h^{**}(0)$ 的值。或者利用 $h^{**}(0)$ 是 $h^*$ 在0點的共軛得到 $extbf{D}$ 的等價定義： $max_{y^*in D^*}-h^*(y^*)=max_{y^*in D^*}-phi^*(0,y^*)$ .

對比 $extbf{P}$ 關於 $phi$ 的定義，我們得到了一組min-max的對偶形式，在原問題中出現的是 $x,phi$ 和定義域 $C$ ，在對偶問題中出現的是變數 $y$ ， $phi$ 的共軛和 $D$ 的對偶空間，在數學上十分優美。

在這個數學形式下，各種優化理論的經典命題可以很容易討論。比如強對偶定理即意味著 $phi^{**}=phi$ （對偶問題perturb之後和原問題等價），而這個定理的成立要求 $Y$ 和 $Y^{**}$ 同構，這便是我們通常看不到此類討論的深層原因。

最後我們給出拉格朗日對偶是這個框架的特例。此時， $extbf{P}$ 定義為

$egin{align} min_{xin mathbb{R}}~ f(x)\ ext{s.t. } g(x)leq 0. end{align}$

可以被擾動成（對任意 $y in mathbb{R}$ ）

$egin{align} min_{xin mathbb{R}}~ f(x)\ ext{s.t. } g(x)+yleq 0. end{align}$

沿用之前的定義，我們知道 $phi(x,y)=f(x) cdot 1(g(x)+yleq 0 ) + infty cdot 1(g(x)+y>0 )$ 那麼 $extbf{P}$ 仍然可以看做在估計 $h(0)$ 的值。為了求 $extbf{D}$ ，我們知道我們需要求出 $-phi^*(0,y^*)$ 的顯式形式，即

$egin{align} -phi^*(0,y^*) = -suplimits_{g(x)+yleq 0 } (langle y^*,y angle -f(x))\ = -suplimits_{xin mathbb{R}, qgeq 0} langle y^*,-g(x)-q angle - f(x)\ = inf_{xin mathbb{R},qgeq 0} f(x)+langle y^*,g(x) angle +langle y^*,q angle. end{align}$

注意到 $mathbb{R}$ 的對偶空間和 $mathbb{R}$ 同構，我們用 $lambda$ 代替 $y^*$ ，那麼顯然 $-phi^*(0,lambda) = inf_{xin mathbb{R}} (f(x)+langle lambda,g(x) angle)cdot 1(lambdageq 0)-infty cdot 1 (lambda<0) .$

這便是拉格朗日對偶的標準形式。最後申明：我的回答非常受StackExchange上這段討論的影響：Please explain the intuition behind the dual problem in optimization.

這個問題我老師問過我。。。。

看了 @覃含章的答案感覺自己答得太淺薄了，所以只留下講義推薦和definition

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

dual space是所有linear functionals(linear map from Vector space to Field) 組成的vector space.

lagrange duality是將原來的問題轉換成一個對偶問題即primal problem 和 dual problem,其中通過解決dual problem可以給primal提供解集的一定範圍。

推薦伯村的這個講義..

https://people.eecs.berkeley.edu/~elghaoui/Teaching/EE227A/lecture7.pdf