7.107 이차 계획 문제의 표준형

1. 이차 계획의 정의

이차 계획(Quadratic Programming, QP) 문제는 이차 목적 함수를 선형 제약 조건하에서 최소화하는 최적화 문제이다. 표준형은 다음과 같다.

\min_{\mathbf{x} \in \mathbb{R}^n} \quad \frac{1}{2}\mathbf{x}^T\mathbf{H}\mathbf{x} + \mathbf{c}^T\mathbf{x}

\text{subject to} \quad \mathbf{A}_{eq}\mathbf{x} = \mathbf{b}_{eq}

\mathbf{A}_{ineq}\mathbf{x} \leq \mathbf{b}_{ineq}

여기서 \mathbf{H} \in \mathbb{R}^{n \times n}은 대칭 행렬(헤시안), \mathbf{c} \in \mathbb{R}^n은 선형 비용 벡터, \mathbf{A}_{eq} \in \mathbb{R}^{p \times n}과 \mathbf{b}_{eq} \in \mathbb{R}^p는 등식 제약의 행렬과 벡터, \mathbf{A}_{ineq} \in \mathbb{R}^{m \times n}과 \mathbf{b}_{ineq} \in \mathbb{R}^m은 부등식 제약의 행렬과 벡터이다.

2. 볼록 이차 계획

\mathbf{H} \succeq 0 (양의 반정치)이면 목적 함수가 볼록이 되어 볼록 QP가 된다. 볼록 QP에서는 모든 국소 최적해가 전역 최적해이며, 다항 시간 내에 풀 수 있는 효율적 알고리즘이 존재한다.

\mathbf{H} \succ 0 (양정치)이면 목적 함수가 강볼록이 되어 해가 유일하다. \mathbf{H} \succeq 0이지만 양정치가 아닌 경우, 최적해가 유일하지 않을 수 있으나 최적 목적 함수값은 유일하다.

\mathbf{H}가 부정치(indefinite)이면 비볼록 QP가 되어 NP-어려운 문제에 속한다. 로봇 공학에서 다루는 대부분의 QP는 볼록이다.

3. 대안적 표준형

다양한 QP 해법기(solver)는 서로 다른 형식의 입력을 요구한다.

3.1 일반 부등식 형식

\min_{\mathbf{x}} \quad \frac{1}{2}\mathbf{x}^T\mathbf{H}\mathbf{x} + \mathbf{c}^T\mathbf{x} \quad \text{s.t.} \quad \mathbf{l} \leq \mathbf{A}\mathbf{x} \leq \mathbf{u}, \quad \mathbf{l}_x \leq \mathbf{x} \leq \mathbf{u}_x

구간 제약과 일반 부등식 제약을 상하한의 쌍으로 표현한다. OSQP, qpOASES 등의 해법기가 이 형식을 사용한다.

3.2 여유 변수 포함 형식

부등식 제약에 비음 여유 변수 \mathbf{s} \geq \mathbf{0}을 도입하여 등식 제약으로 변환한다.

\mathbf{A}_{ineq}\mathbf{x} + \mathbf{s} = \mathbf{b}_{ineq}, \quad \mathbf{s} \geq \mathbf{0}

내점법 기반 해법기에서 이 형식이 사용된다.

4. KKT 시스템

볼록 QP의 KKT 조건은 다음의 선형-상보성 시스템으로 표현된다.

\mathbf{H}\mathbf{x} + \mathbf{c} + \mathbf{A}_{eq}^T\boldsymbol{\nu} + \mathbf{A}_{ineq}^T\boldsymbol{\mu} = \mathbf{0}

\mathbf{A}_{eq}\mathbf{x} = \mathbf{b}_{eq}

\mathbf{A}_{ineq}\mathbf{x} \leq \mathbf{b}_{ineq}, \quad \boldsymbol{\mu} \geq \mathbf{0}

\mu_i(\mathbf{a}_i^T\mathbf{x} - b_i) = 0, \quad i = 1, \ldots, m

등식 제약만 존재하는 경우, KKT 조건은 다음의 선형 시스템으로 환원된다.

\begin{bmatrix} \mathbf{H} & \mathbf{A}_{eq}^T \\ \mathbf{A}_{eq} & \mathbf{0} \end{bmatrix} \begin{bmatrix} \mathbf{x} \\ \boldsymbol{\nu} \end{bmatrix} = \begin{bmatrix} -\mathbf{c} \\ \mathbf{b}_{eq} \end{bmatrix}

이 KKT 행렬은 부정치 대칭 행렬이며, LDL 분해로 효율적으로 풀 수 있다.

5. 희소 구조의 활용

로봇 궤적 최적화에서 이산화된 QP는 시간 단계에 따른 밴드 구조(banded structure)를 갖는다. 인접한 시간 단계의 변수만이 동역학 제약으로 결합되므로, KKT 행렬이 희소(sparse)하다. 이 희소 구조를 활용한 효율적 분해가 실시간 성능의 핵심이다.

6. 로봇 공학에서의 QP 응용

로봇 공학은 이차 계획법의 가장 활발한 응용 분야 중 하나이다.

전신 운동 제어: 로봇의 각 관절 토크를 결정하기 위해, 과업 우선순위와 물리적 제약을 QP로 정식화한다.

\min_{\ddot{\mathbf{q}}, \boldsymbol{\tau}} \quad \lVert \mathbf{J}\ddot{\mathbf{q}} + \dot{\mathbf{J}}\dot{\mathbf{q}} - \ddot{\mathbf{x}}_d \rVert^2

\text{s.t.} \quad \mathbf{M}\ddot{\mathbf{q}} + \mathbf{h} = \boldsymbol{\tau} + \mathbf{J}_c^T\mathbf{f}_c

\boldsymbol{\tau}_{\min} \leq \boldsymbol{\tau} \leq \boldsymbol{\tau}_{\max}

모델 예측 제어(MPC): 선형화된 시스템 모델에 기반한 MPC에서 유한 시간 지평의 최적 제어 문제가 QP로 정식화된다.

역동역학 최적화: 주어진 관절 가속도를 달성하는 최소 노름 토크를 구하는 문제가 QP이다.

7. 대표적 QP 해법기

로봇 제어 주기(1~10ms)에서의 QP 해법에는 웜 스타트(warm start) 기능이 특히 중요하며, 이전 해를 초기 추정으로 활용하여 수렴에 필요한 반복 횟수를 최소화한다.

8. 참고 문헌

• Nocedal, J., & Wright, S. J. (2006). Numerical Optimization (2nd ed.). Springer.
• Boyd, S., & Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press.
• Ferreau, H. J., Kirches, C., Potschka, A., Bock, H. G., & Diehl, M. (2014). “qpOASES: A Parametric Active-Set Algorithm for Quadratic Programming.” Mathematical Programming Computation, 6(4), 327–363.
• Stellato, B., Banjac, G., Goulart, P., Bemporad, A., & Boyd, S. (2020). “OSQP: An Operator Splitting Solver for Quadratic Programs.” Mathematical Programming Computation, 12(4), 637–672.

version: 1.0