Кусочно-выпуклые формулировки бинарных и перестановочных задач

Хорошо известно, что максимизацию любой разности выпуклых функций можно трансформировать в выпуклую максимизацию; здесь наша цель – получить вместо этого кусочно-выпуклую максимизацию задачи. Несмотря на то, что это может показаться более трудным, иногда размерность может быть уменьшена на единицу и локальный поиск может быть улучшен путем использования экстремальных точек замыкания выпуклой оболочки лучших точек. Мы показываем, что это всегда имеет место как для бинарных, так и для перестановочных задач, и даем, в качестве примера, кусочно-выпуклые формулировки задачи о максимальной клике и квадратичной задачи о назначениях.