Finding Extrema

1. Extrema 의 존재성 확인

가장 먼저 extrema가 존재하는지 확인을 해야 한다.

 

compact domain $D$에서 정의된 $C^1$ 함수 $f : D \to \mathbb{R}$ 가 주어졌다고 하자.

 

Extreme value theorem에 의해 extrema 존재한다.

 

global extremum points 후보 = ($D$ 내부의 critical points) + ($\partial D$ 의 critical points)

 

2. $D$ 내부에서 후보 찾기

Thm 1

Let $f \in C^1$.

 

$\mathbf{x_0}$ : Local extremum point $\Rightarrow$  $\nabla f(\mathbf{x_0}) = \mathbf{0}$

 

 

Thm 1을 이용해 local extremum point가 아닌 점들을 1차로 걸러낼 수 있다.

 

 

Second partial derivative test

Let $f \in C^2 \ $ and $\ \nabla f(\mathbf{x_0}) = \mathbf{0}$.  
Let $H$ be the Hessian of $f$ at $\mathbf{x_0}$. 

① $H$ : positive definite $\ \Rightarrow \ $ $f$ attains local minimum at $\mathbf{x_0}$.
② $H$ : negative definite $\ \Rightarrow \ $ $f$ attains local maximum at $\mathbf{x_0}$.
③ $H$ : indefinite $\ \Rightarrow \ $ $\mathbf{x_0}$ is a saddle point of $f$.

 

 

$f(\mathbf{x}) \approx f(\mathbf{x_0}) + \nabla f(\mathbf{x_0}) ^T (\mathbf{x-x_0}) + \frac{1}{2} (\mathbf{x-x_0})^T H (\mathbf{x-x_0})\ $ 를 생각해보면 명백하다.

 

 

Second partial derivative test for 2 variable functions

Let $f \in C^2 \ $ and $\ \nabla f(x_0, y_0) = \mathbf{0}$. 
Let $H$ be the Hessian of $f$ at $(x_0, y_0)$. 

① $det(H) > 0 \ $ and $\ f_{xx} > 0$ $\ \Rightarrow \ $ $f$ attains local minimum at $(x_0, y_0)$.
② $det(H) > 0 \ $ and $\ f_{xx} < 0$ $\ \Rightarrow \ $ $f$ attains local maximum at $(x_0, y_0)$.
③ $det(H) < 0 \ $ and $\ f_{xx} > 0$ $\ \Rightarrow \ $ $(x_0, y_0)$ is a saddle point of $f$.

 

 

필요하다면 second partial derivative test를 이용해 Thm 1 을 통과한 점들 중 local extremum point가 아닌 점들을 2차로 걸러낼 수 있다.

물론 이 시점에서도 $D$ 내부에 걸러지지 않은 saddle point가 존재할 수 있다.

3. $\partial D$ 에서 후보 찾기

Lagrange multiplier theorem

Suppose $f, g \in C^1\ $, $\ \nabla g(\mathbf{x_0}) \neq \mathbf{0}\ $ and $\ f$ attains local extremum subject to $g(\mathbf{x}) = 0\ $ at $\ \mathbf{x_0}$.

 

Then, $\exists \lambda \ $ such that $\ \nabla (f + \lambda g) (\mathbf{x_0}) = \mathbf{0}$.

 

 

Lagrange multiplier theorem 을 이용해 $\partial D$ 내부에서 local extremum point가 아닌 점들을 걸러낼 수 있다.

 

만약 $\partial D$ 에 대한 boundary가 또 존재한다면 그 부분에 대해서도 따로 생각을 해줘야 한다.

 

Note

Lagrange multiplier theorem은 이렇게 이해하면 쉽다.

 

특별히 three variable case 를 생각하자.

constrained $f$가 local maximum을 갖는다고 해보자.

 

$f(x, y, z) = C$, $\quad g(x, y, z) = 0\quad$ 둘 다 level surface이다.

 

WLOG, $f(x, y, z) = C$ 를 큰 풍선, $\ g(x, y, z) = 0$ 를 큰 풍선 안에 있는 작은 풍선이라고 생각하자.

$C$ 값을 조절해 큰 풍선의 부피를 점점 줄여나갈 수 있다. 

 

큰 풍선의 부피를 줄여나가다 보면 어느 순간 작은 풍선 $g(x, y, z) = 0$ 에 접촉하게 되고, 이 때 $f$는 constrained local maximum 을 갖는다.

 

한편, 접촉점에서 두 평면 $f(x, y, z) = C \ $ 과 $\ g(x, y, z) = 0$ 이 접하게 되므로 $f$ 와 $g$ 의 gradient는 평행하게 된다 (gradient는 level surface에 수직이다).

Note

예를 들어 $\partial D$ 가 삼각형 모양인 경우, 삼각형을 구성하는 각 직선에 대해 Lagrange를 한 뒤 $\partial \partial D$ 인 vertices 도 고려해줘야 한다.

 

 

 

Lagrange multiplier theorem with multiple constraints

Suppose $f, g_1, g_2, ..., g_m \in C^1\ $, $\ g_1, g_2, ..., g_m\ $ are linearly independent and $\ f$ attains local extremum subject to $g_i(\mathbf{x}) = 0\ \forall i$ at $\ \mathbf{x_0}$.

 

Then, $\exists \lambda_1, \lambda_2, ..., \lambda_m \ $ such that $\ \nabla (f + \lambda_1 g_1 + \lambda_2 g_2 + ... + \lambda_m g_m) (\mathbf{x_0}) = \mathbf{0}$.

 

 

Note

Lagrange multiplier theorem with multiple constraints는 이렇게 이해할 수 있다.

 

 

우리가 level set $g_i(\mathbf{x}) = \mathbf{0}$ 을 따라서 걷는다고 해보자.

 

각 점은 allowable direction의 공간을 가질 것이다.

 

즉, 각 점은 $\nabla g_i$에 수직한 방향들의 공간을 가질 것이다.

 

 

이제 각 점에 대해 모든 constraints에 대한 allowable directio 의 공간 A를 생각한다.

 

$S = span\{\nabla g_1, \nabla g_2, ..., \nabla g_m\}$ 라고 정의할 때 $\ A = S^\perp$ 가 된다.

 

 

우리는 모든 level set의 교집합을 걸어가다가 순간적으로 모든 allowable direction에 대해 $f$ 가 변하지 않는 점을 지나게 된다.

 

특히 constrained local extremum point가 그렇다. 

 

 

 

그리고 이 점에서 모든 allowable direction이 $\nabla f$ 에 수직하게 된다.

 

따라서, $\nabla f \in A^\perp = S$.

 

 

$\boldsymbol{\therefore}$ $\boldsymbol{f}\ $ is a linear combination of $\boldsymbol{g_1, g_2, ..., g_m}$