에너지시스템 최적화/게임이론 강의: 12) Variants of ADMM and applications
이 포스팅은, Technical University of Denmark의 박사과정 과목 “Advanced Optimization and Game Theory for Energy Systems” (Prof. Jalal Kazempour) 의 12강을 필자가 요약한 내용이다.
Economic dispatch
여러 대의 발전기로 시간별 수요를 만족시키는 최소비용의 스케줄을 구하는 문제에서는, 각 수요-공급 일치 조건이 complicating constraint이다. 해당 제약조건에 모든 발전기의 출력 항들이 포함되기 때문으로, 해당 제약조건을 relax하면 각 발전기 별 subproblem으로 나눌 수 있다.
위 예제에서는 목적함수가 quadratic function이므로, Lagrangian Relaxation (LR) 을 적용할 수 있다.
Complicating constraint인 수요-공급 일치 제약에 dual variable $\lambda$을 곱한 항을 목적함수에 추가하고, dual variable의 값을 $\bar{\lambda}$ 로 고정하면, 각 발전기 별 subproblem으로 나눌 수 있다.
그리고 각 발전기 별 subproblem을 풀어 $v$번째 iteration 기준 $p_g^{(v)}$를 구하고, 이를 통해 아래와 같이 $\bar{\lambda}^{(v)}$를 $\bar{\lambda}^{(v+1)}$로 업데이트한다.
이 때 $\bar{\lambda}^{(v)}$는 수요-공급 일치 제약에 대한 dual variable이므로 ‘가격’이기도 하다. 여기서는 각 발전기 별로 자신의 이익을 최대화하는 발전량을 설정하고, 이를 모두 취합한 market operator가 가격을 업데이트한 후 다시 발전기들에게 통보한다. 그리고 각 발전기는 수정된 가격에 대해 발전량을 재설정하고, market operator는 이를 다시 취합해 가격을 업데이트하는 과정을 수렴할 때까지 반복한다.
이런 식으로 가격을 iterative하게 결정하는 시장을 Walrasian auction이라고 한다.
이러한 ‘distributed’ technique 기반으로 가격을 결정하는 방법은, 시장에 여러 가지 externalities가 추가되어 시장 균형 문제가 더 이상 동치인 최적화 문제를 갖지 않는 경우에 특히 유용한 것으로 알려져 있다.
Market clearing (with linear offers)
Market clearing problem에서도 수요-공급 일치 조건이 complicating constraint이다.
만약 위 예제처럼 목적함수가 quadratic이 아니라 linear function이면, ‘augmented’ LR을 사용해야 한다. 그러므로 목적함수에 complicating constraint의 제곱항을 추가한다 (regulization coefficient $\gamma/2$를 곱해서).
단, 이 경우 $\lambda$의 값을 $\bar{\lambda}$로 고정해도 각 발전기 별 subproblem으로 바로 나눌 수 없다. Complicating constraint의 제곱항 내에 변수들 간 product term이 있기 때문이다. 그러므로 각 발전기에 대해, 나머지 발전기들의 발전량을 고정하여 구성한 문제를 푼다 (ADMM). 각 발전기 별 최적의 발전량을 기반으로, $\bar{\lambda}$가 업데이트된다.
Privacy 이슈를 고려한 Exchange ADMM
위 슬라이드의 ADMM에는 한 가지 ‘실질적인’ 문제가 있다. 발전기 1번의 ($v$번째 iteration에서의) 발전량을 계산하려면 발전기 2와 발전기 3의 ($v-1$번째 iteration에서의) 발전량 정보가 발전기 1에 전달되어야 하는데, 이는 ‘privacy 침해’로 볼 수 있기 때문이다.
그러나 문제의 식을 아래 슬라이드와 같이 ‘모든 발전기들의 발전량들의 평균’을 도입해 변형하면, 이러한 ‘privacy 침해’ 문제를 완화할 수 있다.
각 발전기는 $v-1$번째 iteration에서의 자기 자신의 발전량 $x_i^{(v-1)}$ 및 ‘모든 발전기들의 발전량들의 평균’ $\bar{x}^{(v-1)}$ 을 알면, $x_i^{(v)}$를 계산할 수 있다. 즉 각자의 발전량 정보는 market operator에게는 전달되지만, 다른 개별 발전기들에게는 전달되지 않기 때문에 privacy 침해 문제가 완화된다. 이를 ‘exchange’ ADMM이라 한다.
Consensus ADMM
모든 subproblem들에 공통으로 포함된 complicating variable이 있을 경우 이를 Bender’s decomposition으로 푸는 대신, ADMM 방식으로 풀 수도 있다.
아래 슬라이드에서는, 원래 문제에서의 complicating variable $x$를 각 subproblem $i$ 별로 $x_i$라는 변수로 두고, 대신 $x_i$가 공통의 값 $z$와 같다는 제약을 추가했다. 이 문제에서 $z$는 parameter가 아닌 변수임에 주의한다.
$x_i=z$는 complicating constraint이다. 그러므로, 각 subproblem별 목적함수에 제약 $x_i-z=0$의 좌변에 dual variable을 곱한 항과 좌변의 제곱에 regularization coefficient를 곱한 항을 추가 후 dual variable과 $z$의 값을 고정해 ADMM 스타일의 문제를 아래와 같이 구성할 수 있다.
각각의 $x_i$가 전부 특정 값 $z$로 같아야 한다는, 즉 ‘consensus를 이뤄야 한다는’ 제약이 있어, 이를 consensus ADMM이라 한다.
여기서 난점은, $\bar{\lambda}$ 뿐 아니라 complicating variable이 최종적으로 가져야 할 값 $z$도 업데이트해야 한다는 것이다.
다행히도, $z$를 업데이트하는 문제는 아래와 같이 analytic solution을 가진다.
$N^{-1} \sum_{i=1}^N x_i^{(v)}$를 $\bar{x}^{(v)}$로 쓰면, 아래와 같다.
이 식들을 적절히 결합하면, 최종적으로 $z$가 사라진 아래와 같은 알고리즘을 얻는다.
즉 $v$번째 iteration에서 각 $x_i^{(v)}$는, $v-1$번째 iteration에서의 $x_i^{(v-1)}$들의 평균 $\bar{x}^{(v-1)}$ 으로부터 멀어질수록 penalty를 가하는 목적함수에 의해 결정된다. 이 penalty가 zero가 되는 시점은 모든 $x_i^{(v)}$들이 같아질 때, 즉 consensus를 이룰 때이다. (이러한 방법을 progressive hedging이라고도 한다.)
Consensus ADMM은 stochastic market clearing에서 하루전 시장에서의 급전변수들을 결정할 때, 전력 네트워크에 여러 개의 node들이 있을 때 각 node 개별의 ‘distributed optimal power flow’ 문제들로 나눌 때 쓸 수 있다.
01) Market clearing as an optimization problem
02) Market clearing as an equilibrium problem
03) Desirable properties of market-clearing mechanisms
04) Market clearing using a cooperative game approach
05) Stochastic market clearing
06) Robust approaches for market clearing
07) Bilevel programming in energy systems
08) Optimization problems with decomposable structure
09) Benders’ decomposition: Theory
10) Benders’ decomposition: Applications
11) Augmented Lagrangian relaxation
12) Variants of ADMM and applications