본문 바로가기

분류 전체보기

 (135)
decision problem 과 optimization problem 의 관계 (feat. np) optimization problem 에 대해 배우는 최적화 수업과 decision problem 의 다양한 구분들 (p, np)에 대해 배우는 알고리즘 수업을 동시에 듣다가 optimization 문제를 decision problem 으로 바꿀 수 있다는 사실을 알게되었다. 예를들어 traveling salesperson problem (TSP) 문제를 최적화 문제로 말한다면 우리는 모든 도시를 방문하는 최소 경로를 구하고 싶다고 할 수 있다. 이걸 decision problem 으로 바꾸면 어떨까? 참고로 decision problem 은 YES/NO로 답을 내릴 수 있는 문제를 의미한다. 모든 도시를 방문하면서 최대 k거리를 갖는 경로가 있을까? 로 바꿀 수 있다. 만약 decision proble..
Duality 변환 공식 암기하지말고 이해하기 Duality 변환 공식 선형계획법에서 Duality 에 대해 배우다보면 아래와 같은 dual 변환 공식을 종종 접한다. 다음과 같이 규칙 기반으로 표를 외우는 방법도 있다. 한쪽 문제의 equality constraints는 다른쪽 문제의 free variables 과 대응된다. minimize 문제의 constrainst 와 그의 dual 인 maximize 문제의 variables 의 부호는 같다. minimize 문제의 variables 과 그의 dual 인 maximize 문제의 contraints 부호는 다르다. 하지만 왜 꼭 이렇게 되어야만 하는것인지 규칙에 숨겨진 원리를 당위적으로 이해하고 싶은 사람이라면 아래 예제를 살펴보자. 다음 LP 예제를 살펴보자 min⁡x1+3x2\min x_1+..
Lagrange Multiplier 로 유도해보는 dual 공식을 써보지 않고 Lagrange Multiplier Method 에 대한 선행 지식만 가지고 있다고 가정한 채 dual 을 유도해볼 것이다. 과정을 한번 따라 써보면 dual에 대해 다른 관점으로 이해할 수 있을 것이다. 아래는 LP minimization 문제의 standard form 이다. min⁡c′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 ..

티스토리툴바