[Math] Second Order Condition : Convexity

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

 

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임.)

 

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

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

gradient가 $\textbf{0}$인 stationary point (or critical point)가 극대인지, 극소인지, 아니면 saddle point인지를 Hessian으로 판정할 수 있다.

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이

• positve definite matrix (모든 eigen value들이 양수)일 경우, 해당하는 critical point가 maximum ($f$ is convex),
• negative definite matrix (모든 eigne value들이 음수)일 경우,  해당하는 critical point가 minimum ($f$ is concave),
• eigen value가 양수와 음수가 혼재된 경우, 해당하는 critical point가 saddle point임.

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

[Math] Hessian : Summary

 

Second order condition은 Hessian matrix의 eigen value들 중 음수가 없는 경우, 해당 function이 convex라고 할 수 있음을 나타냄 (convex정의에 있는 등호가 있어서 positive semi-definite임.)

 

Optimization에서 대부분, stationary point들을 구한 후 hessian으로 local minimum인지 아닌지를 판별함.