本文主要对优化中的对偶和泛函分析中的对偶作一点联系。本文的阅读需要一定的泛函分析知识。

共轭函数

下面要用到的一个概念是共轭函数(conjugate function)：设X为一赋范向量空间，函数f:X\to\mathbb R的共轭函数为f^\ast:X^\prime \to\overline{\mathbb R}，定义为
x^\prime \mapsto\sup _ {x}\, [x^\prime (x)-f(x)],\quad x^\prime \in X^\prime .其中X^\prime是X的对偶空间(dual space)，那么x^\prime自然是其中的连续线性泛函了。

在泛函分析里我们知道X可以看作是X^{\prime\prime}的子空间（在一个线性同距(linear isometry)之下，称作典则同距(canonical isometry)）：映射J:x\in X\to Jx\in X^{\prime\prime}定义为Jx(x^\prime ):= x^\prime (x)\, (\forall x^\prime \in X^\prime )。我们可以证明f^{\ast\ast}(Jx)\leqslant f(x)——由定义f^\ast(x^\prime )\geqslant x^\prime (x)-f(x)，即f(x)\geqslant Jx(x^\prime )-f^\ast(x^\prime )，这对任何x^\prime \in X^\prime成立，故f(x)\geqslant\sup _ {x^\prime \in X^\prime }[Jx(x^\prime )-f^\ast(x^\prime )]=f^{\ast\ast}(Jx)。

命题：f^{\ast\ast}\leqslant f，其中左边自变量是Jx，右边是x。

当f是闭函数（即图像\{(x,f(x))\}是闭的）、凸函数，那么等号成立。

命题：f^{\ast\ast}=f，其中左边自变量是Jx，右边是x，函数f是闭的凸函数。

证明：考虑上图像\operatorname{epi} f:=\{(x,t)\mid t\geqslant f(x)\}，f闭、凸，则\operatorname{epi}f闭、凸。我们只需要证f^{\ast\ast}(Jx)\geqslant f(x)，若不然，存在x _ 0使得f^{\ast\ast}(Jx _ 0)<f(x _ 0)。由凸集的严格分离（Hahn-Banach定理的几何表述之一），存在\ell\in (X\times\mathbb R)^\prime，c\in \mathbb R和\delta>0使得\ell(x,t)<c<\ell(x _ 0,f^{\ast\ast}(Jx _ 0)) (\forall (x,t)\in\operatorname{epi}f)，我们可以求出\ell：\ell(x,t)=\ell(x,0)+\ell(0,t)=x^\prime (x)+bt (x^\prime \in X^\prime ,\, b\in\mathbb R)，于是x^\prime (x)+bt<c<x^\prime (x _ 0)+bf^{\ast\ast}(Jx _ 0)，即：存在x^\prime ,x _ 0,b,c使得对所有(x,t)\in\operatorname{epi}f该不等式成立。可以看出b\neq0，否则取x=x _ 0就矛盾；也不会b>0，否则可取t充分大导致矛盾。对于负数b，可不妨设b=-1，再令t=f(x)得x^\prime (x)-f(x)<c<x^\prime (x _ 0)-f^{\ast\ast}(Jx _ 0)两边对x取上确界得f^\ast(x^\prime )<x^\prime (x _ 0)-f^{\ast\ast}(Jx _ 0)，但由定义f^{\ast\ast}(Jx _ 0)\geqslant Jx _ 0(x^\prime )-f^\ast(x^\prime )=x^\prime (x _ 0)-f^\ast(x^\prime )，矛盾。

优化问题的扰动

假设我们的优化问题可以以某种方式参数化，使其能表示为
\min _ \boldsymbol x\psi(\boldsymbol x,\boldsymbol 0)其扰动问题为
\min _ \boldsymbol x\psi(\boldsymbol x,\boldsymbol y).此时将\inf _ \boldsymbol x\psi(\boldsymbol x,\boldsymbol y)看作是\boldsymbol y的函数q(\boldsymbol y)，\boldsymbol y\in Y，那么原问题就对应q(\boldsymbol 0)，由共轭函数的性质：q(\boldsymbol 0)\geqslant q^{\ast\ast}(J(\boldsymbol 0))。

对偶问题即是计算q^{\ast\ast}(J(\boldsymbol 0))，而q^{\ast\ast}(J(\boldsymbol 0))=\sup _ {y^\prime \in Y^\prime }\, [J _ \boldsymbol 0(y^\prime )-q^\ast(y^\prime )]=\sup _ {y^\prime \in Y^\prime }\, [-q^\ast(y^\prime )]（对偶函数即是-q^\ast(y^\prime )）。

这是一个在Y的对偶空间上的优化问题。

形式上我们也将对偶问题也写作\psi的形式：\max _ {y^\prime \in Y^\prime }[-\psi^\ast(\boldsymbol 0,y^\prime )]。那么，原问题与对偶问题（形式稍作修改）写在一起就变为了
\min _ {\boldsymbol x\in X}\;\psi(\boldsymbol x,\boldsymbol 0)\quad\longleftrightarrow\quad\min _ {y^\prime \in Y^\prime }\psi^\ast(\boldsymbol 0,y^\prime ).

导出Lagrange对偶

为了描述的简明，下面只写出不等约束，加进等式约束只是多一半类似的表述而已。考虑优化问题
\begin{aligned}\min _ \boldsymbol x&\quad f(\boldsymbol x)\\\text{s.t. }&\quad \boldsymbol g(\boldsymbol x)\geqslant0.\end{aligned}此即考虑优化
\min\phi(\boldsymbol x,\boldsymbol y)=\min\; [f(\boldsymbol x)\, \mathbb I(\boldsymbol g(\boldsymbol x)\geqslant \boldsymbol y)+\infty\, \mathbb I(\boldsymbol g(\boldsymbol x)\ngeqslant\boldsymbol y)].对偶问题需计算对偶函数-q^{\ast}(y^\prime )，
\begin{aligned}-q^\ast(y^\prime )&=-\sup _ {\boldsymbol y}\, [y^\prime (\boldsymbol y)-q(\boldsymbol y)]=\inf _ {\boldsymbol y}\, -[y^\prime (\boldsymbol y)-\phi(\boldsymbol x,\boldsymbol y)]=\inf _ {\boldsymbol g(\boldsymbol x)\geqslant\boldsymbol y}\, -[y^\prime (\boldsymbol y)-f(\boldsymbol x)]\\&=\inf _ {\boldsymbol g(\boldsymbol x)-\boldsymbol y\geqslant 0}\, -[y^\prime (\boldsymbol g(\boldsymbol x))-y^\prime (\boldsymbol g(\boldsymbol x)-\boldsymbol y)-f(\boldsymbol x)]\\&=\inf _ {\boldsymbol g(\boldsymbol x)-\boldsymbol y\geqslant 0}\, [f(\boldsymbol x)-y^\prime (\boldsymbol g(\boldsymbol x))+y^\prime (\boldsymbol g(\boldsymbol x)-\boldsymbol y)].\end{aligned}如果存在\tilde{\boldsymbol y}\geqslant0，使得y^\prime (\tilde{\boldsymbol y})<0，那么显然此时对偶函数的值为-\infty；若对\tilde{\boldsymbol y}\geqslant0总有y^\prime (\tilde{\boldsymbol y})\geqslant0，那么对偶函数为
-q^\ast(y^\prime )=\inf _ {\boldsymbol x}\, [f(\boldsymbol x)-y^\prime (\boldsymbol g(\boldsymbol x))].对偶问题：\max _ {y^\prime }(-q^\ast(y^\prime ))。

现在要导出我们熟悉的Lagrange对偶的形式。这是一般情形下的特殊化。考虑Y是Hilbert空间，此时我们可以对空间中的连续线性泛函用内积来表示。用到的是如下的F. Riesz表示定理：

Hilbert空间中的F. Riesz表示定理：对任一y^\prime \in Y，存在一个且仅存在一个y _ 0\in Y使得y^\prime (y)=(y,y _ 0) (\forall y\in Y)。

现在我们令Y=\mathbb R^p，内积为常规的欧几里得内积。设y^\prime对应的是y，对偶函数此时写为
\phi(\boldsymbol y)=\inf _ {\boldsymbol x}\, [f(\boldsymbol x)-\boldsymbol y^\mathsf T\boldsymbol g(\boldsymbol x)],\quad \forall\boldsymbol y\geqslant0.这正是我们前面定义的Lagrange函数。对偶问题当然也一致了。与此同时，由于Hilbert空间是自反的(reflexive)，即X^{\prime\prime}=X，所以前面的关于共轭函数的结论可以写得更为直观：f^{\ast\ast}(\boldsymbol x)\leqslant f(\boldsymbol x)，对所有\boldsymbol x\in\mathbb R^p。

现在我们可以得出小结论：Lagrange函数中的Lagrange乘数即对应对偶空间中的向量。