A class of implementable algorithms is proposed for minimizing any convex, not necessarily differentiable, function: f of several variables, which requires only the calculation of f and one subgradient of f at each generated point.
Each algorithm generates a point which is closer and forms acuter angle to the solution set than the point generated by the conventional subgratient method, and if the solution set is nonempty, then this sequence of points generated by each algorithm converges to an element of the solution set. These algorithms still remain very simple or have the adjustment factor such that the computational burden per iteration can be controlled by an user.
An aggregate subgradient algorithm of this class is constructed from the algorithm of Poljak in the similar way that Kiwiel did in the descent subgradient algorithm of Lemarechal. This algorithm is related to the algorithm of Camerini et al. and the clear clarification of that algorithm is made. A variant of the aggregate subgradient algorithm is proposed as a modified algorithm of the algorithm of Camerini et al. and is shown to have better performance than that algorithm by computational test. Furthermore, under a simple assumption, an extended algorithm of the aggregate subgradient algorithm terminates after finite iterations when function: f is piecewise linear.
A two-direction subgradient algorithm of this class is proposed with the selection scheme for one preceding direction. A simple variant of the two-direction subgradient algorithm is also proposed and is shown to have great improvement in the computational efficiency, compared with the conventional subgradient method.
우리가 부딪히는 최적화 문제들, 종종 경제학적 상황에서 제기되는 여러 문제들이 미분불가능일 경우가 많다. 이점에 착안하여 우리는 여기서 실제적으로 응용 가능한 알고리즘을 제시하고 있다.
우리가 제시한 각 알고리즘은 기존의 수리 계획법에서 가장 많이 쓰이는 방법중의 하나인 Subgradient 방법보다 구하고자 하는 데에 보다 가깝고 정확한 방향을 가르키고 있음을 이론적으로 증명하고 있다. 또한, 기존의 방법의 장점인 알고리즘의 단순성을 깨지않고 있으며, 적절하고 효율적으로 조절할 수 있는 factor를 가지고 있다.
첫 번째로 제시하고 있는 "Aggregate Subgradient 알고리즘"은 소련의 Poljak의 알고리즘으로부터 idea를 얻어 구성된 것으로서, 이 알고리즘이 여러가지 다양한 특성을 가지고 있음을 밝히고, Camerini et al이 제시한 방법이 우리의 알고리즘에서 극명하게 규명되고 있음도 보여준다. 아울러 수정된 알고리즘을 제시하고, Camerini et al이 제시했던 알고리즘보다 알고리즘의 효율성을 따지는 세 가지 기준에서 모두 우수함을 보이고 있다. 더구나 여기서 하나의 확장된 알고리즘을 제시하고 있으며, 이 알고리즘은 유한한 단계 내에서 수렴함을 보이고 있다.
두 번째로 제시된 "Two-Direction Subgradient 알고리즘"은 현재 정보로서 가지고 있는 Subgradient 와 전스텝에서 축적되어 있는 정보, 즉 Subgradient 들 중에서 선택된 것, 즉 물을 이용하여 효율적인 알고리즘을 제시하고 있다. 여기서 우리는 효과적인 선택 rule을 아울러 제시하고 있으며, 단순화된 "Two-Direction Subgradient 알고리즘"을 제시하고, 이것과 기존의 전통적 Subgradient 방법과 비교했을 때 역시 알고리즘의 효율성의 세 가지 기준에서 볼 때 훨씬 우수함을 보이고 있다. 참고로 알고리즘 효율성의 세기준이란 "보다 정확한 " , " 보다 적은 단계" , "보다 적은 CPU time" 을 말한다.