Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Введение
Алгоритм оптимизации
Алгоритм Фрэнка — Вулфа — это итеративный алгоритм оптимизации первого порядка для задач выпуклой оптимизации с ограничениями. Также известный как метод условного градиента, метод уменьшенного градиента и метод выпуклых комбинаций, этот метод был впервые предложен Маргаритой Франк и Филиппом Вулфом в 1956 году. На каждой итерации алгоритм Фрэнка — Вулфа рассматривает линейное приближение целевой функции и направляется к минимизатору этой линейной функции (на той же области определения).
Optimization algorithm
The Frank–Wolfe algorithm is an iterative first order optimization algorithm for constrained convex optimization. Also known as the conditional gradient method, reduced gradient algorithm and the convex combination algorithm, the method was originally proposed by Marguerite Frank and Philip Wolfe in 1956. In each iteration, the Frank–Wolfe algorithm considers a linear approximation of the objective function, and moves towards a minimizer of this linear function (taken over the same domain).
Свойства
В то время как конкурирующие методы, такие как градиентный спуск для оптимизации с ограничениями, требуют шага проекции обратно к допустимому множеству на каждой итерации, алгоритм Фрэнка — Вулфа требует только решения выпуклой задачи над тем же множеством на каждой итерации и автоматически остается в допустимом множестве. Скорость сходимости алгоритма Фрэнка — Вулфа в общем случае является сублинейной: ошибка в целевой функции к оптимальному значению после k итераций составляет , при условии, что градиент липшиц-непрерывен относительно некоторой нормы. Такая же скорость сходимости может быть показана, если подзадачи решаются лишь приближенно. Итерации алгоритма всегда могут быть представлены как разреженная выпуклая комбинация крайних точек допустимого множества, что способствовало его популярности для разреженной жадной оптимизации в задачах машинного обучения и обработки сигналов, а также, например, для оптимизации потоков минимальной стоимости в транспортных сетях. Если допустимое множество задано набором линейных ограничений, то подзадача, которую необходимо решить на каждой итерации, становится задачей линейного программирования. Хотя скорость сходимости в худшем случае с не может быть улучшена в общем случае, более быстрая сходимость может быть достигнута для специальных классов задач, таких как некоторые сильно выпуклые задачи.
While competing methods such as gradient descent for constrained optimization require a projection step back to the feasible set in each iteration, the Frank–Wolfe algorithm only needs the solution of a convex problem over the same set in each iteration, and automatically stays in the feasible set. The convergence of the Frank–Wolfe algorithm is sublinear in general: the error in the objective function to the optimum is after k iterations, so long as the gradient is Lipschitz continuous with respect to some norm. The same convergence rate can also be shown if the sub problems are only solved approximately. The iterations of the algorithm can always be represented as a sparse convex combination of the extreme points of the feasible set, which has helped to the popularity of the algorithm for sparse greedy optimization in machine learning and signal processing problems, as well as for example the optimization of minimum–cost flows in transportation networks. If the feasible set is given by a set of linear constraints, then the subproblem to be solved in each iteration becomes a linear program. While the worst case convergence rate with can not be improved in general, faster convergence can be obtained for special problem classes, such as some strongly convex problems.