Быстрый ускоренный метод проксимального градиента с новым членом экстраполяции для многокритериальной оптимизации

Основная информация

• ID статьи: 2507.06737
• Название: Fast Accelerated Proximal Gradient Method with New Extrapolation Term for Multiobjective Optimization
• Автор: Huang Chengzhi
• Классификация: math.OC (Оптимизация и управление)
• Дата публикации: 17 октября 2025
• Ссылка на статью: https://arxiv.org/abs/2507.06737

Аннотация

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

Исследовательский контекст и мотивация

1. Решаемая проблема: Задачи многокритериальной оптимизации, в частности, составные неограниченные задачи многокритериальной оптимизации: $\min_{x \in \mathbb{R}^n} F(x) \equiv (f_1(x) + g_1(x), \ldots, f_m(x) + g_m(x))^T$ где $f_i$ — гладкие выпуклые функции, $g_i$ — выпуклые функции (возможно, негладкие).
2. Важность проблемы: Многокритериальная оптимизация широко встречается в практических приложениях, таких как восстановление изображений, сжатое зондирование и другие области. Такие задачи обычно не имеют единственного оптимального решения, а состоят из множества решений, образующих множество оптимальных по Парето решений.
3. Ограничения существующих методов:
   • Tanabe и др. расширили FISTA на многокритериальную оптимизацию, достигнув скорости сходимости $O(1/k^2)$
   • Работы Sonntag и др. и Zhang и др. имеют неполные теоретические доказательства; их анализ сходимости зависит от неотрицательности вспомогательной функции $\sigma(z) = \min_{i=1,\ldots,m} F_i(x_k) - F_i(z)$, что трудно гарантировать
4. Исследовательская мотивация: Преодолеть недостатки теоретического анализа существующих методов, предложить метод с более мягкими требованиями к начальной оценке констант Липшица и избежать зависимости от неотрицательности $\sigma$ через ключевые свойства равенства.

Основные вклады

1. Предложена новая схема члена экстраполяции: Используется форма экстраполяции $y_k = x_k + \frac{k+\alpha-4}{k+\alpha-1}(x_k - x_{k-1})$, где $\alpha \geq 3$
2. Установлены мягкие начальные условия: Требуются лишь слабые начальные условия для последовательности оценок констант Липшица
3. Выведены ключевые свойства равенства: Избегается зависимость от неотрицательности вспомогательной функции, совершенствуется теоретический анализ
4. Доказана сублинейная скорость сходимости: В гладком случае достигается скорость $O(1/k^2)$, в негладком случае — $O(1/k)$
5. Расширение на негладкий случай: Полностью негладкие задачи многокритериальной оптимизации обрабатываются с помощью техники сглаживания

Подробное описание метода

Определение задачи

Рассматривается составная неограниченная задача многокритериальной оптимизации (MOP): $\min_{x \in \mathbb{R}^n} F(x) = (f_1(x) + g_1(x), \ldots, f_m(x) + g_m(x))^T$

где:

• $f_i: \mathbb{R}^n \to \mathbb{R}$ — непрерывно дифференцируемые выпуклые функции
• $g_i: \mathbb{R}^n \to \mathbb{R}$ — выпуклые функции (возможно, негладкие)
• Цель — найти слабо оптимальное по Парето решение

Архитектура модели

Алгоритм для гладкого случая (Algorithm 1)

Основная подзадача: $\min_{z \in \mathbb{R}^n} \phi_{L(f)}(z; x, y) = \max_{i=1,\ldots,m}[\langle\nabla f_i(y), z-y\rangle + g_i(z) + f_i(y) - F_i(x)] + \frac{L(f)}{2}\|z-y\|^2$

Шаги алгоритма:

1. Вычисление точки экстраполяции: $y_k = x_k + \frac{k+\alpha-4}{k+\alpha-1}(x_k - x_{k-1})$
2. Решение подзадачи: $x_{k+1} = p_{s_k}(x_k, y_k)$
3. Обновление параметра: $s_{k+1} = \eta s_k$, где $\eta = \frac{(k+\alpha-2)^2}{(k+\alpha-1)(k+\alpha-3)}$

Условия на параметры:

• При $\alpha > 3$: $0 < \frac{\alpha-2}{\alpha-3}s_0 < \frac{1}{L(f)}$
• При $\alpha = 3$: $0 < s_0 < \frac{1}{L(f)}$

Алгоритм для негладкого случая (Algorithm 2)

Через функцию сглаживания $\tilde{f}_i(x, \mu)$ аппроксимируются негладкие функции $f_i(x)$, где функция сглаживания удовлетворяет:

• Непрерывная дифференцируемость: для фиксированного $\mu > 0$, $\tilde{f}(\cdot, \mu)$ непрерывно дифференцируема
• Согласованность: $\lim_{z \to x, \mu \downarrow 0} \tilde{f}(z, \mu) = f(x)$
• Согласованность градиентов: $\{\lim_{z \to x, \mu \downarrow 0} \nabla\tilde{f}(z, \mu)\} \subseteq \partial f(x)$

Технические инновации

1. Новая конструкция коэффициентов экстраполяции: Через специфический способ обновления параметров $\eta = \frac{(k+\alpha-2)^2}{(k+\alpha-1)(k+\alpha-3)}$ обеспечивается, что $s_k < \frac{1}{L(f)}$ всегда выполняется
2. Вывод ключевых свойств равенства: Через тщательные алгебраические манипуляции и выбор параметров избегается зависимость от неотрицательности $\sigma_k(z)$
3. Единая схема: При $\alpha = 3$ вырождается в существующие методы, но обеспечивает более полный теоретический анализ

Экспериментальная установка

Наборы данных

В статье упоминаются численные эксперименты на трех трёхкритериальных задачах оптимизации:

• Задача BK1&ℓ1
• Задача JOS1&ℓ1
• Задача SP1&ℓ1

Метрики оценки

Используется функция достоинства $u_0(x) = \sup_{z \in \mathbb{R}^n} \min_{i=1,\ldots,m}[F_i(x) - F_i(z)]$ для оценки производительности алгоритма, которая удовлетворяет:

• $u_0(x) \geq 0$ для всех $x$
• $x$ оптимально по Парето тогда и только тогда, когда $u_0(x) = 0$

Детали реализации

• Критерий остановки: $\|x_k - x_{k+1}\| < \varepsilon$
• Для негладкого случая также требуется $\mu_k < \varepsilon$
• Обновление параметров: $\mu_{k+1} = \frac{k+\alpha-2}{k+\alpha-1}\mu_k$, $s_{k+1} = \frac{k+\alpha-2}{k+\alpha-3}s_k$

Результаты экспериментов

Основные результаты

В статье представлены графики фронта Парето для трех трёхкритериальных задач оптимизации, однако конкретные численные результаты и данные сравнения производительности в предоставленном документе неполные.

Теоретические результаты сходимости

Гладкий случай (Theorem 4.3): $u_0(x_k) \leq \frac{L(f)(\alpha-1)^2}{2(k+\alpha-1)^2}R$ достигается скорость сходимости $O(1/k^2)$.

Негладкий случай (Theorem 6.2): $u_0(x_{k+1}) \leq O\left(\frac{1}{k}\right)$ достигается скорость сходимости $O(1/k)$.

Связанные работы

1. Расширение многокритериального FISTA: Tanabe и др. впервые расширили FISTA на многокритериальную оптимизацию, достигнув скорости сходимости $O(1/k^2)$
2. Монотонные варианты: Nishimura и др. предложили монотонный вариант многокритериального FISTA
3. Обобщённая схема: Tanabe и др. расширили схему на однокритериальный случай путём введения гиперпараметра
4. Схемы типа Нестерова: Sonntag и др. и Zhang и др. попытались использовать более эффективные члены экстраполяции, но теоретический анализ неполный
5. Негладкие методы: Gebken и др. предложили алгоритм субградиентного спуска для негладкой многокритериальной оптимизации

Заключение и обсуждение

Основные выводы

1. Предложен ускоренный метод проксимального градиента с новым членом экстраполяции, применимый к гладкой и негладкой многокритериальной оптимизации
2. Установлена полная теория сходимости, избегающая теоретических недостатков существующих методов
3. Гладкий случай достигает скорости сходимости $O(1/k^2)$, негладкий случай — $O(1/k)$

Ограничения

1. Недостаточная экспериментальная часть: Результаты численных экспериментов представлены неполно, отсутствуют детальные сравнения производительности
2. Ограничения выбора параметров: Имеются специфические требования к начальному параметру $s_0$ и $\alpha$
3. Более медленная сходимость в негладком случае: По сравнению с гладким случаем, скорость сходимости негладкой версии снижается до $O(1/k)$

Направления будущих исследований

1. Исследование лучших техник сглаживания для повышения скорости сходимости в негладком случае
2. Изучение стратегий адаптивного выбора параметров
3. Расширение на задачи многокритериальной оптимизации с ограничениями

Глубокая оценка

Преимущества

1. Значительный теоретический вклад: Решены ключевые недостатки теоретического анализа существующих методов, обеспечено полное доказательство сходимости
2. Искусное проектирование метода: Специфическая стратегия обновления параметров обеспечивает теоретические гарантии алгоритма
3. Единство схемы: Гладкий и негладкий случаи объединены в единую схему
4. Математическая строгость: Доказательства детальны, логика ясна

Недостатки

1. Недостаточная экспериментальная проверка: Часть численных экспериментов слишком проста, отсутствуют детальные сравнения с другими передовыми методами
2. Отсутствие анализа практичности: Недостаёт глубокого анализа вычислительной сложности и практических сценариев применения
3. Не обсуждена чувствительность к параметрам: Не проанализировано влияние выбора параметров на производительность алгоритма

Влияние

1. Высокая теоретическая ценность: Обеспечивает более совершенную теоретическую базу для ускоренных методов многокритериальной оптимизации
2. Практическая ценность требует проверки: Необходимы дополнительные эксперименты для проверки эффективности на практических задачах
3. Хорошая воспроизводимость: Описание алгоритма ясно, теоретический анализ полный

Применимые сценарии

1. Задачи многокритериальной оптимизации с составной структурой
2. Приложения в обработке изображений и сжатом зондировании
3. Сценарии оптимизации, требующие теоретических гарантий

Библиография

В статье цитируются важные работы в области многокритериальной оптимизации, включая:

• Основополагающие работы Tanabe и др. по многокритериальному FISTA
• Теорию ускоренных методов Нестерова
• Литературу по техникам сглаживания
• Классическую теорию многокритериальной оптимизации

Общая оценка: Это статья с выдающимся теоретическим вкладом, успешно решившая теоретические недостатки существующих ускоренных методов проксимального градиента для многокритериальной оптимизации и обеспечившая полный анализ сходимости. Однако статья имеет возможности для улучшения в области экспериментальной проверки и анализа практичности.