求解凸规划和变分不等式的投影收缩算法

《求解凸规划和变分不等式的投影收缩算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、1ProjectionandContractionMethodsforConvexOptimizationandMonotoneVariationalInequalities求求求解解解凸凸凸规规规划划划和和和变变变分分分不不不等等等式式式的的的投投投影影影收收收缩缩缩算算算法法法南京大学数学系何炳生hebma@nju.edu.cn21.变变变分分分不不不等等等式式式是是是一一一种种种统统统一一一的的的问问问题题题表表表述述述模模模式式式设•½

2、:(1.1)1.1可可可微微微凸凸凸优优优化化化就就就是是是一一一个个个特特特殊殊殊的的的单单单调调调变变变分分分不不不等等等式式式n设•是R中的非空闭凸集,我们先来看一个可微凸优化问题minff(x)jx2•g:(1.2)我们用rf(x)表示f(x)的梯度,将rf(x)写成F(x),可微凸优化问题就归结为求0T0x2•;(x¡x)F(x)¸0;8x2•;这就是一个变分不等式。31.2线线线性性性约约约束束束的的的可可可微微微凸凸凸优优优化化化问问问题题题minfµ(x)jAx=b;x2Xg:(1.3)设¸是Lagrange乘子,记rµ(x)=f(x),最优的(x¤;¸¤)满

3、足8<¤¤T¤T¤x2X;(x¡x)(f(x)¡A¸)¸0;8x2X(1.4):Ax¤=b如果记0101xf(x)¡AT¸u=@A;F(u)=@A和•=X£>(x¡x¤)T(f(x¤)¡

4、AT¸¤)¸0;<(x¤;y¤;¸¤)2•;(y¡y¤)T(g(y¤)¡BT¸¤)¸0;8(x;y;¸)2•;>>:¤T¤¤(¸¡¸)(Ax+By¡b)¸0;其中m•:=X£Y£<:5利利利用用用0101xf(x)¡AT¸BCBCu=ByC和和和F(u)=Bg(y)¡BT¸C;@A@A¸Ax+By¡b这这这个个个凸凸凸优优优化化化问问问题题题的的的一一一阶阶阶最最最优优优性性性条条条件件件可可可以以以写写写成成成u¤2•;(u¡u¤)TF(u¤)¸0;8u2•:1.4经经经营营营者者者追追追求求求利利利益益益最最最大大大化化化是是是一一一个个个互互互补补补问问问题题题在给定政

5、策下,经营者们会根据“贪婪原理”找到他们的最优经营方案xij(对策),是一个互补问题。1.5寻寻寻求求求最最最优优优政政政策策策是是是一一一个个个“““黑黑黑箱箱箱”””条条条件件件下下下的的的互互互补补补问问问题题题6不同类型变分不等式中的算子F对称型的非对称型的线性的Hx+cTT(H=H)Mu+q(M6=M)非线性的rf(x)2(rf(x)对称)F(u)(rF(u)不对称)对称型的变分不等式等价于一个优化问题。线性对称型变分不等式等价的优化问题1TTminfxHx+cxjx2•g:2非线性对称型变分不等式等价的优化问题minff(x)jx2•g:72.三三三个个个基基基本

6、本本不不不等等等式式式和和和投投投影影影收收收缩缩缩算算算法法法2.1变变变分分分不不不等等等式式式的的的一一一些些些基基基本本本性性性质质质一个变分不等式称为单调的,是指VI(•;F)中的F是从

7、基基基本本本性性性质质质及及及变变变分分分不不不等等等式式式等等等价价价的的的投投投影影影方方方程程程用P•(¢)表示欧氏范数下在凸集•上的投影,也就是说P•(v)=Argminfku¡vkju2•:gqv6¢6¢q¢PquB(v)uqqP@¡¡@B(u)@@q¡@qvPB(u)@©©-¡@©q-@¡PB(v)B1B1¡@¡@@¡Fig.1.ProjectiononB1Fig.2.ProjectiononB19我们记u~=P•[u¡F(u)]:Lemma1设•½Rn是闭凸集,则有Tn(v¡P•(v))(