2025-11-10T02:43:53.338320

Fast Accelerated Proximal Gradient Method with New Extrapolation Term for Multiobjective Optimization

Huang

In this paper, we propose a novel extrapolation coefficient scheme within a new extrapolation term and develop an accelerated proximal gradient algorithm. We establish that the algorithm achieves a sublinear convergence rate. The proposed scheme only requires the Lipschitz constant estimate sequence to satisfy mild initial conditions, under which a key equality property can be derived to support the convergence analysis. Numerical experiments are provided to demonstrate the effectiveness and practical performance of the proposed method.

academic

다목적 최적화를 위한 새로운 외삽 항을 포함한 빠른 가속 근접 경사 방법

기본 정보

논문 ID: 2507.06737
제목: Fast Accelerated Proximal Gradient Method with New Extrapolation Term for Multiobjective Optimization
저자: Huang Chengzhi
분류: math.OC (최적화 및 제어)
발표 시간: 2025년 10월 17일
논문 링크: https://arxiv.org/abs/2507.06737

초록

본 논문은 새로운 외삽 계수 방안과 외삽 항을 제안하고, 가속 근접 경사 알고리즘을 개발했습니다. 이 알고리즘은 준선형 수렴률을 달성합니다. 제안된 방안은 Lipschitz 상수 추정 수열이 온화한 초기 조건만을 만족하도록 요구하며, 이 조건 하에서 수렴성 분석을 지원하는 핵심 등식 성질을 도출할 수 있습니다. 수치 실험은 제안된 방법의 유효성과 실제 성능을 검증합니다.

연구 배경 및 동기

해결해야 할 문제: 다목적 최적화 문제, 특히 복합 무제약 다목적 최적화 문제: $\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$ 는 볼록 함수(비매끄러울 수 있음)입니다.
문제의 중요성: 다목적 최적화는 이미지 복원, 압축 센싱 등 실제 응용에서 광범위하게 존재합니다. 이러한 문제는 일반적으로 단일 최적해가 존재하지 않으며, 파레토 최적해로 구성된 해 집합이 존재합니다.
기존 방법의 한계:
- Tanabe 등이 FISTA를 다목적 최적화로 확장하여 $O(1/k^2)$ 수렴률을 달성했습니다.
- Sonntag 등과 Zhang 등의 연구에서 이론적 증명이 불완전한 문제가 있으며, 수렴성 분석이 보조 함수 $\sigma(z) = \min_{i=1,\ldots,m} F_i(x_k) - F_i(z)$ 의 비음성에 의존하는데, 이 조건은 보장하기 어렵습니다.
연구 동기: 기존 방법의 이론 분석 결함을 극복하고, Lipschitz 상수의 초기 추정에 대한 요구를 더 온화하게 하며, 핵심 등식을 통해 $\sigma$ 의 비음성에 대한 의존성을 피합니다.

핵심 기여

새로운 외삽 항 방안 제안: $y_k = x_k + \frac{k+\alpha-4}{k+\alpha-1}(x_k - x_{k-1})$ 의 외삽 형태 사용, 여기서 $\alpha \geq 3$
온화한 초기 조건 수립: Lipschitz 상수 추정 수열이 더 약한 초기 조건만을 만족하도록 요구
핵심 등식 성질 도출: 보조 함수의 비음성에 대한 의존성을 피하고 이론 분석을 완성
준선형 수렴률 증명: 매끄러운 경우 $O(1/k^2)$ 수렴률, 비매끄러운 경우 $O(1/k)$ 수렴률 달성
비매끄러운 경우로 확장: 평활화 기법을 통해 완전히 비매끄러운 다목적 최적화 문제 처리

방법 상세 설명

작업 정의

복합 무제약 다목적 최적화 문제(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$

알고리즘 단계:

외삽점 계산: $y_k = x_k + \frac{k+\alpha-4}{k+\alpha-1}(x_k - x_{k-1})$
부분 문제 해결: $x_{k+1} = p_{s_k}(x_k, y_k)$
매개변수 업데이트: $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)$

기술적 혁신점

새로운 외삽 계수 설계: 특정 매개변수 업데이트 방식 $\eta = \frac{(k+\alpha-2)^2}{(k+\alpha-1)(k+\alpha-3)}$ 을 통해 $s_k < \frac{1}{L(f)}$ 가 항상 성립하도록 보장
핵심 등식 도출: 정교한 대수 조작과 매개변수 선택을 통해 $\sigma_k(z)$ 의 비음성에 대한 의존성 회피
통일된 프레임워크: $\alpha = 3$ 일 때 기존 방법으로 축퇴되지만 더 완전한 이론 분석 제공

실험 설정

데이터 집합

논문은 세 개의 삼목적 최적화 문제의 수치 실험을 언급합니다:

BK1&ℓ1 문제
JOS1&ℓ1 문제
SP1&ℓ1 문제

평가 지표

merit 함수 $u_0(x) = \sup_{z \in \mathbb{R}^n} \min_{i=1,\ldots,m}[F_i(x) - F_i(z)]$ 를 사용하여 알고리즘 성능을 평가하며, 이 함수는 다음을 만족합니다:

모든 $x$ 에 대해 $u_0(x) \geq 0$
$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$