In theory and applications of mathematical programming, the role of nondifferentiable optimization has been remarkably increased. Indeed, in spite of the fact that important results have been obtained in the way of constructing and justifying algorithms under certain assumptions regarding differentiability and regularity, there is still a wide range of practically significant economic problems which are difficult to solve by algorithms of this kind. A comprehensive situation surrounded by these problems is called, in this thesis, nonsmooth economy.
Algorithms suggested for optimization under nonsmooth economy can be largely divided into three groups; subgradient methods, space dilation methods, and descent methods. But, in the case of space dilation methods, it has been noticed that they require considerable amount of computations for which better convergence properties do not seem to paid, compared with those of the other groups. Thus, in this thesis we will focus on subgradient methods and descent methods.
The earlier subgradient versions distinguished themselves by simplicity and efficient use of the memory of a computer. Due to the very point, the versions (in particular, Polyak's scheme) have been widely applied to many practical applications. However, the versions also showed their shortcomings of rather slow convergence, and difficulty in assessing the accuracy of the approximate solution or requirement of a good estimation of the optimal function value, which motivated suggestion of various modifications. Some researchers suggested use of information obtained at previous steps and others endeavored to overcome the requirement of a good estimation of the optimal function value. But, the former failed to provide theoretical clarification for their suggestion or did not develop a generalized convergence condition. The latter presented algorithms of heuristic nature or of limited value, which seem to be insufficient to provide a convergent prototype that does not require any prior knowledge of the optimal function value.
Our studies in subgradient methods are based on the above observations, which are largely grouped into two ones. Firstly, we provide some theoretical insights into several improvements of the Polyak's scheme through use of information obtained at previous steps. For various schemes using the previous information, we present a generalized version and provide its convergence condition. Moreover, we extend the Polyak's scheme to allow $\varepsilon$-subgradients and show its convergence properties. Such generalized version and extension will give one more flexibility.
Secondly, by introducing variable target values we provide a convergent prototype (VTVSM) which is based on the Polyak's scheme but never requires any prior knowledge of the optimal function value. Our suggestion is shown to have several significant merits over the previous variants of the Polyak's scheme. What is the most important, it converges to an optimal solution without any prior knowledge of the optimal function value. Unlike other variants, it does not require any heuristic manipulation for the convergence. It also allows definite termination criterion. Up to the present, other variants have suffered from lack of such termination criterion.
On the other hand, for some reason or another, it may be needed to have the monotone decrease of function values. However, in the case of most descent algorithms, their some promising properties have been paid for a drawback that for a descent direction, one must solve a sequence of constrained quadratic programming problems. Our last work in this thesis is devoted to development of a new descent algorithm. This algorithm is constructed by finding that the VTVSM can be successfully applied to a subproblem for descent directions. If one prefers the monotone decrease of function values for some reasons, our suggestion is expected to be a good alternative for this objective.
수리계획법의 이론 및 응용에 있어서 미분불가능 최적화의 역할은 크게 증대되고 있다. 사실, 지금까지 경제모형에 관련된 중요한 이론적 결과와 그 해법은 differentiability 와 regularity 라는 가정하에서 이루어져 왔다. 그러나 이런 종류의 결과와 해법만으로는 해결되기 어려운, 현실적으로 중요한 문제들이 광범위하게 존재한다.
현재까지 개발된, 미분불가능 경제모형의 최적화 방안으로 제안된 것은 크게 subgradient method 와 space dilation method, 그리고 descent method 로 분류될 수 있다. 그런데 space dilation method 의 경우, 다른 두 부류에 비해 상당히 많은 계산량을 요구하며 더구나 그에 상응하는 좋은 수렴특성이 보장되는 것으로 판단되지 않으므로, 이 논문에서는 subgradient method 와 descent method 에 초점을 두었다.
1960 년대부터 소련에서 광범위하게 개발 및 응용된 초기의 subgradient method의 경우, 그 해법의 단순성과 컴퓨터 메모리의 효율적 사용 등으로 인해 기타 다른 해법에 비해, 대규모 최적화 모형에 상당한 이점을 가진 것으로 부각되었다. 바로 그 점으로 인해, 현실적 필요에 의해 발생된 많은 미분불가능 경제 모형에 광범위하게 응용되었으며, 오늘날 이 방법에 대한 연구가 계속되고 있는 것이다. 그러나, 이러한 장점에도 불구하고, 문제구조에 따라 불규칙한 수렴현상 및 적절한 종결조건의 부재 또는 최적목적함수값에 대한 사전추정의 필요성 등으로 인해 그 후 이를 개선하기 위한 노력이 촉진되게 되었다. 그 노력의 유형을 보게 되면, 일부는 앞의 단계에서 이용된 정보, 즉 subgradient 를 현재단계에서 활용함으로써 최적해를 향한 방향의 개선을 도모하는 쪽으로 연구를 진행했으며, 또 일부는 최적목적함수값의 사전추정의 필요성을 나름대로 극복하려는 시도를 했다. 그러나, 전자의 경우, 그 방법의 타당성에 대한 이론적 규명을 하지 못했으며 또한 일반적 scheme 에 대한 수렴조건의 제시가 없었다. 또 후자의 경우, 제안된 방법이 heuristic nature 를 갖거나, 제한적인 의미를 가짐으로써, 최적목적함수값의 사전추정을 요구하지 않는, 하나의 prototype 으로서의 해법이 되기에는 불충분한 점이 많이 존재한다고 볼 수 있다.
이 연구에서 subgradient method 에 대해 다룬 내용은 크게 두가지로 분류될 수 있다. 첫째, 오늘날 가장 많이 인용되고 응용되는 소위 Polyak 의 방법 (1969)에 대해 앞의 단계에서 사용된 정보의 이용을 통한 수정노력에 관하여 이론적으로 규명되고, 1987 년에 제시된 우리의 two direction subgradient method 가 어떤 동기로 이루어 진 것인지에 대해 간단히 소개되었다. 또한, 위와 같이 앞의 단계에서 활용된 정보를 이용하여 현재 단계에서 최적해를 향한 방향을 구축하는 노력들에 대한 일반적인 수렴조건의 제시가 이루어 졌다. 그리고 Poyak 의 방법이 subgradient 보다 완화된 direction 을 허용할 수 있도록 일반화도 이루어 졌다.
둘째로, 궁극적으로 Polyak 의 방법이 일반적인 미분불가능 볼록함수의 최적화에 적용될 때 사실상 최적목적함수값의 사전추정은 불가능하기 때문에, 우리는 목표치의 체계적인 변화를 통해 최적해로 수렴해 가는 소위 가변 목표치 서브그래디어트 방법 (variable target value subgradient method) 을 제시했다. 우리의 방법은 전에 있었던 Polyak 방법의 여러 변종들에 비해 다음과 같은 이점을 가진 것으로 나타난다. 우선 가장 중요한 점으로, 최적목적함수값에 대한 어떠한 사전정보도 요구하지 않는다. 또, 수렴을 위한 heuristic manipulation 을 하지 않는다. 지금까지의 subgradient method 에 부재했던 실제적인 종결조건이 제시된다.
한편, 미분불가능 최적화 모형에 대한 또 하나의 해법으로서, descent method 가 있는데, 이는 각 단계에서 보다 나은 목적함수값을 찾아 진행해 나가는 해법이다. 따라서 subgradient method 에 비해 단계별 계산량이 많다는 것은 명백하지만, 안전성 측면이나, 또 긴급히 stop 했을 때의 얻어진 해의 quality 측면에서, user 에 의해 선호될 수도 있다. 그런데 기존의 descent method 의 경우, 각 단계에서 목적함수값의 감소를 보장하는 방향을 찾을 때까지 일련의 quadratic problems 을 해결해야 한다는 부담을 안고 있다. 이 논문의 마지막 부분은 바로 이와 같은 관찰에 기초하고 있는 데, 우리는 앞에서 언급 된 가변 목표치 서브그래디언트 방법이 하나의 descent direction 을 찾는데 있어 효율적으로 응용될 수 있음을 발견함으로써, 새로운 descent method를 제시했다. 이러한 우리의 방법은 어떠한 storage 상의 문제도 안고 있지 않다는 점에서 지금까지의 descent method 보다 유리하게 적용되리라 기대된다.
