최적화, 라그랑지 승수법 (Optimization with the Method of Lagrange multipliers)
kipid2023. 10. 25. 09:55
반응형
# 최적화, 라그랑지 승수법 (Optimization with the Method of Lagrange multipliers)
by kipid
This document is written in Korean. Only the last section is written in English. For more concrete and featured version (this is written in english), see .
Several sections are initially hiden. Click the "▼ Show/Hide" button to see the hidden section. And hide your readen sections so as to save your computer resources.
Complex 관련 section은 숨겨져 있습니다. 보시려면 "▼ Show/Hide" 클릭하시길. 수식들 때문에 느려질수도 있으니 다 본 section은 숨겨놓고 ("▲ Hide" 클릭) 다음걸 보시길 추천드립니다. Section number 옆의 T를 클릭하시면 "Table of Contents"로 이동합니다. 조금 더 자세한 설명 및 증명은 영어버전인 를 보시길.
많은 경우 우리는 최적화 문제와 맞딱드린다. 예를 들면,
부산까지 가는 최단거리 경로(course)는? (들어갈 수 있는 제약조건으로는 `대중교통(기차, 버스, 비행기, 배 등)을 이용', `비포장 도로는 제외' 같은 것들이 있을 수 있겠음.)
강릉까지 가는 최단시간 경로(course)는? (교통정보 및 교통수단, 도로상태 같은 것들도 변수로 작용.)
5년 후 최대 이익을 내는 금융상품은?
학생들에게는 `최소값, 최대값 구하라'는 수학문제들.
까지. 우리들 인생 자체가 최적화 문제라고 할수도 있을것이다. 누구나 `어떻게 살아야 가장 잘 사는 걸까?'를 항상 달고 사니까. 뭐 기준이야 사람마다 다 다르긴 할테지만 말이지. 아무튼, 이러한 최적화 문제를 푸는 수학적 방법 한가지를 소개하고자 한다. 바로 잘 알려진? Lagrange multiplier Formalism(라그랑지 승수법)이다.
물리학과 학생들은 한번쯤 접해봤을테고, 수학과나 공과대 학생들도 간혹 들어봤을듯? 우선 고등학교때 배운 최적화 방법에 대해 잠깐만 알아보고 가자.
## PH
2023-03-16: To SEE.
2015-12-16: Eq. $j \rightarrow l\textrm{'s}$ 로 수정. 실수했었네. 이 문서도 그런데 SEE 로 만들어야 할텐데... 긴 문서라서 귀찮네 ㅡㅡ.
2014-06-12: docuK upgrade. css/js through CDN.
2014-06-11: docuK upgrade.
## TOC
## $f(x)$ (or $f(\{x_i\})$)의 최대/최소값 구하기
함수 $f(x)$의 최대/최소값을 구하는 방법은? 미분값이 0인
\frac{\partial f(x)} {\partial x} = 0
점들과 미분이 안되는 점들, 경계값들을 비교해서 구한다.
함수가 다변수 함수(function with multiple variables)일 경우, 함수 $f(x_1, x_2, \cdots) = f(\{x_i\})$의 최대/최소값은
\frac{\partial f(\{x_i\})} {\partial x_k} = 0
모든 변수에 대한 미분이 0이 되는 점들과 미분이 안되는 구간, 경계 구간들을 비교해서 구한다.
// 왜 이렇게 이런 점들만 비교하면 되는지는 따로 설명안해도 되겠죠?
[Ex] 구간 [-5,5]에서 $f(x) = x^4 + 3 x^3 - 8 x^2 + x - 5$의 최대/최소값은?
\partial_x f(x) = 4 x^3 + 9 x^2 - 16 x^2 + 1 = 0
인 세 점 {(-3.44,-85.2), (0.06,-4.97), (1.14,-8.12)}과 경계값 {(-5,40), (5,800)}을 비교하여 구한다. 즉 이 구간에서 최소값은 $x=-3.44$일 때의 $y=-85.2$이고, 최대값은 $x=5$일 때의 $y=800$이다.
## 라그랑지 승수법: 제약조건이 들어간 최적화 (Method of Lagrange multipliers: Optimization with constraints)
물리학을 배울 때 나오는 제약 조건이 들어간 최적화 문제에는
통계역학: 전체 에너지가 정해지거나 입자수가 정해져있을때 확률을 최대로 만드는 $(P, V, N)$ 값.
Euler-Lagrange Equation: Lagrangian Mechanics에서 경로에 제약조건을 걸 때.
등이 있는데, 이런 것들을 배우면서 라그랑지 승수법(Method of Lagrange multipliers)에 대해서 들어봤을 것이다. 내가 배울때 이 방법론(formalism)을 꼼꼼하게 제대로 가르쳐 준 교수님이 없었던걸로 기억하는데... 내가 수업을 빠졌을때 진도가 나간건가?;; 아무튼 이 방법론에 대해서 자세히 설명해 볼까 한다.
### Multiple variables and single constraint
변수들이 $g(\{x_i\})=$const 인 제약조건을 갖는 상태에서 $f(\{x_i\})$의 최소/최대값을 구해보자. (The optimization problem minimizing (or maximizing) $f(\{x_i\})$ subject to constraint $g(\{x_i\})=$const.)
이 최소/최대점에서는 변수들이 조금 변하더라도 함수 $f(\{x_i\})$값은 변하지 않을 것이다. 이를 수식적으로 표현하면
\sum_{k} \frac{\partial f(\{x_i\})} {\partial x_k} \delta x_k = 0 \quad \textrm{at extreme points}
로 표현되겠고, 이 미소변화에 의해 제약조건에서 벗어나면 안되므로
\sum_{k} \frac{\partial g(\{x_i\})} {\partial x_k} \delta x_k = 0
이라고 할 수 있다. 즉, 제약조건이 하나 들어오면 변수 하나가 나머지 변수들에 종속이 되어서 무작위로 바뀔 수 있는 변수의 갯수가 줄어드는 효과로 나타난다.
\begin{split}
&\frac{\partial g(\{x_i\})} {\partial x_l} \delta x_l
+ \sum_{k \neq l} \frac{\partial g(\{x_i\})} {\partial x_k} \delta x_k = 0 \\
&\delta x_l = - \frac{\sum_{k \neq l} \partial_{x_k} \big[ g(\{x_i\}) \big] \delta x_k} {\partial_{x_l} \big[ g(\{x_i\}) \big]} .
\end{split}
$\partial_{x_l} \big[ g(\{x_i\}) \big] \neq 0$인 $l$을 하나 택한 뒤,
\frac{\partial f(\{x_i\})} {\partial x_l}
- \lambda \frac{\partial g(\{x_i\})} {\partial x_l} = 0
을 만족하도록 $\lambda$를 도입한다. 즉,
\lambda \equiv \frac{\partial_{x_l} \big[ f(\{x_i\}) \big]} {\partial_{x_l} \big[ g(\{x_i\}) \big]} .
최소/최대점에서는 이런 변수들의 가능한 모든 미소변화에 대해 Eq 과 를 만족해야 하므로,
\begin{split}
&\frac{\partial f(\{x_i\})} {\partial x_l} \delta x_l
+ \sum_{k \neq l} \frac{\partial f(\{x_i\})} {\partial x_k} \delta x_k = 0 \\
&\frac{\partial f(\{x_i\})} {\partial x_l}
\bigg[ - \frac{\sum_{k \neq l} \partial_{x_k} \big[ g(\{x_i\}) \big] \delta x_k} {\partial_{x_l} \big[ g(\{x_i\}) \big]} \bigg]
+ \sum_{k \neq l} \frac{\partial f(\{x_i\})} {\partial x_k} \delta x_k = 0 \\
&- \lambda \sum_{k \neq l} \frac{\partial g(\{x_i\})} {\partial x_k} \delta x_k
+ \sum_{k \neq l} \frac{\partial f(\{x_i\})} {\partial x_k} \delta x_k = 0 \\
&\sum_{k \neq l} \bigg[ \frac{\partial f(\{x_i\})} {\partial x_k} - \lambda \frac{\partial g(\{x_i\})} {\partial x_k} \bigg] \delta x_k = 0
\end{split}
$\delta x_l$만 다른 미소 변화에 대해 종속적으로 만들면 나머지 $\delta x_k$들은 완전히 무작위하게 변할 수 있다. 따라서 이런 무작위한 모든 변화 $\delta x_k$들에 대해 위 식을 만족해야 하므로
\frac{\partial f(\{x_i\})} {\partial x_k}
- \lambda \frac{\partial g(\{x_i\})} {\partial x_k}
= 0 \quad \textrm{for } k \neq l
Eq 와 을 종합하면 모든 변수에 대해 위와같은 방정식을 만족해야 함을 알 수 있다.
바로 이것이 가장 기초적인, 한가지 제약조건이 들어간 최적화법, 라그랑지 승수법 공식이다.
\frac{\partial f(\{x_i\})} {\partial x_k}
- \lambda \frac{\partial g(\{x_i\})} {\partial x_k}
= 0 \quad \textrm{for all } k
따라서 위 두식을 결합하면 결과적으로
\frac{\partial f(\{x_i\})} {\partial x_k}
- \sum_{j=1}^{N} \lambda_{j} \frac{\partial g_j (\{x_i\})} {\partial x_k}
= 0 \quad \textrm{for all } k
로 제약조건인 여러개 일때의 라그랑지 승수법 공식이 나오게 된다.
조금 더 간단하게는
\frac{\partial f(\{x_i\})} {\partial x_p}
- \sum_{j=1}^{N} \lambda_{j} \frac{\partial g_j (\{x_i\})} {\partial x_p}
= 0 \quad \textrm{for }p = l\textrm{'s}
를 만족하도록 $\lambda_j$들을 적절히 선택했다고 가정하고 시작할수도 있다.
### Functional variables and multiple constraints
간혹 함수가 들어간 적분형태의 값을 최적화해야 하는 경우도 볼 수 있는데, 다음과 같은 상황을 생각하자. 우리가 최적화 시켜야 하는 값 $S$가 다음과 같이 주어져 있다고 하자.
S \big( h(x) \big) = \int_{a}^{b} f \big( h(x) \big) dx
이 때의 제약조건이
\int_{a}^{b} g \big( h(x) \big) dx = \textrm{const}
와 같이 나타난다고 한다면 $S$의 최소/최대값은 어떻게 구할까? 이 때의 변수는 함수형태 $f(x)$로 표현되는데 이 때문에 일반적인 실수 변수(real variables)와는 다른 항들(terms)이 들어오게 된다.
아주 간단하게 생각한다면 $a \sim b$ 구간을 충분히 큰 수 $N$으로 나눠서 N개의 변수 $h(x_i)$들로 이루어진
S \big( h(x) \big) = \sum_{i=1}^{N} f \big( h(x_i) \big) \frac{b-a} {N}
를 제약조건
\sum_{i=1}^{N} g \big( h(x) \big) \frac{b-a} {N} = \textrm{const}
내에서 최적화 시키는 문제와 같다고 볼수도 있다. 하지만 크게 차이가 나는 부분이 한가지 있는데, $h(x)$의 1차 미분, 2차 미분, ... 항들
\begin{split}
&\frac{\partial h(x)} {\partial x}
\simeq \frac{h(x_{i+1}) - h(x_i)} {(b-a)/N} , \\
&\frac{\partial^2 h(x)} {\partial x^2}
\simeq \frac{h(x_{i+1}) + h(x_{i-1}) - 2 h(x_i)} {\big[ (b-a)/N \big]^2} , \\
&\cdots
\end{split}
이 들어갈수도 있다는 점이다. 이러한 점 때문에 약간은 다르게 다루어 주어야 하는 부분들이 존재한다.
$h(x)$가 extreme form에서 약간 벗어났을 때 $S$ 값이 어떻게 변할지를 생각해보면,
\begin{split}
&\delta S \big( h(x) \big)
= S \big( h(x) + \delta h(x) \big)
- S \big( h(x) \big) \\
&= \int_{a}^{b} \Big[ f \big( h(x) + \delta h(x) \big)
- f \big( h(x) \big) \Big] dx \\
&= \int_{a}^{b} \Big[ \frac{\partial f} {\partial h(x)} \delta h(x)
+ \frac{\partial f} {\partial \dot{h}(x)} \delta \big( \dot{h}(x) \big)
+ \frac{\partial f} {\partial \ddot{h}(x)}
\delta \big( \ddot{h}(x) \big)
+ \cdots \Big] dx = 0
\end{split}
where
\begin{split}
&\dot{h}(x) \equiv \frac{d h(x)} {d x}
= d_x h(x) , \\
&\ddot{h}(x) \equiv \frac{d^2 h(x)} {d x^2}
= d_x^2 h(x) , \\ \cdots
\end{split}
Boundary condition (periodic, zeros at boundary or infinity, and so on)과 Integration by part를 이용, 더 정리해보면...
\begin{split}
\delta S \big( h(x) \big)
= &\int_{a}^{b} \bigg[\frac{\partial f} {\partial h (x)} \delta h (x) \bigg] dx \\
&+ \frac{\partial f} {\partial \dot{h}(x)} \delta h (x) \bigg|_{a}^{b}
- \int_{a}^{b} \bigg[\frac{d}{dx} \Big[\frac{\partial f} {\partial \dot{h} (x)} \Big] \delta h (x) \bigg] dx \\
&+ \frac{\partial f} {\partial \ddot{h}(x)} \delta \big( \dot{h} (x) \big) \bigg|_{a}^{b}
- \frac{d}{dx} \Big[ \frac{\partial f} {\partial \ddot{h} (x)} \Big] \delta h (x) \bigg|_{a}^{b}
+ \int_{a}^{b} \bigg[ \frac{d^2}{dx^2} \Big[\frac{\partial f} {\partial \ddot{h} (x)} \Big] \delta h (x) \bigg] dx \\
&+ \cdots
\end{split}
##[.hiden#sec-Complex] Method of Lagrange multipliers with complex variables
// 영어로 먼저 정리해놨던건데 한글로 다시 번역하기가 귀찮아서 -ㅇ-;; Complex를 쓰는 경우 이정도 영어는 능숙할거라 생각해서 따로 번역은 안하겠습니다.
### Complex variables and simple constraint
Let's consider the optimization problem minimizing (or maximizing) $f(\{z_k\})$ subject to $g(\{z_k\})=c$, where $f(\{z_k\})$ is real function, but composed of complex variables $z_k$'s. Expressing $z_k$'s with two real numbers
z_k = a_k + i b_k ,
$f$ can be expressed with these real numbers only
f(\{z_k\}) = f(\{a_k, b_k\}) .
At extreme (minimun, maximum or possibly saddle) points, arbitrary variations on $\{a_k, b_k\}$, but subject to the constraints $g(\{a_k, b_k\})=c$, does not change the value of function $f$.
\sum_k \bigg[ \frac{\partial f}{\partial a_k} (\delta a_k) + \frac{\partial f}{\partial b_k} (\delta b_k) \bigg] = 0
subject to (upper arbitrary variations of $\{a_k, b_k\}$ must satisfy this condition.)
\sum_k \bigg[ \frac{\partial g}{\partial a_k} (\delta a_k) + \frac{\partial g}{\partial b_k} (\delta b_k) \bigg] = 0 .
So picking up only one variable $a_i$ (or $b_i$) of which $\frac{\partial g}{\partial a_i} \neq 0$, we can make the other variations $\{(\delta a_k),(\delta b_k)\}$ be fully arbitrary and only $(\delta a_i)$ be deterministic or dependent on the others. Then introducing a real constant $\lambda$ which satisfies
\frac{\partial f}{\partial a_i} - \lambda \frac{\partial g}{\partial a_i} = 0 ,
let's make
\sum_{k}' \bigg[ \big( \frac{\partial f}{\partial a_k} - \lambda \frac{\partial g}{\partial a_k} \big) (\delta a_k) + \big( \frac{\partial f}{\partial b_k} - \lambda \frac{\partial g}{\partial b_k} \big) (\delta b_k) \bigg] = 0
for fully arbitrary $\{(\delta a_k),(\delta b_k)\}$'s except $(\delta a_i)$. ($\sum_{k}'$ means summation without $a_i$.)
Then
\frac{\partial f}{\partial a_k}
- \lambda \frac{\partial g}{\partial a_k} = 0
\qquad \textrm{and} \qquad
\frac{\partial f}{\partial b_k} - \lambda \frac{\partial g}{\partial b_k} = 0 .
So for all variables,
\frac{\partial f}{\partial a_k}
- \lambda \frac{\partial g}{\partial a_k} = 0
\qquad \textrm{and} \qquad
\frac{\partial f}{\partial b_k} - \lambda \frac{\partial g}{\partial b_k} = 0
should be satisfied at an extreme point.
Expressing $f(\{a_k, b_k\})$ as
f(\{a_k, b_k\}) = f(\{\frac{z_k+z_k^*}{2}, \frac{z_k-z_k^*}{2i}\}) ,
we can define
\frac{\partial f}{\partial z_k} = \frac{1}{2} \frac{\partial f}{\partial a_k} + \frac{1}{2i} \frac{\partial f}{\partial b_k} .
\qquad \textrm{and} \qquad
\frac{\partial f}{\partial z_k^*} = \frac{1}{2} \frac{\partial f}{\partial a_k} - \frac{1}{2i} \frac{\partial f}{\partial b_k}
As the function $f$ and constraint $g$ is always real and therefore the derivatives $\frac{\partial f}{\partial a_k}$ and $\frac{\partial f}{\partial b_k}$ are also real always, above two real equations can become one complex equation
\frac{\partial f}{\partial z_k^*} - \lambda \frac{\partial g}{\partial z_k^*}
= \frac{1}{2} \bigg( \frac{\partial f}{\partial a_k} - \lambda \frac{\partial g}{\partial a_k} \bigg)
- \frac{1}{2i} \bigg( \frac{\partial f}{\partial b_k} - \lambda \frac{\partial g}{\partial b_k} \bigg) = 0 .
Then the extreme points can be found with
\frac{\partial f}{\partial z_k^*}
= \lambda \frac{\partial g}{\partial z_k^*}.
### Functional variables and constraints with integration
When functional variables and integration come into this optimization problem, i.e. the problem is to minimize $S = \int dt \int d \vec{x} ~ f(\{z_k (\vec{x}, t)\})$ subject to multiple constraints (type1: $\int dt \int d \vec{x} ~ g_l(\{z_k (\vec{x},t)\}) =$ constant, type2: $\int d \vec{x} ~ g_l(\{z_k (\vec{x},t)\}) =$ constant), what changes? At this time also, $f$ can be expressed by two real variables.
f(\{z_k (\vec{x},t)\}) = f(\{a_k (\vec{x},t), b_k (\vec{x},t)\}) .
However distinct from discrete variables case, $f$ can contain derivative terms such as $\partial a_k / \partial t$, $\partial a_k / \partial x$, $\partial^2 b_k / \partial x \partial y$, $\partial^3 a_k / \partial z^3$ and so on.
Then arbitrary (but subject to constraints) variations on $\{a_k (\vec{x},t), b_k (\vec{x},t)\}$'s make
\begin{split}
\delta S = \int dt \int d \vec{x} ~ \sum_k \bigg[
&\frac{\partial f}{\partial a_k} \big(\delta a_k \big) + \frac{\partial f}{\partial b_k} \big(\delta b_k \big) \\
&+ \frac{\partial f}{\partial \big( d_x a_k \big)} d_x \big(\delta a_k \big) + \cdots \\
&+ \frac{\partial f} {\partial \big( d_x d_y a_k \big)} d_x d_y \big(\delta a_k \big) + \cdots \\
&+ \frac{\partial f} {\partial \big( d_z^3 a_k \big)} d_z^3 \big(\delta a_k \big) + \cdots \bigg] = 0 .
\end{split}
I expressed $\partial / \partial x$ by $d_x$ to discriminate two different kinds of derivatives ($\frac{\partial}{\partial x}$'s and $\frac{\partial}{\partial a_k (\vec{x},t)}$'s).
Then using integration by part and boundary conditions (periodic or zeros at infinite points),
\begin{split}
\delta S = \int d \vec{x} ~ \sum_k \Bigg[
&\frac{\partial f}{\partial a_k} \big(\delta a_k \big) + \frac{\partial f}{\partial b_k} \big(\delta b_k \big) \\
&- \frac{d}{d x} \Big( \frac{\partial f} {\partial \big( d_x a_k \big)} \Big) \big(\delta a_k \big) - \cdots \\
&+ \frac{d^2}{d x d y} \Big( \frac{\partial f} {\partial \big( d_x d_y a_k \big)} \Big) \big(\delta a_k \big) + \cdots \\
&- \frac{d^3}{d z^3} \Big( \frac{\partial f} {\partial \big( d_z^3 a_k \big)} \Big) \big( \delta a_k \big) - \cdots \Bigg] = 0 .
\end{split}
Since there are constraints on $\{a_k (\vec{x},t), b_k (\vec{x},t)\}$'s, they have to satisfy that
for type1 constraints
\int dt \int d \vec{x} ~ \sum_k \Bigg[ \frac{\partial g_l} {\partial a_k} \big(\delta a_k \big)
+ \frac{\partial g_l} {\partial b_k} \big(\delta b_k \big) \Bigg] = 0
(I supposed for the simplicity that the constraints $g_l$'s do not contain derivative terms.)
and for type2 constraints
\int d \vec{x} ~ \sum_k \Bigg[ \frac{\partial g_l} {\partial a_k} \big(\delta a_k \big)
+ \frac{\partial g_l} {\partial b_k} \big(\delta b_k \big) \Bigg] = 0 .
Then introducing arbitrary function $\lambda (t)$, even
\int d t ~\lambda (t) \int d \vec{x} ~
\sum_k \Bigg[ \frac{\partial g_l} {\partial a_k} \big(\delta a_k \big)
+ \frac{\partial g_l} {\partial b_k} \big(\delta b_k \big) \Bigg] = 0 .
Taking summation concept on integration, we can do similar procedure as before.
\begin{split}
&\int_{\vec{x}_p} d \vec{x} ~ \bigg[ \frac{\partial g_l} {\partial a_i} \big(\delta a_i \big) \bigg]
+ \int_{V - \vec{x}_p} d \vec{x} ~ \bigg[ \frac{\partial g_l} {\partial a_i} \big(\delta a_i \big) \bigg] \\
&+ \int d \vec{x} ~ \sum_{k}' \Bigg[ \frac{\partial g_l} {\partial a_k} \big(\delta a_k \big)
+ \frac{\partial g_l} {\partial b_k} \big(\delta b_k \big) \Bigg] = 0
\end{split}
where
\frac{\partial g_l} {\partial a_i (\vec{x},t)} \bigg|_{\vec{x}_p} \neq 0 .
(For multiple constraints, the matrix $\frac{\partial g_l}{\partial a_i}$ must be chosen to be invertible.)
Making only $\big(\delta a_i (\vec{x}_p,t)\big)$ be deterministic, we can make the others be fully arbitrary. Applying similar procedures, final results become
\begin{split}
&\frac{\partial f} {\partial a_k}
- \frac{d}{d x} \Big( \frac{\partial f} {\partial \big( d_x a_k \big)} \Big) - \cdots \\
&+ \frac{d^2}{d x d y} \Big( \frac{\partial f} {\partial \big( d_x d_y a_k \big)} \Big) + \cdots \\
&- \frac{d^3}{d z^3} \Big( \frac{\partial f} {\partial \big( d_z^3 a_k \big)} \Big) - \cdots \\
&~~~- \sum_{l \in \textrm{type1}} \lambda_l \frac{\partial g_l} {\partial a_k}
- \sum_{l \in \textrm{type2}} \lambda_l (t) \frac{\partial g_l} {\partial a_k} \\
&= 0 \quad \textrm{at every points.}
\end{split}
With the fact that
\frac{\partial f} {\partial z_k^*}
= \frac{1}{2} \frac{\partial f}{\partial a_k}
- \frac{1}{2i} \frac{\partial f}{\partial b_k} ,
\frac{\partial f}{\partial d_x z_k^*}
= \frac{1}{2} \frac{\partial f}{\partial d_x a_k}
- \frac{1}{2i} \frac{\partial f}{\partial d_x b_k} ,
$\cdots$, two real equations can become one complex equation
