학생 인터뷰: 이승준 박사과정생

CDSL 학생들은 어떤 연구를 하고 있을까? 이번 포스팅에서는 이승준 학생을 인터뷰 하였다.

Q. 안녕하세요. 오늘 인터뷰에 응해주셔서 감사합니다.

A. 안녕하세요. 저는 2020년 현재 제어 및 동역학 연구실의 박사과정 4년차인 이승준입니다.

Q. 연구하시는 분야에 대해 간략하게 소개해주시겠어요?

A. 제가 연구하고 있는 분야는 한마디로 분산 최적화(distributed optimization)분야입니다. 본래 최적화는 특정한 제한 조건(constraint)을 가지는 집합 위에서 정의된 함수 등에 대해 그 값이 최대나 최소가 되는 상태를 해석하는 문제로 잘 알려져있습니다. 분산 최적화 분야에서도 마찬가지로 같은 최적화 문제를 풀고자 합니다만, 다중 개체(multi-agent)를 이용한 분산적 접근 방식이 기존의 최적화 분야에서와 가장 다른 점이라고 할 수 있습니다. 쉽게 생각해보면, 여러 대의 컴퓨터가 하나의 최적화 문제를 풀고자 할 때 컴퓨터들은 서로 어떤 정보를 활용할 것인지, 어떻게 정보를 합칠 것인지 등을 약속해야합니다. 이러한 약속(protocol)을 잘 설계하여 주어진 다중 개체를 효율적으로 활용하는 것이 분산 최적화 분야에서 주로 가지는 목표라고 할 수 있습니다.

Q. 다중 개체를 이용하는 분산적 접근 방식이 기존의 방식에 비해 가지는 장점은 무엇인가요?

A. 논문 [1, 2]에서 소개된 EDP(Economic Dispatch Problem)를 예로 들어 설명하는 것이 좋을 것 같습니다. EDP는 그림1과 같이 여러 대의 발전소가 전력 생산을 함께할 때, 각 발전소의 생산량을 결정하는 문제입니다. 특히, 각 노드(발전소)의 전력 생산에 따른 비용함수가 \(J_i\)로, 전력 수요량이 \(d_i\)로 주어질 때 전력 생산량의 합이 전력 수요량의 합과 일치하는 제한 조건 하에서 전체 생산 비용을 최소화하는 전력 생산량 \(x_i\)를 구하고자 합니다. 이를 최적화 문제로 표현하면 다음과 같습니다.

\( \displaystyle\min_{x_1, x_2, \ldots, x_N} \sum_{i=1}^{N} J_i(x_i) \)
subject to \(\displaystyle\sum_{i=1}^{N} x_i = \sum_{i=1}^{N} d_i \)

위와 같은 문제를 기존의 방식대로 중앙집중적(centralized)으로 푼다면, 먼저 1개의 특정 리더 노드가 모든 노드의 전력 생산에 따른 비용함수 \(J_i\)와 생산량 \(x_i\), 수요량 \(d_i\) 를 모두 파악하고 있어야 합니다. 또한, 혹시라도 그 리더에 문제가 발생한다면 아예 최적해를 구하는 일이 불가능해집니다. 한편, 실제의 발전소들과 같이 노드들이 매우 넓게 퍼져있는 상황을 가정한다면 모든 노드는 리더와 통신해야하므로 각 노드가 충분히 강한 통신 출력을 필요로 하게 됩니다.

반면, 같은 문제를 분산적(distributed)으로 푼다면, 노드들은 서로 자신의 비용함수 \( J_i\)를 서로 공유할 필요가 없게 되어 보안성을 강화할 수 있습니다. 또한, 어떠한 이유로 몇몇의 노드에 문제가 발생한다고 해도 기존의 방법에 비해 강인하게 최적해를 찾아낼 수 있게 됩니다. 마찬가지로 노드들이 넓게 퍼져있는 네트워크에서도 분산적 접근 방법에서는 각 노드가 오직 자신의 이웃들과 통신하므로 이전만큼 강한 통신 출력이 요구되지 않습니다. 본 문제에 대한 자세한 설명은 [1, 2]와 다음 링크에 주어져 있습니다.

Q. 구체적인 연구 내용을 알려주세요.

매우 일반적인 최적화 문제에 대한 연구실 고유의 결과인 논문 [3]이 있어 이를 소개해드리고자 합니다. 먼저 다음과 같은 최적화 문제를 가정하겠습니다.

\( \displaystyle \min_ {x_1, x_2, \ldots, x_N} \sum_{i=1}^{N} f_i(x_i) \tag{\(\ast\)} \label{eq:opt}\)
subject to \( \displaystyle x_1=x_2=\ldots=x_N\)

이때, 노드들이 나타내는 그래프는 연결되어 있고, 방향성이 없어서 노드 사이에 양방향 통신이 가능하다고 가정합니다. 이러한 문제를 중앙집중적으로 풀기 위해서는 그림2와 같이 잘 알려진 경사 하강 알고리즘(gradient descent algorithm)을 사용하면 충분합니다. 즉, \(\dot x = – \nabla \sum_{i=1}^{N} f_i(x)\)의 동역학을 임의의 초기값으로부터 출발시켜 돌리게 되면 \(x\)는 우리가 찾고자 했던 최적해(최소값)로 수렴한다는 것입니다. 하지만 최적해를 찾는 이러한 방식은 위에서 언급한 중앙집중적 접근의 여러 가지 한계를 지니게 됩니다.

반면, 같은 문제를 분산적으로 풀기 위해서 총 \(N\)개의 노드로 이루어진 네트워크 상에서 임의의 \(i\)번째 노드에 대해 다음과 같은 동역학을 정의합니다.

\(\displaystyle \dot x_i = {\color{red}{-\nabla f_i(x_i)}} + {\color{blue}{k \sum_{j \in \mathcal{N}_i} (x_j-x_i)}} \tag{1} \label{eq:x_i}\)

이때, \(\mathcal{N}_i\)는 \(i\)번째 노드와 직접 연결된 이웃 노드로 구성된 집합을 의미합니다. 이 동역학은 최적해로 다가가는 동역학(빨간색)과 다른 노드와 자신의 값을 비교하여 자신의 값과 이웃의 값의 차이를 감소시키도록 만드는 동역학(파란색)으로 구성되어 있음을 쉽게 살펴볼 수 있습니다. 하지만 동역학 \eqref{eq:x_i}의 \(x_i\)가 \(x_i^*\)로 가까워진다고 할 때, 우리는 아직 수렴점 \(x_i^*\)가 모든 \(i\)에 대해서 같은 값을 가지는지, 그리고 \(x_i^*\) 가 실제로 위 \eqref{eq:opt}의 최적해가 되는지 알 수 없습니다. 따라서 동역학 \eqref{eq:x_i}를 자세히 해석하기 위해 연구실에서 새롭게 제시한 average dynamics 또는 blended dynamics로 불리우는 동역학은 다음과 같이 정의됩니다. blended dynamics에 대한 자세한 설명은 다음 링크에서 찾아볼 수 있습니다.

\(\displaystyle \dot s = -\frac{1}{N}\sum_{i=1}^{N} \nabla f_i(s) \tag{2} \label{eq:blended} \)

위의 동역학은 \eqref{eq:x_i}의 벡터장을 모두 모아 산술 평균을 취한 것을 하나의 벡터장으로 가지는 가상의 동역학입니다. 이때, [3]은 충분히 큰 \(k\)에 대해 \eqref{eq:x_i}의 해가 \eqref{eq:blended}의 해로 충분히 작은 오차범위 내에서 practically 수렴한다는 것을 보여줍니다. 다시 말하면, 다음이 성립한다는 것입니다.

\(\forall \epsilon > 0, \exists k^*\) such that for all \(k\geq k^*, \displaystyle\limsup_{t\to\infty} |x_i(t)-s(t)| < \epsilon \)

따라서 \eqref{eq:blended}의 수렴점을 \(s^*\)라고 할 때, 충분히 큰 \(k\)를 사용하여 구성한 \eqref{eq:x_i}의 해는 \(i\)에 관계없이 \(s^*\)로 수렴하며 심지어

\(\displaystyle -\frac{1}{N} \sum_{i=1}^{N}\nabla f_i(s^*) = 0 \:\Rightarrow\: \nabla\big(\sum_{i=1}^{N}f_i(s^*)\big) = 0 \)

이 성립하므로 모든 \(i\)와 임의의 초기값에 대해 동역학 \eqref{eq:x_i}를 돌리면 \eqref{eq:opt}의 최적해에 충분히 가까운 해를 구할 수 있음을 알 수 있습니다. 정리하면, \eqref{eq:opt}와 최적화 문제를 분산적으로 풀고자 할 때, 각 노드에서는 충분히 큰 \(k\)로 구성된 \eqref{eq:x_i}를 풀면 충분하다는 것입니다. 여기에서 위에서 언급한 최적화의 분산적 접근이 가지는 장점이 드러나는데, 각 노드들이 서로 자신의 벡터장 \(f_i\)를 공유하지 않고 이웃한 노드의 상태 변수(\(x_j, j\in\mathcal{N}_i\))만을 공유하여 전체 문제에 해당하는 최적해를 찾을 수 있다는 것입니다. EDP를 예로 들면, 각 노드(발전소)가 지니는 자신의 벡터장 \(f_i\)는 전력의 생산 단가와 같이 경쟁 업체에게 보여주고 싶지 않은 정보를 포함하기 때문에 자신의 벡터장 \(f_i\)를 공유하지 않는다는 장점이 큰 효과를 발휘하게 됩니다.

Q. 연구의 계기, 동기가 궁금합니다.

A. 사실 저는 학부생 시절부터 그래프 이론과 다중 개체 시스템(multi-agent system)에 관심을 가지고 있었습니다. 그러한 관심사들의 교집합을 찾다 보니 본 연구실에 들어와 관련 연구를 진행하게 되었습니다. 개인적으로 분산 최적화 분야의 연구가 흥미롭다고 생각하는 이유는 다음과 같습니다. 보통 최적화라 함은 컴퓨터 상에서 이산 시간 연산을 통해 이루어지게 되고, 최적화 알고리즘에 대한 해석 또한 이산 시간 위에서 이루어지는 것이 일반적이었습니다. 하지만 최근 제어 이론 연구자들은 여러 가지 최적화 알고리즘을 연속 시간 도메인으로 가져온 뒤 연속 시간 시스템에 대해 잘 정립된 비선형 해석 도구들을 동원하여 새로운 결과들을 내고 있습니다. 이러한 접근 방식이 이산 시간에서의 최적화 알고리즘에 대한 사람들의 직관과 이해도를 높이는데 큰 도움을 주고 있다는 점에서 연구해볼만 한 부분이라고 생각합니다.

Q. 연구에 도움이 되었던, 혹은 연구와 밀접한 관련이 있는 학부 수업은 무엇이 있을까요?

A. 석박통합과정을 대상으로 하는 수업이긴 하지만 전기정보공학부의 최적화기법 수업은 학부생에게도 추천할만 하다고 생각합니다. 물론, 전기시스템선형대수 등 선형대수학 수업도 연구와 밀접한 관련이 있는 것 같습니다.

말씀 감사합니다!

[1] “Initialization-free privacy-guaranteed distributed algorithm for economic dispatch problem”
Hyeonjun Yun, Hyungbo Shim, and Hyo-Sung Ahn
Automatica, vol. 102, pp. 86-93, 2019.
10.1016/j.automatica.2018.12.033

[2] “Distributed algorithm for economic dispatch problem with separable losses”
Seungjoon Lee, Hyungbo Shim
Control Systems Letters IEEE, vol. 3, no. 3, pp. 685-690, 2019.
10.1109/LCSYS.2019.2916250

[3] “Robustness of synchronization of heterogeneous agents by strong coupling and a large number of agents”
Jaeyong Kim, Jongwook Yang, Hyungbo Shim, Jung-Su Kim, and Jin Heon Seo
IEEE Trans. on Automatic Control, vol. 61, no. 10, pp. 3096-3102 , 2015.
10.1109/TAC.2015.2498138