Optimization

[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임. $\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$가 이차미분 가능하고 연속 함수인 ..

[Math] Linear Programming and Quadratic Programming

우리나라 말로 번역하면, 선형계획법 또는 이차계획법인 걸로 알고 있다. 약어로 LP, QP로 자주 사용한다. 참고로 Programming이라고 이름이 붙어있지만 이는 computer programming과는 상관이 없고, optimization problem(최적화 문제)를 가르키는 용어이다. 컴퓨터 프로그래밍이 이렇게 널리 사용되기 이전부터 사용되던 용어라고 하는데 programming이라는 의미가 사실 잘 안 와닿는 프로그래머라... ==;; 최적화에선 programming을 problem 또는 optimization problem으로 바꿔 읽으면 된다. optimization problem은 object function과 constraints들로 정의가 되기 때문에, optimization prob..

[Math] Slater's Condition

Slater's condition은 Strong Duality의 Sufficient Condition으로 유명하고, 동시에, Slater's condition을 만족하는 경우에는 KKT가 necessary condition이 되기 위해 선행적으로 요구되는 Regularity Condtion이 성립된다는 성질을 가지고 있는 조건임. Slater's condition은 convex optimization인 경우에만 성립되는 조건인데, KKT conditions가 convex optimization에서는 necessary sufficient condition이 되기 때문에, 결국 Slater's condition을 만족할 경우, KKT conditions를 통해 optimal solution을 찾을 수 있게 ..

[Math] Karush-Kuhn-Tucker Conditions (KKT Conditions)

KKT Conditions KKT조건은 inequality constraints을 가지는 contrained optimization problem의 optimal solution이 만족해야하는 necessary condition들의 집합(4개의 necessary condition)임. Lagransian multiplier를 도입하여 equality constraints를 가지는 contrained optimization problem을 unconstrained optimization으로 바꾸어 푸는 방식 에서의 necessary condition을 inequality contraints를 가지는 경우로 확장 한 것임. necessary condition 이기 때문에, KKT 조건을 만족한다고 반드시 o..

[ML] Newton-Raphson Method

$f(x)=0$을 만족하는 root(근), $\hat{x}$를 찾는 방법 중 하나 : root-finding algorithm 위의 그림에서 보이듯이 1st order derivative(1차 도함수)를 이용하여 현재의 $x_t$로부터 $x_{t+1}$을 구해낸다. 이를 수식으로 표현하면 다음과 같다. $$\begin{aligned}f^\prime(x_t)&=\dfrac{f(x_{t+1})-f(x_t)}{x_{t+1}-x_t}\\x_{t+1}-x_t&=\dfrac{f(x_{t+1})-f(x_t)}{f^\prime(x_t)}\\x_{t+1}&=x_t+\dfrac{f(x_{t+1})-f(x_t)}{f^\prime(x_t)}\\&=x_t+\dfrac{0-f(x_t)}{f^\prime(x_t)}\\&=x_t-\..

[Math] Hessian : Summary

이 문서는 Numeartor Layout Convention 을 사용함. Hessian : Summary 2nd order derivative of multivariate functoin. 여기서 multivariate function은 입력은 vector, 출력은 scalar Hessian matrix는 다음과 같음. $$\begin{aligned}H[f](\textbf{x})=H(\textbf{x})&=\left(J\left[\nabla f(\textbf{x})\right]\right)^T\\ &= \begin{bmatrix}\dfrac{\partial^2 f}{\partial x_1^2} (\textbf{x})& \dfrac{\partial^2 f}{\partial {x_1} \partial{x_2..