The application of variational inequalities covers a great number of areas. We concern with numerical solution method of the variational inequality over a polyhedral set. Among well known numerical methods are the projection method, Newton method and etc. The subproblems of them, however, require another iterative methods which are themselves often computationally challenging since they are also optimization problems. The purpose of this research is to propose effective methods to solve these subproblems by approximating the given set K via an inscribed ellipsoid. We propose an ellipsoidal projection method and an ellipsoidal Newton method. The subproblems of them are shown to be solved in a closed form. A custom tailored version of the proposed ellipsoidal projection method for fixed demand traffic equilibrium problem is also proposed. A practical version of the ellipsoidal projection method with additional line search step is proposed to give safety against possible risk of small step size. Convergence properties of the above methods are investigated. Limited computational experiments with small sized traffic equilibrium problems show that the proposed ellipsoidal projection method is promising.
변분부등식은 어떤 벡터함수와 볼록집합이 주어진 상태에서 한 점으로부터 발생하는 모든 실행가능방향으로의 벡터가 그 점에서의 함수 값과 예각을 이루는 점을 구하는 것이다. 변분부등식의 응용 영역은 교통량균형문제, PIES 모형, 지역간 시장균형모형, 내쉬균형모형 등의 경쟁적 균형문제와 그 외의 여러 수리계획분야에 이르기까지 다양하다. 경쟁적 균형문제는 그 해의 특성을 알기 위하여 반드시 해를 계산하여야 할 필요가 있는 것은 아니나, 문제의 특성에 따라서는 해가 제시하는 수치자체가 중요 관심사인 경우도 있고 혹은 수치적 방법에 의한 해의 계산만이 그 특성을 감지하기 위한 유일한 방법일 경우도 있다. 본 연구는 다면체에서 정의된 변분부등식의 효율적인 해법을 제시하는 것을 그 목적으로 한다.
변분부등식 해법 연구의 역사는 짧지만, 여러 가지 해법들이 제시되고 분석되었다. 다양한 기존의 해법들을 일반화하여 개략적으로 표현하면, 주어진 원문제의 단순화된 부분 문제들을 연속적으로 풀어서 최종적인 해를 구하는 방향으로 나아가는 방식을 택하고 있다. 따라서 단순화된 문제의 해법이 얼마나 효율적인가에 따라 해법의 효율성이 달라지게 된다. 지금까지 알려진 해법들의 단순화된 부분 문제들 중 가장 좋은 특성을 가진 것이 투사법의 경우와 같은 최적화 문제로 나타나는 것이다. 또한, 효과적인 해법의 하나로 알려진 뉴톤해법처럼 단순화된 부분 문제가 원문제보다 조금 간단한 형태의 변분부등식이 되는 경우도 있다. 요약하면, 기존의 해법들의 공통된 문제점은 단순화된 부분 문제 자체가 별개의 해법 절차를 가지고 있어야 한다는 점이다. 그리고 그 해법은 최소한 수리 계획의 최적화 문제를 풀 수 있는 것 이어야 한다. 본 연구에서는 이러한 문제점에 착안하여 각각의 부분 문제가 반복적 단계를 필요로 하는 형태가 아닌 일회적 계산에 의하여 풀어질 수 있는 해법을 제시하고자 한다.
본 연구에서 제시하는 가장 중요한 착안점은 주어진 집합 대신 그 다면체의 내부에 속하는 타원을 사용하여 부분 문제를 정의한다는 것이다. 기존의 해법들이 주어진 함수의 단순형을 이용하여 부분 문제를 구성한 것에 반하여, 본 연구의 해법은 함수는 물론이고 집합까지도 타원에 의해 단순화하고 그 타원의 반경을 적절히 조정하여 부분 문제 해의 일회적 계산을 가능하게 하였다.
기존의 투사법이 사용하는 부분 문제의 단순화된 함수를 그대로 이용하고 여기에 집합의 타원근사개념을 접합시킴으로써 타원투사법을 제시하였다. 본 연구에서 제시된 타원투사법은 기존 투사법보다 부분 문제를 더 개략화 하였음에도 불구하고 이론적인 수렴성에서 유사한 특성을 지님이 증명되었다. 또한 비록 소규모의 부분적인 예제를 통한 계산 실험이기는 하나 계산 특성도 우수한 것으로 나타났다.
기존의 뉴톤해법은 수렴 특성이 우수하여 유력한 해법으로 인정되고는 있으나, 그 부분 문제를 풀 수 있는 일반 해법을 구하기가 어렵다는 약점을 가지고 있다. 본 연구에서는 뉴톤해법의 해법 절차에 타원근사방식을 적용함으로써, 타원뉴톤해법을 제시하였다. 제시된 해법은, 기존의 뉴톤해법이 기존의 투사법에 비하여 부분 문제의 해법절차상에 문제가 있음에 반하여, 앞에 제시된 타원투사법과 동일한 방식에의하여 일회적 계산으로 부분 문제의 해를 구할 수 있다.
변분부등식의 응용 영역의 하나인 고정수요 교통량균형문제는 특수한 형태를 가진 문제이므로, 이 문제를 풀기 위한 보다 단순화된 타원투사해법을 제시하였다. 이 문제의 특수 구조를 이용하여 부분 문제를 보다 단순화된 여러 개의 소문제로 다시 나눈 다음 이에 타원투사해법을 적용하였다. 여기에 적절한 계산 과정상의 몇 가지 기법을 추가함으로써 각 문제들이 계산량의 부담이 거의 없는 방식으로 계산될 수 있음을 보였다.
앞에서 제시한 타원투사법의 경우 사용된 타원의 반경이 가능한 한 큰 것이 바람직하고, 반대로 그 반경이 너무 작아지는 것은 해법의 효율을 나빠지게 할 가능성이 있다. 또한 그 반경이 작아질 수 있는 가능성을 이론적으로 배제하지는 못하였다. 따라서 본 연구에서는 마지막으로 계산량의 부담이 거의 없는 추가적 계산 과정을 위의 타원투사법에 첨가함으로써 만일의 경우 반경이 너무 작아질 수 있다는 위험에 대비하도록 하는 실천적 해법 과정을 제시하였다. 이 실천적 과정도 원래의 타원투사법과 마찬가지의 수렴 특성을 가지는 것으로 판명되었다.
