서지주요정보
Improvement of the ellipsoid method for nonlinear programming = 비선형문제를 위한 타원체 방법의 개선에 관한 연구
서명 / 저자 Improvement of the ellipsoid method for nonlinear programming = 비선형문제를 위한 타원체 방법의 개선에 관한 연구 / Kun-Nyeong Chang.
저자명 Chang, Kun-Nyeong ; 장근녕
발행사항 [대전 : 한국과학기술원, 1990].
Online Access 제한공개(로그인 후 원문보기 가능)원문

소장정보

등록번호

8001225

소장위치/청구기호

학술문화관(문화관) 보존서고

MMGS 9026

SMS전송

도서상태

이용가능

대출가능

반납예정일

초록정보

For nonlinear programming, the ellipsoid algorithm is extremely robust and competitive with some widely used algorithm with regard to efficiency. But most of the variants suggested so far did not improve the efficiency of the ellipsoid algorithm because the benefit of the larger reductions in ellipsoid volume was offset by the extra effort. We focus on improving the method relative to convergence rate and computational efficiency. We have suggested the two-step search ellipsoid algorithm with a scheme for constructing an ellipsoid of smaller volume using two successive subgradients. The suggested method improves convergence rate, and our computational results show an improvement in computational efficiency due to the advantage of our algorithm outweighing the extra effort. Furthermore we have provided general rank-two update formulas for minimum volume ellipsoid that contains wedge-shaped subset of a given ellipsoid. Using this formulas, deep-cut options and other factors, we have suggested a simple variant of the two-step search ellipsoid algorithm, and it is showed that of all the other ellipsoid algorithms used in the comparison, the variant is most efficient.

비선형문제에 있어서, 타원체 방법은 널리 알려진 다른 방법들에 비해 최적해를 찾는 능력이 뛰어나고 효율적이다. 그런데, 지금까지 제시된 대부분의 변형들은, 타원체 체적의 더 큰 감소에 의한 이익이 추가되는 노력에 의해 상쇄되기 때문에, 기존의 타원체 방법에 비해 그렇게 효율적이지 못하다. 이 논문은 기존 타원체 방법의 수렴률과 효율성의 개선에 촛점을 맞추고 있다. 우리는 연속적인 두 개의 서브그래디언트(subgradient)를 이용하여 더 작은 체적을 가진 타원체를 만들기 위한 체계를 이용한 2단계 탐색 타원체 방법(two-step search ellipsoid method)을 제시하였다. 이 방법은 수렴률을 개선하고, 또한 이 방법에 의하여 얻을 수 있는 이익이 추가되는 노력을 능가하기 때문에 계산적인 측면에서의 효율성도 개선된다. 또한, 우리는 주어진 타원체의 쇄기 모양 부분(wedge-shaped subset)을 포함하는 최소 최적 타원체를 만들기 위한 일반적인 rank-two update formulas를 유도하였다. 이 수식과 deep-cuts 등을 이용하여, 우리는 2단계 탐색 타원체 방법의 간단한 변형을 제시하였는데, 이 방법은 비교한 다른 모든 타원체 방법에 비해 더 효율적이었다.

서지기타정보

서지기타정보
청구기호 {MMGS 9026
형태사항 ii, 56, [1] p. : 삽도 ; 26 cm
언어 영어
일반주기 저자명의 한글표기 : 장근녕
지도교수의 영문표기 : Se-Hun Kim
지도교수의 한글표기 : 김세헌
학위논문 학위논문(석사) - 한국과학기술원 : 경영과학과,
서지주기 Reference : p. 53-56
주제 Nonlinear programming.
Mathematical optimization.
타원. --과학기술용어시소러스
최적화 문제. --과학기술용어시소러스
비선형 문제. --과학기술용어시소러스
Ellipsoid.
QR CODE qr code