티스토리 뷰

Algorithm

Optimization.

Rocknz 2018.07.23 15:57

Gradient Descent => $$x_{n+1} = x_n - \nabla f(x_n) \times \alpha $$


Newton Method =>  $$x_{n+1} = x_n + (\nabla^2 f(x_n))^{-1} \times \nabla f(x_n) $$


Levenberg-Marquardt algorithm (LM) =>

 LM is used to solve non-linear least squares problems. These minimization problems arise, especially in the least squares curve fitting.

 https://en.wikipedia.org/wiki/Levenberg%E2%80%93Marquardt_algorithm



Linear Programming(LP) =>

$$ \min_{x} Wx + b $$

subject to 

$$ Ax \leq a $$

$$ Cx = c $$


Objective function이 Linear 해야 하고, constraints가 affine 이여아함. ( Ax + b 꼴..)




Qudratic programming (QP) =>


방정식이나 부등식 제한 조건을 가지는 일반화된 이차형식(quadratic form)의 값을 최소화하는 문제를 QP(Quadratic Programming) 문제라고 한다.


$$ \min_{x} x^T Kx + Wx + b $$

subject to 

$$ Ax \leq a $$

$$ Cx = c $$

Objective function이 quadratic + linear 해야 하고, constraints가 affine 이여아함. ( Ax + b 꼴..)




SQP Sequential Quadratic programming (SQP) =>

 Optimization 문제를 나눠서 local affine approximation을 하여 objective functional f 를 quadratic approximation 하고

 Constraints는 local affine approximation을 하여

 QP문제를 optimization 하여 d 값을 구함. ( $ d = x - x^k $ )

댓글
댓글쓰기 폼