A modification of the inscribed ellipsoid method

An inscribed ellipsoid method is considered for solving a convex programming problem with linear constraints. A new approximate solution is obtained by using the minimizer of the objective function on the current ellipsoid of the maximum volume. It is shown that the number N(ε) of iterations needed to achieve an accuracy ε in the n-dimensional space of feasible solutions is determined by an inequality N(ε) ≤ n · log2(1/ε). One can consider the proposed algorithm as a proof of the existence of a method which has the same estimation of complexity as a dichotomy, and therefore, is theoretically not improvable.