이차계획법

편집 역사 토론
수치해석 최적설계 마지막 수정: 2026-07-22 04:19:05

1. 개요[편집]

이차계획법(Quadratic Programming, QP)은 목적함수가 2차식(quadratic)이고 제약조건이 모두 선형(linear)인 최적화 문제를 푸는 방법이자 그 문제 부류를 가리킨다. 선형계획법(LP)에서 목적함수만 2차로 올린 바로 윗동네로, 비선형 최적화 중에서는 가장 다루기 쉬운 축에 속한다. 특히 목적함수의 헤세 행렬이 양의 준정부호이면 볼록 QP가 되어 국소해가 곧 전역해가 되는, 최적화하는 사람 입장에서 천국 같은 성질을 가진다.1

표준형은 다음과 같이 쓴다.

min⁡x  12x⊤Qx+c⊤xs.t.Ax≤b,  Ex=d\min_{\mathbf{x}} \; \frac{1}{2}\mathbf{x}^\top Q \mathbf{x} + \mathbf{c}^\top \mathbf{x} \quad \text{s.t.} \quad A\mathbf{x} \le \mathbf{b},\; E\mathbf{x} = \mathbf{d}

여기서 QQ가 목적함수의 곡률을 담은 대칭 행렬이다. QQ가 양의 정부호이면 유일한 전역 최소가 존재하고, 부정부호이면 문제 자체가 NP-난해로 튀어버린다. 그래서 QP를 논할 때 “QQ가 어떤 놈이냐”가 모든 것을 가른다.

2. 응용[편집]

QP는 순수 이론이 아니라 실무 최적화의 밑바닥에서 부품처럼 굴러다닌다.

  • 포트폴리오 최적화: 마코위츠의 평균-분산 모형이 그대로 QP다. 분산(위험)이 2차항, 기대수익 제약이 선형. 금융공학의 원조 QP.
  • 모델 예측 제어(MPC): 매 제어 주기마다 QP를 한 번씩 푼다. 로봇·자율주행·공정제어의 심장이 실시간 QP 솔버다.
  • 서포트 벡터 머신(SVM): 마진 최대화가 볼록 QP로 정식화된다. 딥러닝 이전 분류기의 왕.
  • 구조 최적화의 부분문제: 위상 최적화와 형상 최적화에서 재료 분포나 형상 변수를 갱신할 때, 원래의 비선형 문제를 매 반복 QP로 근사해 푼다. 뒤에 나올 SQP의 무대다.
  • 접촉·마찰 역학: 부등식 제약이 있는 접촉 해석은 선형 상보성 문제로 귀결되는데, 이는 QP의 KKT 조건과 사실상 한 몸이다.

QP가 이토록 편애받는 이유는, 어려운 비선형 문제를 국소적으로 2차 근사하면 매번 QP가 튀어나오기 때문이다. “일단 2차로 근사하고 QP로 풀어”가 비선형 최적화의 국룰인 셈.2

3. KKT 조건[편집]

QP의 최적해가 만족해야 하는 필요조건이 카루시-쿤-터커 조건(KKT)이다. 등식·부등식 제약에 라그랑주 승수 λ,μ\boldsymbol{\lambda}, \boldsymbol{\mu}를 붙인 라그랑지안을 세우고 정류 조건을 쓰면, 볼록 QP에서는 KKT가 필요충분조건이 된다. 등식 제약만 있는 경우 KKT 시스템은 하나의 큰 선형계로 깔끔하게 정리된다.

[QE⊤E0][xλ]=[−cd]\begin{bmatrix} Q & E^\top \\ E & 0 \end{bmatrix} \begin{bmatrix} \mathbf{x} \\ \boldsymbol{\lambda} \end{bmatrix} = \begin{bmatrix} -\mathbf{c} \\ \mathbf{d} \end{bmatrix}

이 대칭 부정부호(saddle-point) 시스템을 KKT 시스템이라 부른다. 즉 등식 제약 QP는 결국 선형계 하나 푸는 문제로 환원되며, 이걸 안정적으로 푸는 것이 QP 솔버 내부의 핵심 연산이다. 골치 아픈 건 부등식 제약 Ax≤bA\mathbf{x}\le\mathbf{b}의 상보성 조건 μi(Aix−bi)=0\mu_i (A_i\mathbf{x} - b_i) = 0인데, “제약이 등호로 활성인지 부등호로 비활성인지”를 알아내는 조합 문제가 여기서 생긴다. 이 조합을 어떻게 다루느냐로 QP 알고리즘이 두 갈래로 갈린다.

4. 활성 집합법[편집]

활성 집합법(active-set method)은 어느 부등식 제약이 최적해에서 등호로 걸리는지(활성 집합)를 반복적으로 추측하며 좁혀 나가는 방식이다.

  1. 현재 활성이라 가정한 제약들을 등식으로 고정하고, 등식 제약 QP(위의 KKT 선형계)를 푼다.
  2. 해가 나머지 부등식 제약을 위반하면, 위반한 제약을 활성 집합에 추가한다.
  3. 라그랑주 승수가 음수인(즉 떼어내야 이득인) 활성 제약이 있으면 집합에서 제거한다.
  4. 활성 집합이 더는 변하지 않으면 종료.

선형계획법의 심플렉스법과 사촌뻘로, 한 번에 제약 하나씩 넣고 빼며 꼭짓점을 옮겨 다닌다. 제약 수가 적고 중간 규모인 문제, 그리고 비슷한 QP를 반복해서 푸는 경우(웜 스타트가 강력)에 특히 유리하다. SQP 내부 QP 솔버로 애용되는 이유가 이 웜 스타트 궁합이다. 단점은 최악의 경우 활성 집합 조합이 지수적으로 많아질 수 있다는 것.3

5. 내부점법[편집]

내부점법(interior-point method)은 정반대 전략이다. 제약 경계를 밟지 않고 실현가능 영역 내부를 가로질러 최적해로 접근한다. 부등식 제약을 로그 장벽 함수로 목적함수에 녹여

min⁡x  12x⊤Qx+c⊤x−τ∑iln⁡(bi−Aix)\min_{\mathbf{x}} \; \frac{1}{2}\mathbf{x}^\top Q \mathbf{x} + \mathbf{c}^\top \mathbf{x} - \tau \sum_i \ln(b_i - A_i \mathbf{x})

로 바꾼 뒤, 장벽 파라미터 τ\tau를 0으로 줄여 가며 각 단계의 완화된 KKT 시스템을 뉴턴-랩슨법으로 푼다. 활성 집합 조합을 아예 건드리지 않으므로, 제약이 수만·수십만 개인 대규모 QP에서 반복 횟수가 문제 크기에 거의 무관하게 일정하다는 것이 최대 강점. 대신 매 반복이 무겁고(큰 선형계 한 번씩), 웜 스타트가 활성 집합법만큼 잘 먹지 않는다. 대규모·희소 문제는 내부점법, 중규모·반복 호출은 활성 집합법이 대략적인 선택 기준이다.4

6. SQP와의 관계[편집]

QP가 실무에서 가장 빛나는 무대는 순차 이차계획법(Sequential Quadratic Programming, SQP)이다. 일반적인 비선형 제약 최적화를 풀 때, SQP는 매 반복마다 목적함수를 2차로, 제약을 1차로 테일러 근사해 QP 부분문제를 하나 만들고 그것을 푼다. 이때 QP의 QQ 자리에는 라그랑지안의 헤세 행렬(또는 준-뉴턴법식 BFGS 근사)이 들어간다. 즉 위상 최적화·형상 최적화 같은 공학 최적화의 반복 한 스텝 한 스텝이 전부 QP를 푸는 일이다. QP가 비선형 최적화 세계의 벽돌인 이유가 여기 있다.

7. 관련 문서[편집]

8. Footnotes[편집]

  1. QQ가 양의 준정부호면 볼록 QP라 다항 시간에 풀리지만, 부정부호 QP는 국소 최소가 우글거려 NP-난해다. 목적함수 하나가 2차냐 아니냐로 천국과 지옥이 갈린다. ↩

  2. “어려우면 2차로 근사해서 QP로 풀어라”는 최적화판 국룰이다. 비선형이 무서우면 일단 국소적으로 QP로 만들어 놓고 반복하는 것이 SQP의 정신. ↩

  3. 활성 집합법의 웜 스타트는 “이전에 푼 QP의 활성 집합에서 조금만 바꾸면 된다”는 아이디어인데, MPC처럼 매 주기 비슷한 QP를 푸는 상황에서는 거의 사기적으로 빠르다. ↩

  4. 활성 집합법 대 내부점법은 QP 세계의 오랜 종교전쟁이다. 결론은 늘 “문제 나름”이라, 상용 솔버(Gurobi, MOSEK 등)는 둘 다 넣어두고 골라 쓰게 한다. ↩