UA SIE545 优化理论基础4 对偶理论简介6 求解对偶问题的梯度算法

UA SIE545 优化理论基础4 对偶理论简介6 求解对偶问题的梯度算法

这一讲我们介绍求解对偶问题的另一个算法——梯度算法(gradient method)。

假设原问题为
$$\underset{x\in X}{\min }f(x)s.t.g(x)\le 0,h(x)=0$$

假设$f,g,h$是连续函数，$X$是紧集。根据定义，这个优化的对偶问题是
$$\underset{u\ge 0}{\max }\theta (u,v)=\underset{u\ge 0}{\max }\underset{x\in X}{\min }f(x)+u^{T}g(x)+v^{T}h(x)$$

假设$\theta$可微。考虑对偶问题可行域中的点$(\bar{u},\bar{v})$，记
$$\bar{x}=\underset{x\in X}{\mathrm{argmin}}f(x)+{\bar{u}}^{T}g(x)+{\bar{v}}^{T}h(x)$$

则
$$\nabla \theta (\bar{u},\bar{v})=[g(\bar{x}),h(\bar{x}){]}^T$$

引理 如果$(d_u,d_v)$非零，则它是一个feasible ascent direction，其中
$$(d_u,d_v)=[\hat{g}(\bar{x}),h(\bar{x}){]}^T,{\hat{g}}_i(\bar{x})=\{\begin{array}{l}{g}_i(\bar{x}),{\bar{u}}_i>0\\ \max (0,g_i(\bar{x})),{\bar{u}}_i=0\end{array}$$

评注
i）我们先从直觉上理解一下这个结果，如果$\bar{u}$每一个分量都满足${\bar{u}}_i>0$，那么$(d_u,d_v)$就是$\theta$的梯度，这时算法思路就是无约束优化的梯度下降；如果${\bar{u}}_i=0$，说明当前位置已经位于可行域的边界了，我们必须限制这个feasible ascent direction使它不会把我们带到${\bar{u}}_i<0$的区域，因此需要定义${\hat{g}}_i(\bar{x})=\max (0,g_i(\bar{x}))$。

ii）与梯度下降类似，在有了这个feasible ascent direction之后，我们可以用line search的思路去找最优的下降步长，
$$\underset{\lambda }{\max }\{\theta (\bar{u}+\lambda d_u,\bar{v}+\lambda d_v):\bar{u}+\lambda d_u\ge 0,\lambda \ge 0\}$$

获得下一组$(\bar{u},\bar{v})$然后重复这个过程，下面证明的第一部分给出了最优值的判定准则。

证明

i）如果$(d_u,d_v)$为零向量，则$(\bar{u},\bar{v})$就已经是对偶问题的解了。

因为对偶问题的目标函数是concave function，所以对偶问题的KKT point就是最优解，我们只需说明$(\bar{u},\bar{v})$满足KKT条件即可，也就是$\exists z_1$满足
$$\begin{gathered} -{\nabla }_u\theta (\bar{u},\bar{v})-z_1=0 \\ -{\nabla }_v\theta (\bar{u},\bar{v})=0 \\ {z}_1^T\bar{u}=0,z_1\ge 0 \end{gathered}$$

因为$d_v=0$，我们知道${\nabla }_v\theta (\bar{u},\bar{v})=h(\bar{x})=0$，并且为了使$d_u=0$，需要${\nabla }_u\theta (\bar{u},\bar{v})=g(\bar{x})\le 0$，以及$g(\bar{x}{)}^T{z}_1=0$，因此存在$z_1=-g(\bar{x})$满足上述条件，所以$(\bar{u},\bar{v})$是对偶问题的解。

ii）如果$(d_u,d_v)$非零，在评注i）中我们已经说明了$(d_u,d_v)$是一个feasible direction，下面我们说明它也是一个ascent direction，计算
$$\begin{gathered} \nabla \theta (\bar{u},\bar{v}{)}^{T}d={\nabla }_u\theta (\bar{u},\bar{v}{)}^T{d}_u+{\nabla }_v\theta (\bar{u},\bar{v}{)}^T{d}_v \\ =g^T(\bar{x})\hat{g}(\bar{x})+h(\bar{x}{)}^{T}h(\bar{x}) \end{gathered}$$

显然它是大于零的。因此它是一个feasible ascent direction。

---

例 用梯度方法求解下列优化的对偶问题
$$\begin{gathered} \min x_1^2+x_2^2 \\ s.t.-x_1+x_2+4\le 0 \\ {x}_1+2x_2-8\le 0 \end{gathered}$$

假设初始值为$(u_1,u_2)=(0,0)$。

解
我们先写出对偶问题的目标函数
$$\begin{gathered} \theta (u_1,u_2)=\min \{x_1^2+x_2^2+u_1(-x_1-x_2+4) \\ +u_2(x_1+2x_2-8)\} \end{gathered}$$

第一次循环：$(u_1,u_2)=(0,0)$
$\theta (u_1,u_2)=\theta (0,0)=0$，此时$x_1=x_2=0$，因此
$$(d_1,d_2)=(\max (0,4),\max (0,-8))=(4,0)$$

此时
$$\theta (u_1+\lambda d_1,u_2+\lambda d_2)=-8{\lambda }^2+16\lambda$$

当$\lambda =1$时上式取最大值，因此下一次迭代使用$(u_1,u_2)=(4,0)$。

第二次循环：$(u_1,u_2)=(4,0)$
类似第一次循环的操作，可以计算出$(d_1,d_2)=(0,0)$，因此$(4,0)$是对偶问题的最优解。

总结

以上是生活随笔为你收集整理的UA SIE545 优化理论基础4 对偶理论简介6 求解对偶问题的梯度算法的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。