《凸优化和单调变分不等式的收缩算法》由会员分享，可在线阅读，更多相关《凸优化和单调变分不等式的收缩算法（28页珍藏版）》请在金锄头文库上搜索。
1、P - 1凸凸凸优优优化化化和和和单单单调调调变变变分分分不不不等等等式式式的的的收收收缩缩缩算算算法法法 统统统一一一框框框架架架与与与应应应用用用前前前言言言目目目录录录与与与各各各章章章提提提要要要南京大学数学系何炳生P - 2一一一个个个科科科学学学家家家最最最大大大的的的本本本领领领就就就在在在于于于化化化复复复杂杂杂为为为简简简单单单,用用用简简简单单单的的的方方方法法法去去去解解解决决决复复复杂杂杂的的的问问问题题题。 冯冯冯康康康z先贤名言,铭记在心。纵然可以没有本领,也不迷失价值标准z爱爱爱美美美之之之心心心,人人人皆皆皆有有有之之之。数数数学学学往往往往往往被被被人人人认认
2、认为为为是是是枯枯枯燥燥燥的的的,计计计算算算更更更是是是被被被人人人看看看作作作是是是繁繁繁琐琐琐的的的。领领领悟悟悟了了了数数数学学学之之之美美美的的的数数数学学学工工工作作作者者者,他他他的的的职职职业业业生生生涯涯涯才才才可可可能能能是是是充充充满满满乐乐乐趣趣趣的的的。z世上三百六十行,应是同一道理z数数数学学学之之之美美美,不不不是是是纯纯纯数数数学学学的的的专专专利利利。为为为应应应用用用服服服务务务的的的最最最优优优化化化方方方法法法研研研究究究,同同同样样样可可可以以以追追追求求求简简简单单单与与与统统统一一一。只只只因因因自自自以以以为为为发发发现现现了了了其其其中中中的的
3、的数数数学学学之之之美美美,研研研究究究才才才变变变得得得满满满怀怀怀激激激情情情和和和欲欲欲罢罢罢不不不能能能。P - 3对凸规划和单调变分不等式的收缩算法的研究,我们始终追求简明统一的原则。一个统一框架,二个孪生方向,三个基本不等式。不同方向,竟可用相同步长。漂亮的形式,令我沾沾自喜。但也常问自己,或以平庸为神奇?统一框架,指导我们针对问题设计算法,也帮助我们简化算法的收敛性证明。理论有了保证,还要计算验证。 尺有所短,寸有所长。 自己动手编程,多些计算体验,才能给初学者提些有价值的参考意见。投影收缩算法的定义在Springer出版社1975年出版的Blum和Oettli的德文专著中就有了
4、说明,作者均是苏黎世大学的博士,Oettli生前曾是Math.Programming的编委。出于对历史的敬畏和对前人工作的尊重,根据算法具有的收缩特征,我们把所述方法都称为收缩方法。从研究出发点开始,介绍收缩算法的基本原理。分若干篇章,对问题类型和主要方法作了梳理。谈问题,说算法,讲应用,给基本算例,也附简单程序。一条主线,一个模式。读懂一个算法,理解后面的篇章就不要再费多少力气。One algorithm framework should be flexible enough to solve many problems !P - 4凸凸凸优优优化化化和和和单单单调调调变变变分分分不不不等等
5、等式式式的的的收收收缩缩缩算算算法法法 目目目录录录第第第一一一部部部分分分:单单单调调调变变变分分分不不不等等等式式式的的的求求求解解解方方方法法法第第第一一一讲讲讲变分不等式作为多种问题的统一表述模式第第第二二二讲讲讲三个基本不等式和变分不等式的投影收缩算法第第第三三三讲讲讲单调变分不等式收缩算法的统一框架第第第二二二部部部分分分:凸凸凸优优优化化化问问问题题题 minf(x)|Ax = b,x X 的的的求求求解解解方方方法法法第第第四四四讲讲讲为线性约束凸优化问题定制的PPA算法及其应用第第第五五五讲讲讲线性约束凸优化问题基于松弛PPA的收缩算法第第第六六六讲讲讲线性约束凸优化扩展问题
6、的PPA和松弛PPA算法第第第七七七讲讲讲基于增广Lagrange乘子法的PPA收缩算法P - 5第第第三三三部部部分分分:基基基于于于投投投影影影梯梯梯度度度的的的收收收缩缩缩算算算法法法第第第八八八讲讲讲基于梯度投影的凸优化收缩算法和下降算法第第第九九九讲讲讲线性约束凸优化基于对偶上升的自适应方法第第第十十十讲讲讲线性约束单调变分不等式的自适应投影收缩算法第第第四四四部部部分分分:凸凸凸优优优化化化问问问题题题minn1(x) + 2(y)flflflAx + By = bx X,y Yo的的的交交交替替替方方方向向向法法法第第第十十十一一一讲讲讲结构型优化的交替方向收缩算法第第第十十十二
7、二二讲讲讲线性化的交替方向收缩算法第第第十十十三三三讲讲讲定制PPA算法意义下的交替方向法第第第十十十四四四讲讲讲定制PPA算法意义的线性化交替方向法P - 6第第第五五五部部部分分分:多多多个个个可可可分分分离离离算算算子子子凸凸凸优优优化化化问问问题题题带带带简简简单单单校校校正正正的的的分分分裂裂裂方方方法法法第第第十十十五五五讲讲讲三个可分离算子凸优化的平行分裂ALM乘子法第第第十十十六六六讲讲讲三个可分离算子凸优化的略有改动的交替方向法第第第十十十七七七讲讲讲多个可分离算子凸优化带回代的交替方向收缩算法第第第十十十八八八讲讲讲多个可分离算子凸优化带回代的线性化交替方向法第第第六六六部
8、部部分分分:计计计算算算复复复杂杂杂性性性分分分析析析第第第十十十九九九讲讲讲L-连续的单调变分不等式投影收缩算法的收敛速率第第第二二二十十十讲讲讲交替方向法的计算复杂性和收敛速率可可可只只只读读读不不不带带带 的的的篇篇篇章章章.分分分解解解降降降低低低难难难度度度,整整整合合合把把把握握握方方方向向向,是是是该该该系系系列列列讲讲讲义义义的的的主主主要要要思思思想想想.懂懂懂些些些变变变分分分不不不等等等式式式的的的基基基本本本概概概念念念,对对对凸凸凸优优优化化化收收收缩缩缩算算算法法法的的的设设设计计计和和和收收收敛敛敛性性性分分分析析析很很很有有有帮帮帮助助助.P - 7凸凸凸优优优
9、化化化和和和单单单调调调变变变分分分不不不等等等式式式的的的收收收缩缩缩算算算法法法 内内内容容容提提提要要要1.变变变分分分不不不等等等式式式作作作为为为多多多种种种问问问题题题的的的统统统一一一表表表述述述模模模式式式变分不等式的一般形式是:求u ,(u u)TF(u) 0,u .应用科学中,特别是统计与机器学习中的许多问题都可以归结为形如min(x) | Ax = b, x X或者min1(x) + 2(y) | Ax + By = b, x X, y Y的凸优化问题。它们的一阶必要性条件就是一个单调变分不等式,其中F(u) =(x) ATAx b!或F(u) =1(x) AT2(y)
10、BTAx + By b.相应的 = X m或者 = X Y 0.基本不等式的组合提供了距离函数 kuuk2的下降方向 d(u, u).对典型的线性和非线性变分不等式,构造到解集距离越来越近的收缩算法.由于 u 是由投影得来的,这类算法称为投影收缩算法.算例说明,投影收缩算法效率比花费相当的外梯度算法(Extragradient Methods)有明显的提高。P - 93.单单单调调调变变变分分分不不不等等等式式式收收收缩缩缩算算算法法法的的的统统统一一一框框框架架架对给定的 u,由一定的法则生成 u ,如果 u = u u ,这样的 u称作检验点或者预测点。生成检验点 u 的公式往往能写成 u
11、 ,(u0 u)Td2(u, u) d1(u, u) 0, u0 .或其等价形式 u = P u d2(u, u) d1(u, u).由投影 u = PuF(u) 得到的检验点,可以写成 u = P ud2(u, u)d1(u, u)其中d1(u, u) = (u u) (F(u) F( u)和d2(u, u) = F( u).这样的 d1(u, u) 和 d2(u, u) 称为一对孪生方向.不难找到( u u)Td2(u, u) + (u u)Td1(u, u)的下界函数 (u, u) ku uk2满足 (u, u) = 0 u = u.例如：PPA算法从 u 得到的 u 满足 u , (u
12、0 u)TF( u) + ( u u) 0, u0 . u 就是一个检验点.记 d1(u, u) = u u,d2(u, u) = F( u) 和 (u, u) = ku uk2就有 = 1.由此对任何解点 u,得到二个几乎相同的不等式：(u u)Td1(u, u) (u, u)和(u u)Td2(u, u) (u, u).不同的只是后者只对属于 的 u 成立.用相同的步长 ,不同的迭代公式uk+1= uk d1(uk, uk)和uk+1= Puk d2(uk, uk)产生的序列 uk 有同样的理论性质.算例说明了不同算法的效率差别。P - 104.为为为线线线性性性约约约束束束凸凸凸优优优化
13、化化定定定制制制的的的PPA算算算法法法及及及其其其应应应用用用在 min(x) +r2kx ak2|x X 容易求解的假设下,对凸优化问题min(x) | Ax = b, x X等价的变分不等式VI(,F) 给出了一个 G-模下的PPA算法,这里u =x!,F(u) =(x) ATAx b!, = X kATAk 的假设下,生成的预测点 uk满足 uk ,(u uk)TF( uk) + G( uk uk) 0, u ,其中 G 是正定矩阵.这是 G-模下PPA算法的基本框架.用uk+1= uk (uk uk), (0,2)产生的序列 uk 就满足kuk+1 uk2G kuk uk2G (2
14、)kuk ukk2G这样的PPA收缩性质.给出了典型算例,说明方法简单,效果不错。P - 115.线线线性性性约约约束束束凸凸凸优优优化化化问问问题题题基基基于于于松松松弛弛弛PPA的的的收收收缩缩缩算算算法法法在 min(x) +r2kx ak2|x X 容易求解的假设下,对凸优化问题min(x) | Ax b, x X等价的变分不等式VI(,F) 给出了一个基于松弛PPA的收投影收缩算法.对给定的 uk= (xk,k) 和 r 0,通过求解min(x) +r2?x xk+1rATk?2flflx X“得到Primal预测点 xk.再用自调比法则选取适当的 s,并用k= Pk1s(A xk
15、b)生成Dual预测点k.在一定条件下,这样得到的预测点 uk满足 uk ,(u uk)TF( uk) Hd(uk, uk) 0, u ,其中 H 是正定矩阵.这是统一框架中的基本形式.用收缩算法的步长准则确定 k,由迭代公式uk+1= uk kd(uk, uk)产生的序列uk 具有 H-模下的收缩性质(c0 0 为常数)kuk+1 uk2H kuk uk2H c0kuk ukk2H.与前一讲的PPA算法比,需多算一个步长,但计算实践说明总花费更少。P - 126.线线线性性性约约约束束束凸凸凸优优优化化化扩扩扩展展展问问问题题题的的的PPA和和和松松松弛弛弛PPA收收收缩缩缩算算算法法法还是
16、在问题 min(x) +r2kx ak2|x X 容易求解的假设下,对凸优化扩展问题min(x) | Ax B, x X等价的变分不等式给出类似于前二讲的收缩算法。与前二讲的方法相比,只是生成预测点的Dual部分k的公式有了改变。如果采用PPA根据求 xk和k的不同顺序,分别由k=1sPBAxk sk (Axk sk)“和k=1sPBA(2 xk xk) sk A(2 xk xk) sk“给出k.在其他公式全部相同的情况下,得到相应的求解扩展问题的PPA方法.当这里的 B 退化成 B = b 时,上面两个生成Dual预测点k的公式就分别变成前两讲中的k= k1s(Axk b)和k= k1s(A
17、(2 xk xk) b).按照同样的思路,也可以将松弛PPA算法改造后用来求解扩展问题。P - 137.基基基于于于增增增广广广Lagrange乘乘乘子子子法法法的的的PPA收收收缩缩缩算算算法法法凸优化问题min(x) | Ax = b, x X的增广Lagrange函数LA(x,) = (x)T(Ax b) +12skAx bk2,多加了二次函数12skAx bk2.增广Lagrange乘子法中 x 只是中间变量.对给定的 k,通过求解 x 的子问题 minLA(x,k)|x X 得 xk,再用k+1= ks(A xk b), (0,2)产生新的迭代点 k+1,迭代序列 k 满足kk+1k
18、2 kk k2 (2 )k1s(A xk b)k2.在只有形如 min(x) +r2kx ak2|x X 的问题才容易求解的假设下,对增广Lagrange函数的二次部分12skAx bk2做线性化近似,并加上正则项r2kx xkk2.这样迭代就要从 uk= (xk,k) 出发,通过求解min (x) +1s(Axk b) sk)TAx +r2kx xkk2|x X得到Primal预测点 xk.再由k= k1(A xk b) 给出Dual预测点k.当 rs kATAk 时,生成的预测点 uk满足统一框架中PPA算法的条件: uk ,(u uk)TF( uk) + G( uk uk) 0, u0
19、.用 uk+1= uk (uk uk) 产生 G-模下 kuk ukG 的收缩序列。P - 148.基基基于于于梯梯梯度度度投投投影影影的的的凸凸凸优优优化化化收收收缩缩缩算算算法法法和和和下下下降降降算算算法法法讨论可微凸优化min f(x) | x 的梯度算法.对无约束凸二次规划,有关方法相当于缩短了步长的最速下降法.有算例说明,最速下降法故意缩短步长,收敛速率却有令人难以置信的数量级提高.现实生活中有一类变分不等式x ,(x x)Tg(x) 0, x ,其中 g(x) 是某个凸函数 f(x) 的梯度.这种变分不等式形式上等价于所讨论的约束凸优化问题,然而 f(x) 是无法提供的,只是对给
20、定的 x,可以观测到 g(x),求解时只有 g(x) 的信息可以使用.采用迭代公式xk+1= Pxk kg(xk),要求 xk,步长 k和新的迭代点 xk+1满足(xk xk+1)T(g(xk) g(xk+1) (/k)kxk xk+1k2, (0,1).这样产生的序列 xk 隐含了(那个我们并不知道的)f(x) 满足下降性质f(xk+1) f(xk) (1 )/kkxk xk+1k2.对第一讲提及的经济平衡互补问题求解,说明了方法的实用性和优越性.P - 159.线线线性性性约约约束束束凸凸凸优优优化化化基基基于于于对对对偶偶偶上上上升升升的的的自自自适适适应应应方方方法法法凸优化问题min
21、f(x) | Ax = b, x X 的Lagrange的对偶问题是(maxx,L(x,) = f(x) T(Ax b)s. tx X, (x0 x)TxL(x,) 0, x0 X.一对 (x,) 被说成是对偶可行当且仅当x X, (x0 x)T(f(x) AT) 0, x0 X.换句话说,对给定的 k m,通过求解 minL(x,k)flflx X 得到 xk,这样的一对 (xk,k) 就是对偶可行的.从对偶可行的 (xk,k) 开始,令k+1= k k(Axk b),并通过 xk+1=ArgminL(x,k+1)flflx X 求得 xk+1,要求它们满足(k k+1)TA(xk xk+1
22、) (/k)kk k+1k2, (0,1).这样产生的序列 (xk,k) 使对偶问题的目标函数满足上升性质L(xk+1,k+1) L(xk,k) (1 )/kkk k+1k2.对第四、 五讲提及的相关性矩阵校正问题求解并与前述方法比较,收敛速度几乎提高了一倍.说明对某些问题对偶上升方法是很有效的方法.P - 1610.线线线性性性约约约束束束单单单调调调变变变分分分不不不等等等式式式的的的自自自适适适应应应投投投影影影收收收缩缩缩算算算法法法设 A mn, b m.线性约束的单调变分不等式是求 x S,使得(x x)Tf(x) 0,x S,其中 S = x n| ATx = b (or ATx
23、 b), x X.这类问题大量出现在交通网络分析里.可微凸优化 min(x)|x S,记 f(x) = (x),就可以描述成这类变分不等式的特例,对这类凸优化问题,这一讲的方法是只用梯度的方法.对线性约束引入Lagrange乘子 ,问题要求 (x,),(x X,(x x)Tf(x) + A 0,x X, ,( )T(ATx+ b) 0, ,其中 = m(ATx = b) 或者 = m+(ATx b).它的紧凑形式是u ,(u0 u)TF(u) 0,u0 .不同于简单投影 uk= Puk kF(uk),我们用Gauss-Seidel型的投影k= Pk+k(ATxk b), xk= PXxk kf
24、(xk) + Ak“,得到预测点 uk= ( xk,k),在第二个投影中用了刚刚更新的k.进而根据第三讲变分不等式收缩算法的统一框架,构造收缩算法.由于预测点由投影得来,迭代序列 uk 又向解集收缩,算法还称为投影收缩算法.P - 1711.结结结构构构型型型优优优化化化的的的交交交替替替方方方向向向法法法从这讲开始的四讲考虑结构型优化问题min1(x) + 2(y)|Ax + By = b, x X, y Y.它等价于变分不等式 w , (w w)TF(w) 0, w .其中w =xyandF(w) =1(x) AT2(y) BTAx + By b, = X Y 0 使得 kATA(xk x
25、k)k 0 使得 kATA(xk xk)k 0,若 u 满足 u andsupu1k uuk( u u)TF(u)“ ,则 u 被称为遍历意义下的 近似解.第三讲中提及的单调变分不等式的投影收缩算法,预测点 uk和步长 k满足 uk= P uk kF( uk) d(uk, uk), k=(uk uk)Td(uk, uk)kd(uk, uk)k212.对用不同(的孪生)方向,相同步长产生新迭代点uk+1= uk kd(uk, uk)和uk+1= Puk kkF( uk)的投影收缩算法,在算子 FLipschitz连续的假设下,都能经过 O(1/) 次迭代得到遍历意义下的 近似解.算法因此具有 O
26、(1/k) 收敛速率.P - 2620.交交交替替替方方方向向向法法法的的的计计计算算算复复复杂杂杂性性性和和和收收收敛敛敛速速速率率率结构型优化问题min1(x) + 2(y)|Ax + By = b, x X, y Y的交替方向法中 x 是隐式变量,迭代从给定的 vk= (yk,k) 出发,依次求解关于 x 和 y 的子问题.分别是xk+1=Argmin1(x) +2k(Ax + Byk b) 1kk2|x X“yk+1=Argmin2(y) +2k(Axk+1+ By b) 1kk2|y Y“和k+1= k (Axk+1+ Byk+1 b).所得的序列 vk 满足kvk+1 vk2H k
27、vk vk2H kvk vk+1k2H,H =BTB001Im.这样的收缩性质.在变分不等式的框架下证明了交替方向法具有 O(1/k)收敛速率以外,同时证明了残量序列 kvk vk+1k2H 具有单调不增性kvk vk+1k2H kvk1 vkk2H.由收缩性和单调不增性,经过 k 次迭代,就能是误差 kvk vk+1k2H达到kvk vk+1k2H1kkv0 vk2H这样 O(1/k) 的精度.P - 27动动动因因因与与与说说说明明明与这个系列讲义相关的研究工作,主要包括以下四个方面：投影收缩算法、交替方向法、多元分裂算法以及变分不等式框架下的松弛PPA算法.促使我整理这些讲义的动因,是这
28、些工作分别得到了不同学科的一些著名学者引用.一投影收缩算法：投影收缩算法方面的论文,得到包括UC Berkeley计算机系Jordan教授在内的学者引用,相关内容被写进他们的附录.这类成果近年也被一些北美名校(宾习法尼亚大学,多伦多大学,UC Berkeley,哥伦比亚大学)的博士们在语音识别、光纤网络、机器学习等的博士论文中提到.Jordan教授是美国科学院和工程院院士.二交替方向法：最优化中采用分裂算法,就像现实生活中大工程需要分包.从招收第一批博士生开始,在收缩算法框架下研究交替方向法就是我们的一个主要课题.新应用领域的发现,使交替方向法渐得广泛认可.我们多年前发表的这类方法中的一个自调
29、比准则,被Stanford大学电子工程系Boyd教授在2010年的一篇综述文章中称为一个简单而有效的公式(A simple scheme that often works well),对我们的分析依据也作了简要介绍.Boyd教授是2006年世界数学家大会邀请报告人.三多个可分离算子的分裂算法：交替方向法处理的是含两个可分离算子的问题.对多于两个可分离算子的问题,同样需要易于实现的分裂方法.基于到鞍点越来越近的收缩思想,我们给出了一些解决此类问题的方法.这类工作,已经被UCLA数学系教授Osher的课题组在降维问题上应用.他们在文章中说到,The method proposed by He,Ta
30、o and Yuan is appropriate for this application.Osher教授是美国科学院院士,2010年世界数学家大会一小时邀请报告人.P - 28四变分不等式框架下的松弛PPA算法：在变分不等式框架中构造算法的优越性,得到越来越多的学者认可.我们2012年在SIAM Journal Image Science发表的文章,初稿就被一些欧洲的学者在他们最新的研究中引用.例如,Pock and Chambolle的文章中说到,用He and Yuan的PPA形式,极大地简化了收敛性分析(which greatly simplified theconvergence
31、analysis).Chambolle是在图像学领域有很大影响的学者.五一阶算法的收敛速率：好方法需要有好的理论结果保证.2005年以来,Nemirovski和Nestrov等最优化理论与方法领域的世界数学家大会邀请报告人对一阶算法收敛速率表现出的浓厚兴趣,激发了我们对这个系列讲义中主要方法收敛速率的研究热情.最后两讲,我们用简单的方法和简短的篇幅,分别论证了投影收缩算法和交替方向法都具有 O(1/k) 的收敛速率.换句话说,对给定的 0,经过 O(1/) 次迭代,就能得到遍历意义下的 近似解.授授授人人人以以以鱼鱼鱼不不不如如如授授授人人人以以以渔渔渔。一一一个个个好好好的的的优优优化化化方方方法法法,应应应该该该是是是容容容易易易被被被工工工程程程师师师们们们掌掌掌握握握,让让让人人人用用用来来来自自自己己己解解解决决决问问问题题题的的的方方方法法法。z为相关学科所用,恰是我们从事优化方法研究的本源追求z
