Many decision problems are now formulated as mathematical programs, requiring the maximization or minimization of an objective function subject to constraints. Such programs often have special structure. In truly large problems, some definite structure is almost always found since these commonly arise from a linking of independent subunits in either time or space. By developing specialized solution algorithms to take advantage of this structure, significant gains in computational efficiency and reductions in computer memory requirements may be achieved. Such methods are mandatory for truly large problems, which cannot otherwise be solved because of time and/or storage limitations.
One of the most computationally useful ideas of the 1970s is the observation that many hard problems can be viewed as easy problems complicated by a relatively small set of global constraints which concern all subunits. Lagrangean duality, also referred to as Lagrangean relaxation, incorporates the complicating constraints into the objective function via Lagrangean multipliers, resulting in a problem that only contains the simple constraints. Despite the possible presence of a duality gap, this fact and the desirable properties of the dual function make this approach appealing in many respects. So this approach has led to dramatically improved algorithms for a number of important problems in the areas of routing, location, scheduling, assignment, set covering and so forth.
Recently, there has been a great deal of interest in the area of nondifferentiable optimization. Nondifferential optimization arises naturally in many eigenvalue and min-max problems. Particularly, even if the original functions are differentiable, the Lagrangean dual function is not differentiable, thus necessitating special schemes for its maximization. Furthermore, in many large scale optimization problems, the set of variables can be decomposed in two sets, where an optimal solution can be easily obtained as one set of the variables is fixed. This formulation also leads naturally to a nondifferentiable optimization problem.
Subgradient optimization is one of the most widely used tools in the field of nondifferentiable optimization, especially within the contexts of Lagrangean relaxation, and branch and bound. Despite its acceptability among researchers and despite the availability of ample theoretical convergence results, many researchers have experienced erratic behavior of the method as different rules for choosing the step size along the subgradient vector are used. One reason of the erratic behavior is the Markov nature of the subgradient method. That is, the subsequent iteration makes no use of the information obtained at the previous iterations.
The first purpose of this thesis is to suggest subgradient methods which use parts of subgradients generated at previous iterations. Two algorithms will be introduced. One is an extension of Polyak's improved subgradient method and the other is an extension of two-direction subgradient method. Since the latter is a special case of the former, these algorithms have similar properties. First, these methods converge to an optimal solution without any prior knowledge of optimal objective value. Second, these methods include the target value updating scheme so that these generate the good upper bound of the optimal value and these allow practical termination criteria in real applications. Third, existing step size strategies under Polyak's subgradient method can be applied to our methods. Besides, extended two-direction method maintains the simplicity like original two-direction method. We compare computational results of our methods to those of subgradient methods with the same step size rules.
The second purpose is to apply the Lagrangean relaxation method to the unit commitment problem of a power generation system with pumpedstorage units. Then the subproblem for each thermal unit and for each pumped-storage unit becomes the shortest path problem and the minimal cost flow problem, respectively. A method for finding a better feasible solution from a solution of a relaxed problem is presented. A real Korean power generation system with 39 thermal units and one pumped-storage unit with 168 planning hours is tested.
많은 의사결정문제는 제약식과 목직식을 지닌 수리적문제로 정식화 되며 이러한 문제는 자주 특별한 구조를 포함한 형태로 나타난다. 특별한 구조를 잘 이용하는 알고리즘의 개발은 계산속도를 단축시키고 계산기의 기억장치를 적게 사용한다는 면에서 매우 바람직하게 된다. 많은 풀기가 어려운 문제에서도 전체에 관련한 제약식은 상대적으로 소수이며, 이를 제외한 나머지만을 고려하면 풀기 쉬운문제가 되는 구조적특성을 지니는 것이 일반적이다. 라그란쥐완화기법(Lagrangean relaxation method)은 위와 같이 상황을 어렵게하는 전체에 관련한 소수의 제약식에 라그란쥐 승수를 이용하여 목적식으로 올려버리고 나머지 다루기 쉬운 제약식만을 고려함으로서 문제를 풀기 쉽게만드는 계산기법이며, 여러분야에 적용되어 괄목할만한 계산성과를 보여준 방법이다.
대규모 혼합정수계획문제에 라그란쥐완화기법을 적용함으로서 얻어지는 라그란쥐 쌍대함수(Lagrangean dual function)는 항상 미분불가능한 함수가 되며, 따라서 라그란쥐 쌍대문제(Lagrangean dual problem)는 미분불가능한 함수의 최적화 과정을 항상 포함한다. 일반적으로 서브그래디언트 방법이 가장 많이 사용되나 매 단계에서 그 단계에서 구한 서브그래디언트만을 이용한다는 마아코프특징에 기인하여 수렴속도가 늦은 단점이 있다. 향상된 서브그래디언트 방법(improved subgradient method)과 두개방향의 서브그래디언트방법(two-direction subgradient method)은 이런점을 보완한 방법이나 최적값을 사전에 아는 문제에만 적용이 가능하다. 본 논문에서 다룬 첫번째 주재는 이와 관련된 것으로 이러한 방법들을 계량한 것이다. 여기서 제시된 방법들은 다음의 특징을 지닌다.
첫째, 향상된 서브그래디언트 방법과 두개방향의 서브그래디언트방법을 최적값에 대한 상한(최대화의 문제에 대해서) 만으로도 사용이 가능하도록 보다 일반적인 경우로 확장하였으며, 제안된 방식은 최적해에 대한 사전지식없이 최적해에 수렴함을 증명하였다.
둘째, 제시된 방법들은 상한을 향상시키는 과정을 포함하고 있으며, 이를 위한 추가계산은 거의 요구되지 않는다. 또한 이런과정을 통해 얻어진 상한은 매단계에서 구한 해가 최적에 얼마나 근접했는지를 알려주어 종료조건에 이용되고 있다.
세째, Polyak의 서브그래디언트 방법과 같은 step size전략을 이용하여 비교한 결과 제시된 두 방법 모두가 서브그래디언트 방법보다 우수하다는 결과를 보여주고 있다.
네째, 제시된 두 방법은 각기의 특징을 지니고 있다. 확장된 두개방향의 서브그래디언트방법의 특징은 단순성이다. 따라서 매 단계에서 새로운 점을 찾는데 소요되는 시간은 확장된 improved subgradient method보다 적게 걸린다. 그러나 이것이 확장된 두 개방향의 서브그래디언트방법이 확장된 improved subgradient method보다 우수하다는 것을 증명하는 것은 아니다. 예를들어 라그란쥐완화기법하에서는 매 단계에서 부문제를 해결해야 하고 그결과 많은 시간이 매 단계에서 소요되기 때문에 계산에 소요되는 총시간은 총반복회수에 따라서 결정되어지는 경우가 많다. 따라서 매 단계에서 짧은 시간내에 적당한 점을 구하는 방식보다는 시간이 더 소요되더라도 최적해에 가까운점을 구하는 방식이 결과적으로는 총 반복횟수를 줄이는 방법이 될것이다. 확장된 improved subgradient method는 cut의 수를 임의로 늘리는 것이 가능하므로 최적해가 존재하는 영역을 상당히 좁힐 수 있고, 따라서 최적해에 보다 가까운 점을 구할것으로 예측되어, 총반복회수는 수정된 두개방향의 서브그래디언트방법보다 작을 것이다. 결론적으로 말하면, 목적이 단순히 미분불가능함수의 최적화이고 이 함수의 서브그래디언트는 쉽게 구해진다면 수정된 two-direction method가 바람직하리라고 보며, 전체 반복회수를 줄이는 것이 총 소요시간을 단축하는 가장좋은 방법이라고 예상되는 경우라면 수정된 improved subgradient method의 사용이 바람직하리라 본다.
본 논문의 두번째 주제는 라그란쥐완화기법을 발전시스템 기동정지계획문제에 적용하는 방법에 관한 것이다. 고려된 발전기의 종류는 화력과 양수발전기이며 이에관련한 라그란쥐 탐색적기법(Lagrangean heuristic)을 제시하였다. 승수를 이용하여 완화시킨후 얻어진 화력발전기의 문제는 기존의 방식으로 해결하였으며, 양수발전기에 관한 문제는 네트워크접근법을 통해 해결가능함을 보였다. 이러한 탐색적기법을 실제의 한국의 발전 시스템의 1주간의 운영계획에 적용하여 매우 빠른시간내에 최적해에 상당히 근접한 해를 얻음으로서 이러한 접근방법이 계산적으로 가능함(computationally feasible)을 보였다.
