-
随机优化、鲁棒优化和分布鲁棒优化有什么联系和区别?
- 时间:2024-07-29 来源:佚名 人气:
优化问题有四大类:传统确定优化问题,随机规划问题,鲁棒优化,分布鲁棒优化
相对于传统确定规划而言,也就是参数都是确定的,比如加工时间确定,运送时间确定,实际生活中,这些值往往是有波动的,就有了不确定优化。
不确定优化一般分为随机规划和鲁棒优化:前者假定参数服从一个分布,一般来说会以期望值为优化目标;后者假定分布未知但是现实中的数据中可以获得一些信息,比如参数出现的所有情况,这就是离散的鲁棒优化,或者是每个参数的取值区间,这就是区间鲁棒优化,而鲁棒优化的目标,可以根据需要的保守程度来制定,如果问题涉及安全,那我们肯定是要不出现任何事故,类似这样的就可以制定绝对目标,优化最差的情况,如果是其他的不需要如此保守的,或许可以制定最优化最大后悔值,等等。
分布鲁棒优化是比较新的研究方向,研究难度相对来说也是大一点点的,结合了随机规划和鲁棒优化,假定参数有多个取值情况,而每一个取值又服从一个分布。
新手入门不确定规划,建议从鲁棒优化的区间类型开始着手。
考虑这样一个简单的线性规划问题:有若干种材料可以制成若干种商品,每种商品有其销售价格,在原料约束和成本约束下最大化其利润。
这个问题中的参数是原料的采购价格、销售价格等,待求解的是生产计划。
这样一个问题是好求解的,但现实中往往遇到各种各样的问题。比如预料不到的价格变化,或者是测量过程中出现的参数误差,这都有可能会导致解的不准确。又或者我们不知道最后的需求是多少,无法计算生产计划能带来多少利润。此外,线性规划中很多等式都是恰好取等号的,参数的微小变动往往会导致选取的“最优解”无法继续满足约束条件。
总的来说,实际生活中我们碰到的优化问题大都包含不确定性,而随机优化、鲁棒优化和分布鲁棒优化则是处理不确定优化问题的工具。这是这三者的联系。
《Robust Optimization》这本书举了一个例子,对一个线性规划问题的最优解 和一个取了等号的约束条件 ,令 是 的 均匀扰动,以及:
最后得到结果是: 容易看到,在比较 dirty 的现实问题中,参数的一个小扰动都会使约束条件严重不可行。
兴起于上世纪90年代的鲁棒优化 (robust optimization) 这一优化领域的分支就是主要解决这一问题的。与确定性优化不同的是,RO 认为优化问题中的参数都是取值于一个 uncertainty set 的不确定的值,优化的目的是克服这种不确定性(immunize against uncertainty),找到一个必定满足约束条件的、尽可能最优的解。
对于一个线性规划问题: 。RO 进一步假设参数取值于一个不确定集 ,希望得到的解(robust solution)对任何 中的参数,都是可行的(robust feasible)。而对于目标函数,我们会希望它在最差的时候最好,最终得到 RO 形式的线性规划问题: 它具有等价形式(robust counterpart ):
转换成 RC 形式是我们处理一个RO问题的重要方法。
那如果不确定性出现在目标函数怎么办?比方说
其中 是一个带有不确定性的参数。RO 仍然认为 取值一个不确定集 ,优化的目标是使最坏的情况最好,也就是
与 RO 类似的、同样是处理不确定性优化问题的还有随机规划(stochastic programming)。随机规划一个最经典的问题应该就是报童问题 (newsvender problem) 吧,已知需求的分布,如何去安排供给来使得期望利润最大化:
这里 表示订货量为 ,需求为 时的利润。很自然的想法是把期望利润当做目标函数进行优化。注意到,因为在外面取了一个期望,对于一个给定的分布,目标函数只是待优化变量 的函数。很多运筹学的教科书都采取这种做法。
但是,实际中我们很难知道真实的需求分布是多少,我们可能只有一些 i.i.d 的 demand samples。这时候有两种方法,一种是假设需求服从某个参数分布,比如正态分布,用数据拟合正态分布的期望和方差,最后代入计算。
另一种是非参数方法,我们直接用样本的经验分布代替真实分布,如果我们有样本 ,那么优化的目标函数就是
这种方法我们把它叫做 SAA (sample average approximation)。
SAA 方法可能导致 optimizer's curse,这是一个很有趣的现象,具体可以参见 Melvyn sim 的一些文章。
SP 对“随机的”约束条件的处理办法是机会约束 (chance constraint) ,针对随机参数的扰动可能使约束条件不成立这一问题,我们可以给定一个置信度 ,保证约束条件 在很高的概率成立,即:
如果置信度 取成 ,那么就变成了一定要求在 的支集上满足约束的鲁棒优化了。尽管这样做看似很好,但其实机会约束处理起来可能会非常困难,一是概率值很难精确计算,二是问题不能保证是凸的,从而难有一个好的算法。
一般我们都认为随机规划问题针对的是一个给定的概率分布,但实际中这个概率分布往往不能得到,通常只能通过历史数据去估计真实的概率分布,因为估计误差的存在,SP 在实际应用中可能会出现较大的偏离,这是 SP 的一个缺点。一个例子就是资产配置中的均值方差模型,最后的 portfolio 对一个参数估计值的变化可能是非常敏感的。
RO 自身也存在一个问题,那就是太过死板和保守(too conservative)。比如说我们通过历史数据得到了参数的一个估计,然后希望结果在参数有 的相对扰动的情况下仍然成立,尽管所有的参数同时有 的误差这种可能性在实际中微乎其微,但是 RO 还是坚持让 optimal solution 在这种情况下可行,这就会使我们的可行域变得很小,畏畏缩缩,不敢冒进,导致解的实际效果不好。
SP 与 RO 的一个区别就在于,RO 里面我们是不知道参数的真实分布情况的,或者说我们不敢断言参数的真实分布。当我们面临的优化问题的 uncertain parameter 有一些样本的时候,我们把 SP 和 RO 的思想结合起来,能得到一个更好的方法,那就是分布鲁棒优化。
通过历史数据能的的确确推导出一个近似的概率分布,尽管我们往往没有把握说这个概率分布一定准确,但是可以有把握地说真实的分布一定与近似的分布很接近,这个接近的程度可以用统计学的方法来进行衡量。那么继续使用 robustness 的思想来考虑问题,对这一系列“疑似”的真实分布,我们让“最坏的情况最好”。这就是所谓的“分布鲁棒优化”,它能够恰如其分地改善 RO 和 SP 的缺点。相比之下,RO 和 SP 或多或少在统计或是优化理论上的解释性不如 DRO 那么优秀。
近10年来快速发展的分布鲁棒优化(Distributionally Robust Optimization)较好地解决了上述RO 和 SP 存在的一些问题。它结合了统计学习与优化理论,通过假定参数服从某些可能的分布,来得到一个足够好的解。
假设我们有一个名义上的优化问题: 以及我们有 的一些样本,我们努力地找到了一个分布集 ,它以很大的概率包含 的分布函数 ,于是可以写出问题的分布鲁棒优化形式: 注意到,我们可以把问题分成两个阶段,其第一阶段是给定 ,求:
然后再转化为对 的确定性优化问题 .
如果不确定参数出现在约束条件,那么处理方法也是类似的,读者可以试着写一写,这里我不赘述了。
DRO 相较于 RO 而言,可以充分地利用数据;相较于 SP 而言,有更好的 robustness。但缺点也是很明显的,因为问题变复杂了,所以理论分析和求解的难度都要更大。
尽管 DRO 满足了我们对一个优化问题的所有“幻想”,但作为一个新兴的、还不够成熟的学科分支,解决一个 DRO 问题可能并不是非常容易的。
第一个要面对的问题就是如何通过历史数据(data-driven)来构造分布集 ,现在主流的两种方式分别是 moment-based 和 metrics-based,这都会造成集合 是一个无限集,给问题的解决增加了困难。
第二个问题是,建模出的 DRO 问题是不是可解的(tractability),简单来说就是时间复杂度是多少,还有就是能不能转化为凸的问题,NP-Hard 和非凸都会给解决问题增加很大的困难。
总结一下,本文给大家介绍了鲁棒优化、随机规划和分布鲁棒优化的思想和优化形式,并对其优缺点进行了简要分析。本文首发于2020年冬,很高兴能有200+的小伙伴给我点赞,2023年春我把文章修改了一下,如果朋友你觉得文章对你有帮助的话,记得点赞+喜欢哦!
推荐最近的一篇综述,可以系统地回答这个问题:
Rahimian, H. and S. Mehrotra. “Distributionally Robust Optimization: A Review.” ArXiv abs/1908.05659 (2019).
Distributionally Robust Optimization: A Review刚刚入门,来勉强答一波,希望大家能够帮我纠错。
三个都是考虑了数据的不确定性,即存在扰动y,但是假设不一样。
假设现实情况下的y属于某个概率分布p,随机规划假设决策者是知道这个p,这是不现实的;
鲁棒优化假设决策者有一个不确定集U,这个集合中的元素均满足某个条件,但鲁棒优化要求最坏的情况也要能够应对,实际上最坏的情况有时候绝不可能发生,这将会过于保守甚至不存在解;
分布鲁棒优化假设决策者不完全知道p,但大概知道p会是个什么样子,因此他确定某个概率分布的集合P,在P里面找出最坏的p worst,在p worst的情况去优化。
总之,如果概率分布集合P仅包含y的实际分布p,分布鲁棒优化变为随机规划;如果概率分布集合P包含U中的所有情况,分布鲁棒优化变为鲁棒优化。
References:
Rahimian, H. and S. Mehrotra. “Distributionally Robust Optimization: A Review.”ArXivabs/1908.05659 (2019).
程序名称:数据驱动的多离散场景电热综合能源系统分布鲁棒优化算法
实现平台:matlab-yalmip-cplex/gurobi
代码简介:数据驱动的分布鲁棒优化算法。考虑四个离散场景,模型采用列与约束生成(CCG)算法进行迭代求解,场景分布的概率模糊集由1-范数和oo-范数约束组成的综合范数约束,程序含拉丁超立方抽样+kmeans数据处理程序,程序完美运行,超级无敌精品,有详细参考文献。
注:分布鲁棒是现在非常热门的不确定性优化算法,可谓是论文催化剂,随便套个模型发个中等偏上的中核轻轻松松
参考文献:《新能源电力系统供需灵活性量化及分布鲁棒优化调度》《基于场景聚类的主动配电网分布鲁棒综合优化》《基于数据驱动的交直流配电网分布鲁棒优化调度》《计及需求响应柔性调节的分布鲁棒 DG 优化配置》《考虑风电不确定性的电热综合系统分布鲁棒协调优化调度模型》《能源互联网环境下基于分布鲁棒优化的能量枢纽负荷优化调度》
代码获取方式:【代码分享】数据驱动的多离散场景电热综合能源系统分布鲁棒优化算法
【代码推荐购买指南】时间序列与回归分类预测、电力系统运行优化与规划
24.1.10近期推文汇总/电力系统预测与优化方向论文推荐与matlab代码分享
【视角】能源互联网背景下数据中心参与电力系统运行的机遇与挑战
【转发收藏】2024年电力系统方向最新研究热点总结/征稿专辑(1)
【转发收藏】优化调度模型使用Gurobi 加速混合整数规划问题求解速度的方法
【视角】如何应对高比例新能源电力系统带来的电力保供和新能源消纳难题?
运行结果展示
clc;clear all
tic
ps0=[22.7; 15.6; 38.05; 23.65]'https://www.zhihu.com/question/100;%场景概率
ps=ps0;
alfa1=0.99;alfaw=0.99;N=5000;
theta1=4/N/2*log(2*4/(1-alfa1));%公式46-47
thetaw=1/N/2*log(2*4/(1-alfaw));
tn=24;%时序性参数
Pgmax=300;ru=50;rd=50;%微燃机最大出力,爬坡约束 原pgmax=100
Sch=400;Pchmax=0.2*Sch;ee0=0.5*Sch;socmax=0.9;socmin=0.1;
eta=0.95;%储能充放电效率
cg=1.7;%MTG运行成本
cq=0.62;%弃风弃光成本
ccn=0.3*7/100;%储能老化成本 原/1000
cqt=0.25;%启停成本
d2h=1.2;%电热比
yitagl=0.9;%电锅炉
UB=inf;
LB=-inf;
for k=1:4
% while UB-LB>1
MP427;
LB=obj_mp;
LB1(k)=LB;
SP427;
UB=min([UB,UB1]);
UB2(k)=UB;
end
P_qw=p0_wt-p_wt;
P_qv=p0_pv-p_pv;
toc
disp(['运行时间: ',num2str(toc)]);
%结果画图
xx=1:4;
figure;
plot(xx,UB2,'m-*','LineWidth',1)
hold on
plot(xx,LB1,'b--o','LineWidth',1)
xticks([1 2 3 4]);
legend('UB','LB');
xlabel('迭代次数');
ylabel('目标函数值');
fprintf('弃风率为')
qw*100
fprintf('弃光率为')
qv*100
figure;
yc=[-p_gl(:,1)';-p_sell(:,1)';-p_ch(:,1)']';
bar(yc,'stack')
hold on
yy=[p_dis(:,1)';p_buy(:,1)';p_g(:,1)';p_wt(:,1)';p_pv(:,1)']';
bar(yy,'stack')
plot(p_l(:,1)+pdz(:,1)-pdd(:,1),'b-*','LineWidth',1)
legend('电锅炉','售电','充电','放电','购电','微燃机发电','风电','光伏','电负荷')
xlabel('时间(h)');
ylabel('功率(kW)');
title('场景1');
figure;
yc=[-p_gl(:,2)';-p_sell(:,2)';-p_ch(:,2)']';
bar(yc,'stack')
hold on
yy=[p_dis(:,2)';p_buy(:,2)';p_g(:,2)';p_wt(:,2)';p_pv(:,2)']';
bar(yy,'stack')
plot(p_l(:,2)+pdz(:,2)-pdd(:,2),'b-*','LineWidth',1)
legend('电锅炉','售电','充电','放电','购电','微燃机发电','风电','光伏','电负荷')
xlabel('时间(h)');
ylabel('功率(kW)');
title('场景2');
figure;
yc=[-p_gl(:,3)';-p_sell(:,3)';-p_ch(:,3)']';
bar(yc,'stack')
hold on
yy=[p_dis(:,3)';p_buy(:,3)';p_g(:,3)';p_wt(:,3)';p_pv(:,3)']';
bar(yy,'stack')
plot(p_l(:,3)+pdz(:,3)-pdd(:,3),'b-*','LineWidth',1)
legend('电锅炉','售电','充电','放电','购电','微燃机发电','风电','光伏','电负荷')
xlabel('时间(h)');
ylabel('功率(kW)');
title('场景3');
figure;
yc=[-p_gl(:,4)';-p_sell(:,4)';-p_ch(:,4)']';
bar(yc,'stack')
hold on
yy=[p_dis(:,4)';p_buy(:,4)';p_g(:,4)';p_wt(:,4)';p_pv(:,4)']';
bar(yy,'stack')
plot(p_l(:,4)+pdz(:,4)-pdd(:,4),'b-*','LineWidth',1)
legend('电锅炉','售电','充电','放电','购电','微燃机发电','风电','光伏','电负荷')
xlabel('时间(h)');
ylabel('功率(kW)');
title('场景4');
figure;
yy1=-h_ch(:,1)';
bar(yy1,'m','stack')
hold on
yy=[h_dis(:,1)';1.2.*p_g(:,1)';0.9.*p_gl(:,1)']';
bar(yy,'stack')
hold on
plot(p_h(:,1)-phd(:,1),'m-*','LineWidth',1);
legend('储热','放热','微燃机热供应','电锅炉','热负荷')
xlabel('时间(h)');
ylabel('功率(kW)');
title('场景1');
figure;
yy1=-h_ch(:,2)';
bar(yy1,'m','stack')
hold on
yy=[h_dis(:,2)';1.2.*p_g(:,2)';0.9.*p_gl(:,2)']';
bar(yy,'stack')
hold on
plot(p_h(:,2)-phd(:,2),'m-*','LineWidth',1);
legend('储热','放热','微燃机热供应','电锅炉','热负荷')
xlabel('时间(h)');
ylabel('功率(kW)');
title('场景2');
figure;
yy1=-h_ch(:,3)';
bar(yy1,'m','stack')
hold on
yy=[h_dis(:,3)';1.2.*p_g(:,3)';0.9.*p_gl(:,3)']';
bar(yy,'stack')
hold on
plot(p_h(:,3)-phd(:,3),'m-*','LineWidth',1);
legend('储热','放热','微燃机热供应','电锅炉','热负荷')
xlabel('时间(h)');
ylabel('功率(kW)');
title('场景3');
figure;
yy1=-h_ch(:,4)';
bar(yy1,'m','stack')
hold on
yy=[h_dis(:,4)';1.2.*p_g(:,4)';0.9.*p_gl(:,4)']';
bar(yy,'stack')
hold on
plot(p_h(:,4)-phd(:,4),'m-*','LineWidth',1);
legend('储热','放热','微燃机热供应','电锅炉','热负荷')
xlabel('时间(h)');
ylabel('功率(kW)');
title('场景4');
figure;
plot(p_l(:,1),'b--','LineWidth',1.5);
hold on
plot(p_l(:,1)+pdz(:,1)-pdd(:,1),'c-','LineWidth',1.5);
bar(pdd(:,1),'m');
legend('需求响应前负荷','需求响应后负荷','可中断负荷');
xlabel('时间');
ylabel('功率');
title('场景1');
figure;
plot(p_l(:,2),'b--','LineWidth',1.5);
hold on
plot(p_l(:,2)+pdz(:,2)-pdd(:,2),'c-','LineWidth',1.5);
bar(pdd(:,2),'m');
legend('需求响应前负荷','需求响应后负荷','可中断负荷');
xlabel('时间');
ylabel('功率');
title('场景2');
figure;
plot(p_l(:,3),'b--','LineWidth',1.5);
hold on
plot(p_l(:,3)+pdz(:,3)-pdd(:,3),'c-','LineWidth',1.5);
bar(pdd(:,3),'m');
legend('需求响应前负荷','需求响应后负荷','可中断负荷');
xlabel('时间');
ylabel('功率');
title('场景3');
figure;
plot(p_l(:,4),'b--','LineWidth',1.5);
hold on
plot(p_l(:,4)+pdz(:,4)-pdd(:,4),'c-','LineWidth',1.5);
bar(pdd(:,4),'m');
legend('需求响应前负荷','需求响应后负荷','可中断负荷');
xlabel('时间');
ylabel('功率');
title('场景4');
figure;
plot(p_h(:,1),'b--','LineWidth',1.5);
hold on
plot(p_h(:,1)-phd(:,1),'c-','LineWidth',1.5);
bar(phd(:,1),'m');
legend('需求响应前热负荷','需求响应后热负荷','削减热负荷');
xlabel('时间');
ylabel('功率');
title('场景1');
figure;
plot(p_h(:,2),'b--','LineWidth',1.5);
hold on
plot(p_h(:,2)-phd(:,2),'c-','LineWidth',1.5);
bar(phd(:,2),'m');
legend('需求响应前热负荷','需求响应后热负荷','削减热负荷');
xlabel('时间');
ylabel('功率');
title('场景2');
figure;
plot(p_h(:,3),'b--','LineWidth',1.5);
hold on
plot(p_h(:,3)-phd(:,3),'c-','LineWidth',1.5);
bar(phd(:,3),'m');
legend('需求响应前热负荷','需求响应后热负荷','削减热负荷');
xlabel('时间');
ylabel('功率');
title('场景3');
figure;
plot(p_h(:,4),'b--','LineWidth',1.5);
hold on
plot(p_h(:,4)-phd(:,4),'c-','LineWidth',1.5);
bar(phd(:,4),'m');
legend('需求响应前热负荷','需求响应后热负荷','削减热负荷');
xlabel('时间');
ylabel('功率');
title('场景4');
figure;
kzyp=max(pdz(:,1),zeros(24,1));
kzyb=min(pdz(:,1),zeros(24,1));
plot(p_l(:,1),'b--','LineWidth',1.5);
hold on
plot(p_l(:,1)+pdz(:,1)-pdd(:,1),'c-','LineWidth',1.5);
plot(p_h(:,1),'r--','LineWidth',1.5);
plot(p_h(:,1)-phd(:,1),'m-','LineWidth',1.5);
bar(kzyb);
yy=[kzyp,pdd(:,1),phd(:,1)];
bar(yy,'stack');
legend('需求响应前电负荷','需求响应后电负荷','需求响应前热负荷','需求响应后热负荷','可转移电负荷(-)','可转移电负荷(+)','可中断电负荷','可中断热负荷');
xlabel('时间');
ylabel('功率');
title('场景1');
figure;
kzyp=max(pdz(:,2),zeros(24,1));
kzyb=min(pdz(:,2),zeros(24,1));
plot(p_l(:,2),'b--','LineWidth',1.5);
hold on
plot(p_l(:,2)+pdz(:,2)-pdd(:,2),'c-','LineWidth',1.5);
plot(p_h(:,2),'r--','LineWidth',1.5);
plot(p_h(:,2)-phd(:,2),'m-','LineWidth',1.5);
bar(kzyb);
yy=[kzyp,pdd(:,2),phd(:,2)];
bar(yy,'stack');
legend('需求响应前电负荷','需求响应后电负荷','需求响应前热负荷','需求响应后热负荷','可转移电负荷(-)','可转移电负荷(+)','可中断电负荷','可中断热负荷');
xlabel('时间');
ylabel('功率');
title('场景2');
figure;
kzyp=max(pdz(:,3),zeros(24,1));
kzyb=min(pdz(:,3),zeros(24,1));
plot(p_l(:,3),'b--','LineWidth',1.5);
hold on
plot(p_l(:,3)+pdz(:,3)-pdd(:,3),'c-','LineWidth',1.5);
plot(p_h(:,3),'r--','LineWidth',1.5);
plot(p_h(:,3)-phd(:,3),'m-','LineWidth',1.5);
bar(kzyb);
yy=[kzyp,pdd(:,3),phd(:,3)];
bar(yy,'stack');
legend('需求响应前电负荷','需求响应后电负荷','需求响应前热负荷','需求响应后热负荷','可转移电负荷(-)','可转移电负荷(+)','可中断电负荷','可中断热负荷');
xlabel('时间');
ylabel('功率');
title('场景3');
figure;
kzyp=max(pdz(:,4),zeros(24,1));
kzyb=min(pdz(:,4),zeros(24,1));
plot(p_l(:,4),'b--','LineWidth',1.5);
hold on
plot(p_l(:,4)+pdz(:,4)-pdd(:,4),'c-','LineWidth',1.5);
plot(p_h(:,4),'r--','LineWidth',1.5);
plot(p_h(:,4)-phd(:,4),'m-','LineWidth',1.5);
bar(kzyb);
yy=[kzyp,pdd(:,4),phd(:,4)];
bar(yy,'stack');
legend('需求响应前电负荷','需求响应后电负荷','需求响应前热负荷','需求响应后热负荷','可转移电负荷(-)','可转移电负荷(+)','可中断电负荷','可中断热负荷');
xlabel('时间');
ylabel('功率');
title('场景4');