The method of projective transformations for the minimization problem of a submodular function (Q1571242)

It is shown that the method of projective transformations of Karmarkar, which was originally developed for linear programming problems, can be employed without substantial modifications for the minimization of positively homogeneous convex functions. In the case of nonsmooth functions, the subgradient method or a truncation method is used to find descent directions on the iterations of Karmarkar's method. This approach is used for solving the problem of minimal mean value of a submodular function.