일기/수업 필기 노트 (11) 썸네일형 리스트형 Lagrange Multiplier 로 유도해보는 dual 공식을 써보지 않고 Lagrange Multiplier Method 에 대한 선행 지식만 가지고 있다고 가정한 채 dual 을 유도해볼 것이다. 과정을 한번 따라 써보면 dual에 대해 다른 관점으로 이해할 수 있을 것이다. 아래는 LP minimization 문제의 standard form 이다. minc′x\min c'xminc′x s.t. Ax=bAx = bAx=b x≥0x \geq 0x≥0 이러한 LP 문제를 보면 가장 먼저 궁금해져야하는 것이 각 벡터와 행렬의 차원이다. c, x 는 n 차원의 벡터이며 A는 m x n 행렬, b는 m 차원의 벡터이다. c와 x 벡터를 내적해주기 위해 그냥 c 벡터가 아니라 c′c'c′를 사용한다. 참고로 c′c'c′는 c벡터를 transpose 한 cTc^Tc.. simplex method와 cycling 극복법 Simplex method 는 유한한 시간 안에 끝날까? 수학식으로 증명하는 것 말고 수식은 최대한 줄이고 말로 풀어 직관적으로 설명해보려한다. 이 글은 기본적으로 simplex method가 무엇인지 알고 있어야 이해할 수 있다. Simplex method는 유한한 시간 안에 해를 구해내는 것을 보장할까? 결론부터 말하자면 그렇다. non-degeneracy 를 가정했을 때 non-degeneracy 를 가정하면 쉽다. Simple method는 항상 Basic feasible solution (BFS) 이 감소하는 방향으로만 움직이니 같은 basis 로 돌아올 수가 없다. 우리는 유한한 basis 를 가지고 있으니 유한한 시간 안에 알고리즘이 끝난다. degeneracy 가 있을 때- cycling .. [선형대수] 그림으로 알아보는 Basic feasible solution 사전 지식active 하다는 것? 만일 어떤 벡터가 제약식의 equality 를 만족하면 그 제약식은 active 혹은 binding 되었다고 한다. 직관적으로 크거나 같다/ 작거나 같다 등의 조건이 있을때 그 조건에 딱 걸쳐있는 벡터를 상상하면 쉽다. Basic solution 이란? 어떤 벡터가 basic solution 이 될 조건은? (차원이 n 이라고 하자)(1) active contraints 중 선형 독립이 n개 존재해야 함. (n은 차원의 수)(2) equality contrains 은 무조건 active 해야함.첫번째 조건은 직관적으로 이해가 된다. solution을 어떤 한 점이라고 생각한다면 2차원의 공간에서 한 점을 특정하기위해서는 2개의 선분이 필요할테고 3차원의 공간에서 한 점을.. 이전 1 2 다음
