对偶问题多解

对偶问题多解（精选三篇）

对偶问题多解 篇1

电价问题是电力市场运营的核心问题之一。在一般经济活动中, 供给和需求曲线通常为两条接近光滑的曲线, 而在现货电力市场中, 供求曲线中的机组报价曲线和负荷报价曲线通常呈现明显的阶梯形。前者按照供电报价从低到高的顺序排列, 后者则按照购电报价从高到低的顺序排列。若阶梯形的供应曲线和需求曲线有唯一交点, 则该点为市场均衡点, 对应的价格为市场出清价格[1,2]。若交点并不唯一, 就会发生对偶问题多解 (multiple dual solutions, MDS) 情况。倘若市场参与者的报价单元足够小, 报价段数足够多的话, 那么原本阶梯形的供求曲线会接近于一般的光滑供求曲线, 可以尽量减小MDS问题的影响, 但这样的做法大大增加了市场出清的计算量和操作复杂度。因此, 在实际电力市场中, 通常有对最小报价单位或最多报价段数的要求。例如, 北欧电力市场 (Nord Pool) 要求最小的报价单位为1 (MW·h) /h[3], 美国PJM[4]和澳大利亚电力市场[5]要求一张标书中最多不超过10段报价, 丹麦、瑞典、挪威和芬兰的平衡市场要求最小的报价单位为10 (MW·h) /h[6]。

MDS情况并不少见, 尤其在规模效应显著的电力行业。一旦发生MDS情况, 基于拉格朗日乘子的经典边际定价方法只能给出电价的理论区间, 而无法确定一组唯一的节点电价, 需要有别的准则协助定价。

目前各国电力市场有一些特殊方法来处理MDS情况下的定价问题, 如美国PJM电力市场依据额外生产或者消费1 MW电能的报价来确定电价[4], 新英格兰[7]和伊比利亚半岛电力市场[8]则选择出清价格的理论区间的最大值作为定价依据[9], 还有一些电力市场则采取基于特定扰动的灵敏度分析来应对MDS情况的发生[10], 但这些方法所得的结果难以保证解的最优性。另外一些电力市场则制定了提高订单数值精度的相关规定, 认为这样可以降低MDS发生的概率[11]。

针对MDS情况, 本文对传统定价理论进行了合理延伸, 分析了问题产生的本质, 进而提出了一种基于激励的定价方法, 并详细阐述了该方法的激励相容特性。算例表明该定价方法能完成若干MDS情况下对社会剩余的合理分配。

1 电力市场出清问题

在双侧竞价模型中, 电力市场出清问题可以表述为[12,13,14,15,16]:

式中:i为系统机组的编号, i=1, 2, …, NG;λGi为机组i的报价;PGi为机组i的有功出力;j为系统负荷的编号, j=1, 2, …, ND;λDj为负荷j的报价;PDj为负荷j的有功消耗功率;b为系统节点的编号, b=1, 2, …, B;l为系统线路的编号, l=1, 2, …, Nl;Tlb为线路l关于节点b的功率传输分配系数;Fl-为线路l的容量;fG (i) 为机组i所在节点的编号;fD (j) 为负荷j所在节点的编号;P-Gi和PGi分别为机组i-的有功出力上下限;P-Dj和P-Dj分别为负荷j的有功消耗功率上下限。

为求解出清问题, 构造拉格朗日函数:

式中:λ, μl, 分别为对应约束条件 (式 (2) —式 (5) ) 的拉格朗日乘子。

若存在边际机组k, 其所在节点的编号记为fG (k) , 依据KKT条件, 可知, 从而, 节点fG (k) 上的电价直接由边际机组k的报价确定, 。类似地, 若存在边际负荷s, 则其所在节点fD (s) 上的电价由边际负荷s的报价确定, 。

若不存在边际机组或边际负荷, 那么乘子会出现多解情况, 传统的方法就无法给出明确定价, 需要新的方法来解决此时的定价问题。

2 基于激励的定价方法

在电力市场中, 如果存在大的参与者, 那么很有可能发生定价多解的情况。此时由于没有一组唯一确定的对偶解, 对社会剩余的分配是存在争议的。并且, 电力市场中供求双方的报价活动并不限于一次交易, 而是多次重复的。那么怎样定价才能获得供求双方的认同, 从而使双方都能保持如实报价, 而没有动机偏离其真实保留价格以获得更大收益呢?这就要求市场的定价方法是激励相容的[16,17]。因此, 本文从对供电方和购电方的激励出发来讨论MDS情况下的定价问题。

2.1 MDS情况下定价的理论区间

虽然定价求解可能出现多解情况, 但是所有合理的解都应该在理论区间内。

若机组i处于出力上限 (记做i∈GUL) , 则, 有

若负荷j处于消耗功率上限 (记做j∈LUL) , 则ξj=0, 又, 有

类似地, 机组i处于出力下限 (记做i∈GLL) , 应有

负荷j处于消耗功率下限 (记做j∈LLL) , 应有

为确定合理的定价区间, 需考虑所有参与调度的关键机组和负荷。因此, 除了处于出力 (消耗功率) 上下限的机组 (负荷) 外, 还需考虑由于线路约束从而出力 (消耗功率) 不完全的机组 (负荷) 对于定价区间的影响, 主要体现在下文定义的Sl和Dh中。

综上, 可以定义:

其中, 用以确定Sl的元素, 不止考虑了处于出力上限的机组 (i∈GUL) , 也包括了由于线路约束而出力不完全的机组, 故其计算范围应该是所有不处于出力下限的机组 (iGLL) 。类似地, 用以确定Dh的元素的计算范围则应该是所有不处于消耗功率下限的负荷 (jLLL) 。

在对MDS情况下的定价问题进行讨论时, Sh, Sl, Dh, Dl是4个重要的定价指标, 对应于一般情况下的边际报价, 为了表述的一致性, 称这4个指标为伪边际报价 (pseudo marginal bid, PMB) 。上述4个方程称为PMB方程, 而与PMB相关的机组和负荷, 则称为伪边际机组 (PMG) 和伪边际负荷 (PML) 。每一个PMB都由PMG (PML) 的报价和阻塞成本两部分组成。

平衡节点上的电价为ρ=-λ, 那么该节点上定价的理论区间即为:

后文将式 (12) 中的max (Dl, Sl) 称为定价下限, min (Dh, Sh) 称为定价上限。

2.2 MDS情况下基于激励的定价方法

PMG的Sl有动机去提高他的报价, 直到他的报价提高到只比min (Dh, Sh) 略低。PML的Dh也有动机去压低他的报价, 直到他的报价只比max (Dl, Sl) 略高。为杜绝市场出现操纵价格的现象, 必须使供电方和购电方都没有动机偏离其真实报价。对于供电方, 市场需要将价格定为min (Dh, Sh) , 而对于购电方, 市场则需要将价格定为max (Dl, Sl) 。在对偶问题存在唯一解时, 存在至少一个边际机组, 解得的定价为ρ=min (Dh, Sh) =max (Dl, Sl) , 能同时满足这两个要求。而存在多解时, 就没有定价能同时满足这两个要求了。针对MDS情况下的定价问题, 本文提出一种基于激励的定价方法。

在MDS情况下, 社会剩余量是确定的, 市场通过定价来实现对供求双方的剩余分配, 而其中有争议的部分也就是max (Dl, Sl) 和min (Dh, Sh) 之间的社会剩余, 称为可分配剩余。因此讨论社会剩余分配问题时, 不能仅仅局限于可分配剩余。为了方便表述, 先定义几个变量:

可以定义一个与可分配剩余密切联系的剩余量伪公共剩余。伪公共剩余的上下边界线分别为Dh和Sl, 若整个市场出清产量或总出力, 则有伪公共剩余值为:

由式 (14) 可知, 伪公共剩余既不等同于全部的社会剩余, 也不局限于可分配剩余。

若将SPC中的 (a+b) P*分配给那些报价已被接受的购电方, 定价为max (Dl, Sl) , 是购电方能购买到电能的最低价格, 此时购电方没有动机去压低报价。因此, 将SCI= (a+b) P*定义为对购电方的激励剩余。类似地, 若将SPC中的 (b+c) P*分配给那些报价已被接受的供电方, 定价为min (Dh, Sh) , 是供电方订单能达到的最高价格, 此时供电方也没有动机去抬高报价。类似地, 将SSI= (b+c) P*定义为对供电方的激励剩余。

如果SCI和SSI有重叠部分, 即可分配剩余部分不为0时, 无法实现理想的分配情况。不妨先增加可分配剩余大小的剩余量再进行分配, 这样的话, 购电方能分得SCI, 供电方能分得SSI, 双方都会满意。因此, 可以考虑以这种比例来分配SPC, 此时购电方分得SCISPC/ (SPC+SA) , 供电方分得SSISPC/ (SPC+SA) , 其中SA表示可分配剩余值。那么, 基于激励的定价形式应为:

化简后有

式 (16) 也就是平衡节点上的定价方程, 而任意节点b的电价则可由式 (17) 确定[12,13]:

下面继续讨论上述定价方法的激励相容特性, 为突出其性质, 本文取3种极端情况进行分析。

情况1:有一个PML为无弹性的负荷 (用电效益是无穷大的, 如医院) 的情况。此时的供求曲线如图1所示。

依据定价方法, 先计算PMB有:Sh=S3, Sl=S2, Dh→∞, Dl=D2。代入式 (13) , 有a→∞, b=S3-S2, c=0, d=S2。再代入式 (16) , 求得的定价为S3。

从激励的角度来分析这个定价:对报S2的参与方而言, 只要报价一直低于S3, 就不会影响收益, 若抬高报价到高于S3, 就会失去订单从而收益为0, 所以他没有动机去改变报价。对报S3的参与方而言, 若压低报价, 收益将会是负的, 若抬高报价, 也一样拿不到订单, 收益为0, 所以他也没有动机去改变报价。对报D1的参与方而言, 无论价格多高, 他都需要用电, 为一个价格接受者, 同样没有动机去改变报价。

从数学角度, 由于a→∞, c=0, SA=bP*对于SCI= (a+b) P*是可以忽略不计的, 而对于SSI= (b+c) P*则是全部, 故应将可分配剩余全部分配给供电方。此观点与依据定价方法所作分配是一致的。

不妨选用一种片面追求公平性的方法作对比, 如采用对等分配可分配剩余的方法ρ=c+d+2/b, 确定的定价为 (S2+S3) /2。由于 (S2+S3) /2

情况2:有限台机组供电, 其中有且仅有一台PMG的情况。此时的供求曲线如图2所示。

依据定价方法, 先计算PMB有:Sh→∞, Sl=S2, Dh=D2, Dl=D3。代入式 (13) , 有a=0, b=D2-S2, c=0, d=S2。再代入式 (16) , 求得的定价为 (D2+S2) /2。

从激励的角度来分析这个定价:对报S2的参与方而言, 他分得了可分配剩余SA=D2-S2的一半。他知道若抬高报价, 那下次交易中, 报D2的参与方也会相应压低报价, 双方若反复如此操作下去, 只是将可分配剩余依次变小, 直到双方报价都为 (D2+S2) /2, 此时可分配剩余为零, 而收益并没有发生变化, 所以他没有动机去改变报价。类似地, 报D2的参与方也没有动机去改变报价。对报D3的参与方而言, 除非抬高报价到高于 (D2+S2) /2, 否则一直购买不到电能, 但这样的话收益将会是负的, 所以他同样没有动机去改变报价。

从数学角度, 由于a=0, c=0, 此时有SA=SPC=SCI=SSI, SA=bP*对于SCI= (a+b) P*是全部, 对于SSI= (b+c) P*也是全部, 故应将可分配剩余平均分配给供电方和购电方。此观点与依据定价方法所作分配是一致的。

情况3:有限台机组中有一台PMG, 并且有一个PML为无弹性的负荷的情况。此时的供求曲线如图3所示。

依据定价方法, 先计算PMB有Sh→∞, Sl=S2, Dh→∞, Dl=D2。代入式 (13) , 有a=0, b→∞, c=0, d=S2。再代入式 (16) , 求得的定价为S2+b/2→∞。

从激励的角度来分析这个定价:类似于情况2, 对报S2和D1的参与方而言, 各分得了可分配剩余的一半, 都是满意的, 没有动机去改变各自报价。

从数学角度, 由于a=0, c=0, 有SA=SPC=SCI=SSI, 故应将可分配剩余平均分配给供电方和购电方。此观点与依据定价方法所作分配是一致的。

通过上述分析可知, 该定价方法具有激励相容性, 能促使市场中所有参与者保持其报价不偏离其真实成本或效用, 从而起到稳定市场价格的作用。

3 算例分析

本节采用一个3节点系统为例来验证所提出的定价方法。具体网络结构如图4所示, 机组和负荷的基本信息如表1所示。

首先, 利用经典线性规划方法求解式 (1) —式 (5) 。若线路容量足够大 (即不考虑线路阻塞的情况) , 那么系统所有节点上的电价是相同的, 又G31为边际机组, 出清电价由G31的报价确定为20元/MW。

若考虑线路阻塞的情况, 求得的优化调度方案会发生变化, 如表2所示。由表2可知, 由于线路L12的容量约束, 机组G21的有功出力从1 000 MW下降到了600 MW。利用出清模型 (式 (1) —式 (5) ) 依旧可以求得优化调度方案, 但如何确定各节点上的电价成为了一个难题。因为此时不存在严格意义上的边际机组 (负荷) , 所有参与调度的关键机组 (负荷) 都是PMG (PML) 。

选取节点3作为平衡节点, 依据式 (1) —式 (5) , 电力市场出清问题可以表述为 (为表述方便, 以下公式中变量统一取标幺值) :

利用经典线性规划方法求解的结果为: (PG21, PG31, PG32, PD11, PD12, PD13) *= (600, 300, 0, 700, 200, 0) , 线路L12出现了阻塞情况。

构造拉格朗日函数:

将原问题的解 (600, 300, 0, 700, 200, 0) 代入KKT条件, 有

根据KKT条件, 得到化简后的方程组为:

式 (30) —式 (35) 一共有6个方程, 其中有7个变量, 故这些乘子不能唯一确定, 存在MDS节点。

对所有节点进行分类。节点1和节点3为MDS节点, 节点2为非MDS节点。既然节点3是MDS节点, 不妨仍选取节点3作为平衡节点重新求解, 依据此时的KKT条件, 得到化简后的方程组 (式 (30) —式 (35) ) 。

检验已有方程和变量个数。方程个数Ne为6, 变量个数Nv为7, Ne-Nv=1, 需要构造关于PMB的附加方程。

又依据, 得到λ和μ1的取值范围, -35≤λ≤-20, 15≤μ1≤60。由PMB方程 (式 (11) ) 与式 (30) —式 (35) 得到:

将式 (36) 的结果代入式 (13) , 有

将式 (37) 的结果代入定价方程 (式 (16) ) , 得到一个关于乘子的附加方程:

通过式 (30) —式 (35) 和式 (38) 一共7个方程求⌒解变量, 求解结果为:

将上述结果代入式 (17) , 求得各节点电价:

在节点2上, 增加1 MW出力需增加的最小费用为15元, 减少1 MW出力可节省的最大费用为15元。两者相等, 故该节点上出清价格应该定为15元/MW。也就是说G12为严格意义上的边际机组, 出清价格直接由G12的报价确定为15元/MW。

若在节点1上增加1 MW出力, 考虑L12的线路约束, 存在唯一的出力调整方案是机组G21减少1 MW出力, 机组G32增加2 MW出力, 产生的额外费用为55 (35×2-15×1) 元, 即在节点1上增加1 MW出力需增加的最小费用为55元;相反, 若在节点1上减少1 MW出力, 考虑到L12的线路约束, 存在多种出力调整方案, 但其中节省费用最多的方案是机组G21增加1 MW出力, 机组G32减少2 MW出力, 产生的额外费用为-25 (15×1-20×2) 元, 即在节点1上减少1 MW出力可节省的最大费用为25元。两者不相等, 不存在严格意义上的边际机组, 出现多解情况。定价方法求得的节点1上电价为40元/MW, 在区间[25, 55]元/MW内, 是合理的。

将节点1上的电价定为40元/MW。对用户D12而言, 若压低报价, 将无法购得电能, 若抬高报价, 也不会影响收益, 所以他没有动机去改变报价。对用户D13而言, 除非将报价抬高到不低于40元/MW, 否则一直无法购得电能, 但这样的话收益将会是负的, 所以他同样没有动机去改变报价。

若在节点3上增加1 MW出力, 考虑L12的线路约束, 存在唯一的出力调整方案是机组G32增加1 MW出力, 产生的额外费用为35元, 即在节点3上增加1 MW出力需增加的最小费用为35元;相反, 若在节点3上减少1 MW出力, 考虑L12的线路约束, 存在多种出力调整方案, 但其中节省费用最多的方案是机组G31减少1 MW出力, 产生的额外费用为-20元, 即在节点3上减少1 MW出力可节省最大费用20元。两者不相等, 不存在严格意义上的边际机组, 出现多解情况。定价方法求得的节点3上电价为27.5元/MW, 在区间[20, 35]元/MW内, 是合理的。

将节点2上的电价定为27.5元/MW。对机组G31而言, 若抬高报价到高于27.5元/MW, 将无法获得订单, 而其他情况, 则不会影响收益, 所以他没有动机去改变报价。对机组G32而言, 除非压低报价到低于27.5元/MW, 否则一直拿不到订单, 但这样的话收益将会是负的, 所以他同样没有动机去改变报价。

为方便比较, 表3列出了考虑线路阻塞和不考虑线路阻塞两种情况下各节点上的电价。由于线路L12出现阻塞情况, 使得3个节点的电价各不相同, 负荷节点1的电价要明显高于接有发电机组的节点2和节点3。

4 结语

对偶问题多解 篇2

求解随机凸规划概率约束问题的对偶算法

1 引言 随机规划中的概率约束问题在工程和管理中有广泛的应用.因为问题中包含非线性的概率约束,它们的.求解非常困难.如果目标函数是线性的,问题的求解就比较容易.[5]给出了一个求解随机线性规划概率约束问题的综述.原-对偶算法[3]和切平面算法[6]是比较有效的.

作 者：唐恒永 赵传立 Tang Hengyong Zhao Chuanli 作者单位：沈阳师范大学数学与系统科学学院,沈阳,110034刊 名：高等学校计算数学学报 ISTIC PKU英文刊名：NUMERICAL MATHEMATICS A JOURNAL OF CHINESE UNIVERSITIES年，卷(期)：30(2)分类号：O221.5关键词：

复合二项对偶模型的最优分红问题 篇3

关键词对偶模型；HJB方程；压缩映射；最优分红策略

中图分类号O211.6 文献标识码A

AbstractThis paper discussed the problem of optimal dividendpayment in compound binomial dual model. The relationship between the optimal dividend strategy and the corresponding optimal value function was found by analysing the HJB equation， and a simple algorithm was obtained for calculating the optimal value function. From the properties of the optimal dividend strategy， an upper bound and a lower bound of the optimal value function were derived.

Key wordsdual model； HJB equation； contraction mapping； optimal dividend strategy

1引言

分红问题的提出可以追溯到De Finetti1在纽约第15届国际精算师大会上发表的一篇文章，他认为在风险模型中考虑分红更切实际. 目前研究得最多的分红策略有：Barrier策略2-4和Threshold策略5-9. 随着金融管理、公司业务和保险业务的发展，经典风险模型的对偶模型越来越受到重视10-14， 讨论相对较多的是连续时间经典风险模型的最优分红问题，例如：Avanzi等10运用拉普拉斯变换方法讨论了复合Poisson对偶模型的最优红利Barrier的确定方法；Gerber等11讨论了复合Poisson对偶模型的最优红利Barrier的一些近似方法. 然而离散时间的最优分红问题显然还没有得到足够的重视，尽管De Finetti11最开始讨论红利问题就是在一个离散模型中. 对偶模型可描述为：

本文研究复合二项对偶模型的最优分红问题，发现最优值函数满足一个离散的哈密顿-雅可比 -贝尔曼（HJB）方程，并运用压缩映射原理证明最优值函数是这个方程的唯一解，从而得到了最优分红策略的计算方法. 通过讨论最优红利策略的一些性质本文构造出了最优值函数的可无限逼近的一个上界和一个下界，以便能运用递归算法在Matlab中进行数值计算.

2基本模型假设

参考文献

1.B DE FINETTI. Su un'impostazione alternativa della teoria collettiva delrischioJ.. Transactions of the XVth International Congress of Actuaries，1957（2）：433-443.

2.X S LIN， G E WILLMO， S DREKIC. The classical risk model with a constant dividend barrier： Analysis of the GerberShiu discounted penalty functionJ.. Insurance： Mathematics and Economic， 2003，33（3）： 551-566.

3.S LI， J GARRIDO. On a class of renewal risk models with a constant dividend barrierJ.. Insurance： Mathematics and Economics，2004，35（3）：691-701.

4.K C YUEN， G WANG， W K LI. The GerberShiu expected discounted penalty function for risk processes with interest and a constant dividend barrierJ.. Insurance： Mathematics and Economics， 2007，40（1）：104-112.

5.何庆国，何传江. 阈值分红策略下带常利率的对偶风险模型J..经济数学，2012， 29（4）： 67-70.

6.X S LIN， K P PAVLOVA. The compound Poisson risk model with a threshold dividend strategy J.. Insurance：Mathematics and Economics，2006，38（1）：57-80.

7.H U GERBER， E S W SHIU. On Optimal dividend strategies in the compound Poisson modelJ.. North American Actuarial Journal，2006，10（2）：76-93.

8.N WAN. Dividend payments with a threshold strategy in the compound Poisson risk model perturbed by diffusionJ.. Insurance：Mathematics and Economics，2007， 40（3）：509-523.

nlc202309051527

9.S GAO， Z M LIU. The perturbed compound Poisson risk model with constant interest and a threshold dividend strategyJ.. Journal of Computational and Applied Mathematics，2010，233（9）：2181-2188.

10.B AVANZI， H U GERBER， E S W SHIU. Optimal dividends in the dual modelJ.， Insurance： Mathematics and Economics，2007，41（1）：111-123.

11.H U GERBER， S NATHANIE. Optimal dividends with incomplete information in the dual modelJ.. Insurance：Mathematics and Economics，2008，43（2）：227-233.

12.C Y N ANDREW. On a dual model with a dividend thresholdJ.. Insurance：Mathematics and Economics， 2009，44（2）：315-324.

13.B LI， R WU. The dividend function in the jumpdiffusion dual model with barrier dividend strategyJ.. Appl Math Mech（English Edition），2008，29（9）：1239-1279.

14.B AVANZI， E C K CHEUNG， B WONG， JK WOO. On a periodic dividend barrier strategy in the dual model with continuous monitoring of solvencyJ.. Insurance： Mathematics and Economics， 2013，52（1）： 98-113.