Using two successive subgradients in the ellipsoid method for nonlinear programming (Q1337226)

An improved version of the ellipsoid method for (nonsmooth) convex optimization problems is presented. To speed the convergence of the algorithm the authors provide a possibility of the reduction in ellipsoid volume. For this no extra subgradient evaluation or line search are required. Then new ellipsoids are constructed by special alternative cuts (one-side cuts, parallel cuts, wedge-shaped cuts) which are generated by the data of two consecutive iteration steps of the usual ellipsoid method. The authors show that the proposed cuts do not eliminate any feasible points and that in each step the volume of the generated ellipsoid is smaller than using two consecutive conventional center cuts. A strategy for the selection of the suitable cut in each step is given in the enclosed algorithm. A computational test using randomly generated optimization problems with quadratic objective functions and quadratic constraint functions show a significant reduction in the iteration number and CPU time.