Evaluating the solution performance of the augmented Lagrangian function on Ising machines

기술 요약: Ising Machine에서의 Augmented Lagrangian Function의 솔루션 성능 평가

문제 정의
Ising machine은 이싱 모델(Ising model)의 바닥 상태(ground state)로 매핑함으로써 조합 최적화 문제를 해결하도록 설계된 특화된 컴퓨팅 장치이다. 제약 조건이 있는 문제에 이 기계들을 적용할 때 발생하는 주요 과제는 제약 조건을 공식화하는 것이다. 일반적으로 제약 조건은 페널티 계수($\mu$)를 통해 목적 함수와 제약 만족도 사이의 균형을 맞추는 페널티 항을 통해 목적 함수에 통합된다. 이 계수는 내재적인 트레이드오프를 수반한다: 만약 $\mu$가 너무 작으면 기계는 실행 불가능한(infeasible) 상태를 샘플링하고, 만약 $\mu$가 너무 크면 에너지 지형(energy landscape)이 제약 항에 의해 지배되어 목적 함수 값의 차이를 가려 고품질의 실행 가능한 해를 찾는 것을 어렵게 만든다. $\mu$를 조정하기 위한 다양한 튜닝 방법들이 존재하지만, 이들은 일반적으로 이 트레이드오프를 관리하기 위해 단일 파라미터에 의존한다.

방법론
본 연구는 Ising machine을 위한 대안적 공식화로서 **Augmented Lagrangian Function (ALF)**을 평가하며, 특히 표준 Penalty Function (PF) 공식과 비교한다. 저자들은 **Quadratic Knapsack Problem (QKP)**을 벤치마크로 활용하는데, 이는 아이템의 가치를 최대화하되 무게 용량을 초 exceed하지 않도록 하는 부등식 제약 문제를 포함한다.

1. 공식화:

   • Penalty Function: 문제 해밀토니안은 $H_P(x) = f(x) + \frac{\mu}{2}[g(x) - c]^2$로 정의된다. 여기서 $f(x)$는 목적 함수이고 $g(x)=c$는 제약 조건이다.
   • Augmented Lagrangian Function: 해밀토니안은 $H_{AL}(x) = f(x) + \frac{\mu}{2}[g(x) - c]^2 - \lambda[g(x) - c]$로 정의된다. 이는 제약 위반에 선형적인 라그랑주 승수(Lagrange multiplier) 항 $\lambda$를 도입한다.
   • 본 연구는 ALF를 탐색 과정 중에 파라미터를 업데이트하는 반복 알고리즘이 아닌, 고정된 하이퍼파라미터($\mu, \lambda$)를 가진 정적 공식으로 취급한다. 다만, 보조 분석으로서 반복적 Augmented Lagrangian Method (ALM)에 대해서도 논의한다.

2. 실험 설정:

   • 솔버: Fixstars Amplify Annealing Engine (AE)가 사용되었다.
   • 인스턴스: 알려진 최적해를 가진 세 가지 QKP 벤치마크 인스턴스($N=100, 200, 300$)가 사용되었다.
   • 지표: 성능은 상대적 허용 오차 $\epsilon$ (0.05로 설정) 및 목표 확률 $p_R = 0.99$ 내에서 실행 가능한 해를 얻는 데 필요한 총 계산 시간인 **Time-to-Epsilon ($TT_\epsilon$)**을 사용하여 평가되었다.
   • 파라미터: $\mu$ (0 to 100)와 $\lambda$ (-500 to 500)에 대한 그리드 서치가 수행되었다.

주요 기여 및 결과
본 연구는 ALF 공식이 PF 공식과 비교하여 솔루션 성능에 어떻게 영향을 미치는지에 대한 정량적 평가를 제공한다.

• $TT_\epsilon$ 감소: ALF 공식은 가장 성능이 좋은 PF 공식에 비해 $TT_\epsilon$을 약 한 자릿수(one order of magnitude) 감소시켰다. 구체적으로, 인스턴스 'r 100 50 5'의 경우, PF의 최소 $TT_\epsilon$은 $\mu=40$에서 발견되었으나, ALF는 훨씬 작은 $\mu$ 값(예: $\mu=5, \lambda=100$)에서도 현저히 낮은 $TT_\epsilon$ 값을 달성하였다.
• 파라미터 의존성: 결과는 ALF가 실행 가능한 해를 얻으면서도 상대적으로 작은 $\mu$ 값을 사용할 수 있음을 입증했다. PF 공식에서 작은 $\mu$는 실행 불가능성으로 이어지는 반면, 큰 $\mu$는 솔루션 품질을 저하시킨다. ALF는 $\lambda$ 항을 사용하여 에너지 지형을 교정함으로써, $\mu$가 작을 때도 목적 함수의 상대적 에너지 스케일을 유지하여 이 문제를 완화한다.
• 시간적 진화: 대표적인 ALF 설정 하에서 현재 최적해(incumbent solution)의 시간적 진화 분석을 수행한 결과, ALF는 PF에 비해 실행 시간 중 더 이른 시점에 플래토(plateau, 근사 최적 목적 함수 값)에 도달했다. 또한, ALF의 실행 가능한 해들 사이의 변동성도 더 작았다.
• 구조적 설명: "제곱 완성(square-completion)" 분석을 통해, 저자들은 ALF가 제약의 유효 용량(effective capacity)을 이동시키는 것과 수학적으로 동일함을 보여주었다. $\lambda$ 항은 페널티 항의 최소점을 $H_{const}=0$에서 $H_{const}=\lambda/\mu$로 효과적으로 이동시킨다. $\lambda > 0$인 경우, 이는 전체 무게가 더 작은 아이템 선택 쪽으로 탐색을 유도하여, 큰 $\mu$를 요구하지 않고도 원래의 부등식 제약을 만족할 확률을 높인다.

의의 및 주장
본 논문은 Augmented Lagrangian Function이 Ising machine의 솔루션 성능를 향상시키기 위한 유망한 공식이라고 주장한다. 주요 의의는 라그랑주 승수 항의 도입을 통해 페널티 계수 $\mu$를 작게 유지할 수 있다는 점에 있다. 이는 에너지 지형에서 목적 함수 항의 기여도를 보존하여, 표준 페널티 함수보다 더 효율적으로 작은 목적 함수 오차를 가진 실행 가능한 해를 발견할 수 있게 한다.

저자들은 자신들의 결론이 QKP 벤치마크 인스턴스와 특정 솔버 설정에 기반하고 있음을 언급한다. 그들은 ALF가 왜 더 일찍 점근적 값(asymptotic value)에 도달하는지에 대한 상세한 동역학적 메커니즘이 아직 명확히 규명되지 않았으며, 상태 전이 동작에 대한 추가적인 조사가 필요하다고 명시했다. 또한, 본 연구는 공식 자체에 집중하고 있으나, 결과는 이러한 장점이 제약 위반에 따라 파라미터를 적응적으로 업데이트하는 반복적 Augmented Lagrangian Method (ALM)에 의해 활용될 수 있음을 시사한다. 다만, 반복적 업데이트와 직접적인 파라미터 탐색 간의 체계적인 비용 비교는 향후 과제로 남겨두었다.