An ellipsoid method for minimization of convex function

We consider the generalized ellipsoid method – an algorithm with the space dilation. For a certain choice of the dilation coefficient, this is a method of outer approximation of semi-ellipsoids by ellipsoids with a monotonous decrease in their volume. The Yudin-Nemirovski-Shor ellipsoid method is a specific case. The paper provides properties of two algorithmic realizations of the generalized ellipsoid method. The first algorithm is based on updating nonsymmetric matrix B, as in the Shor ellipsoid method, and the second is based on updating symmetric matrix H = BBT, as in the Yudin-Nemirovski ellipsoid method. We present the Emshor algorithm (Ellipsoid Method of Shor) for computing a solution of the problem of unconstrained minimization of a convex function. It updates nonsymmetric matrix B and uses a stopping criterion that, for a convex function, guarantees to find a point at which the function value does not deviate more than a specified tolerance from the optimal function value. It is shown that the Emshor algorithm finds sufficiently accurate approximations to the minimum point of a ravine convex function, and for functions of twenty variables it takes no longer than a few seconds on a usual PC. Hence, the algorithm can be useful for solving small optimization problems. The Emshor algorithm is planned to be used to develop a dual method for solving a two-stage transportation problem, when the number of intermediate points is not greater than twenty. The computational complexity of the dual method is determined by the complexity of calculating the value of the dual function and its supergradient, for which we need not more than twenty times to find the minimum elements in two one-dimensional arrays whose lengths m and n correspond to the numbers of suppliers and consumers. This means that the dual method can be oriented to the case of large m and n (thousands, tens of thousands), for which solving linear programming problems corresponding to the two-stage transportation problem by general-purpose programs is impossible or requires significant computational resources.