[Math] Second Order Condition : Convexity

First order condition과 함께 convexity를 판정하는 조건.

 

Second Order Condition

Real Vector Space $\mathbb{R}^n$에서 $f:\mathbb{R}^n \to \mathbb{R}$이 second derivative 를 구할 수 있다면,

다음의 두 조건이 필요충분조건임.

1. $f$ 는 Convex Function임.
2. $\text{dom }f$는 Convex Set이고,
   이에 속하는 임의의 $\textbf{x} \in \text{dom }f$에 대해
   $\nabla^2 f(\textbf{x})$는 Positive Semi-Definite 임.
   ($\nabla^2 f(\textbf{x})$ 은 vector에 대한 vector의 미분이라 matrix임: Hessian)

$f$가 이차미분 가능하고 연속 함수인 경우, 이를 2차 미분한 것이 바로 Hessian에 해당한다.

---

스칼라 x와 벡터 x에 대한 함수 비교: Qaudratic Form

아래와 깉은 scalar $x$에서 convex, concave를 결정하는 것은 바로 이차항에 대한 계수 $a$임.

$$ax^2+bx +c = 0$$

위의 $ax^2$ 항에 해당하는 것이  vector $\textbf{x}$의 경우는 Quadratic Form임.

이는 다음과 같음.

$$\mathbf{x}^\top A \mathbf{x}$$

여기서 matrix $A$가 바로 Hessian에 해당하며 scalar의 경우의 $a$에 해당함.

---

Second Derivative: Hessian

scalar function에서 이차도함수(second derivative) $a$ 를 가지고 극대,극소 등을 판정하던 것 (아래 그림)처럼,

gradient가 $\textbf{0}$인 stationary point (or critical point)가

• 극대인지,
• 극소인지, 아니면
• saddle point인지를

Hessian $\nabla^2$ (위의 예에선 matrix $A$)으로 판정할 수 있다.

2023.07.10 - [.../Math] - [Math] Stationary point (or Critical point)

[Math] Stationary point (or Critical point)

 

Second Order Codnition은
$f$의 Hessian이 Positive Semi-definite Matrix일 때
$f$가 Convex Function이라는 정리임.

 

 

참고로, Hessian $\nabla^2 f$이

• positve definite matrix (모든 eigen value들이 양수)일 경우, 해당하는 critical point가 minimum ($f$ is convex),
  • $\textbf{x}^\top \nabla^2 f \textbf{x} > 0$
  • where, $\textbf{x} \ne \textbf{0}, \textbf{x} \in \mathbb{R}^n$.
• negative definite matrix (모든 eigne value들이 음수)일 경우,  해당하는 critical point가 maximum ($f$ is concave),
  • $\textbf{x}^\top \nabla^2 f \textbf{x} < 0 $
  • where, $\textbf{x} \ne \textbf{0}, \textbf{x} in \mathbb{R}^n$.
• Eigenvalue가 양수와 음수가 혼재된 경우, 해당하는 critical point가 saddle point임.

2022.06.05 - [Programming/DIP] - [Math] Hessian : Summary

[Math] Hessian : Summary

 

Second Order Condition은

• Hessian Matrix의 Eigenvalue들 중 음수가 없는 경우,
• 해당 function이 Convex라고 할 수 있음을 나타냄
• (convex 정의에 있는 등호가 있어서 positive semi-definite임.)

 

Optimization에서 대부분,
Stationary Point들을 구한 후
Hessian으로 Local Minimum인지 아닌지를 판별함.