The optimization problem of a convex, not necessarily differentiable function under linear constraints is considered in this thesis. For this problem the conventional subgradient method has a weakness in that the involved projection step requires a heavy computational burden when the number of constraints is large. We have developed numerical methods with special attention to the computational efficiency. The suggested methods have simplified the involved projection to reduce computational requirement considerably while preserving the simplicity of the algorithm. Some related properties of our search direction are provided. Our computational results show a improvement in computational efficiency over Poljak's method. Furthermore it is discussed that our methods can be applied as an efficient optional rule to avoid the heavy computational load in implementing the improved subgradient method of Poljak.
본 논문은 선형 부등 제약식을 지닌 볼록 함수의 최적화를 다루고 있다. 이러한 문제에서 기존의 subgradient 해법이 지니는 문제점은 선형 제약식의 수가 많은 경우에 실현 가능한 해를 얻기 위해 필요로하는 사영 (projection) 문제가 너무 커진다는 것이다. 이러한 사영문제의 크기를 줄임으로써 효율적인, 수정된 해법을 제시하고자 하는 것이 본 논문의 주 목적이다.
우리는 사영 문제에서 현재의 해에서 등식으로 성립되는 제약식 (binding constraints)만을 도입하였다. 이로부터 우리는 projected subgradient 를 얻는 데 이는 변형된 목적 함수의 subgradient가 된다. 이를 이용하여 제약이 없는 경우의 subgradient 해법의 단순성을 지니면서도 계산의 양이 크게 줄어든 projected subgradient 해법을 제시하였다. 이 해법은 search direction 의 성격상 Zoutendijk 의 feasible direction 해법과 밀접한 관계를 지닌다. 이 해법은 computational test 를 통하여 효율적임이 밝혀졌으며, 이 방법이 지니는 좋은 성질에 대해서도 논의되었다.
이 해법은 일반적으로 충분한 step-size 가 보장되지 않는다는 단점이 있다. 이런 단점을 보완할 수 있는 방법으로 이 해법을 확장 시킨 iterative projection scheme 을 사영 문제에 적용하였다. 이 방법은 Zoutendijk 의 feasible direction 해법을 subgradient 해법의 사영 문제가 지니는 특수한 구조에 맞게 변형시킨 것이다. 이 해법의 효율성도 computational test 를 통해서 밝혀졌다.
