原问题与对偶问题的定义和关系

2022-04-09

字数统计: 601字 | 阅读时长: 2分

阅读量

原问题与对偶问题的定义和关系

(1)原问题与对偶问题定义

一个优化问题的原问题和对偶问题定义如下：

原问题：

$最小化:~~~f(w)\\限制条件: \begin{cases} g_i(w)\leq0~~~i=1\cdots K\\ h_i(w)=0~~~i=1\cdots M \end{cases}\tag{1}$

定义一函数$L(w,\alpha,\beta)$为：

$L(w,\alpha,\beta)=f(w)+ \sum_{i=1}^K\alpha_ig_i(w)+\sum_{i=1}^M\beta_ih_i(w)\tag{2}$

当然可以用矩阵写成简单的形式：

$L(w,\alpha,\beta)=f(w)+\alpha^Tg(w)+\beta^Th(w) \tag{3}$

公式$(3)$中$\alpha^T$和$g(w)$都是$K$维的，而$\beta^T$和$h(w)$都是$M$维的。则原问题的对偶问题为：

$最大化\quad\theta(\alpha,\beta)=\inf \limits_{所有w}\{~L(w,\alpha,\beta)~\}\\限制条件：\alpha_i~\ge~0\quad(i=1\cdots K)\tag{4}$

其中$\inf \limits_{所有w}{~L(w,\alpha,\beta)~}$的意思是在限制$\alpha$和$\beta$的情况下遍历所有的$w$求最小值，即每确定一个$\alpha$和$\beta$都能算出一个最小值，即每一个$\alpha$和$\beta$都对应一个值，很明显，这是$\alpha$和$\beta$的函数，故写作$\theta(\alpha,\beta)$。那么公式$(4)$是针对所有的$\alpha$和$\beta$求最大值，即在所有的最小值中找最大的。

(2)原问题和对偶问题的关系

定理：如果$w^\ast$是原问题的解，而$\alpha^\ast$和$\beta^\ast$是对偶问题的解，则有：

$f(w^*)\ge\theta(\alpha^*,\beta^*)\tag{5}$

定理证明如下：

${ \theta(\alpha^*,\beta^*)=\inf\limits_{所有w}\{~L(w,\alpha^*,\beta^*)~\}\\ \leq L(w^*,\alpha^*,\beta^*)\\ =f(w^*)+\sum_{i=1}^K\alpha_i^*g_i(w^*)+\sum_{i=1}^M\beta_i^*h_i(w^*)\\ 利用原问题和对偶问题的限制条件可知： \\\alpha_i^*\ge0,g_i(w^*)\leq0,h_i(w^*)=0\\ 进而可得：\\ \sum_{i=1}^K\alpha_i^*g_i(w^*)\leq0,\sum_{i=1}^M\beta_i^*h_i(w^*)=0\\ 最终可得：\theta(\alpha^*,\beta^*)\leq f(w^*)-证毕 }$

接下来又有一个定义：$G=f(w^\ast)-\theta(\alpha^\ast,\beta^\ast)\ge0$，这里的${G}$叫作原问题与对偶问题的间距，对于某些特定的优化问题，可以证明$G=0$。

强对偶定理：若$f(w)$为凸函数，且$g(w)=Aw+b$(线性)，$h(w)=Cw+d$(线性)，则此优化问题原问题与对偶问题的间距为零，即$f(w^\ast)=\theta(\alpha^\ast,\beta^\ast)$，此证明比较麻烦，这里不作证明。这时我们就可以将原问题的求解转化到对偶问题的求解上来。