Stationary point (or Critical point, 정류점)
$\nabla f(x)=\mathbf{0}$ 가 성립하는 지점을 stationary point라고 부르며, solution이 될 수 있는 candidate임.
(Convex) Opimization에서 찾고자하는 solution은 objective function에 대한 local minimum이다.
- 이를 곧바로 찾기는 쉽지 않기 때문에, solution이 될 수 있는 candidates(후보점들)를 먼저 gradient (or 1st order derivative)를 이용하여 찾아낸다.
- Convex optimization에서 solution에서 objective function의 gradient $\nabla f$는 반드시 $\textbf{0}$여야 한다
(역은 항상 true라고 보장 못함. 즉 necessary condition).
Convex optimization 문제에서는 모든 local minimum이 global minimum이므로,
단순히 local minimum을 찾는 조건만으로도 global minimum을 찾는 것과 같음.
정의
$\nabla f(\textbf{x}^*)=0$ 를 만족하는 $\textbf{x}^*$를 가르켜 stationary point 또는 critical point라고 부른다.
보다 엄밀하게는 미분가능하지 않은 점도 stationary point에 속한다.
일부 문헌에서는 non-differentiabl point 로 구분하여 다루기도 하지만, 엄밀히는 다음이 성립:
- critical point = stationary point + nondifferentiable minimum candidate
다음을 통해 solution을 구할 수 있다. (물론 objectvie funtion이 2차미분가능하고 continuous여야만 가능한 일임.)
- constraints를 만족하는 feasible set에서
- gradient를 통해 stationary points를 찾고,
- 이를 한번 더 미분한 Hessian matrix를 구해 해당 stationary point가 local minimum인지를 판별
참고: continuous and smooth function의 중요성
[Math] Importance of Continuous and Smooth Functions in Optimization Problems
Continuous and Smooth FunctionOptimization에서 objective function과 constraint functions은 일반적으로 continuous 이면서smooth function (= 무한차수의 derivative를 구할 수 있는 function)임.Optimization이 statonarity 와 gradient
dsaint31.tistory.com
참고: 최대인지 최소인지, saddle point인지 확인을 위한 second order condtion for convexity
2023.07.10 - [.../Math] - [Math] Second Order Condition : Convexity
[Math] Second Order Condition : Convexity
First order condition과 함께 convexity를 판정하는 조건. Real vector space $\mathbb{R}^n$에서 $f:\mathbb{R}^n \to \mathbb{R}$이 second derivative 를 구할 수 있다면, 다음의 두 조건이 필요충분조건임. $f$ 는 convex function
dsaint31.tistory.com
더 읽어보면 좋은 URL
2023.07.07 - [.../Math] - [Math] A regular point of the feasible set.
[Math] A regular point of the feasible set.
Consider the constrained optimization problem of minimizing $f(\textbf{x})$ subject to the constraints $h_i(\textbf{x})=0, i=1 \text { to } p$. A point $\textbf{x}^*$ satisfying the constraints is said to be a regular point of the feasible set if $f(\textb
dsaint31.tistory.com
2022.06.05 - [Programming/DIP] - [Math] Hessian : Summary
[Math] Hessian : Summary
이 문서는 Numeartor Layout Convention 을 사용함. Hessian : Summary 2nd order derivative of multivariate functoin. 여기서 multivariate function은 입력은 vector, 출력은 scalar Hessian matrix는 다음과 같음. $$\begin{aligned}H[f](\textb
dsaint31.tistory.com
'... > Math' 카테고리의 다른 글
| [ML] Cosine Similarity (0) | 2023.07.23 |
|---|---|
| [Math] Sequence (수열) and Series (급수) (1) | 2023.07.21 |
| [Math] Second Order Condition : Convexity (0) | 2023.07.10 |
| [Math] First Order Condition : Convexity (0) | 2023.07.10 |
| [Math] Linear Programming and Quadratic Programming (0) | 2023.07.08 |