Метод проективных преобразований для задачи минимизации субмодулярной функции

Показано, что метод проективных преобразований Кармаркара, первоначально разработанный для решения задач линейного программирования, без существенных изменений может быть применен для минимизации положительно-однородных выпуклых фукнций. В случае негладких функций для поиска направлений спуска на итерациях метода Кармаркара предлагается использовать метод субградиентов или один из методов отсечений. Данный подход применяется для решения задачи о минимальном среднем значении субмодулярной функции. Показано, что последняя задача эквивалентна классической задаче минимизации субмодулярной функции.