에너지시스템 최적화/게임이론 강의: 11) (Augmented) Lagrangian relaxation
이 포스팅은, Technical University of Denmark의 박사과정 과목 “Advanced Optimization and Game Theory for Energy Systems” (Prof. Jalal Kazempour) 의 11강을 필자가 요약한 내용이다.
Complicating constraint가 있을 경우의 Lagrangian Relaxation (LR)
에너지시스템 최적화 문제에서는 수요-공급 일치 조건, ramping limit 조건, 두 지역을 잇는 송전선 관련 조건 등이, ‘여러 소문제들의 변수들을 포함하는’ complicating constraint로써 포함되곤 한다. 해당 제약을 relax해서 큰 문제 대신 작은 subproblem들을 풀 수 있다.
(이를테면 여러 지역을 잇는 송전 제약을 relax하면, 각 지역 별 market clearing problem을 따로 푸는 문제로 변환될 수 있다.)
핵심은, 아래와 같이 complicating constraint들을 dual variable을 곱한 term으로 목적함수에 포함시키는 것, 그리고 dual variable들을 특정 값으로 고정하는 것이다.
Complicating constraint가 아닌 constraint는 그대로 두고 complicating constraint들만을 목적함수에 포함시키므로, 이는 ‘partial’ Lagrangian으로 볼 수 있다. 그래서 이 기법의 이름이 Lagrangian Relaxation (LR) 이다.
Dual variable의 값을 고정함으로써, 위 예시 기준으로 각 $i$별 subproblem들이 구성된다. 단, 해당 고정값이 최적의 값인지 모르므로, iteration을 통해 최적의 값에 가까워지게 해야 한다.
간단한 예시는 아래와 같다.
Complicating constraint $-x-y+4=0$에 dual variable $\mu$를 곱한 값을 목적함수에 더한 후 $\mu$의 값을 $\bar{\mu}$로 고정 후 $x$와 $y$ 각각에 대한 subproblem을 푼다. 그 결과 얻은 variable들의 값들 $x^{(v)}$와 $y^{(v)}$에 기반해 $\bar{\mu}$를 업데이트한다.
이 때 $a$와 $b$는 일종의 hyperparameter로, 그 값에 따라 수렴 속도 및 안정성이 달라진다. (Bender’s decomposition에서는 이런 hyperparamter가 없었다. 그래서 필자가 보기엔 LR은 약간은 ‘learning’ 요소가 있는 기법이다.)
목적함수가 linear function일 때의 ‘Augmented’ LR
주의할 점은, LR을 그대로 쓰려면 목적함수의 first derivative가 연속함수여야 한다는 것이다. 이 연속함수는 상수함수를 포함하지 않는다. 따라서 위 예제처럼 목적함수가 quadratic function인 경우 LR을 쓸 수 있지만, 만약 목적함수가 linear function이라면 LR을 쓸 수 없다 (정확히는 쓰더라도 수렴이 보장되지 않는다).
목적함수가 linear function이지만 complicating constraint를 relax해 subproblem들로 쪼개고 싶은 경우 쓸 수 있는 방법으로, ‘Augmented’ Lagrangian Relaxation (ALR) 이 있다.
ALR에서는 목적함수를 확실하게 quadratic function으로 만들기 위해, complicating constraint의 제곱항을 추가한다. 예시는 아래와 같다.
(위 예시에서 목적함수가 이미 quadratic이므로 굳이 ALR을 쓸 필요가 없지만, 이해를 돕기 위해 앞의 LR 예시와 같은 예시로 설명하였다.)
어차피 optimal point에서는 $-x-y+4=0$이므로, 위 항을 추가해도 여전히 같은 문제를 푸는 셈이다. 위 식에서 $\gamma$는 regularization hyperparameter로 볼 수 있다.
단, 위 문제에서는 $\lambda$를 고정시키더라도 $x$와 $y$ 각각의 subproblem으로 쪼갤 수 없다. $(-x-y+4)^2$ 가 $xy$, 즉 product term을 포함하기 때문이다.
Alternating Direction Method of Multipliers (ADMM)
Product term 때문에 문제를 쪼갤 수 없다면, 차선책은 product term에 있는 변수 중 하나를 고정시키고 나머지 변수에 대한 문제를 푸는 것이다. 이러한 방법을 alternating direction method of multipliers (ADMM) 이라 한다.
위 예시에 ADMM을 적용하는 과정은 아래와 같다.
여기서 윗첨자가 $(v)$인 항들이 변수이고, 윗첨자가 $(v-1)$인 항들은 parameter들이다 (이전 iteration에서 구한 값들). Optimal point에서는 $-x-y+4=0$ 이므로, $\lambda^{(v)} \approx \lambda^{(v-1)}$ 이면 optimal point에 수렴한 것으로 본다.
$\gamma$가 일종의 learing rate 역할을 하므로, 이를 너무 크거나 작지 않게 적절히 결정해 주어야 한다.
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