The Lagrangean relaxation is a widely used tool for nonlinear programming problems where the multipliers are usually updated by Polyak's subgradient method. In this thesis we present a new multiplier-updating procedure for the Lagrangean function which uses ε-subgradients and preserves the simplicity of the subgradient method with Polyak's step-size rule. This allows us to use a heuristic algorithm in solving dual subproblems. It is shown that an ε-optimal solution of a Lagrangean problem provides an ε-subgradient of the Lagrangean function. The negative of this ε-subgradient forms an acute angle with the direction toward the optimal solution set. Thus, using it as a search direction we can find an approximate optimal solution for the Lagrangean dual problem.
엡실론 서브그래디언트를 이용한 라그란지 승수 개선에 관한 연구 많은 비선형 계획 문제에 이용되고 있는 Lagrangean 완화 기법에서 대개의 경우 Lagrange 승수는 Subgradient 방법에 의해 개선되고 있다. 본 논문에서는 Subgradient 대신 ε-subgradient를 이용하는 새로운 Lagrange 승수 개선법을 제시하였다. 이 방법은 Sugradient 방법의 단순함을 그대로 유지하면서도 Subgradient 방법에서와는 달리 부문제의 최적해대신 근사해를 구하기만 해도 된다는 잇점을 갖고 있다. 이와 같은 결과는 부문제의 ε -최적해는 Lagrange 함수의 ε -subgradient 가 되고 이 ε -subgradient 의 반대 방향과 최적 승수의 방향이 예각을 이룬다는 두가지 사실로부터 도출된다. 본 논문에서는 이사실들이 증명되었다.
