- Анализ скорости сходимости рандомизированного и циклического спуска в координатах для выпуклой оптимизации посредством полуопределенного программирования(arXiv)
Автор: Хади Аббасзадехпеивасти, Этьен де Клерк, Муслим Замани
Аннотация: в этой статье мы изучаем рандомизированный и циклический спуск по координатам для выпуклых задач оптимизации без ограничений. Мы улучшаем известные скорости сходимости в некоторых случаях, используя численный метод оценки производительности полуопределенного программирования. В качестве побочного продукта мы предоставляем метод анализа производительности итеративного метода Гаусса-Зейделя в наихудшем случае для линейных систем, где матрица коэффициентов является положительно-полуопределенной с положительной диагональю.
2.Эффективные методы первого порядка для выпуклой оптимизации с сильно выпуклыми функциональными ограничениями(arXiv)
Автор:Чжэньвэй Линь, Ци Дэн
Аннотация:: оптимизация с ограничениями выпуклых функций в последнее время вызывает растущий интерес исследователей. Для специальной выпуклой задачи с сильно выпуклыми функциональными ограничениями мы разрабатываем новый ускоренный прямо-двойственный метод первого порядка, который дает оценку сложности $\Ocal(1/\sqrt{\vep})$, улучшая $\Ocal( 1/{\vep})$ результат для современных методов первого порядка. Ключевым компонентом нашей разработки являются некоторые новые методы для постепенной оценки сильной выпуклости функции Лагранжа, которые обеспечивают адаптивный выбор размера шага и более быструю сходимость. Кроме того, мы показываем, что сложность можно дополнительно улучшить с точки зрения зависимости от некоторого параметра задачи с помощью схемы перезапуска, которая многократно вызывает ускоренный метод. В качестве приложения мы рассматриваем оптимизацию с ограничениями, вызывающую разреженность, которая имеет разделимую выпуклую цель и сильно выпуклое ограничение потерь. В дополнение к достижению быстрой сходимости мы показываем, что перезапущенный метод может эффективно идентифицировать шаблон разреженности (активный набор) оптимального решения за конечные шаги. Насколько нам известно, это первый результат идентификации активного набора для оптимизации с ограничениями, вызывающей разреженность.
