A method of projection onto an acute cone with level control in convex minimization

We study a projection method for convex minimization problems. In each step we construct a certain polyhedral function that approximates the objective function from below. The affine pieces of the approximating function are linearizations of the objective function obtained in previous steps. The linearizations are determined by a linearly independent system of subgradients which generates an obtuse cone. The current approximation of the solution is projected onto a sublevel set of the polyhedral function with level which estimates the optimal value and is updated in each iteration. The projection can be easily obtained by solving a system of linear equations and is, actually, the projection onto a translated acute cone dual to the constructed obtuse cone. The construction ensures long steps between successive approximations of the solution. Such long steps are important for the good behavior of the method.