Optimization

[CV] Camera Model Parameter Estimation: $\underset{\textbf{x}}{\text{argmin }} \mathbf{x}^T A^T A \mathbf{x}$

Camera Model Parameter Estimation: $\underset{\textbf{x}}{\text{argmin }} \mathbf{x}^T A^T A \mathbf{x}$Camera Model Parameter Estimation 문제를$$\underset{\mathbf{x}}{\text{argmin }} \mathbf{x}^T A^T A \mathbf{x} \\  \text{subject to } \ ||\mathbf{x}||=1$$constrained optimization problem로 유도하는 과정을 설명함.Camera Model Parameter Estimation의 기본 배경Camera Model Matrix $P$는world space, 3D 공간의 점 $(x, y, z)^..

[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

Linear Programming and Quadratic Programming우리나라 말로 번역하면, 선형계획법 또는 이차계획법 으로 불림.약어로 LP, QP로 자주 사용한다. 참고로 Programming이라고 이름이 붙어있지만 이는 computer programming과는 상관이 없고, optimization problem(최적화 문제)를 가르키는 용어이다.컴퓨터 프로그래밍이 이렇게 널리 사용되기 이전부터 사용되던 용어임.Optimization에서 사용되는 programming이라는 용어는프로그래머의 관점으로 해석한다면 problem 또는 optimization problem으로 생각하면 된다. optimization problem은 object function과 constraints들로 정의가 되..

[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 ConditionsKKT조건은inequality constraints을 가지는 constrained optimization problem의optimal solution이 만족해야하는 necessary condition들의 집합(4개의 necessary conditions)임.Lagransian multiplier (or dual variable)를 도입하여 equality constraints를 가지는 contrained optimization problem을 unconstrained optimization으로 바꾸어 푸는 방식 (=Lagrange Method) 에서의 necessary condition을 inequality contraints를 가지는 경우로 확장 한 것임. necessary c..

[ML] Newton-Raphson Method

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)}\\\quad\\x_{t+1}&=x_t+\dfrac{f(x_{t+1})-f(x_t)}{f^\prime(x_t)}\\&=x_t+\dfrac{0-f(x_t)}..

[Math] Hessian: Summary

이 문서는 Numerator Layout Convention 을 사용함.Hessian : Summary 2nd order derivative of multivariable function.여기서 multivariable function은 입력은 vector, 출력은 scalar 인 함수를 의미함: ML에서의 loss function을 생각해 볼 것.Hessian matrix $H[f](\textbf{x})$는 다음과 같음.$$\begin{aligned}H[f](\textbf{x})=H(\textbf{x})&=\left(J\left[\nabla f(\textbf{x})\right]\right)^\top \\ &= \begin{bmatrix}\dfrac{\partial^2 f}{\partial x_1^2} ..