On the role of semismoothness in nonsmooth numerical analysis: Theory

본 논문은 단일값 사상의 세미스무스 도함수와 다치 사상의 세미스무스* 성질 간의 상호작용, 특히 매개변수 세미스무스* 포함식의 해 사상에 대한 세미스무스 도함수의 역할을 제한 코도함수나 SC 도함수와 같은 일반화된 도함수를 통해 규명하고, 이를 통해 세미스무스* 다치 사상의 엄밀 프로토 미분 가능성에 대한 결과를 도출합니다.

핵심

이 논문은 수학의 '매끄럽지 않은 (Nonsmooth)' 문제들을 컴퓨터로 푸는 방법에 대한 연구입니다. 보통 우리가 수학 문제를 풀 때는 곡선이 부드럽게 이어져 있어 미분 (기울기) 을 쉽게 구할 수 있지만, 현실 세계의 많은 문제 (예: 최적화, 게임 이론, 공학 설계) 는 꺾인 부분이나 불연속적인 부분이 많아 '미분'이라는 도구가 통하지 않습니다.

이 논문은 그런 뾰족하고 거친 문제를 해결하기 위해, 완벽한 미분값 대신 '반-매끄러운 (Semismooth)' 근사값을 어떻게 사용하면 좋은지, 그리고 그 이론적 근거를 다룹니다.

이 복잡한 내용을 일상적인 비유로 쉽게 설명해 드릴게요.

---

1. 핵심 개념: "완벽한 지도가 없다면, 나침반만으로도 갈 수 있다"

상황:
산에서 정상으로 올라가야 한다고 상상해 보세요.

• 부드러운 산 (미분 가능): 경사가 일정하게 이어져 있어, 어디에 서든 "이쪽으로 30 도 기울어져 있다"고 정확히 알 수 있습니다. (기존의 미분법)
• 거친 산 (비미분 가능): 바위와 절벽이 섞여 있어, 특정 지점에서는 "어느 쪽이 위로 올라가는지" 정확히 알 수 없거나 여러 방향이 동시에 존재할 수 있습니다. ( Clarke 의 일반화 미분)

이 논문의 주장:
"완벽한 지도 (정확한 미분값) 를 구하는 건 너무 어렵고 비쌉니다. 대신, **대충 방향을 알려주는 나침반 (반-매끄러운 도함수)**만 있으면 충분합니다. 이 나침반이 '반-매끄러운' 성질 (약간의 오차는 있지만 전체적인 흐름은 맞는 성질) 을 갖기만 한다면, 컴퓨터 알고리즘이 정상에 도달할 수 있습니다."

2. 세 가지 주요 발견 (비유로 설명)

① "나침반"의 종류가 다양해도 괜찮다 (단일 함수의 반-매끄러움)

기존에는 문제를 풀 때 '클라크 (Clarke) 일반화 미분'이라는 아주 엄격한 나침반을 써야 한다고 믿었습니다. 하지만 이 논문은 **"어떤 나침반이든, 그 나침반이 '반-매끄러운' 성질만 지니고 있다면, 그걸로 충분하다"**고 증명했습니다.

• 비유: 정상에 가는 길에 '정확한 GPS'가 없어도, '대충 북쪽을 가리키는 나침반'만 있다면 길 잃지 않고 갈 수 있다는 뜻입니다. 게다가 이 나침반은 거의 모든 곳에서 실제 방향과 일치한다는 것도 증명했습니다.

② "복잡한 시스템"을 단순화하는 뼈대 (SCD 매핑)

문제에 여러 변수가 얽혀 있고, 어떤 함수가 '여러 값을 가질 수 있는' (Set-valued) 경우를 다룹니다. 예를 들어, "이 입력을 주면 가능한 출력은 A, B, C 중 하나다"라고 할 때, 정확한 미분을 구하는 건 매우 복잡합니다.

• 비유: 거대한 기계 장치가 있다고 칩시다. 모든 기어와 스프링을 다 분석하는 건 불가능합니다. 하지만 이 논문은 **"이 기계의 핵심 뼈대 (SCD, Subspace Containing Derivative) 만 분석하면, 전체 시스템의 움직임을 예측할 수 있다"**고 말합니다.
• 이 '뼈대'를 이용하면, 복잡한 시스템에서도 마치 단순한 기계처럼 미분 계산을 할 수 있게 되어 계산이 훨씬 빨라집니다.

③ "숨겨진 관계"를 찾아내는 법 (해의 매핑)

실제 문제는 보통 "A 를 최소화하라. 단, B 라는 조건이 만족되어야 한다"는 형태입니다. 여기서 B 조건을 만족하는 해 (Solution) 를 찾아내는 과정이 복잡합니다.

• 비유: 요리사 (최적화 알고리즘) 가 요리를 하려면, 먼저 재료를 구해야 합니다. 재료상점 (조건 B) 이 복잡하게 돌아서 재료를 주는 방식이 불규칙하다면 요리사는 당황합니다.
• 이 논문은 **"재료상점의 움직임이 '반-매끄러운' 성질을 가진다면, 요리사는 그 불규칙함 속에서도 안정적으로 요리를 완성할 수 있다"**는 이론을 제시합니다. 이를 통해 복잡한 2 단계 최적화 문제 (Bilevel Programming) 를 해결하는 새로운 방법을 제안합니다.

3. 왜 이것이 중요한가요? (실생활 적용)

이 이론은 단순히 수학책에 남는 이야기가 아니라, 실제 컴퓨터 알고리즘에 적용됩니다.

• 기존 방식: 정확한 미분값을 찾으려다 계산이 너무 오래 걸리거나, 아예 계산이 안 되는 경우가 많았습니다.
• 이 논문의 방식: "완벽한 값" 대신 "충분히 좋은 근사값 (나침반)"을 사용하면, 컴퓨터가 훨씬 빠르게 정답에 수렴합니다.
• 적용 예시:
  • 공학적 설계: 비행기 날개 모양을 최적화할 때, 공기역학 방정식이 불연속적인 경우.
  • 경제학/게임: 여러 이해관계자가 얽힌 시장 균형점을 찾을 때.
  • 머신러닝: 손실 함수가 뾰족한 부분을 가질 때 학습 속도를 높이는 것.

4. 요약: 한 줄로 정리하면?

"완벽한 지도가 없는 험난한 산 (비미분 문제) 에서, 우리는 정확한 미분값 대신 '반-매끄러운 나침반'을 사용하면 정상에 도달할 수 있으며, 이 나침반을 만드는 새로운 규칙 (SCD) 을 발견하여 복잡한 문제도 쉽게 풀 수 있다."

이 논문은 수학적으로 매우 엄밀한 증명을 통해, **"추측과 근사가 어떻게 체계적인 계산으로 이어질 수 있는지"**에 대한 강력한 이론적 토대를 마련했습니다. 앞으로 이 방법을 쓰면, 기존에 풀기 너무 어려워서 포기했던 복잡한 문제들도 컴퓨터가 해결할 수 있게 될 것입니다.

기술 요약

1. 연구 배경 및 문제 제기

• 비매끄러운 최적화 문제의 수치해: 비매끄러운 (nonsmooth) 최적화 문제, 방정식, 포함식 (inclusion) 을 수치적으로 해결할 때, 정확한 일반화된 야코비안 (generalized Jacobian) 이나 서브그래디언트 (subgradient) 를 구하는 것이 항상 필수적인 것은 아닙니다. 대신, 특정 반매끄러움 (semismoothness) 성질을 만족하는 '반매끄러운 도함수 (semismooth derivative)'만 존재하면 충분할 수 있습니다.
• 기존 접근법의 한계:
  • 번들 방법 (Bundle Methods): 최적화 문제 해결 시 클라크 (Clarke) 서브그래디언트 대신 '의사그래디언트 (pseudogradient)'를 사용하는 경우, 이는 반매끄러움 성질을 만족하지만 원래 함수가 약한 반매끄러움 (weakly semismooth) 일 필요는 없습니다.
  • 반매끄러운 뉴턴 방법: 무한 차원 공간이나 일반화된 포함식 (set-valued inclusions) 의 경우, 클라크 일반화된 야코비안이 존재하지 않거나 계산이 불가능할 수 있습니다.
  • 암시적 프로그래밍 (ImP) 접근법: 계층적 최적화 (bilevel programming) 나 균형 제약 조건이 있는 수학적 계획 (MPEC) 문제와 같이 $0 \in F(x, y)$형태의 제약이 있는 문제를 풀 때, 하위 문제의 해$\sigma(x)$를 이용해 목적함수를 축소 ($\theta(x) = \phi(x, \sigma(x))$) 하는 방식이 널리 쓰입니다. 그러나$\sigma(x)$가 단일 값이 아니거나 국소 리프시츠 (Lipschitz) 성질이 보장되지 않을 경우, 축소된 목적함수$\theta$ 의 서브그래디언트를 구하기 어렵습니다.
• 핵심 질문: 단일 값 함수의 반매끄러움과 다치 함수 (multifunctions) 의 '반매끄러움*' (semismooth*) 성질 사이의 상호작용을 어떻게 체계화하여, 이러한 복잡한 문제들의 수치적 해법을 위한 이론적 기반을 마련할 수 있는가?

2. 방법론 및 주요 개념

저자는 기존의 반매끄러움 개념을 확장하고 새로운 개념들을 도입하여 이론적 체계를 구축했습니다.

• $\Psi$-반매끄러움 ($\Psi$-semismoothness):

  • 단일 값 함수 $F$ 가 특정 다치 함수 $\Psi$ (예: 일반화된 야코비안의 집합) 에 대해 반매끄러울 때를 정의합니다.
  • 이는 점 (solution point) 에서뿐만 아니라 정의역 전체에서 성립해야 하며, Norkin 의 일반화 미분 개념과 밀접하게 연관됩니다.
  • $\Psi$-반매끄러움은 $F$ 가 국소 리프시츠 연속임을 보장하며, 거의 모든 점에서 엄밀 미분가능 (strictly differentiable) 하고, $\Psi$ 와 일반화된 야코비안이 거의 모든 점에서 일치함을 보입니다.

• 다치 함수의 $\Gamma$-반매끄러움 ($\Gamma$-semismooth):**

  • 다치 함수 $F$ 에 대해, limiting coderivative ($D^*F$) 대신 더 넓은 집합 $\Gamma$ 를 사용하여 반매끄러움* 성질을 정의합니다.
  • 이는 코디버ivat(derivative) 계산 규칙이 포함식 (inclusion) 형태를 가질 때, 정확한 코디버ivat 대신 $\Gamma$ 의 원소를 사용하여도 수렴성이 보장됨을 의미합니다.

• SCD-반매끄러움 (SCD-semismooth):**

  • SCD(Subspace Containing Derivative): 다치 함수의 그래프 접선 공간이 부분공간을 포함하는 성질을 가진 mappings 에 초점을 맞춥니다.
  • SCD-반매끄러움* 은 SCD mapping 에 대해 정의되며, 이는 B-Jacobian 의 다치 함수 일반화로 볼 수 있습니다.
  • 그래프 리프시츠 (Graphically Lipschitzian) 매핑: 좌표 변환 후 리프시츠 단일 값 함수의 그래프와 일치하는 매핑에 대해, SCD-반매끄러움* 성질은 변환된 함수의 G-반매끄러움 (Gowda-semismooth) 성질과 동치임을 증명했습니다.

• 해 매핑 (Solution Map) 의 분석:

  • 포함식 $0 \in F(x, y)$의 해 매핑$S(x)$에 대해,$F$의 SCD-반매끄러움* 성질과 자격 조건 (qualification condition) 하에서$S(x)$의 국소 선택 (local selection)$\sigma(x)$가$\Psi$-반매끄러움임을 증명했습니다.
  • 이를 통해 축소된 목적함수 $\theta(x) = \phi(x, \sigma(x))$ 도 반매끄러운 도함수를 가짐을 보였습니다.

3. 주요 결과 및 이론적 발견

1. 단일 값 함수의 반매끄러움과 G-반매끄러움의 동치:

   • 열린 집합 위에서 단일 값 함수가 어떤 $\Psi$-반매끄러움 도함수를 가질 필요충분조건은 그 함수가 G-반매끄러움 (Gowda-semismooth) 임을 증명했습니다.
   • 이는 함수가 거의 모든 점에서 엄밀 미분가능하며, 반매끄러운 도함수가 일반화된 클라크 야코비안과 거의 모든 점에서 일치함을 의미합니다.

2. 그래프 리프시츠 매핑의 성질:

   • 그래프 리프시츠 매핑이 SCD-반매끄러움* 일 필요충분조건은 변환된 함수가 G-반매끄러움임을 보였습니다.
   • 부산물: SCD-반매끄러움* 매핑은 거의 모든 점에서 엄밀 프로 - 미분가능 (strictly proto-differentiable) 이며, SC 도함수는 거의 모든 곳에서 단일 집합 (singleton) 이 되어 계산이 용이함을 증명했습니다.

3. 해 매핑의 반매끄러움성:

   • 포함식 $0 \in F(x, y)$의 해 매핑$S(x)$에 대해,$F$가 SCD-반매끄러움* 이고 적절한 자격 조건을 만족하면,$S(x)$의 연속 국소 선택$\sigma(x)$는$\Psi$-반매끄러움임을 증명했습니다.
   • 구체적으로, $\sigma(x)$ 의 반매끄러운 도함수는 $F$ 의 SC 코디버ivat ($S^*F$) 를 이용하여 명시적으로 구성할 수 있습니다.

4. 계산 규칙 (Calculus Rules):

   • 일반화된 미분 계산 규칙이 보통 포함식 형태를 띠는 반면, 반매끄러운 도함수의 계산 규칙은 다시 반매끄러운 도함수를 산출합니다. 이는 번들 방법 (bundle methods) 과 같은 수치 알고리즘에 매우 유리합니다.

4. 적용 사례 및 알고리즘

• 알고리즘 제안:

  • 제안된 이론을 바탕으로, 축소된 문제 (1.4) 를 해결하기 위한 두 가지 구현 가능한 알고리즘적 체계를 제시했습니다.
  • 이는 $F$ 의 limiting coderivative 또는 SC 도함수를 통해 $\theta$ 의 반매끄러운 도함수를 계산하는 '오라클 (oracle)'을 제공합니다.
  • 이 오라클은 번들 방법 (예: BT 알고리즘) 과 결합되어, 기존의 ImP 접근법이 적용되지 않던 영역 (예: 해가 단일 값이 아니거나 국소 리프시츠가 보장되지 않는 경우) 에서도 수렴성을 보장합니다.

• 수치 예시:

  • 비선형 2 단계 최적화 (bilevel programming) 문제를 다루는 학술적 예제를 통해 방법론을 검증했습니다.
  • 하위 문제의 해가 단일 값이 아닌 경우에도, 제안된 SCD 기반 오라클을 사용하여 BT 알고리즘이 성공적으로 최적점에 수렴함을 보였습니다.

5. 의의 및 결론

• 이론적 통합: 단일 값 함수의 반매끄러움과 다치 함수의 반매끄러움* 개념을 통합하여, 복잡한 비매끄러운 최적화 문제 (특히 균형 제약 조건이 있는 문제) 에 대한 이론적 기반을 강화했습니다.
• 수치해석적 기여:
  • 정확한 클라크 서브그래디언트나 일반화된 야코비안을 계산할 필요 없이, 반매끄러운 도함수 (예: SC 도함수) 만으로도 번들 방법 등의 알고리즘이 수렴함을 보였습니다.
  • 이는 무한 차원 문제나 해가 유일하지 않은 문제와 같이 기존 방법론이 적용하기 어려웠던 영역에 대한 새로운 해결책을 제시합니다.
• 실용성: SCD 도함수는 limiting coderivative 보다 계산이 용이하면서도 중요한 정보를 포함하고 있어, 실제 수치 계산에 매우 유용하게 적용될 수 있음을 입증했습니다.

요약하자면, 이 논문은 SCD(Subspace Containing Derivative) 와 반매끄러움 (semismooth)** 개념을 결합하여, 비매끄러운 포함식의 해 매핑을 통한 최적화 문제 해결에 대한 강력한 이론적 틀을 마련하고, 이를 실제 알고리즘에 적용할 수 있는 구체적인 방법을 제시했습니다.