Inexact Proximal Point and Tseng Algorithms with Nonsummable Errors to Solve Monotone Inclusions

본 논문은 티코노프 정규화, 축약 성질 및 R-연속성 이론을 활용하여, 힐베르트 공간에서의 단조 포함 문제를 해결하기 위한 실용적인 부정확 근접 점 알고리즘(Inexact Proximal Point Algorithm)과 쳉 알고리즘(Tseng Algorithm)의 비가산 오차 하에서의 수렴성을 최초로 입증한다.

핵심

당신이 어둡고 안개가 자욱한 방(즉, "해답")의 정확한 중심을 찾으려고 노력하고 있다고 상상해 보십시오. 당신에게는 중심을 향해 가리키는 나침반(알고리즘)이 있습니다. 완벽한 세상이라면, 당신의 나침반은 결함이 없을 것이고 당신은 중심을 향해 똑바로 걸어갈 것입니다.

하지만 현실 세계에서 당신의 나침반은 약간 흔들립니다. 때로는 약간 왼쪽을 가리키고, 때로는 약간 오른쪽을 가리킵니다. 이 "흔들림"이 수학자들이 말하는 **오차(error)**입니다.

오랫동안 수학자들은 당신이 결국 중심에 도달하기 위해서는, 이 흔들리는 오차가 점점 작아져서 완전히 사라져야 한다고 믿었습니다. 그들은 당신의 전체 여정 동안 발생하는 총 "흔들림"의 양이 아주 작고 유한한 수치여야 한다고 생각했습니다. 만약 흔들림이 일정한 수준으로 계속 발생한다면, 당신은 결코 제자리를 맴도는 것을 멈추지 못할 것이라고 생각했습니다.

이 논문은 이렇게 말합니다: "꼭 그렇지는 않습니다. 하지만 중요한 차이가 있습니다."

저자들인 Ba Khiet Le, Boris S. Mordukhovich, 그리고 Michel Théra는 오차가 사라지지 않고 일정한 수준으로 계속 유지되더라도 길을 찾아낼 수 있는 새로운 항해 방법을 발견했습니다. 다만, 이 방법은 당신이 정확한 중심에 도달하게 해주는 것이 아니라, 중심 근처의 아주 작은 영역 안에 안정적으로 머무르게 해줍니다.

다음은 이들이 이를 설명하기 위해 사용한 간단한 비유입니다.

1. 문제: "가산성(Summable)" 규칙

전통적으로, 당신이 중심에 정확히 도달하는 것을 보장하기 위한 규칙은 다음과 같았습니다: 오차는 결국 사라져야 한다.
이것은 바람이 부는 곳을 향해 목표물을 향해 걷는 것과 같습니다. 만약 바람이 점점 약해져서 결국 멈춘다면(오차가 사라진다면), 당신은 결국 목표의 정확한 중심에 도달할 것입니다. 하지만 만약 바람이 일정한 속도로 계속 불고 있다면(오차가 사라지지 않는다면), 전통적인 수학에서는 당신이 결코 그곳에 도달하지 못할 것이라고 말했습니다.

2. 해결책: "자기력(Magnetic Pull)" 추가하기 (티코노프 정규화)

저자들의 비밀 병기는 **티코노프 정규화(Tikhonov regularization)**입니다.
단순히 평평한 바닥 위를 걷는 대신, 중심을 향해 곧장 이어지는 완만한 곡선 경사로를 걷는다고 상상해 보십시오. 설령 바람(오차)이 당신을 옆으로 계속 밀어내더라도, 경사(수학적 "끌림")가 당신을 끊임없이 경로로 다시 끌어당깁니다.

그들의 수학에서는, 문제에 작은 인위적인 "힘"($\epsilon$으로 표현됨)을 추가합니다. 이 힘은 지형을 더 "가파르고" 명확하게 만듭니다. 이는 평평하고 미끄러운 지면을 그릇 모양으로 바꿉니다. 비록 당신이 일정한 오차에 의해 경로를 벗어나도록 밀려나더라도, 그 그릇 모양 덕분에 당신은 영원히 방황하지 않고 중심 근처의 아주 작은 영역 안에 안착하게 됩니다.

중요한 점: 이 방법으로는 당신이 그릇의 가장 깊은 점(정확한 중심)에 완전히 멈추거나 도달하지는 않습니다. 대신, 당신은 그릇 바닥을 중심으로 아주 작은 범위 내에서 계속 살짝 흔들리며 (wobbling) 머무르게 됩니다. 하지만 그 흔들림이 너무 커지지 않고 항상 통제 가능한 범위 안에 머무는 것이 핵심입니다.

3. 두 가지 알고리즘: 등산객과 가이드

이 논문은 이 아이디어를 두 가지 특정 유형의 "등산객"(알고리즘)에 대해 테스트합니다.

• 불완전 근접 점 알고리즘 (Inexact Proximal Point Algorithm, IPPA): 이것은 한 걸음을 내딛고, 지도를 확인하고, 경로를 수정하는 등산객과 같습니다. 저자들은 지도가 약간 흐릿하더라도(오차), "자기력 경사"가 등산객이 목표물의 정확한 중심에 닿지는 못하지만, 목표물과 아주 가까운 안전한 거리 내에서 멈추게 만든다는 것을 보여줍니다.
• 불완전 쳉 알고리즘 (Inexact Tseng Algorithm, ITA): 이것은 두 가지 다른 유형의 지형(두 가지 다른 수학적 연산자)을 동시에 다뤄야 하는 더 복잡한 등산객입니다. 저자들은 이러한 추가적인 복잡성과 지속적인 오차에도 불구하고, "자기력 경사"가 여전히 등산객을 중심 근처의 좁은 영역 안에 머물게 하는 데 효과적임을 보여줍니다.

4. "R-연속성(R-continuity)" 안전망

이것이 작동함을 증명하기 위해, 그들은 R-연속성이라는 개념을 사용합니다.
이것은 *"목표에 가까워지면 당신의 발걸음이 예측 가능해진다"*라고 말하는 안전망과 같습니다. 이는 "자기력의 끌림"이 변덕스럽게 행동하지 않음을 보장합니다. 지도가 중심 근처에서 갑자기 이상하게 뒤틀리지만 않는다면, 등산객은 예측 가능한 거리 내에 머물 것입니다.

5. 결과: "충분히 좋은 것"이면 충분하다

이 논문은 이 새로운 방법을 통해 다음과 같은 결과를 얻을 수 있음을 증명합니다:

• 오차가 반드시 사라질 필요는 없습니다.
• 오차가 아주 작은 숫자로 합쳐질 필요도 없습니다.
• 단지 오차가 고정된 관리 가능한 한계치(예: 항상 2도 이내로 오차가 발생하는 나침반) 내에 머물기만 하면 됩니다.

매개변수를 올바르게 설정한다면, 등산객은 방황을 멈추고 진정한 중심 근처의 작은 거리 안에 안정적으로 머무릅니다. 논문에서는 이를 **"근사 해(approximate solution)"**라고 부릅니다. 정확한 중심에 도달하는 것은 오차가 사라지는(가산성 조건을 만족하는) 옛날 방법의 영역이며, 이 새로운 방법은 오차가 사라지지 않아도 '충분히 좋은' 답을 찾는 데 초점을 맞춥니다.

이 연구가 중요한 이유 (논문에 따르면)

실제 컴퓨터 계산에서 오차를 완전히 없애거나 오차의 합을 아주 작은 숫자로 만드는 것은 종종 불가능합니다. 컴퓨터에는 한계가 있으며, 결코 완전히 사라지지 않는 약간의 "노이즈"나 "반올림 오차"가 항상 존재합니다.

이 논문은 "자기력 경사" 기술을 사용함으로써, 컴퓨터의 오차가 끈질기게 남아있더라도 이 알고리즘들이 충분히 좋은 답을 찾아낼 것이라고 신뢰할 수 있다고 주장합니다. 이는 초점을 "완벽한 정밀도(정확한 중심 도달)"에서 "안정적이고 실용적인 결과(중심 근처 안정화)"로 전환합니다.

실제 세계에서는 오차가 영원히 사라지지 않기 때문에, 우리는 오차가 사라지기를 기다리기보다 **"매번 발생하는 오차가 아주 작은 고정된 한계치 아래에 있는지"**만 확인하면 되는 간단한 규칙이 필요합니다. 이 논문이 제안하는 방법이 바로 그 실용적인 규칙을 제공합니다.

요약하자면: 이 논문은 도구가 불완전하고 오차가 멈추지 않더라도, 오차가 당신을 너무 멀리 밀어내지 못하도록 문제의 형태를 바꿈으로써 여전히 해답의 정확한 중심 근처에 안정적으로 머무를 수 있다는 것을 가르쳐 줍니다. 당신은 정확한 중심에 도달하지는 못하지만, 그 근처에서 멈추는 것이 현실 세계에서는 이미 성공적인 결과입니다.

기술 요약

기술 요약: 비가산 오차를 갖는 부정확 근접 점 및 Tseng 알고리즘

문제 정의
본 논문은 실수 힐베르트 공간 $H$에서 $0 \in Ax$ 형태의 단조 포함 문제를 해결하는 문제를 다룬다. 여기서 $A: H \rightrightarrows H$는 다가(set-valued) 최대 단조 연산자이다. 이 연구의 주요 초점은 두 가지 고전적 알고리즘인 근접 점 알고리즘(Proximal Point Algorithm, PPA)과 Tseng 알고리즘(복합 포함 문제 $0 \in Ax + Bx$에 대한 것)의 실용적인 부정확 버전들의 수렴성에 있다.

이 연구의 핵심적인 제약 사항은 계산 오차를 다루는 방식이다. 기존 문헌 대부분은 오차 수열이 가산(즉, $\sum \|y_k\| < \infty$이므로 오차가 점근적으로 소멸함)된다고 가정하는 것과 달리, 본 논문은 유계이며 비가산적인 오차(bounded, nonsummable errors) 하에서의 알고리즘을 조사한다. 구체적으로 오차 수열 $(y_k)$는 $\|y_k\| \le \delta$ (여기서 $\delta > 0$인 고정된 허용 오차)를 만족한다. 실제 계산 환경에서는 오차 $y_k$가 0 으로 수렴하지 않는 경우가 흔하므로, 이를 다루기 위해 상대적 오차 기준 (실제 검증이 어려운 경우) 과 절대적 유계 오차 기준 (검증이 용이한 경우) 이 제안된다. 본 논문은 검증이 용이한 절대적 유계 오차 조건을 채택하여, 오차가 소멸하지 않더라도 알고리즘이 어떻게 동작하는지를 분석한다.

방법론
저자들은 오차의 가산성에 의존하지 않는 새로운 접근 방식을 제안한다. 대신, 이 방법론은 다음 세 가지 핵심 요소에 기반한다:

1. 티코노프 정규화(Tikhonov Regularization): 원래의 포함 문제는 $\epsilon I$ (여기에서 $\epsilon > 0$)라는 강한 단조 항을 추가함으로써 정규화된다. PPA 의 경우, 연산자는 $\tilde{A} = A + \epsilon I$가 된다. 복합 문제의 경우, 정규화된 포함 관계는 $0 \in \tilde{A}x + Bx$가 된다. 이 정규화는 관련 역 근접 연산자(resolvent operators)가 강한 축약 성질을 갖도록 보장한다.
2. 축약 성질(Contraction Properties): 정규화 항에 의해 유도된 강한 단조성을 활용함으로써, 저자들은 역 근접 연산자(및 관련 Tseng 매핑)가 축약(contractive)됨을 입증한다. 이를 통해 오차가 0 으로 감소할 필요 없이 오차 전파를 제어할 수 있다.
3. R-연속성 이론(R-Continuity Theory): 수렴 분석은 다가 매핑에 대해 최근 개발된 R-연속성 이론을 활용한다. 구체적으로, 저자들은 역 연산자(예: $A^{-1}$ 또는 $(A+B)^{-1}$)가 원점에서 R-연속이라고 가정한다. 이 성질을 통해 저자들은 정규화된 문제의 해와 원래 문제의 해 집합 사이의 거리를 제한할 수 있다.

주요 기여 및 결과

• 부정확 근접 점 알고리즘 (Inexact Proximal Point Algorithm, IPPA):
  본 논문은 $\|y_{k+1}\| \le \delta$라는 유계 오차 가정 하에서 $x_{k+1} = J_{\gamma \tilde{A}}x_k + y_{k+1}$로 정의되는 IPPA 의 거동을 분석한다. 여기서 $y_{k+1}$은 $k$번째 단계에서 역 근접 연산자(resolvent) 또는 근접 연산자(proximal operator)를 평가할 때 발생하는 **계산 오차(inexactness)**를 나타내며, 이는 반복 단계별 계산 오차로 $\delta$라는 작은 양의 허용 오차 범위 내에서 유계로 유지되지만 0 으로 수렴하지는 않는다.

  • 결과: 중요한 점은, 비가산적인 유계 오차 조건 하에서는 반복열 $(x_k)$가 원래 문제의 해 집합 $S$ 내의 특정 점으로 수렴 (converge) 하지 않는다는 것이다. 대신, $(x_k)$는 해 집합 $S$로부터 유계된 거리 내에 점근적으로 머무르는 (asymptotically remains within a bounded distance) 성질을 가진다. 즉, 알고리즘은 정확한 해로 수렴하는 것이 아니라, 오차 크기에 비례하는 '근사 해'의 영역에 안정적으로 머무른다. 저자들은 원래 해 집합 $S = \text{zer}(A)$에 대한 점근적 거리의 구성적인 상한을 도출한다:
    $$\limsup_{k \to \infty} d(x_k, S) \le \delta(1 + \gamma^{-1}\epsilon^{-1}) + \rho(\epsilon a)$$
    여기서 $\rho$는 0 에서의 $A^{-1}$의 R-연속성 계수이며, $a$는 $S$의 최소 노름 원소의 노름이다.
  • 수렴 조건 및 해석: 만약 오차 수열이 가산적 (summable, $\sum \|y_k\| < \infty$) 이라는 고전적인 조건을 만족한다면, $(x_k)$는 약하게 (weakly) 실제 해로 수렴할 수 있다. 그러나 본 논문이 다루는 비가산적 유계 오차 설정에서는 이러한 강한 수렴 결과가 성립하지 않으며, 대신 위와 같이 명시적으로 제한된 거리 내에서의 안정성 (stability) 만이 보장된다. $\delta = \epsilon^2$로 선택하면, $\epsilon \to 0$일 때 상한이 소멸하여 알고리즘이 임의의 정확도를 가진 근사해를 생성할 수 있음을 보이지만, 이는 고정된 $\delta$ 하에서의 수렴이 아님에 유의해야 한다.

• 부정확 Tseng 알고리즘 (Inexact Tseng Algorithm, ITA):
  이 접근 방식은 $B$가 단일 값(single-valued), 단조, 그리고 립시츠 연속인 복합 문제 $0 \in Ax + Bx$로 확장된다. ITA 는 티코노프 정규화된 문제에 적용된다.

  • 결과: $(A+B)^{-1}$이 0 에서 R-연속이라는 가정하에, 저자들은 ITA 수열이 해 집합으로 수렴하지는 않지만, 유계된 거리 내에 점근적으로 머무름을 증명한다. 도출된 오차 상한은 다음과 같다:
    $$d(x_k, S) \le \delta(1 + 2\gamma^{-1}\epsilon^{-1}) + \rho(\epsilon a)$$
  • IPPA 와 마찬가지로, $\delta = \epsilon^2$로 설정하면 정규화 매개변수 $\epsilon$이 0 에 접근함에 따라 이 거리 상한이 줄어들어 해 집합에 더 가까운 근사해를 얻을 수 있으나, 고정된 비가산 오차 하에서는 반복열이 특정 해 점으로 수렴하지 않는다.

의의 및 주장
본 논문은 유계이며 비가산적인 오차만을 가정하여 실용적인 부정확 PPA 및 Tseng 알고리즘의 안정성 (stability) 을 확립한 최초의 문헌임을 주장한다.

저자들은 이러한 알고리즘의 안정성과 적절성(well-posedness)을 보장하는 핵심 메커니즘이 고전적인 오차의 가산성이 아니라, 티코노프 정규화에 의해 유도된 강한 단조성임을 강조한다. 그들은 표준적인 가산성 가정이 실제 계산에서는 보장하기 어려운 경우가 많은 반면, 유계 오차 조건은 계산적으로 더 현실적이라고 주장한다. 특히, 오차가 0 으로 수렴하지 않는 실제 환경에서 알고리즘이 해 집합으로부터 얼마나 멀리 벗어날 수 있는지에 대한 명시적인 상한을 제공함으로써, 알고리즘의 신뢰성을 평가하는 새로운 기준을 제시한다.

제안된 기법들은 비가산적 섭동을 포함하는 최적화 관련 문제의 다른 부정확 알고리즘들을 분석하기 위한 유연한 프레임워크로 확장될 수 있다고 제시된다. 본 논문은 새로운 응용 사례나 실험적 검증을 제안하기보다는, 비가산 오차 조건 하에서 알고리즘이 해로 수렴하지는 않지만 유계된 근사 영역에 머무른다는 이론적 정당화에 집중한다.