Karmarkar's algorithm is known to have some practical deficiency in spite of its polynomial complexity. It requires prior knowledge of the exact optimal value and it does not generate the optimal dual solutions. Ye and Kojima developed a standard form variant of Karmarkar's algorithm that generates a dual solution through successive lower bound updating scheme of the unknown optimal objective value.
In this thesis, to improve the algorithm of Ye and Kojima further, Karmarkar's algorithm is joined with the ellipsoid method using dualcontaining ellipsoid. A dual-containing ellipsoid contains all of the optimal dual solutions, and this ellipsoid shrinks at a fixed ratio. Our method, then finds dual feasible solutions contained in this ellipsoid and uses them to generate a new lower bound of the optimal objective value. This boudn is utilized in the Ye and Kojima's scheme to improve its computational efficiency.
Our method has been tested on 12 example problems. We observed that the number of iterations has been reduced significantly in all test problems. However, the total CPU times did not reduced due to the additional computational times required in the process of obtaining a dual feasible solution.
Karmarkar 알고리즘은 polynomial complexity 에도 불구하고 약간의 실제적 문제가 있는 것으로 알려져 있다. 즉, 사전적으로 최적해가 알려져 있어야 하며 쌍대최적해를 구하지 못한다는 것이다. Ye 와 Kojima 는 최적해를 모르는 경우 하한을 계속적으로 개선해가며 쌍대값을 구해내는 기법을 개발하였다.
이 논문에서는 Ye 와 Kojima 의 방법을 개선하기 위해 Karmarkar 알고리즘과 ellipsoid 방법을 쌍대포함타원체 (dual-containing ellipsoid) 를 사용하여 이론적으로 연계하였다. 이 쌍대포함타원체는 쌍대최적해를 모두 포함하고 있으며 일정한 비율로 체적이 줄어든다는 것이 알려져 있다. 그래서, 우리는 쌍대포함타원체 안에 있으면서 쌍대실행가능한 해 (dual feasible solutions) 를 구해서 새로운 하한을 구해내고, 계산상의 효율성을 제고하기 위해 Ye와 Kojima 의 방법에 이 하한을 사용하였다.
이 기법을 12개의 문제에 적용해 본 결과 모든 문제에서 계산횟수 (iteration) 가 현저하게 줄어드는 것을 관찰하였다. 그러나, 쌍대실행가능해를 구하는 과정에서의 부가적인 계산량 때문에 전체적인 계산시간은 줄어들지 않았다.
