Three Ellipsoids for External Approximation of the Half-Ball

Abstract

Introduction. Ellipsoids that approximate the half-ball in Rn (n≥2) and their volume is smaller than the volume of the ball can be used to construct algorithms for solving the problem of minimization of a convex (smooth or non-smooth) function, the problem of minimization of a convex function on a sphere, a general problem convex programming, saddle point problems of convex-concave functions and others. The speed of convergence of such algorithms will be determined by the ratio of the volume of the approximating ellipsoid to the volume of the ball. The purpose of the work is to describe properties of three ellipsoids for approximation of a n-dimensional half-ball, the volume reduction factor of which depends only on n - dimension of space. The first is the well-known ellipsoid of minimum volume, which is used in the classical Yudin-Nemirovsky-Shor ellipsoid method. It provides a minimum volume reduction factor and can be used if n≥2. If n=1, then the classical ellipsoid method replaces the dichotomy method. The other two ellipsoids are close to the minimum volume ellipsoid and at large n guarantee volume reduction coefficients close to the minimum. The results. It is shown that when n=1 the first approximate ellipsoid provides a coefficient of reduction of the segment length equal to 2–√2 ≈ 0.5858. The second approximate ellipsoid is new and the volume reduction factor for it is slightly larger than the factor for the first approximate ellipsoid. If n=1, then it provides a coefficient of reduction of the segment length equal to (√5–1)/2 ≈ 0.6180. For three ellipsoids, comparative results are given in terms of volume reduction coefficients (n=1/20) and the number of iterations for solving problems with relative accuracy 1e-10 (n=1/30). Conclusions. A new ellipsoid has been constructed to approximate the n-dimensional half-ball, which is close in volume to the minimal ellipsoid. The volume reduction factor of the proposed ellipsoid is approximated by an asymptotic formula 1–1/(2n)+1/n², which differs little from the formula 1–1/(2n) for an ellipsoid of minimum volume.

Keywords

• ball
• ellipsoid
• space dilation
• ellipsoid method
• dichotomy method