순차 이차계획법

최적설계 수치해석 마지막 수정: 2026-07-29 04:27:03

1. 개요[편집]

순차 이차계획법(Sequential Quadratic Programming, SQP)은 제약이 있는 비선형 최적화 문제(NLP)를 풀 때, 매 반복마다 이차계획(QP) 부분문제를 하나씩 풀어 다음 스텝을 정하는 방법이다. 대상 문제는 보통 이렇게 쓴다.

\min_{x \in \mathbb{R}^n} \; f(x) \quad \text{s.t.} \quad h(x) = 0, \; g(x) \le 0

한 줄로 요약하면 SQP = 카루시-쿤-터커 조건에 뉴턴법을 적용한 것이다. 무제약 최적화에서 뉴턴법이 $\nabla f = 0$ 을 뉴턴 반복으로 푸는 것이라면, SQP는 그 자리에 KKT 조건이라는 비선형 연립방정식을 놓고 같은 짓을 한다. 그래서 국소적으로는 뉴턴법과 같은 이차 수렴을 가지며, 함수·기울기 계산이 비싼 공학 문제에서 반복 횟수가 압도적으로 적다는 이유로 오래 사랑받아 왔다.¹

내점법이 부등식 제약을 배리어로 부드럽게 뭉개 내부에서 접근한다면, SQP는 활성 제약 집합을 매 반복 QP가 직접 골라내며 경계 위를 걷는다. 대규모 희소 문제는 내점법, 제약 대비 자유도가 적고 함수 평가가 비싼 문제는 SQP — 대략 이런 분업이 현장의 감각이다.

2. KKT 조건에서 QP 부분문제 유도[편집]

라그랑지안을 $\mathcal{L}(x,\lambda,\mu) = f(x) + \lambda^\top h(x) + \mu^\top g(x)$ 로 두면 KKT 조건은 다음과 같다.

\nabla_x \mathcal{L} = 0, \quad h(x) = 0, \quad g(x) \le 0, \quad \mu \ge 0, \quad \mu_i g_i(x) = 0

먼저 등식 제약만 있는 경우를 보자. $(\nabla_x \mathcal{L}, h)$ 를 0으로 만드는 뉴턴 스텝은 다음 선형계를 푸는 것이다.

\begin{bmatrix} W_k & A_k^\top \\ A_k & 0 \end{bmatrix} \begin{bmatrix} d \\ \lambda_{k+1} \end{bmatrix} = \begin{bmatrix} -\nabla f_k \\ -h_k \end{bmatrix}

여기서 $W_k = \nabla^2_{xx}\mathcal{L}(x_k,\lambda_k)$ , $A_k = \nabla h(x_k)^\top$ 이다. 그런데 이 KKT 계는 다음 등식제약 QP의 최적성 조건과 정확히 같다.

\min_{d} \; \tfrac{1}{2} d^\top W_k d + \nabla f_k^\top d \quad \text{s.t.} \quad A_k d + h_k = 0

즉 뉴턴 스텝과 QP 부분문제는 같은 물건의 두 얼굴이다. 이 관점의 장점은 부등식 제약으로의 확장이 자연스럽다는 것 — 제약을 그냥 선형화해서 QP에 넣으면 된다.

\min_{d} \; \tfrac{1}{2} d^\top B_k d + \nabla f_k^\top d \quad \text{s.t.} \quad h_k + \nabla h_k^\top d = 0, \; g_k + \nabla g_k^\top d \le 0

여기서 반드시 짚어야 할 점 두 가지.

목적함수의 이차항은 $f$ 의 헤세 행렬이 아니라 라그랑지안의 헤세다. 제약의 곡률이 빠지면 수렴이 선형으로 주저앉는다. 초심자가 가장 자주 틀리는 부분.
제약은 1차 선형화만 한다. 그래서 부분문제가 QP(이차 목적 + 선형 제약)로 유지되고, 활성집합·내점 QP 솔버를 그대로 쓸 수 있다.

해 근방에서 QP가 고르는 활성집합은 원래 NLP의 활성집합과 일치하게 되고(LICQ + 엄격 상보성 가정), 그 시점부터는 등식제약 뉴턴법과 같아져 국소 이차 수렴이 나온다.

3. 헤세 근사와 준-뉴턴 SQP[편집]

$\nabla^2_{xx}\mathcal{L}$ 을 정확히 계산하려면 $f$ 와 모든 제약의 2계 도함수가 필요하다. 자동 미분이 붙은 코드라면 가능하지만, 상용 CAE 솔버를 블랙박스로 두드리는 상황에서는 꿈같은 얘기다. 게다가 정확한 $W_k$ 는 부정부호일 수 있어 QP가 비볼록이 되고 부분문제 자체가 NP-난해로 넘어간다.

그래서 실무 SQP는 준-뉴턴법, 그중에서도 BFGS로 $B_k \approx \nabla^2_{xx}\mathcal{L}$ 을 근사한다. 갱신에 쓰는 벡터는

s_k = x_{k+1} - x_k, \qquad y_k = \nabla_x \mathcal{L}(x_{k+1}, \lambda_{k+1}) - \nabla_x \mathcal{L}(x_k, \lambda_{k+1})

로, 같은 승수에서 평가한 라그랑지안 기울기의 차이여야 한다. 그냥 $\nabla f$ 의 차이를 쓰면 근사하는 대상이 달라진다.

문제는 라그랑지안 헤세가 실제로 부정부호일 수 있어 곡률 조건 $s_k^\top y_k > 0$ 이 깨진다는 것이다. BFGS는 이게 깨지면 양정부호성을 잃고 붕괴한다. 파월(Powell)의 감쇠 BFGS(damped BFGS)는 $s_k^\top y_k$ 가 $0.2\, s_k^\top B_k s_k$ 보다 작으면 $y_k$ 를 $B_k s_k$ 쪽으로 섞어

r_k = \theta y_k + (1-\theta) B_k s_k

를 대신 쓴다. 곡률 조건이 강제로 유지되어 $B_k$ 가 항상 양정부호로 남고, QP 부분문제는 언제나 볼록해진다. 변수 수가 많으면 L-BFGS나 축소 헤세(reduced Hessian, 제약의 영공간 위에서만 근사) 방식으로 메모리를 줄인다.

4. 전역화 — 메리트 함수, 마라토스 효과, 필터[편집]

QP가 준 방향 $d_k$ 는 어디까지나 국소 모형의 산물이라, 초기점이 멀면 그대로 $x_k + d_k$ 로 가면 안 된다. 뭔가 “좋아졌다”를 판정할 척도가 필요한데, 여기서 목적함수 감소와 제약 위반 감소라는 두 목표가 충돌한다는 게 제약 최적화 전역화의 본질적 어려움이다.

전통적 해법은 둘을 하나의 스칼라로 합치는 메리트 함수다. 대표가 $\ell_1$ 벌점 함수다.

\phi_1(x;\nu) = f(x) + \nu \left( \|h(x)\|_1 + \|[g(x)]^{+}\|_1 \right)

$\nu$ 가 최적 승수의 크기보다 크면 이 함수는 정확 벌점 함수가 되어, 원문제의 해가 $\phi_1$ 의 국소 최소점이 된다. QP 방향은 이 함수의 하강 방향임이 보장되므로 라인서치를 걸 수 있다. 단점은 미분 불가능한 꺾인 함수라는 점, 그리고 $\nu$ 를 너무 크게 잡으면 스텝이 잘게 썰린다는 점.

그리고 유명한 함정이 하나 있다. 마라토스 효과(Maratos effect)다. 해에 아주 가까운 곳에서도, 이차 수렴을 주는 단위 스텝 $d_k$ 가 메리트 함수를 증가시켜 라인서치에 거부당하는 현상이다. 곡선인 제약면을 선형화해 걷다 보니 스텝 끝에서 제약 위반이 $\|d_k\|^2$ 규모로 생기는데, 목적함수 감소는 그보다 고차라 벌점항에 잡아먹히는 것. 결과적으로 이차 수렴이 파괴되고 반복이 기어간다. 처방은 세 가지가 알려져 있다.

2차 보정(second-order correction): $x_k + d_k$ 에서 제약을 다시 평가해 위반을 상쇄하는 보정 스텝을 한 번 더 얹는다.
워치독(watchdog) / 비단조 전략: 몇 반복 동안은 메리트 함수가 늘어나는 것을 눈감아 준다.
필터법(filter method): 플레처-레이퍼가 제안한 방식으로, $f$ 와 제약 위반도 $\theta(x)$ 를 합치지 않고 2목적으로 두고, 기존 반복점들에 지배당하지 않으면 받아들인다. 벌점 파라미터 $\nu$ 를 튜닝할 필요가 없다는 게 큰 장점.

자세한 현상 분석은 마라토스 효과 문서에서 다룬다.

5. 신뢰영역 SQP와 QP 부분문제 해법[편집]

라인서치 대신 신뢰 영역 방법을 쓰는 SQP도 있다. QP에 $\|d\| \le \Delta_k$ 를 추가하는 건데, 여기서 고약한 문제가 생긴다 — 신뢰영역과 선형화된 제약이 동시에 만족 불가능할 수 있다. 선형화한 등식 제약을 만족하려면 반경 밖으로 나가야 하는 상황이 실제로 흔하다. 대처법은 이렇다.

$S\ell_1$ QP: 제약을 QP 목적함수의 $\ell_1$ 벌점으로 옮겨 부분문제를 항상 실행가능하게 만든다.
합성 스텝(Byrd-Omojokun): 스텝을 법선 스텝(제약 위반을 반경의 일정 비율 안에서 줄임)과 접선 스텝(제약의 영공간 안에서 모형 목적을 줄임)으로 쪼갠다. 대형 신뢰영역 SQP의 표준.

QP 부분문제 자체는 활성집합법이나 내점법으로 푼다. SQP 반복 간에 활성집합이 거의 변하지 않는다는 성질 때문에 웜스타트가 잘 먹히는 활성집합 QP가 전통적으로 유리했고, 부분문제가 초대형 희소 구조면 내점 QP가 유리하다. 부분문제를 매번 끝까지 풀지 않고 몇 스텝만 돌리는 부정확 SQP도 실시간 제어에서 쓰인다.

6. 소프트웨어와 공학 적용[편집]

SNOPT — 희소 문제용 축소 헤세 준-뉴턴 SQP. 제약 위반을 탄성 변수로 흡수하는 elastic mode를 갖춰 실행불가능 구간에서도 잘 버틴다. 항공 궤적 최적화의 사실상 표준.
filterSQP / WORHP / NLPQLP — 각각 필터 기반, 대형 희소, 밀집 중소형 계열의 구현.
SLSQP — 크라프트(Kraft)의 고전 구현. SciPy minimize(method='SLSQP')로 널리 쓰이며, 중소 규모 문제의 기본값 취급을 받는다.
MATLAB fmincon — 'sqp', 'active-set', 'interior-point' 알고리즘을 옵션으로 고를 수 있다. 공학도가 SQP를 처음 만나는 장소일 확률이 높다.
IPOPT / KNITRO — IPOPT는 SQP가 아니라 라인서치 필터 내점법이지만, 비교 대상으로 늘 같이 언급된다. KNITRO는 내점법과 활성집합(SQP 계열)을 모두 탑재.

공학에서 SQP가 특히 강한 자리는 함수 한 번 평가가 비싼 문제다. CFD·FEM 한 케이스가 수십 분씩 걸리는 형상 최적화에서, 반복 30회로 끝나느냐 3000회로 끝나느냐는 프로젝트의 생사를 가른다. 이때 기울기는 유한차분 대신 민감도 해석의 수반법(adjoint)이나 자동 미분으로 뽑는 것이 정석이다 — 설계변수가 수백 개일 때 유한차분은 매 반복 수백 번의 해석을 요구해서 SQP의 장점을 통째로 날려먹는다.² 궤적 최적화의 직접 배치법(direct collocation), 모델 예측 제어의 실시간 반복(real-time iteration) 기법도 SQP 골격 위에 서 있다.

마지막으로 한계. SQP는 어디까지나 국소 방법이라, 찾아주는 건 KKT 점이지 전역 최적해가 아니다.³ 다봉 설계공간이면 다중 시작점이나 유전 알고리즘 같은 전역 탐색으로 초기점을 뿌린 뒤 SQP로 다듬는 하이브리드가 현실적이다. 또 목적·제약 함수에 잡음이 있으면(수렴이 덜 된 CFD 잔차 같은 것) 유한차분 기울기가 통째로 거짓말을 하고 QP가 엉뚱한 방향을 내놓는다. 해석이 수렴하지 않은 상태로 최적화를 돌리는 것이 SQP 실패담의 1순위다.

7. 관련 문서[편집]

“반복 횟수가 적다”는 말은 “총 계산량이 적다”와 같지 않다. 반복당 QP를 하나씩 푸는 비용이 있기 때문. 다만 CFD 한 번 돌리는 데 40분 걸리는 문제에서 QP 푸는 0.3초는 반올림 오차 취급을 받는다. 무엇이 비싼지는 문제가 정한다. ↩
그래서 설계변수 수백~수천 개짜리 위상 최적화에서는 SQP 대신 이동점근법(MMA) 같은 분리형 근사법이 표준이 됐다. SQP가 모든 곳에서 최고라는 뜻은 아니다. ↩
게다가 KKT 점이라는 것도 제약자격(LICQ, MFCQ 등)이 성립할 때의 얘기다. 제약을 중복해서 걸어놨거나 등식 제약이 서로 종속이면 승수가 발산하면서 솔버가 “수렴했습니다”라며 이상한 점을 뱉는다. 로그에 승수 크기가 $10^{12}$ 쯤 찍혀 있으면 알고리즘이 아니라 모델을 의심하자. ↩