不等式空间价格

I-1凸凸凸优优优化化化和和和单单单调调调变变变分分分不不不等等等式式式的的的收收收缩缩缩算算算法法法第一讲:变分不等式作为多种问题的统一表述模式Variationalinequalityisauniformapproachfordifferentproblems南京大学数学系何炳生hebma@nju.
edu.
cnI-2变分不等式是一种统一的问题表述模式.
管理科学与统计计算中存在大量凸优化问题.
信号处理,图像恢复,矩阵完整化,机器学习等信息技术领域中也有许多问题可以归结为(或松弛成)一个凸优化问题.
凸优化的一阶必要性条件就是一个单调变分不等式.
在变分不等式的框架下研究凸优化的求解方法,就像微积分中用导数求一元函数的极值,常常会带来很大的方便.
除了通常的最优化问题以外,互补问题是约束为正卦限的变分不等式.
经济活动中的空间价格平衡,保护资源–保障供给中的调控手段,用经济手段解决交通疏导等问题,都可以用变分不等式(或其特殊形式互补问题)来描述.
这一讲叙述以下一些常见问题与变分不等式的关系.
那些主要想从这个系列讲义学习结构型凸优化问题一阶算法的读者,这一讲中只需要了解第一节.
凸凸凸优优优化化化与与与单单单调调调变变变分分分不不不等等等式式式商商商品品品流流流通通通、、、保保保护护护资资资源源源、、、保保保障障障供供供给给给中中中的的的变变变分分分不不不等等等式式式交交交通通通疏疏疏导导导中中中的的的变变变分分分不不不等等等式式式广广广义义义线线线性性性规规规划划划问问问题题题的的的线线线性性性变变变分分分不不不等等等式式式最最最短短短距距距离离离和和和问问问题题题的的的线线线性性性变变变分分分不不不等等等式式式极极极小小小化化化最最最大大大特特特征征征值值值之之之变变变分分分不不不等等等式式式I-31凸凸凸优优优化化化与与与单单单调调调变变变分分分不不不等等等式式式连连连续续续优优优化化化方方方法法法中中中一一一些些些代代代表表表性性性的的的数数数学学学模模模型型型简单约束优化问题min{f(x)|x∈}.
线性约束优化问题min{θ(x)|Ax=b,x∈X}.
结构型优化问题min{θ1(x)+θ2(y)|Ax+By=b,x∈X,y∈Y}.
非线性互补问题x≥0,F(x)≥0,xTF(x)=0.
变分不等式x∈,(x′x)TF(x)≥0,x′∈.
我们只讲述求解凸优化和单调变分不等式的收缩算法.
从一般问题(非线性互补问题和变分不等式)的求解方法(L2–L3)开始;然后利用变分不等式刻画凸优化问题最优性条件,讨论线性约束优化问题的求解方法(L4–L7).
L8讲述求解简单约束优化问题的只用导数信息的收缩算法.
L9讨论线性约束优化问题对偶变量的收缩算法.
L10是只用梯度的线性约束凸优化的求解.
L11–L14讨论结构型优化问题的收缩算法.
L15–L18讨论多个可分离算子的结构型优化问题的收缩算法.
最后,L19–L20对主要算法的收敛速率做了论述.
I-41.
1可可可微微微凸凸凸优优优化化化等等等价价价于于于一一一个个个特特特殊殊殊的的的单单单调调调变变变分分分不不不等等等式式式设是n中的非空闭凸集,我们先来讨论可微凸优化问题min{θ(x)|x∈}(1.
1)的最优性条件.
类似于瞎子爬山原理,我们有如果某一点x是最优点,它必须属于,并且从这点出发的所有可行方向都不是下降方向.
我们用θ(x)表示θ(x)的梯度,并记Sd(x)={s∈n|sTθ(x)0.
I-17对给定的资源税率y1,y2,ym和补贴标准z1,z2,zn(政策),经营者们会根据"贪婪原理"找到他们的最优经营方案xij(对策).
X=x11x12.
.
.
x1nx21x22.
.
.
x2n.
.
.
.
.
.
.
.
.
xm1xm2.
.
.
xmn,如果记F(X)=F11F12.
.
.
F1nF21F22.
.
.
F2n.
.
.
.
.
.
.
.
.
Fm1Fm2.
.
.
Fmn,I-18其中Fij(X)={hsi(si)+yi+tij}{hdj(dj)+zj},si=n∑j=1xij,dj=m∑i=1xij.
那么,由经营者的最优经营方案形成的非负m*n矩阵X和F(X)中,同样下标的元素中最多只能有一个大于零.
换句话说,经营者的最优经营方案是互补问题X≥0,F(X)≥0,Trace(XTF(X))=0的解.
上式中的Trace(·)表示矩阵的"迹"——矩阵对角元的和.
我们能观测到的是问题解中相应的si(y,z)=∑nj=1xij(y,z)anddj(y,z)=∑mi=1xij(y,z)它们是由政策向量(y,z)决定的.
I-192.
2政政政府府府部部部门门门制制制定定定最最最优优优政政政策策策之之之互互互补补补问问问题题题政政政府府府部部部门门门的的的职职职责责责---保保保护护护资资资源源源和和和保保保障障障供供供给给给坚持可持续发展及环境保护,防止资源被过度开采,si≤smaxi;保障基本供给,从而保证社会稳定和民生,dj≥dminj.
手手手段段段(政政政策策策):::在资源过度开采的产地征收资源税,y1,ym;供应紧张的需求地给经营者提供补贴,z1,zn.
经营者们会根据政策给出对策.
政府的任务是给出'最好'的政策.
政政政府府府部部部门门门需需需要要要的的的最最最优优优政政政策策策是是是一一一个个个"""黑黑黑箱箱箱"""条条条件件件下下下的的的互互互补补补问问问题题题:I-20保护了资源,同时又让经济尽可能繁荣;y≥0,smaxs(y,z)≥0,yT(smaxs(y,z))=0,保障了供给,同时又尽可能节约财政支出.
z≥0,d(y,z)dmin≥0,zT(d(y,z)dmin)=0.
职能部门的互补问题的紧凑形式是:u≥0,F(u)≥0,uTF(u)=0,其中u=yz,F(u)=smaxs(u)d(u)dmin,s(u)和d(u)是u的函数.
黑黑黑箱箱箱问问问题题题,是是是指指指F(u)是是是u的的的函函函数数数,有有有确确确定定定的的的关关关系系系,但但但没没没有有有函函函数数数表表表达达达式式式.
I-213交交交通通通疏疏疏导导导问问问题题题之之之互互互补补补问问问题题题设某跨江城市有三座长江大桥,分别为Bridge-1,Bridge-2和Bridge-3.
不失一般性,我们可以将N1,N2,N3看作由北向南的车辆在江北的出发地,把S1,S2,S3看作它们在江南的集散地.
I-22我们只对管理部门的问题感兴趣,假设只收过桥费.
管理部门想制定一个适当的收费标准合理控制桥上流量.
驾驾驾驶驶驶员员员基基基于于于Wardrop原原原理理理的的的最最最优优优出出出行行行方方方案案案最最最小小小费费费用用用路路路径径径对给定的大桥收费y=(y1,y2,y3),驾驶员会找到他们的最优出行方案.
管管管理理理部部部门门门要要要求求求通通通过过过大大大桥桥桥合合合理理理收收收费费费控控控制制制桥桥桥上上上的的的流流流量量量0≤y∈3:桥上的收费向量;f(y)∈3:桥上的流量,它是收费y的函数;0管理部门要求解的数学问题是y≥0,F(y)=bf(y)≥0,yTF(y)=0.
同样,流量f(y)确是收费y的函数,但没有表达式.
只能对给定的自变量,观测相应的函数值,而这种观测,往往代价不菲.
我们从事投影收缩算法研究,着眼点是要得到效率高一些的、只用函数值和少用函数值的方法.
I-234广广广义义义线线线性性性规规规划划划及及及鞍鞍鞍点点点问问问题题题之之之变变变分分分不不不等等等式式式4.
1广广广义义义线线线性性性规规规划划划及及及之之之变变变分分分不不不等等等式式式线性规划的标准形式是min{cTx|Ax=b,x≥0}.
其中A∈m*n,b∈m,c∈n.
在实际经济问题中,向量b一般表示需求量,c表示价格.
我们允许b和c都在一定范围之内变动,考虑更一般的问题min{maxη∈CηTx|Ax∈B,x∈D}(4.
1)其中C,Dn,Bm是闭凸集.
这样的问题我们称之为广义线性规划.
引进辅助变量y和Lagrange乘子λ,得到广义线性规划(4.
1)的Lagrange函数L(x,y,λ,η)=ηTxλT(Axy),它定义在(D*B)*(m*C)上.
广义线性规划等价与一个min-max问题Lλ∈m,η∈CL(x,y,λ,η)≤L(x,y,λ,η)≤Lx∈D,y∈B(x,y,λ,η).
I-24设(x,y,λ,η)是上述min-max问题的解,则有x∈D,(xx)T(ATλ+η)≥0,x∈Dy∈B,(yy)T(λ)≥0,y∈Bλ∈m,(λλ)T(Axy)≥0,λ∈mη∈C,(ηη)T(x)≥0,η∈C.
更紧凑的形式可以写成w∈,(ww)T(Mw+q)≥0,w∈其中w=xyλη,M=00ATI00I0AI00I000,q=0和=D*B*m*C.
I-25一类常常被考虑的分裂可行问题(SplitFeasibilityProblem)Findx∈DsuchthatAx∈B,更是(4.
1)问题中的一个特例.
将其转换成Findx∈D,y∈B,suchthatAxy=0.
上述问题相当于一个目标函数为零的约束优化问题.
设λ为线性约束Axy=0的Lagrange乘子,问题就等价与以下的线性变分不等式:u∈,(uu)TMu≥0,u∈其中u=xyλ,M=00AT00IAI0,和=D*B*m.
I-264.
2一一一般般般鞍鞍鞍点点点问问问题题题之之之变变变分分分不不不等等等式式式用全变差极小处理图像去模糊[1],经离散化以后,问题的数学模型是minx∈Xmaxy∈YΦ(x,y):=θ1(x)yTAxθ2(y)(4.
2)其中Xn,Ym是闭凸集,A∈m*n.
θ1(x):n→,θ2(y):m→为凸函数.
如果(x,y)∈X*Y是问题(4.
2)的解,则有Φy∈Y(x,y)≤Φ(x,y)≤Φx∈X(x,y).
换句话说,(x,y)是Φ(x,y)在X*Y上的鞍点.
因此,问题(4.
2)能够转换成等价的变分不等式:求(x,y)∈X*Y,使得xxyyTf(x)ATyg(y)+Ax≥0,(x,y)∈X*Y,(4.
3)I-27其中f(x)∈θ1(x),g(y)∈θ2(y).
用记号u=xy,F(u)=f(x)ATyAx+g(y)and=X*Y.
问题(4.
3)就是变分不等式u∈,(uu)TF(u)≥0,u∈.
(4.
4)由于θ1(x)和θ2(y)是凸函数,容易验证,这里的F(u)是单调的.
关心这类问题求解方法的可以参阅第四讲与第五讲.
当θ1(x),θ2(y)是非光滑凸函数时,问题(4.
2)也可以表述成混合变分不等式问题:θ(u)θ(u)+(uu)TMu≥0,u∈,(4.
5)其中θ(u)=θ1(x)+θ2(y),M=0ATA0是反对称矩阵.
换句话说,混合变分不等式(4.
5)是单调的.
I-285最最最短短短距距距离离离和和和问问问题题题之之之变变变分分分不不不等等等式式式有些典型的非光滑凸优化问题可以化成结构相当简单的变分不等式.