기술 요약: 하다마르 공간에서의 근접 점 알고리즘 및 일반화된 페르마-토리첼리 문제

1. 문제 정의 및 배경

본 논문은 주어진 점 또는 집합들까지의 거리의 합을 최소화하는 점을 찾는 문제를 다루며, 이는 고전적인 페르마-토리첼리(Fermat-Torricelli) 문제의 일반화이다. 이 문제는 유클리드 공간(헤론, 페르마, 토리첼리, 스테이너)에서 풍부한 역사를 가지고 있으며 힐베르트 공간과 리만 다양체로 확장되어 왔으나, 본 연구는 더 넓은 범위인 하다마르 공간(complete CAT(0) 공간) 내에서 작동한다.

저자들은 세 가지 구별된 볼록 최적화 문제를 하나의 프레임워크로 통합하고자 한다:

1. 가중 페르마-토리첼리 문제 (Weighted Fermat-Torricelli Problem).
2. 볼록 타당성 문제 (Convex Feasibility Problem).
3. 최적 근사 문제 (Best Approximation Problem).

구체적인 과제는 하다마르 공간에서 이러한 문제들을 해결하는 데 있으며, 이 공간들은 힐베르트 공간과 같은 전역적인 선형 구조를 결로하고 있다. 따라서 표준적인 도구인 유계 선형 연산자는 연속적인 측지선 보존 사상(metric 의미에서의 affine maps)으로 대체되어야 한다. 본 논문은 다음 사항에 초점을 맞추어 이러한 문제들을 위한 **불완전 순환 분할 근접 점 알고리즘(inexact cyclic splitting proximal point algorithms, SPPA)**의 수렴 특성을 조사한다:

• $\Delta$-수렴 (metric 의미에서의 약수렴).
• 강수렴 속도 (선형 및 초선형).
• 특정 기하학적 조건 하에서의 유한 종료(finite termination).

2. 방법론 및 수학적 프레임워크

2.1 기하학적 및 해석적 기초

본 연구는 하다마르 공간의 기하학을 활용하며, 다음을 기반으로 한다:

• 접 접합(Tangent Cones): 니콜라예프(Nikolaev)의 접근 방식을 따라, 지수 사상(exponential map) 없이 단조성을 다루기 위해 접 접합 $T_x X$를 정의한다. 이를 통해 이론이 비-매니폴드 공간(예: $\mathbb{R}$-trees, 힐베르트 볼)에도 적용될 수 있도록 한다.
• 준선형화(Quasilinearization): 내적 성질을 일반화하기 위해 준 내적(quasi-inner product) $\langle \vec{ab}, \vec{cd} \rangle$를 사용한다.
• 단조 연산자(Monotone Operators): 접 번들 $TX$와 조건 $g_x(\eta, \mu_{x,y}) + g_y(\nu, \mu_{y,x}) \leq 0$을 통해 정의된다. 본 논문은 이러한 연산자에 대한 **전사 조건(surjectivity condition)**을 가정하는데, 이는 힐베르트 공간에서는 자동으로 보장되지만 하다마르 공간에서는 필수적인 가정이다.
• 해상 연산자(Resolvents): 알고리즘은 요시다-모로 정규화(Yosida-Moreau regularization)를 통해 정의되는 단조 연산자 $A$의 해상 연산자 $J_r^A$에 의존한다.

2.2 알고리즘 구조

본 논문은 세 단계의 불완전 순환 분할 근접 점 알고리즘을 제안하고 분석한다:

1. 기본 불완전 PPA (알고리즘 1.1):
   $$\lambda_n d(y_n, x_n)\mu_{y_n, x_n} \in A(y_n), \quad d(x_{n+1}, y_n) \leq \epsilon_n$$
   이는 단일 단조 연산자 $A$의 특이점(singularity)을 근사한다.

2. 단일 합 불완전 순환 SPPA (알고리즘 1.2):
   $f(x) = \sum_{i=1}^m f_i(x)$를 최소화하기 위해 설계되었다. 해상 연산자를 순환적으로 적용한다:
   $$y_n = J_{r_n}^{f_m} \circ \dots \circ J_{r_n}^{f_1}(x_n), \quad d(x_{n+1}, y_n) \leq \epsilon_n$$

3. 이중 합 불완전 순환 SPPA (알고리즘 1.3):
   이중 합 구조를 가진 일반화된 페르마-토리첼리 문제를 위해 설계되었다:
   $$f(x) = \sum_{i=1}^m \sum_{j=1}^{m_i} f_{i,j}(x)$$
   반복 과정은 중첩된 해상 연산자 합성(nested resolvent compositions)을 포함한다:
   $$x_n^{(i,j)} = J_{r_n}^{f_{i,j}}(x_n^{(i,j-1)}), \quad y_n = x_n^{(m, m_m)}$$
   여기서 $d(x_{n+1}, y_n) \leq \epsilon_n$이다.

3. 주요 기여

본 논문은 분할 알고리즘과 정량적 수렴 이론 사이의 간극을 메우며 세 가지 주요 기여를 한다:

1. 속도 이론을 포함한 이중 합 불완전 순환 분할 PPA:
   저자들은 일반화된 페르마-토리첼리 문제를 위해 설계된 이중 합 버전의 순환 분할 알고리즘을 개발하였다. 기존 연구들이 존재성 유형의 수렴(예: $\Delta$-수렴)만을 확립했던 것과 달리, 본 논문은 이러한 특정 분할 스킴에 대한 선형 및 초선형 수렴 속도와 유한 종료 결과를 확립한다.

2. 선형 구조 없는 메트릭 부정규성(Metric Subregularity):
   본 논문은 공간을 선형화하기 위해 지수 사상에 의존하는 대신, 접 접합에서의 거리($d_x(0_x, A(x))$)를 직접 사용하여 메트릭 부정규성을 공식화한다. 이 정의는 매니폴드가 아닌 일반적인 하다마르 공간(예: $\mathbb{R}$-trees 등)에도 적용 가능하며, 힐베르트 공간 및 매니폴드에서 코헨바흐(Kohlenbach) 등의 연구를 일반 CAT(0) 환경으로 확장한다.

3. 측지선 보존 사상을 통한 일반화된 페르마-토리첼리:
   본 논문은 측지선 보존(affine) 사상 및 볼록 부분집합까지의 거리를 포함하는 새로운 형태의 페르마-토리첼리 문제(문제 6.1)를 도입한다. 이는 이전의 선형/힐베르트 공식을 비선형 하다마르 설정으로 확장하여, 가중 거리 최소화, 타당성, 최적 근사를 통합한다.

4. 주요 결과

4.1 수렴 분석

• $\Delta$-수렴: 오차 수열 $\{\epsilon_n\}$이 합산 가능하다는 가정하에, 생성된 수열은 quasi-Fejér monotone이며 $A^{-1}(0)$ 또는 해 집합 $C$로 $\Delta$-수렴함을 보인다.
• 강수렴 및 속도: 메트릭 부정규성(정의 4.1)을 도입함으로써, 연산자가 메트릭 부정규적이면 알고리즘이 선형적으로 수렴함을 증명한다.
  • 초선형 수렴: 특이점 집합이 단일 원소(singleton)이고, 정규성 계수(regularity modulus)가 퇴화하거나(즉, 계수가 0) 근접 파라미터 $\lambda_n$이 소멸하는 경우($\lim \lambda_n = 0$), 수렴은 초선형이 된다.

4.2 유한 종료

본 논문은 법선 콘(normal cones)에 기반한 약한 날카로운 최솟값 유형 조건(weak sharp minima-type condition, 정의 5.1)을 도입한다.

• 문제가 계수 $\alpha$를 갖는 전역적 약한 날카로운 최솟값 유형 조건을 만족하고, 연산자 $A(x)$가 모든 $x$에 대해 단일 원소인 경우, 알고리즘은 유한한 단계 내에 종료된다.
• 이 결과는 약한 날카로움 조건이 메트릭 부정규성을 함의하며, 오차 허용 범위와 단계 크기가 특정 경계를 만족할 때 반복 계산이 해 집합에 정확히 도달하게 함을 보여줌으로써 도출된다.

4.3 일반화된 페르마-토리첼리에의 적용

• 존재성: 본 논문은 목적 함수가 볼록하고 하반연속(lower semicontinuous)임을 증명한다. 강성 가정(조건 F1 및 F2, 정리 6.1) 하에 최솟값이 존재한다.
• 부미분(Subdifferential) 성질: 가중 페르마-토리첼리 문제의 특수한 경우, 부미분이 메트릭 부정규적임을 보여줌으로써 수렴 속도 정리의 적용 가능성을 검증한다.

5. 수치적 검증

이론적 결과는 특정 하다마르 매니폴드($X = \mathbb{R}_{++}$와 특정 메트릭)에서의 수치 실험을 통해 검증된다.

• 예제 7.1 (초선형 수렴): 가중 페르마-토리첼리 문제를 해결한다. 결과는 초기에는 선형 수렴을 보이다가 $\lambda_n \to 0$에 따라 초선형 수렴으로 전환됨을 보여주며, 이는 정리 6.3과 일치한다.
• 예제 7.2 (유한 종료): 최적 근사 문제를 해결한다. 수열이 유한한 반복 횟수 후에 해 집ଥ에 정확히 도달하여 종료됨을 보여줌으로써, 정리 6.4와 약한 날카로운 최솟값 조건을 검증한다.

6. 의의 및 주장

저자들은 이 연구를 두 가지 이전에 구별되었던 연구 흐름의 통합으로 규정한다:

1. 분할 알고리즘: 하다마르 공간에서의 분할 스킴(예: backward-backward 방식)은 주로 수렴 속도나 유한 종료를 다루지 않고 존재성과 약수렴에 집중해 왔다.
2. 정량적 이론: 기존의 속도 분석(예: Kohlenbach 등의 연구)은 주로 힐베르트 공간 내의 단일 연산자 설정에 국한되었거나 매니폴드 구조를 필요로 했다.

본 논문의 주장은 다음과 같다:

• 이 논문은 일반적인 하다마르 공간에서 분할 알고리즘(특히 이중 합 순환 스킴)에 대한 속도 및 유한 종료 이론을 제공하며, 두 연구 분야가 "아직 만나지 못했던" 간극을 메운다.
• 선형 연산자가 측지선 보존 사상으로 대체되는 환경에서도 명시적인 해상 연산자 공식을 통해 페르마-토리첼리 문제의 다루기 쉬운 성질을 유지하며 성공적으로 확장하였다.
• 본 방법론은 기저 공간이 국소 컴팩트(locally compact)이거나 매니폴드일 필요가 없으므로, $\mathbb{R}$-trees나 힐베르트 볼과 같은 공간으로 근접 점 방법의 적용 범위를 넓힌다.

저자들은 프레임워크가 구축되었으나, 향후 자연스러운 연구 방향은 하다마르 공간에서 여러 출력 집합을 포함하는 분할 타당성 문제(split feasibility problems)로 확장하는 것이라고 결론짓는다.