본문 바로가기

Enginius/Machine Learning

라그랑즈 미정 계수법을 이용한 최적화 기법

A typical problem arising in signal processing is to minimize xTAx subject to the linear constraint cTx=1A is a positive definite, symmetric matrix (a correlation matrix) in most problems. Clearly, the minimum of the objective function occurs at x=0, but his solution cannot satisfy the constraint. The constraint g(x)=cTx1 is a scalar-valued one; hence the theorem of Lagrange applies as there are no multiple components in the constraint forcing a check of linear independence. The Lagrangian is
L(x,λ)=xTAx+λ(cTx1)
Its gradient is 2Ax+λc with a solution x=λA-1c2. To find the value of the Lagrange multiplier, this solution must satisfy the constraint. Imposing the constraint, λcTA-1c=-2; thus, λ=-2cTA-1c and the total solution is
x=A-1ccTA-1c


-
 1. Constraint를 λ로 놓고 x로 미분한다.
 2. 이 미분한 것을 0으로 놨을 때 x = f(λ) 를 구할 수 있다.
 3. 이것을 다시 constraint 식에 넣어서 x를 소거한다. (λ 를 구할 수 있다. )
 4. 이렇게 구한 λ를 다시 2 식에 넣어서 x를 구한다.  

'Enginius > Machine Learning' 카테고리의 다른 글

Expectation of X^n; X~N(u,sigma^2)  (0) 2011.10.24
using FLDA to classify IRIS data set  (0) 2011.10.14
HMM viterbi algorithm  (0) 2011.10.13
"classify" in Matlab  (0) 2011.10.07
Linear Discriminant Analysis (LDA)  (0) 2011.10.06