일변수 함수의 최대, 최소 문제
다음과 같은 일변수 함수 f(x)에서 최대, 최소 값을 찾는 문제는 아래와 같이 해결 할 수 있다.
변수의 경계값에서 함수값을 구한다.
변수의 경계값 내부에 극소값/극대값를 찾는다.
구해진 경계값, 극소값, 극대값에서 최소값, 최대값을 선택한다.
아래 식에서 변수의 경계는 -1, 3이고, 그 때 함수값 f(-1)=3, f(2)=6 이고, 극소값은 f(0)=2 이다. 이중에서 최대인 f(2)=6 이 최대값, f(0)=2가 최소값이 된다.
f ( x ) = x 2 + 2 , − 1 ≤ x ≤ 3 f(x)=x^2+2, \ \ -1\leq x \leq 3 f ( x ) = x 2 + 2 , − 1 ≤ x ≤ 3
이변수 함수의 최대, 최소 문제
이변수 함수 f(x,y)의 최대값과 최소값을 구하는 방법도 일변수 함수의 최대, 최소값을 구하는 방식과 동일하다.
변수의 경계값에서 함수값을 구한다.
변수의 경계값 내부에 극소값/극대값를 찾는다.
구해진 경계값, 극소값, 극대값에서 최소값, 최대값을 선택한다.
x 2 + x y + y 2 = 1 x^2+xy+y^2=1 x 2 + x y + y 2 = 1 x 2 + y 2 x^2+y^2 x 2 + y 2 x 2 + y 2 x^2+y^2 x 2 + y 2 x 2 + x y + y 2 = 1 x^2+xy+y^2=1 x 2 + x y + y 2 = 1 x 2 + y 2 = r x^2+y^2=r x 2 + y 2 = r
다른 각도에서 생각해보면 A,B,C,D 지점에서는 두 함수가 접하기 때문에 공통 접선을 가지게 된다. 점 A에서 곡선 x 2 + x y + y 2 = 1 x^2+xy+y^2=1 x 2 + x y + y 2 = 1 l 1 l_1 l 1 x 2 + y 2 = r x^2+y^2=r x 2 + y 2 = r l 2 l_2 l 2
l 2 = λ l 1 l_2=\lambda l_1 l 2 = λ l 1 나머지 접점 B,C,D에서도 두 직선의 관계는 동일하다. 여기서 λ \lambda λ
f ( x , y ) = x 2 + x y + y 2 g ( x , y ) = x 2 + y 2 ∇ f ( x , y ) = λ ∇ g ( x , y ) f(x,y) = x^2+xy+y^2\\ g(x,y) = x^2+y^2 \\ \nabla f(x,y) = \lambda \nabla g(x,y) f ( x , y ) = x 2 + x y + y 2 g ( x , y ) = x 2 + y 2 ∇ f ( x , y ) = λ ∇ g ( x , y ) 따라서, 경계선 g(x,y)=k에서 f(x,y)=z 의 최대, 최속값을 찾기 위해서는 아래 연립방정식을 풀어서 나오는 x, y값을 구한 뒤 f(x,y)에 대입하면 된다.
∇ f ( x , y ) = λ ∇ g ( x , y ) g ( x , y ) = k \nabla f(x,y) = \lambda \nabla g(x,y) \\ g(x,y)=k ∇ f ( x , y ) = λ ∇ g ( x , y ) g ( x , y ) = k 이렇게 최대값, 최소값을 찾는 방법이 라그랑주 승수법이다.
라그랑주 승수법
위에서 살펴본 최대, 최소와 같은 최적점을 찾을때 사용하는 라그랑주 승수법은 등식 제한조건이 있는 최적점을 찾는 것이 아니라 최적점이 되는 조건을 찾는 방법이다. 핵심 아이디어는 "제약조건 g를 만족하는 f 최소값 또는 최대값은 f와 g가 접하는 지점에 존재 할 수도 있다"는 것이다.
집합 D = { ( x , y ) ∣ g ( x , y ) = k , k i s c o n s t a n t ) } D=\left\{(x,y)|g(x,y)=k,k \ is \ constant)\right\} D = { ( x , y ) ∣ g ( x , y ) = k , k i s c o n s t a n t ) } ( x 0 , y 0 ) (x_0,y_0) ( x 0 , y 0 ) ( x 0 , y 0 ) (x_0,y_0) ( x 0 , y 0 ) λ \lambda λ
∇ f ( x 0 , y 0 ) = λ ∇ g ( x 0 , y 0 ) ∇ g ( x 0 , y 0 ) ≠ 0 ⃗ \nabla f(x_0,y_0) = \lambda \nabla g(x_0,y_0) \\ \nabla g(x_0,y_0) \neq \vec{0} ∇ f ( x 0 , y 0 ) = λ ∇ g ( x 0 , y 0 ) ∇ g ( x 0 , y 0 ) = 0 ∇ g ( x 0 , y 0 ) ≠ 0 ⃗ \nabla g(x_0,y_0) \neq \vec{0} ∇ g ( x 0 , y 0 ) = 0
집합 D = ( x , y , z ) ∣ g ( x , y , z ) = k , h ( x , y , z ) = c , k , c i s c o n s t a n t ) D={(x,y,z)|g(x,y,z)=k,\ h(x,y,z)=c,\ k,c \ is \ constant)} D = ( x , y , z ) ∣ g ( x , y , z ) = k , h ( x , y , z ) = c , k , c i s c o n s t a n t ) ( x 0 , y 0 , z 0 ) (x_0,y_0,z_0) ( x 0 , y 0 , z 0 ) λ , μ \lambda, \mu λ , μ
∇ f ( x 0 , y 0 , z 0 ) = λ ∇ g ( x 0 , y 0 , z 0 ) + μ ∇ h ( x 0 , y 0 , z 0 ) ∇ g ( x 0 , y 0 , z 0 ) ≠ 0 ⃗ , ∇ h ( x 0 , y 0 , z 0 ) ≠ 0 ⃗ \nabla f(x_0,y_0,z_0) = \lambda \nabla g(x_0,y_0,z_0) +\mu \nabla h(x_0,y_0,z_0)\\ \nabla g(x_0,y_0,z_0) \neq \vec{0}, \ \nabla h(x_0,y_0,z_0) \neq \vec{0} ∇ f ( x 0 , y 0 , z 0 ) = λ ∇ g ( x 0 , y 0 , z 0 ) + μ ∇ h ( x 0 , y 0 , z 0 ) ∇ g ( x 0 , y 0 , z 0 ) = 0 , ∇ h ( x 0 , y 0 , z 0 ) = 0 예제
문제)
x 2 8 + y 2 2 = 1 \frac{x^2}{8}+\frac{y^2}{2}=1 8 x 2 + 2 y 2 = 1 f ( x , y ) = x y f(x,y)=xy f ( x , y ) = x y
풀이)
x 2 8 + y 2 2 = 1 \frac{x^2}{8}+\frac{y^2}{2}=1 8 x 2 + 2 y 2 = 1 g ( x , y ) = 1 − x 2 8 − y 2 2 g(x,y)=1-\frac{x^2}{8}-\frac{y^2}{2} g ( x , y ) = 1 − 8 x 2 − 2 y 2
L = f ( x , y ) + λ g ( x , y ) = x y + λ ( 1 − x 2 8 − y 2 2 ) L=f(x,y)+\lambda g(x,y) \\ =xy+\lambda(1-\frac{x^2}{8}-\frac{y^2}{2}) L = f ( x , y ) + λ g ( x , y ) = x y + λ ( 1 − 8 x 2 − 2 y 2 )
x에 대한 편미분이 0인 식을 구하고
∂ L ∂ x = ∂ f ( x , y ) ∂ x + λ ∂ g ( x , y ) ∂ x = y − λ 4 x = 0 y = λ 4 x \frac{\partial L}{\partial x}=\frac{\partial f(x,y)}{\partial x}+\lambda \frac{\partial g(x,y)}{\partial x} \\ =y-\frac{\lambda}{4}x=0 \\ y= \frac{\lambda}{4}x ∂ x ∂ L = ∂ x ∂ f ( x , y ) + λ ∂ x ∂ g ( x , y ) = y − 4 λ x = 0 y = 4 λ x
y에 대한 편미분이 0인 식을 구하고
∂ L ∂ y = ∂ f ( x , y ) ∂ y + λ ∂ g ( x , y ) ∂ y = x − λ y = 0 x = λ y \frac{\partial L}{\partial y}=\frac{\partial f(x,y)}{\partial y}+\lambda \frac{\partial g(x,y)}{\partial y} \\ =x-\lambda y=0 \\ x= \lambda y ∂ y ∂ L = ∂ y ∂ f ( x , y ) + λ ∂ y ∂ g ( x , y ) = x − λ y = 0 x = λ y
λ \lambda λ ∂ L ∂ λ = g ( x , y ) = 0 = 1 − x 2 8 − y 2 2 = 0 \frac{\partial L}{\partial \lambda}=g(x,y)=0 \\ =1-\frac{x^2}{8}-\frac{y^2}{2}=0 ∂ λ ∂ L = g ( x , y ) = 0 = 1 − 8 x 2 − 2 y 2 = 0
세 식을 연립방정식을 풀면 임계점을 구 할 수 있다.
y − λ 4 x = 0 x − λ y = 0 ∴ x = y = 0 , o r λ = ± 2 y-\frac{\lambda}{4}x=0 \\ x-\lambda y=0\\ \therefore x=y=0, or \ \lambda=\pm2 y − 4 λ x = 0 x − λ y = 0 ∴ x = y = 0 , o r λ = ± 2 따라서, 임계점은 (x,y)=(0,0)과 λ = ± 2 \lambda=\pm2 λ = ± 2 x = λ y x=\lambda y x = λ y
1) λ = 2 \lambda=2 λ = 2
x = 2 y 1 − ( 2 y ) 2 8 − y 2 2 = 1 − y 2 = 0 ∴ x = ± 2 , y = ± 1 ( x , y ) = ( ± 2 , ± 1 ) x=2y \\ 1-\frac{(2y)^2}{8}-\frac{y^2}{2}=1-y^2=0\\ \therefore x=\pm 2, y=\pm 1\\ (x,y)=(\pm 2, \pm 1) x = 2 y 1 − 8 ( 2 y ) 2 − 2 y 2 = 1 − y 2 = 0 ∴ x = ± 2 , y = ± 1 ( x , y ) = ( ± 2 , ± 1 ) 2) λ = − 2 \lambda=-2 λ = − 2
x = − 2 y 1 − ( − 2 y ) 2 8 − y 2 2 = 1 − y 2 = 0 ∴ x = ± 2 , y = ∓ 1 ( x , y ) = ( ± 2 , ∓ 1 ) x=-2y \\ 1-\frac{(-2y)^2}{8}-\frac{y^2}{2}=1-y^2=0\\ \therefore x=\pm 2, y=\mp 1\\ (x,y)=(\pm 2, \mp 1) x = − 2 y 1 − 8 ( − 2 y ) 2 − 2 y 2 = 1 − y 2 = 0 ∴ x = ± 2 , y = ∓ 1 ( x , y ) = ( ± 2 , ∓ 1 )
( x , y ) = ( 0 , 0 ) (x,y)=(0,0) ( x , y ) = ( 0 , 0 ) g ( x , y ) − c = 0 g(x,y)-c=0 g ( x , y ) − c = 0
1 − 0 8 − 0 2 ≠ 0 1-\frac{0}{8}-\frac{0}{2} \neq 0 1 − 8 0 − 2 0 = 0 따라서, 임계후보는 4 점 { ( 2 , 1 ) , ( 2 , − 1 ) , ( − 2 , 1 ) , ( − 2 , − 1 ) } \left \{(2,1), (2,-1), (-2,1), (-2,-1)\right \} { ( 2 , 1 ) , ( 2 , − 1 ) , ( − 2 , 1 ) , ( − 2 , − 1 ) } f ( x , y ) f(x,y) f ( x , y )
f ( 2 , 1 ) = 2 f ( 2 , − 1 ) = − 2 f ( − 2 , 1 ) = − 2 f ( − 2 , − 1 ) = 2 ∴ max f ( x , y ) = 2 , min f ( x , y ) = − 2 f(2,1)=2 \\ f(2,-1)=-2 \\ f(-2,1)=-2 \\ f(-2,-1)=2 \\ \therefore \max f(x,y)=2, \ \min f(x,y)=-2 f ( 2 , 1 ) = 2 f ( 2 , − 1 ) = − 2 f ( − 2 , 1 ) = − 2 f ( − 2 , − 1 ) = 2 ∴ max f ( x , y ) = 2 , min f ( x , y ) = − 2 따라서, g ( x , y ) g(x,y) g ( x , y ) f ( x , y ) f(x,y) f ( x , y )
그래프에서 살펴보면 g ( x , y ) g(x,y) g ( x , y ) f ( x , y ) f(x,y) f ( x , y ) x x x
f ( x , y ) f(x,y) f ( x , y ) g ( x , y ) g(x,y) g ( x , y )
확장된 최적화 문제
위의 내용을 입력이 N차원이고, 제약조건이 M개에 대한 최적화 문제로 확장하면 다음과 같이 정리된다. 입력변수가 x ∈ R N \mathbf x\in \mathbb{R}^N x ∈ R N
L ( x , λ ) = f ( x ) + ∑ j = 1 M λ j g j ( x ) L(\mathbf {x}, \mathbf \lambda) = f(\mathbf{x})+\sum_{j=1}^M \lambda_j g_j(\mathbf{x}) L ( x , λ ) = f ( x ) + j = 1 ∑ M λ j g j ( x ) 그레이언트 벡터를 영벡터로 만드는 최적화 필요 조건이 N + M N+M N + M
∂ L ∂ x 1 = ∂ f ∂ x 1 + ∑ j = 1 M λ j ∂ g j ∂ x 1 = 0 ∂ L ∂ x 2 = ∂ f ∂ x 2 + ∑ j = 1 M λ j ∂ g j ∂ x 2 = 0 ⋮ ∂ L ∂ x N = ∂ f ∂ x N + ∑ j = 1 M λ j ∂ g j ∂ x N = 0 ∂ L ∂ λ 1 = g 1 = 0 ⋮ ∂ L ∂ λ M = g M = 0 \frac{\partial L}{\partial x_1} = \frac{\partial f}{\partial x_1} + \sum_{j=1}^M \lambda_j\frac{\partial g_j}{\partial x_1} = 0 \\ \frac{\partial L}{\partial x_2} = \frac{\partial f}{\partial x_2} + \sum_{j=1}^M \lambda_j\dfrac{\partial g_j}{\partial x_2} = 0 \\ \vdots \\ \frac{\partial L}{\partial x_N} = \frac{\partial f}{\partial x_N} + \sum_{j=1}^M \lambda_j\dfrac{\partial g_j}{\partial x_N} = 0 \\ \frac{\partial L}{\partial \lambda_1} = g_1 = 0 \\ \vdots \\ \frac{\partial L}{\partial \lambda_M} = g_M = 0 ∂ x 1 ∂ L = ∂ x 1 ∂ f + j = 1 ∑ M λ j ∂ x 1 ∂ g j = 0 ∂ x 2 ∂ L = ∂ x 2 ∂ f + j = 1 ∑ M λ j ∂ x 2 ∂ g j = 0 ⋮ ∂ x N ∂ L = ∂ x N ∂ f + j = 1 ∑ M λ j ∂ x N ∂ g j = 0 ∂ λ 1 ∂ L = g 1 = 0 ⋮ ∂ λ M ∂ L = g M = 0 따라서, N+M 연립방정식을 풀면 x 1 , x 2 , x 3 , . . . , x n , λ 1 , λ 2 , . . . , λ N x_1, x_2, x_3,...,x_n, \lambda_1,\lambda_2,...,\lambda_N x 1 , x 2 , x 3 , . . . , x n , λ 1 , λ 2 , . . . , λ N x 1 , x 2 , x 3 , . . . , x n x_1, x_2, x_3,...,x_n x 1 , x 2 , x 3 , . . . , x n
부등식 제한조건이 있는 최적화 문제
라그랑주 승수법은 등식 제한조건이 있는 최적화 문제에 적용할 수 있다. 이번에는 부등식 제한조건이 있는 최적화를 살펴보자
x ∗ = arg min x f ( x ) s . t . { g j ( x ) = 0 ( j = 1 , … , N ) , h k ( x ) ≤ 0 ( j = 1 , … , M ) \mathbf x^{\ast} = \text{arg} \min_\mathbf{x} f(\mathbf{x}) \\ s.t. \; \begin{cases} g_j(\mathbf {x}) = 0 \;\; (j=1, \ldots, N),\\ h_k(\mathbf {x}) \leq 0 \;\; (j=1, \ldots, M) \end{cases} x ∗ = arg x min f ( x ) s . t . { g j ( x ) = 0 ( j = 1 , … , N ) , h k ( x ) ≤ 0 ( j = 1 , … , M ) 부등식 제한조건이 있는 최적화 문제도 라그랑주 승수법을 적용한 목적함수을 적용할 수 있다.
a r g min x , λ , μ L ( x , λ , μ ) L ( x , λ , μ ) = f ( x ) + ∑ j = 1 N λ j g j ( x ) + ∑ k = 1 M μ k h k ( x ) arg \min_{\mathbf x, \lambda, \mu}L(\mathbf {x}, \mathbf \lambda, \mathbf \mu) \\ L(\mathbf {x}, \mathbf \lambda, \mathbf \mu) = f(\mathbf{x}) + \sum_{j=1}^N \lambda_j g_j(\mathbf{x}) + \sum_{k=1}^M \mu_k h_k(\mathbf{x}) a r g x , λ , μ min L ( x , λ , μ ) L ( x , λ , μ ) = f ( x ) + j = 1 ∑ N λ j g j ( x ) + k = 1 ∑ M μ k h k ( x ) 이 경우는 KKT(Karush-Kuhn-Tucker) 조건이라하며 4개의 조건으로 구성된다. KKT 조건은 최소점을 찾는데 필요한 1차 충분조건 (First Order Sufficient Condition)이다.
모든 입력변수(독립변수)에 대한 편미분값이 0 이다.
∂ L ( x , λ , μ ) ∂ x i = 0 , i = 1 , 2 , 3 , . . . , N \frac{\partial L(\mathbf{x}, \mathbf{\lambda}, \mathbf{\mu})}{\partial x_i} = 0, \; \; i=1,2,3,...,N ∂ x i ∂ L ( x , λ , μ ) = 0 , i = 1 , 2 , 3 , . . . , N
주어진 문제 f ( x ) f(\mathbf x) f ( x )
g j ( x ) = 0 ( j = 1 , … , N ) , h k ( x ) ≤ 0 ( j = 1 , … , M ) g_j(\mathbf {x}) = 0 \;\; (j=1, \ldots, N),\\ h_k(\mathbf {x}) \leq 0 \;\; (j=1, \ldots, M) g j ( x ) = 0 ( j = 1 , … , N ) , h k ( x ) ≤ 0 ( j = 1 , … , M )
부등식 라그랑주 승수는 음수가 아니어야 하고, 등식 라그랑주 승수는 0이 아니여야 한다.
λ j ≠ 0 j = 1 , 2 , 3 , . . . , N μ k ≥ 0 , j = 1 , 2 , 3 , . . . , M \lambda_j \neq 0 \; j=1,2,3,...,N \\ \mu_k \geq 0, \; j=1,2,3,...,M λ j = 0 j = 1 , 2 , 3 , . . . , N μ k ≥ 0 , j = 1 , 2 , 3 , . . . , M
부등식 라그랑주 승수와 제한조건의 곱은 0이다.
∑ k M μ j h k ( x ) = 0 , j = 1 , 2 , 3 , . . . , M \sum_k^M\mu_j h_k(\mathbf x) = 0 , \; \; j=1,2,3,...,M k ∑ M μ j h k ( x ) = 0 , j = 1 , 2 , 3 , . . . , M 벡터표현
이것의 벡터 형식은 아래와 같다.
x ∗ = arg min x , λ , μ L ( x , λ , μ ) L ( x , λ , μ ) = f ( x ) + λ T g ( x ) + μ T h ( x ) \mathbf x^{\ast} =\text{arg} \min_{\mathbf x, \lambda, \mu} L(\mathbf {x}, \mathbf \lambda, \mathbf \mu) \\L(\mathbf {x}, \mathbf \lambda, \mathbf \mu) = f(\mathbf x)+\mathbf \lambda^T g(\mathbf x)+\mathbf \mu^T h(\mathbf x) x ∗ = arg x , λ , μ min L ( x , λ , μ ) L ( x , λ , μ ) = f ( x ) + λ T g ( x ) + μ T h ( x )
∇ x L ( x , λ , μ ) = 0 \nabla_\mathbf x L(\mathbf x, \lambda, \mu)= \mathbf 0 ∇ x L ( x , λ , μ ) = 0 g ( x ) = 0 , h ( x ) ≤ 0 g(\mathbf x) = \mathbf 0, \; h(\mathbf x) \leq \mathbf 0 g ( x ) = 0 , h ( x ) ≤ 0 λ ≠ 0 , μ ≥ 0 \mathbf \lambda \neq \mathbf 0, \;\mathbf \mu \geq \mathbf 0 λ = 0 , μ ≥ 0 μ T h ( x ) = 0 \mathbf \mu^T h(\mathbf x)=\mathbf 0 μ T h ( x ) = 0
첫번째 조건을 다시 표현하면 아래와 같고,
∇ x [ f ( x ) + λ T g ( x ) + μ T h ( x ) ] = 0 ∇ x f ( x ) = − λ T ∇ x g ( x ) − μ T ∇ x h ( x ) \nabla_\mathbf x \left [f(\mathbf x)+\mathbf \lambda^T g(\mathbf x)+\mathbf \mu^T h(\mathbf x)\right]=\mathbf 0\\ \nabla_\mathbf x f(\mathbf x)=-\mathbf \lambda^T \nabla_\mathbf x g(\mathbf x) - \mathbf \mu^T \nabla_\mathbf x h(\mathbf x) ∇ x [ f ( x ) + λ T g ( x ) + μ T h ( x ) ] = 0 ∇ x f ( x ) = − λ T ∇ x g ( x ) − μ T ∇ x h ( x ) 이 식의 기하학적 의미는 f ( x ) f(\mathbf x) f ( x ) g ( x ) g(\mathbf x) g ( x ) h ( x ) h(\mathbf x) h ( x ) f ( x ) f(\mathbf x) f ( x ) g ( x ) g(\mathbf x) g ( x ) h ( x ) h(\mathbf x) h ( x ) f ( x ) f(\mathbf x) f ( x ) λ , μ \lambda, \mu λ , μ
SOSC(Second Order Sufficient Condition) 체크
H L ( x , λ , μ ) > 0 H_{L(\mathbf x, \lambda, \mu)}>\mathbf 0 H L ( x , λ , μ ) > 0
∂ g ( x ) ∂ x ∂ x ∗ = 0 \frac{\partial g(\mathbf x)}{\partial \mathbf x} \partial \mathbf x^*=0 ∂ x ∂ g ( x ) ∂ x ∗ = 0
∂ h ( x ) ∂ x ∂ x ∗ = 0 \frac{\partial h(\mathbf x)}{\partial \mathbf x} \partial \mathbf x^*=0 ∂ x ∂ h ( x ) ∂ x ∗ = 0
첫번째 조건은 헤시안이 양수라는 것은 양정수 벡터라는 것이다.
