本文主要对优化中的对偶和泛函分析中的对偶作一点联系。本文的阅读需要一定的泛函分析知识。
共轭函数
下面要用到的一个概念是共轭函数(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乘数即对应对偶空间中的向量。
发表回复