SPEAKER

Analysis of ellipsoidal methods for non-smooth optimization problems

Abstract. We will consider three versions of the ellipsoid method proposed by N.Z. Shor in 1970, 1977, and 1979, which are special cases of Shor’s subgradient method with space dilation in the direction of a subgradient. The first method (1970) finds the minimum point of a convex function if its minimum value and the growth constants m and M of the function are known. The second method (1977) is a well-known classical ellipsoid method, where a hemisphere in n-dimensional space is approximated by an ellipsoid of a minimum volume. In 1979 the first polynomial algorithm for solving a linear programming problem with rational coefficients was constructed on its basis, so it played a crucial role in development of methods for solving such problems. The methods (1979) improve the classical ellipsoid method by using deeper cuts, where a spherical segment and a spherical layer are approximated by ellipsoids of minimum volume. Finally, we will present the ellipsoid (Stetsyuk, 2006), which allows to build accelerated ellipsoid methods by using two consecutive operations of space dilation.