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단계 탐색 타원체 방법의 간단한 변형을 제시하였는데, 이 방법은 비교한 다른 모든 타원체 방법에 비해 더 효율적이었다.
