Most large scale problems have special structures. A linear programming problem may have a block structure and a relatively small number of interaction between the subunits, some 'hard' combinatorial problems can also be viewed as 'easy' problems complicated by a relatively small set of side constraints. Efforts to take advantage of such structures often result in the formulation of nondifferentiable optimization (NDO) problems. It is time-consuming to evaluate the objective function of the induced NDO problems even if the number of variables is small.
Until now the subgradient method has been used most favorably to solve the induced NDO problems. The convergence speed of the subgradient method is, however, extremely slowed down at the region where the gradient of the objective function varies rapidly or is discontinuous. This problem becomes especially serious when one is solving an induced problem.
To resolve this problem, Poljak and Camerini et al. have suggested in their improved subgradient method and modified gradient method to take a suitable combination of the subgradients identified during the process and to use it as the search direction. Their suggestion coincides with the current trend of NDO and it was quite obvious that their algorithm would work better. But they failed to provide concrete theoretical arguments that their algorithms are superior to the subgradient method. Moreover, the algorithms require the optimal value of the problem to be known in advance, making it impossible to apply them to the induced NDO problems. For these reasons the algorithm have not been noticed.
In this thesis we show theoretically that the improved subgradient method and the modified gradient method are superior to the subgradient method. That is, we show that the iterate produced by the methods is closer to the optimal solution that that produced by the ordinary subgradient method. We also show that the direction of the methods forms a smaller angle with the direction towards the optimal solution that the direction negative to the subgradient does with the direction towards the optimal solution. Based upon the new findings, we propose the two-direction subgradient method which requires programming effort as little as the subgradient method does but still preserves the main merits of the improved subgradient method. We also propose extended versions of the methods, in which the critical weakness of the methods that the optimal value must be known in advance is overcome. The resulting methods, unlike the original methods, can be applied to almost all NDO problems including those induced from large-scale optimization problems. Computational results show well that our methods are superior to the subgradient method.
분권화된 조직의 의사결정문제나 동적인 의사결정문제 들로부터 도출된 수학적 최적화문제들은 종종 특수한 구조를 갖는다. 특수한 구조의 최적화문제들은 같은 규모의 그렇지 않은 최적화문제들 보다 훨씬 효율적으로 풀 수 있다. 대규모최적화 (Large-scale optimization LSO)란 일반적인 방법으로는 풀 수 없는 대규모의 최적화문제들을 특수한 구조를 이용하여 효율적으로 풀 수 있도록 하는 방법을 연구하는 분야이다.
LSO해법은 크게 기존의 일반적인 해법을 각 특수한 구조에 맞춰 전문화시킨 것과 디컴포지션이나 파티셔닝 (decomposition or partitioning, D/P) 기법에 기초한 것의 두 종류로 나눌 수 있다. 이중 보다 널리 쓰여지고 있는 것들은 D/P기법에 기초한 것들이 다. 그런데, D/P기법은 미분불가능최적화 (nondifferentiable optimization, NDO) 문제를 발생시킨다. 따라서 보다 효율적인 NDO 해법을 개발한다는 것은 보다 효율적인 D/P기법을 개발하는 것과 같다고 할 수 있다. 이러한 점은 일찍부터 인식되어, 1979 년에는 Shapiro에 의해서 NDO가 LSO의 주요한 해법으로 교과서에 소개되었다. 물론, NDO는 다른 분야에서도 그 활용가치를 지니고 있다.
근래에 들어서 많은 NDO해법들이 개발되었다. 그러나, 그 안정성이 인정되어 가장 널리 쓰여지고 있는 것은 비교적 초기의 것인 서브그래디언트 방법 (subgradient method) 이다. 그러나 서브그래디언트 방법은 목적함수의 그래디언트 (gradient) 가 급격히 변하거나 불연속인 지역에서는 그 수렴속도가 매우 늦어진다. 이러한 단점은 LSO문제에서부터 유도된 문제들의 경우에는 특히 심각하여 진다.
Poljak과 Camerini et al.은 서브그래디언트 방법을 개선하여 각각 improved subgradient method와 modified subgradient method를 발표하였다. 이들은 그들의 방법들이 서브그래디언트 방법보다 더 효율적일 것이라고 주장하였으나, 그 이론적인 근거를 제공하는데는 실패하였다. 뿐만 아니라 이들의 방법들에서는 이제 풀려고 하는 문제의 최적값이 미리 알려져 있어야 한다.
이러한 이유에 의해서 이들의 방법들은 주목을 받지 못하고 있었다. 그러나 이들의 방법들은 지금까지 발견된 서브그래디언트를 이용해 지그재깅 (zigzagging) 현상을 방지하려고 한다는 점에서 NDO 의 최근의 추세에 합치된다. 따라서 이들의 방법들이 서브그래디언트 방법보다 더 효율적일 것이라는 것은 쉽게 짐작할 수 있다.
본 논문에서는 Poljak과 Camerini et al,의 방법들이 서브그래디언트 방법보다 더 효율적이라는 (최적값이 미리 알려져 있을 때에는) 것을 이론적으로 증명하였다. 즉, 이 방법들에 의해서 찾아진 해는 서브그래디언트방법에 의해서 찾아진 해보다 최적해에 더 가깝다. 그리고 이 방법들의 탐색방향은 서브그래디언트방법의 탐색방향인 서브그래디언트의 반대방향보다 최적해에 이르는 방향과 더 작은 각도를 이룬다. 이러한 새로운 발견을 이용하여 Poljak의 방법의 장점을 그대로 간직하면서도 프로그래밍 노력이나 계산시간을 크게 절약할 수 있는 two-direction subgradient method를 개발하였다.
또한 Poljak과 Camerine et al.의 방법들을 최적해를 모르는 문제들에 대해서도 적용할 수 있는 방안을 제시하였다. 그 결과 얻어진 extension C와 quasi-descent method는 LSO문제들로 부터 유도된 문제들에도 사용할 수 있다. 실험결과는 이들이 서브그래디언트 방법뿐만 아니라 기존의 어떤 NDO방법보다 더 효율적이라는 것을 잘 보여준다.
