深度学习|改进两阶段鲁棒优化算法i-ccg

maltadirk

1 主要内容

自从2013年的求解两阶段鲁棒优化模型的列和约束生成算法（CC&G）被提出之后，基本没有实质性的创新，都是围绕该算法在各个领域的深度应用，有些小的变形应用也都是基于模型应用，比如嵌套CCG等。所以这些年大热的CC&G研究在算法改进方面鲜有成就，电气专业同学在研究源荷不确定性的过程中基本都要学习该算法，明确求解流程、主子问题研究内容以及对偶、kkt条件等，现给大家推荐一个新鲜出炉的改进算法i-CCG。


2 改进算法

2.1  CC&G算法的优势

一般两阶段鲁棒优化调度模型是 min-max-min 形式的非凸优化问题，难以直接求解。目前常用 Benders 分解或 C&CG 算法将该类型问题转化为包含 min 主问题和 max-min 子问题的两阶段优化。若模型第三层仅包含连续变量，则 max-min子问题可通过强对偶理论或 KKT（Karush-Kuhn-Tucker）条件等效为单层max问题，此时通过主问题和子问题的迭代计算即可求解出优化结果。相较于 Benders分解，C&CG 算法能在较少的迭代次数内达到收敛，其求解效率较高，主要原因为：
1）C&CG 算法在求解子问题时对场景进行严格辨识以缩减模型求解的搜索域；
2）C&CG 算法在求解主问题时保持了主问题的原始模型架构，而 Benders分解利用对偶割平面构建主问题，破坏了原始模型架构，增加了模型计算量。
因此 C&CG 算法已经成为求解两阶段鲁棒优化问题的主要方法。
2.2 i-CCG算法简介

该算法是在2023年刚发表的文章《An inexact column-and-constraint generation method to solve two-stage robust optimization problems》提出来的，有兴趣同学可以下载学习一下，因为是刚发布的算法，用该算法建模型、求解、对比分析和增加小的改动都会提高文章的创新性，解决发表文章难的问题。
目的：该算法是为了解决CCG算法应用于大规模求解或者较难的模型求解速度慢的难题，虽然通过牺牲求解精度来提升求解速度，但是通过迭代参数设置以及求解步骤能够保证最终的结果收敛于最优解。
算法步骤：传统CCG的求解步骤如下：


研究过的同学应该比较了解，传统两阶段鲁棒主要是主子问题的循环迭代，子问题需要通过强对偶或者KKT条件得到最恶劣运行工况，通过增加变量的形式带入主问题，通过迭代获得最优解。整个逻辑比较简单，容易理解，虽然程序语言实现过程中会遇到各种坑，但是基本思路还是挺容易理解的。
i-CCG算法步骤：


该算法初始阶段通过牺牲求解精度（设置emp的值）来达到快速求解的目的，在循环迭代过程中增加了不精确求解变量（相当于在传统CCG算法中增加了一个缓冲层），并对求解的状态进行识别，不同求解状态下会进入不同的循环阶段，直至收敛到阈值以下。
3 结果对比

以《6节点电网两阶段鲁棒优化调度matlab》为例进行算法验证，常规算法下的迭代收敛曲线如下：


i-CCG算法的收敛曲线如下：


很显然，该改进算法的性能确实要好很多，通过实际程序求解时间都能明显感受到i-CCG算法求解速度快得多，因此，大家可以借用新算法开展深入研究和应用，祝大家SCI/EI/核心随便就能中！