In this paper, we suggest the bundle-type subgradient method to update the multipliers in the Lagrangean relaxation procedure. The Lagrangean multipliers usually have been updated through the subgradient method. Although the subgradient method is very simple and generates a sequence which eventually converges to an optimal solution, many researchers have experienced erratic behavior of the subgradient method due to its slow convergence. The slow convergence of the subgradient method is due to its Markov nature.
The bundle-type subgradient method uses some of the subgradients generated by the algorithm at the previous iterations. The bundle-type subgradient method generates a point which is strictly closer and forms a acuter angle to the solution set than that generated by the subgradient method.
We extend the Poljak's sufficient condition to the bundle-type subgradient method. The direction generated by the bundle-type subgradient method at each iteration is a positive linear combination of subgradients obtained by the algorithm at the previous iterations. We give the sufficient conditions of the coefficients for the algorithm to converge to an optimal solution.
Finally, computational results are given and future research directions are discussed.
Lagrangean 완화기법과 subgradient 방법은 최근에 가장 많이 쓰여지고 있는 수리계획법의 하나이다. 비록 subgradient 방법이 Lagrangean 계수들을 향상시켜 나가는데 있어서 간단하고 최적회로의 수렴을 보장해준다 할지라도 수렴률이 느리다는 것이 여러 응용 문제에서 드러나게 되었다. 이것은 subgradient 방법이 과거의 여러 정보들을 전혀 사용하지 않는데서 기인한 것이다.
우리는 여기서 Lagrangean 계수들을 향상시키는데 과거의 정보들을 이용하여 새로이 개발된 다발형태의 subgradient 알고리즘을 사용하고자 한다. 기존의 다발형태 알고리즘은 목적함수의 목적값이 최적값보다 작아야 사용될 수 있었다.
Lagrangean 완화기법과 다발형태 알고리즘을 함께 사용할 경우 목적함수의 목표값이 최적값보다 커지게 되므로 본 논문에서 이를 해결할 2가지 방법을 제시하였다. 비록 최적회로의 수렴을 이론적으로 보장해 주지는 못하지만 2가지 실제문제에 적용시켜본 결과 subgradient 방법과 좋은 해를 구할 수 있었으며 수렴률 역시 실험적으로 좋다는 결론을 얻었다.
또한, 목적함수의 목표값을 알지 못하는 상태에서도 최적회로의 수렴을 보장하는 조건을 개발하게 되엇다.
Poljak의 정리를 응용한 2가지 정리를 통하여 다양한 알고리즘의 개발을 가능하게 할 수 있는 근거를 제시하였다.
