Синтез секущих и отделяющих плоскостей в одном методе негладкой оптимизации

Abstract

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

Запропоновано алгоритм розв’язання задач недиференційованої оптимізації сім’ї методів відокремлювальних площин з додатковими відсіканнями, породжуваними розв’язком допоміжної задачі методу січних площин. Доведено збіжність цього алгоритму і наведено результати обчислювальних експериментів при розв’язанні транспортних задач. Задачі транспортного типу з обмеженнями на потоки зводяться до задач проекції досить віддаленої точки на допустиму множину.

A general scheme for non-smooth convex optimization based on the separating plane algorithm with additional clippings is considered. The convergence of the algorithm is proved. The results of numerical experiments are given, which demonstrated the overall computational efficiency compared to known leaders in this field. Of especial interest are the computational results applied to projection version of the transportation problems with flow constraints.