An augmented Lagrangian algorithm for constrained nonlinear least-squares

기술 요약: 제약 조건이 있는 비선형 최소제곱법을 위한 증강 라그랑주 알고리즘

문제 정식화
본 논문은 비선형 등식 제약 조건 $c(x)=0$과 선형 제약 조건 $x \in \Omega$가 혼합된 형태의 제약 조건 하에서 잔차의 제곱 합 $\frac{1}{2}\|r(x)\|^2$을 최소화하는 제약 조건이 있는 비선형 최소제곱(NLS) 문제를 다룹니다. 집합 $\Omega$는 선형 등식($Ax=b$)과 경계 제약 조건($l \le x \le u$)을 포함합니다. 잔차$r(x)$와 제약 조건$c(x)$는 이계 연속 미분 가능하다고 가정됩니다. 이러한 문제를 해결하는 데 있어 주요 과제는 NLS 구조—즉, 목적 함수의 헤시안을 1차 항인 $J(x)^\top J(x)$와 개별 잔차들의 헤시안을 포함하는 2차 항으로 분해하는 것—를 효율적으로 처리하면서 동시에 일반적인 제약 조건을 강제하는 것입니다.

방법론
Julia로 구현된 TRAULLS는 증강 라그랑주(AL) 프레임워크와 구조적 준-뉴턴(SQN) 근사 및 경사 투영(gradient projection) 기법을 통합합니다.

1. 증강 라그랑주 프레임워크:
   비선형 제약 조건은 AL 페널티 항을 통해 목적 함수에 통합되며, 이를 통해 원래의 문제를 일련의 선형 제약 하의 부문제(subproblems)로 변환합니다. 각 외곽 반복(outer iteration) $K$에서 알고리즘은 다면체 집합 $\Omega$ 위에서 AL 함수 $\Phi(x, \lambda, \mu)$를 최소화합니다.

• 승수 및 페널티 업데이트: 비선형 타당성(feasibility)이 충분히 개선되었다면, 라그랑주 승수는 쌍대 상승(dual ascent, $\lambda_{K+1} = \lambda_K + \mu_K c(x_K)$)을 통해 업데이트됩니다. 만약 타당성이 개선되지 않는다면, 다음 반복에서 제약 조건을 더 엄격하게 강제하기 위해 페널티 파라미터 $\mu_K$를 증가시킵니다.
• 내부 최소화: 부문제( $\Omega$ 상에서 $\Phi$를 최소화하는 문제)는 신뢰 영역(trust-region) 방법을 사용하여 해결됩니다. 알고리즘은 각 외곽 반복이 일련의 내부 반복($k$)을 트리거하고, 이는 다시 미세 반복($j$)으로 구성되는 중첩 구조를 채택합니다.

2. 내부 최소화 및 단계 계산:
   내부 루프는 다면체 집합에 적응된 경사 투영 기법을 활용합니다.

• 코시 단계(Cauchy Step): 투영된 경사 경로를 따라 이차 모델의 첫 번째 국소 최소값을 찾음으로써 코시 단계를 계산합니다. 이는 전역 수렴을 보장합니다.
• 부공간 최소화(Subspace Minimization): 수렴을 가속화하기 위해, 알고리즘은 코시 점에서의 활성 제약 조건에 의해 정의된 부공간 내에서 일련의 미세 반복을 수행합니다. 이 단계들은 **투영 공액 경사법(Projected Conjugate Gradient, PCG)**을 사용하여 계산됩니다.
• 신뢰 영역: 신뢰 영역 전략은 단계의 품질을 제어하며, 다면체 구조를 유지하기 위해 $\ell_\infty$ 노름에 의해 정의된 영역을 사용합니다.

3. 구조적 헤시안 근사:
   핵심 기여는 AL 헤시안의 근사입니다. 전체 2차 항을 계산하는 대신(이는 계산 비용이 많이 듭니다), 본 방법은 헤시안을 $H_k = B^{GN}_k + B_k$로 근사합니다. 여기서:

• $B^{GN}_k = J_k^\top J_kappa + \mu C_k^\top C_k$는 가우스-뉴턴(Gauss-Newton) 근사입니다.
• $B_k$는 잔차와 제약 조건의 2차 항을 근사하는 구조적 보정 항입니다.
• 업데이트 규칙: 본 논문은 NLS 구조에 맞게 설계된 구조적 세칸트 방정식(secant equation)으로부터 유도된 대칭 계수 1(Symmetric Rank-1, SR1) 업데이트를 사용합니다. 이 방정식은 잔차와 제약 조건의 자코비안을 통해 변수의 변화와 경사도의 변화를 연결합니다.
• 하이브리드 전략: 알고리즘은 잔차의 크기(스위칭 기준 $\zeta_k$ 사용)에 따라 순수 가우스-뉴턴 모델과 구조적 SQN 모델 사이를 동적으로 전환합니다. 잔차가 작으면 GN 모델을 사용하고, 그렇지 않으면 정확도를 높이기 위해 구조적 보정을 적용합니다.

주요 기여

• 알고리즘 통합: 본 논문은 목적 함수와 페널티 항 모두의 제곱합 구조에 특화된 구조적 준-뉴턴 업데이트와 증강 라그랑주 프레임워크를 결합한 솔버를 제시합니다.
• 일반 제약 조건 처리: 경계 제약 조건에만 집중하는 기존의 많은 NLS 솔버와 달리, 이 방법은 모든 제약 조건을 경계 조건으로 변환하지 않고도 선형 등식, 경계, 비선형 등식이 혼합된 문제를 직접 처리합니다.
• 구조적 세칸트 방정식: NLS 구조를 존중하는 세칸트 방정식(식 2.26)의 유도는 전체 2차 미분값을 계산하지 않고도 효율적인 헤시안 근사를 가능하게 합니다.
• 전역 수렴: 저자들은 방법론이 표준적인 가정(이계 미분 가능성, 활성 제약 조건의 선형 독립성) 하에서 수렴함을 입증함으로써, 제1차 임계점(first-order critical point)으로의 전역 수렴에 대한 엄격한 증명을 제공합니다.

수치 결과
저자들은 2개에서 1000개의 변수를 가진 79개의 문제 인스턴스(표준 컬렉션 및 특정 벤치마크 포함)에 대해 TRAULLS를 평가했습니다.

• 헤시안 근사 비교: 가우스-뉴턴(GN), 일반 SR1, 일반 BFGS 및 이들의 하이브리드 변형을 비교한 실험 결과, 하이브리드 SR1 접근 방식이 견고성과 효율성 사이에서 최적의 균형을 제공함을 보여주었습니다. GN이 반복당 속도는 가장 빨랐으나, 하이브리드 방식은 내부 반복 횟수가 적었고 잔차가 큰 문제에서 우수한 견고성을 입증했습니다.
• 최신 기술과의 비교: TRAULLS는 범용 내부 점(interior-point) 솔버인 IPOPT 및 또 다른 AL 기반 솔버인 Percival과 비교되었습니다.
  • 성능: TRAMLSS는 IPOPT와 대등한 계산 시간을 달exp성했으나, IPOPT는 정확한 헤시안을 사용하기 때문에 일반적으로 더 적은 함수 계산을 요구했습니다.
  • 견고성: TRAULLS는 Percival을 크게 능가하였으며, 이는 동일한 알고리즘 프레임워크(AL) 내에서도 최소제곱 구조를 활용하는 것이 더 나은 성능을 낸다는 것을 입증했습니다.
  • 한계: 구조적 헤시안 보정에 필요한 밀집 저장(dense storage) 방식은 매우 많은 변수에 대한 확장성을 제한하며, 이는 저자들이 인정한 부분입니다.

의의 및 주장
본 논문은 제약 조건이 있는 NLS 문제를 위해 특별히 설계되어, 최소제곱 구조의 활용과 일반 제약 조건 처리를 위한 유연성 사이의 균형을 효과적으로 맞추는 솔버를 제시한다고 주장합니다. 저자들은 이 접근 방식이 전체 2차 미분값을 계산하는 높은 비용을 피하면서도 구조적 업데이트를 통해 견고함을 유지한다는 점을 강조합니다. 본 연구의 의의는 물리적 일관성(제약 조건에 의해 강제됨)이 요구되는 데이터 피팅 및 파라미터 추정 문제에 특화된 도구를 제공함으로써, IPOPT와 같은 범용 솔버나 기존의 AL 방식인 Percival에 대한 경쟁력 있는 대안을 제시한다는 데 있습니다. 저자들은 현재의 구현이 유망한 성능을 보이지만, 향후 연구를 통해 제한된 메모리 변형(limited-memory variants) 및 대규모 잔차 집합을 위한 적응형 샘플링을 통해 확장성 문제를 해결해야 한다고 겸허히 언급하였습니다.