7.111 순차적 이차 계획법(SQP)

1. 기본 원리

순차적 이차 계획법(Sequential Quadratic Programming, SQP)은 비선형 제약 최적화 문제를 일련의 이차 계획 하위 문제(QP subproblem)로 근사하여 반복적으로 푸는 방법이다. 이는 비제약 최적화에서 뉴턴법이 비선형 방정식을 일련의 선형 근사로 풀어가는 것의 제약 최적화 대응물이다.

일반적인 비선형 계획 문제를 고려하라.

$\min_{\mathbf{x}} f(\mathbf{x}) \quad \text{s.t.} \quad \mathbf{g}(\mathbf{x}) \leq \mathbf{0}, \; \mathbf{h}(\mathbf{x}) = \mathbf{0}$

2. QP 하위 문제의 구성

현재 반복점 $(\mathbf{x}_k, \boldsymbol{\mu}_k, \boldsymbol{\nu}_k)$ 에서 라그랑지안을 2차 테일러 전개하고 제약을 1차 선형화하면, 다음의 QP 하위 문제를 얻는다.

$\min_{\mathbf{d}} \quad \frac{1}{2}\mathbf{d}^T\mathbf{B}_k\mathbf{d} + \nabla f(\mathbf{x}_k)^T\mathbf{d}$

$\text{s.t.} \quad \nabla g_i(\mathbf{x}_k)^T\mathbf{d} + g_i(\mathbf{x}_k) \leq 0, \quad i = 1, \ldots, m$

$\nabla h_j(\mathbf{x}_k)^T\mathbf{d} + h_j(\mathbf{x}_k) = 0, \quad j = 1, \ldots, p$

여기서 $\mathbf{B}_k$ 는 라그랑지안 $\mathcal{L}(\mathbf{x}, \boldsymbol{\mu}, \boldsymbol{\nu}) = f + \boldsymbol{\mu}^T\mathbf{g} + \boldsymbol{\nu}^T\mathbf{h}$ 의 헤시안 $\nabla^2_{\mathbf{x}\mathbf{x}}\mathcal{L}(\mathbf{x}_k, \boldsymbol{\mu}_k, \boldsymbol{\nu}_k)$ 또는 그 양정치 근사이다.

이 QP의 해 $\mathbf{d}_k^*$ 가 탐색 방향이 되며, QP의 KKT 승수가 다음 반복의 라그랑주 승수 추정치를 제공한다.

3. 갱신 규칙

$\mathbf{x}_{k+1} = \mathbf{x}_k + \alpha_k \mathbf{d}_k^*$

스텝 크기 $\alpha_k$ 는 공적 함수(merit function)에 대한 직선 탐색으로 결정된다. 공적 함수는 목적 함수의 감소와 제약 위반의 감소를 동시에 평가한다.

4. 공적 함수

4.1 $\ell_1$ 공적 함수

$\phi_1(\mathbf{x}; \sigma) = f(\mathbf{x}) + \sigma \left(\sum_i \max(0, g_i(\mathbf{x})) + \sum_j \lvert h_j(\mathbf{x}) \rvert\right)$

벌점 매개변수 $\sigma$ 는 제약 위반에 대한 벌점의 세기를 결정하며, $\sigma > \max(\mu_i^*, \lvert \nu_j^* \rvert)$ 이면 정확 벌점으로서 원래 문제의 해와 공적 함수의 최소점이 일치한다.

4.2 증강 라그랑지안 공적 함수

$\phi_{AL}(\mathbf{x}, \boldsymbol{\nu}; \rho) = f(\mathbf{x}) + \boldsymbol{\nu}^T\mathbf{h}(\mathbf{x}) + \frac{\rho}{2}\lVert \mathbf{h}(\mathbf{x}) \rVert^2$

$\ell_1$ 공적 함수의 비매끄러움을 피할 수 있으나, 라그랑주 승수의 갱신이 추가로 필요하다.

5. 헤시안 근사

5.1 정확 헤시안

$\mathbf{B}_k = \nabla^2_{\mathbf{x}\mathbf{x}}\mathcal{L}(\mathbf{x}_k, \boldsymbol{\mu}_k, \boldsymbol{\nu}_k)$ 를 사용하면 이차 수렴이 달성된다. 그러나 라그랑지안의 헤시안은 양정치가 아닐 수 있으므로, 정규화 또는 수정이 필요하다.

5.2 BFGS 근사

라그랑지안의 헤시안을 BFGS 공식으로 근사한다. 비볼록 문제에서 곡률 조건 $\mathbf{s}_k^T\mathbf{y}_k > 0$ 이 위반될 수 있으므로, 댐핑된 BFGS 갱신(Powell의 수정)이 사용된다.

5.3 가우스-뉴턴 근사

최소 제곱 문제에서 헤시안의 2차 항을 무시한 가우스-뉴턴 근사 $\mathbf{B}_k \approx \mathbf{J}^T\mathbf{J}$ 는 항상 양의 반정치이므로 수정이 불필요하다.

6. 수렴 성질

적절한 조건(2차 충분 조건, LICQ, 엄격 상보성)하에서 SQP는 다음의 수렴 성질을 갖는다.

전역 수렴: 공적 함수에 대한 직선 탐색과 결합하면 임의의 초기점에서 정류점으로 수렴한다.
국소 이차 수렴: 정확 헤시안을 사용하면 최적해 근방에서 이차 수렴한다.
국소 초선형 수렴: BFGS 근사를 사용하면 초선형 수렴을 달성한다.

최적해 근방에서 단위 스텝( $\alpha_k = 1$ )이 수용되면, SQP는 등식 제약 문제의 라그랑주-뉴턴 방법과 동치가 되어 급속 수렴한다.

7. 실현 가능성 문제

QP 하위 문제의 선형화된 제약이 원래 비선형 제약과 일치하지 않으므로, QP의 해가 원래 문제의 허용 영역에 놓이지 않을 수 있다. 특히 QP 하위 문제 자체가 비허용(infeasible)이 되는 경우가 발생할 수 있다. 이를 처리하기 위해 탄력 변수(elastic variable)를 도입하여 항상 허용 가능한 QP를 구성하는 기법이 사용된다.

8. 로봇 공학에서의 응용

비선형 궤적 최적화: SQP는 로봇 궤적 최적화의 표준 해법 중 하나이다. 비선형 동역학 제약, 장애물 회피 제약, 관절 한계 등을 포함하는 문제를 직접 처리한다. SNOPT, IPOPT 등의 대규모 SQP/내점법 해법기가 궤적 최적화에 널리 사용된다.

비선형 MPC: 비선형 모델 예측 제어에서 SQP를 한 번 또는 소수 반복만 수행하는 실시간 SQP(real-time SQP) 기법이 사용된다. 이전 해로부터의 웜 스타트와 결합하여 제어 주기 내에 근사 해를 산출한다.

접촉 최적화: 접촉 전환을 포함하는 궤적 최적화에서 SQP는 접촉 제약의 상보성을 반복적으로 근사하여 처리한다.

9. 참고 문헌

Nocedal, J., & Wright, S. J. (2006). Numerical Optimization (2nd ed.). Springer.
Boggs, P. T., & Tolle, J. W. (1995). “Sequential Quadratic Programming.” Acta Numerica, 4, 1–51.
Gill, P. E., Murray, W., & Saunders, M. A. (2005). “SNOPT: An SQP Algorithm for Large-Scale Constrained Optimization.” SIAM Review, 47(1), 99–131.
Diehl, M., Bock, H. G., & Schlöder, J. P. (2005). “A Real-Time Iteration Scheme for Nonlinear Optimization in Optimal Feedback Control.” SIAM Journal on Control and Optimization, 43(5), 1714–1736.

version: 1.0