제1부 수학적 기초

1.17 최적화 V: 다항식 최적화와 인증 — 반정부호 계획법(SDP)·제곱합(SOS)·리아푸노프 함수 탐색

1.17.1 이 장에서 배우는 것 / 선수 지식 / 특히 중요한 독자

이 장은 다항식이 모든 점에서 0 이상임을 계산으로 증명하는 방법을 다룬다. 샘플 점에서 부등식을 점검하면 반례는 찾을 수 있으나 부등식이 모든 점에서 성립함은 보일 수 없다. 다항식을 제곱합으로 나타내면 이 증명이 반정부호 계획법(SDP, semidefinite programming)의 실현 가능성(feasibility) 문제로 바뀌고, 수치 해법기가 이를 푼다. 이 방법으로 다항 시스템의 리아푸노프 함수를 탐색하고 도달 영역(영역 안의 모든 초기 상태가 평형점으로 수렴하는 집합)을 추정한다. 다룰 질문은 다섯 가지다. SDP와 선형 행렬 부등식(LMI)은 무엇인가, 제곱합 분해는 Gram 행렬과 어떻게 대응하는가, 비음 다항식 가운데 제곱합이 아닌 것은 무엇인가, 리아푸노프 조건은 어떻게 제곱합 조건이 되는가, 수치 해법기의 해는 어떤 조건에서 정확한 증명이 되는가.

배우는 것:

• SDP와 LMI — 원 형태·쌍대 형태, 약한 쌍대성, 선형계의 공통 리아푸노프 LMI.
• 제곱합과 Gram 행렬 — 단항식 기저, 계수 일치 제약, 반 뉴턴 다면체에 의한 기저 축소.
• 제곱합의 한계 — 힐베르트의 결과, 모츠킨 다항식, 승수를 곱하는 방법.
• 리아푸노프 함수 탐색 — 선형계의 방정식, 다항계의 SOS 조건, 도달 영역의 S-절차.
• 인증 — 수치 해의 음의 고유값, 유리수 반올림·정확한 투영·유리수 LDL 검사.
• 라이브러리 확인 — cvxpy·SCS·Clarabel과 Drake의 제곱합 제약을 같은 입력으로 비교.

선수 지식: 1.1(LU·QR), 1.9(야코비 고유분해), 1.13(볼록 최적화와 내점법), 12.2(리아푸노프 안정성). 표기는 BK-05와 A.2을 따른다.

특히 중요한 독자: 안정성·안전 조건을 계산으로 증명하려는 제어 연구자, 인증 가능한 알고리즘을 구현하는 엔지니어, 수치 해법기의 출력을 증거로 사용하려는 검증 담당자.

출처 방침. 서지는 Crossref·arXiv 응답으로 확인했다(목록은 이 장 끝). 직접 읽은 자료: ① Drake solvers/mathematical_program.h(master)의 AddSosConstraint 문서 주석, ② SOSTOOLS의 README.md와 sosprogram.m 머리말, ③ SPOTless의 doc/manual.tex, ④ SumOfSquares.jl의 README.md, ⑤ cvxpy 1.9.3 패키지 소스(문자열 검색)와 SCS 3.3.1·Clarabel 0.11.1의 패키지 설명. 직접 실행한 것: cvxpy 1.9.3·SCS 3.3.1·Clarabel 0.11.1(Python 3.12.3, NumPy 2.5.4)과 Drake 1.58.0(PyPI 휠), 조회·실행 2026-11-03. 읽지 못한 것: 인용한 논문·교과서의 본문(정리 번호는 (확인 필요)), SOSTOOLS·SPOTless·SumOfSquares.jl의 실행. 이 장의 수치는 모두 순수 파이썬(표준 라이브러리) 계산이며 1.1의 LU와 1.9의 야코비 고유분해를 불러와 사용했다. SDP는 cvxpy·Drake로 풀고 그 해를 같은 입력의 순수 파이썬 검증기로 점검했다.

1.17.2 개념 — 샘플 점검과 증명

다항식 $p(x)$가 모든 $x\in\mathbb{R}^n$에서 $p(x)\ge0$인지 판정하는 문제는 일반적으로 계산이 어렵다 (확인 필요: 출처). 샘플 점검은 위반 점을 찾으면 반증이 되지만 위반 점이 없어도 증명은 아니다. 제곱합은 증명 가능한 충분조건이다. $p=\sum_kq_k^2$이면 $p\ge0$이고, 제곱합 여부는 반정부호 행렬의 존재 문제이므로 SDP 해법기로 판정한다.

리아푸노프 함수의 탐색은 이 구조에 그대로 들어맞는다. 벡터장이 다항식이면 리아푸노프 조건 $V>0$, $\dot V<0$이 두 개의 다항 부등식이고, 각각을 제곱합 조건으로 바꾸면 $V$의 계수를 미지수로 하는 하나의 SDP가 된다. 안정성·제어 장벽 함수·도달성 인증의 응용은 12.2·12.25·12.21이 맡고, 이 장은 수학적 도구와 그 수치적 한계를 다룬다.

이 장에서 인증(certificate)은 수학적 증명을 뜻하며 제품 인증·규제 인증(certification)과 다르다(1.17.9). 수치 해법기가 반환한 해에는 반올림 오차가 있으므로 그 자체로는 증명이 아니다. 해에서 증명으로 가는 간극을 측정하는 것이 이 장의 목적 가운데 하나이다.

1.17.3 원리

1.17.3.1 반정부호 계획법과 선형 행렬 부등식

결론: SDP는 대칭 행렬 변수의 반정부호성을 제약으로 가지는 볼록 최적화이다. 선형 행렬 부등식(LMI)은 같은 제약을 스칼라 변수의 아핀 함수로 나타낸 것이며, 제어의 많은 안정성 조건이 LMI로 표현된다.

원 형태와 쌍대 형태는 다음과 같다. $\langle A,B\rangle=\mathrm{tr}(A^\top B)$, $\succeq$는 반정부호이다.

$$\min_{X}\ \langle C,X\rangle\ \ \text{s.t.}\ \ \langle A_i,X\rangle=b_i\ (i=1,\dots,m),\ X\succeq0 \qquad\qquad \max_{y}\ b^\top y\ \ \text{s.t.}\ \ S=C-\sum_iy_iA_i\succeq0$$

원 실현 가능해 $X$와 쌍대 실현 가능해 $(y,S)$에 대해 $\langle C,X\rangle-b^\top y=\langle X,S\rangle\ge0$이다(두 반정부호 행렬의 내적은 0 이상). 이 약한 쌍대성은 쌍대 목적값이 원 목적값의 하한임을 말한다. 두 문제가 모두 엄격 실현 가능(strictly feasible, 양정부호 해가 존재)하면 간극이 0이라는 강한 쌍대성은 표준 결과이며 (확인 필요: 정리 번호), 이 장이 다루는 인증 문제에서는 엄격 실현 가능성이 뒤의 1.17.3.6에서 핵심이 된다. LMI는 $F(x)=F_0+\sum_ix_iF_i\succeq0$이며, 스칼라 변수 $x_i$에 대한 SDP의 실현 가능성 문제이다. 선형 계획·이차 계획·2차 원뿔 계획은 SDP의 특수한 경우이고 내점법이 이를 푼다(1.13). SDP의 이론과 응용은 Vandenberghe와 Boyd(1996), 제어에서의 LMI는 Boyd 외(1994)가 정리했다(서지만 확인했다).

1.17.3.2 다항식의 제곱합과 Gram 행렬

결론: 차수 $2d$인 다항식 $p$가 제곱합일 필요충분조건은 단항식 벡터 $z(x)$에 대해 $p=z^\top Qz$인 반정부호 행렬 $Q$가 존재하는 것이다. 계수 일치는 $Q$의 아핀 제약이므로 제곱합 판정은 SDP의 실현 가능성 문제이다.

$Q=\sum_kc_kc_k^\top\succeq0$이면 $p=\sum_k(c_k^\top z)^2$이고, 역으로 $p=\sum_kq_k^2$, $q_k=c_k^\top z$이면 $Q=\sum_kc_kc_k^\top\succeq0$이다. 단항식 $x^\alpha$의 계수 일치는 $\sum_{\beta+\gamma=\alpha}Q_{\beta\gamma}=p_\alpha$이다. $n$변수·차수 $d$ 이하의 단항식은 $\binom{n+d}{d}$개이므로 $Q$의 크기가 변수 수와 차수에 따라 빠르게 커진다(1.17.6의 표). 이 표현은 Powers와 Wörmann(1998), Parrilo(2003)가 다룬다(서지만 확인했다). 같은 단항식을 만드는 칸이 여럿이어서 Gram 행렬은 일반적으로 유일하지 않다. 예를 들어 $p=2x^4+2x^3y-x^2y^2+5y^4$는 $z=(x^2,xy,y^2)$에서

$$Q(\lambda)=\begin{bmatrix}2&1&\lambda\\1&-1-2\lambda&0\\\lambda&0&5\end{bmatrix}$$

이고 $\lambda$는 $x^2y^2$의 계수 $2Q_{13}+Q_{22}=-1$에서 생긴 자유 매개변수이다. 제곱합의 항에 나타나는 단항식은 $p$의 지수 집합의 볼록 껍질(뉴턴 다면체)의 절반 안에 있는 정수점으로 제한된다는 결과가 알려져 있으며 (확인 필요: 출처), 이 장은 이를 기저 축소에 사용한다. Drake의 AddSosConstraint는 기저를 $p$의 희소성에서 선택한다고 문서 주석이 밝히고, 이 장의 세 입력에서 선택한 기저의 크기(3·9·3)는 이 장의 반 뉴턴 다면체 정수점의 수와 같았다.

1.17.3.3 제곱합의 한계 — 힐베르트와 모츠킨

결론: 모든 비음 다항식이 제곱합은 아니다. 제곱합이 아닌 비음 다항식도 적당한 제곱합 승수를 곱하면 제곱합이 되는 경우가 있다.

힐베르트(1888)는 $n$변수 차수 $2d$의 동차 다항식에서 비음성과 제곱합이 같아지는 경우가 $n=2$, $2d=2$, $(n,2d)=(3,4)$뿐임을 보였다고 알려져 있으며 (확인 필요: 정리 번호), 그 밖에는 비음이지만 제곱합이 아닌 다항식이 존재한다. 대표 예는 모츠킨 다항식이다 (확인 필요: 원 출처·연도).

$$M(x,y)=x^4y^2+x^2y^4-3x^2y^2+1$$

산술-기하 평균 부등식으로 $x^4y^2+x^2y^4+1\ge3x^2y^2$이므로 $M\ge0$이고 등호는 $\lvert x\rvert=\lvert y\rvert=1$에서 성립한다. $M$이 제곱합이 아닌 이유는 짧은 논증으로 보일 수 있다. $M=\sum_kq_k^2$이면 각 $q_k$는 반 뉴턴 다면체의 정수점 $\{1,\,xy,\,x^2y,\,xy^2\}$만 포함한다. $x^2y^2$은 이 네 단항식의 곱 가운데 $(xy)^2$에서만 생기므로 $M$의 $x^2y^2$ 계수는 각 $q_k$의 $xy$ 계수의 제곱합이어서 0 이상이어야 하는데, 실제 계수는 $-3$이다. 아르틴(1927)은 모든 비음 다항식이 유리 함수의 제곱합임을 보였고(힐베르트의 17번 문제), 승수를 곱하는 방법은 이 결과의 계산 가능한 형태이다. 17번 문제의 구체적인 측면은 Reznick(2000)이 정리했다(서지만 확인했다). $(x^2+y^2+1)M$은 제곱합이며, 1.17.5에서 다섯 제곱의 항등식을 유리수 연산으로 확인한다.

1.17.3.4 선형계의 리아푸노프 방정식과 LMI

결론: 선형계 $\dot x=Ax$가 점근 안정일 필요충분조건은 임의의 $Q\succ0$에 대해 $A^\top P+PA=-Q$의 해 $P$가 양정부호인 것이다. 방정식은 선형 연립방정식이므로 LU 분해 1회로 풀고, 모델 불확실성이 있으면 방정식 대신 LMI로 공통 $P$를 찾는다.

$V(x)=x^\top Px$이면 $\dot V=x^\top(A^\top P+PA)x$이다. 방정식은 크로네커 곱으로 $(I\otimes A^\top+A^\top\otimes I)\,\mathrm{vec}(P)=-\mathrm{vec}(Q)$이고, 계수 행렬의 고유값은 $\lambda_i+\lambda_j$이므로 $\lambda_i+\lambda_j\ne0$이면 해가 유일하다. 꼭짓점이 $A_1,\dots,A_k$인 다포체 모델에는 $P\succ0$, $A_i^\top P+PA_i\prec0$인 공통 $P$를 LMI로 구한다. 방정식은 꼭짓점마다 다른 해를 주므로 하나의 꼭짓점의 해가 다른 꼭짓점에서 성립한다는 보장이 없다(1.17.5의 ①).

1.17.3.5 다항 시스템의 SOS 리아푸노프 함수와 도달 영역

결론: 벡터장이 다항식이면 리아푸노프 조건이 제곱합 조건이 되고 $V$의 계수에 대해 선형이므로 하나의 SDP로 $V$를 탐색한다. 전역 조건은 전역 점근 안정성의 인증이 되고, 국소 조건은 S-절차로 도달 영역의 인증된 부분집합을 준다.

$\dot x=f(x)$, $f(0)=0$이고 $f$가 다항식일 때 $V(x)-\varepsilon\lVert x\rVert^2$과 $-\nabla V\cdot f-\varepsilon\lVert x\rVert^2$이 모두 제곱합이면 $V\ge\varepsilon\lVert x\rVert^2$, $\dot V\le-\varepsilon\lVert x\rVert^2$이다. $V$는 양정부호이고 반경 무한대이므로 평형점은 전역 점근 안정이다(리아푸노프의 정리, 12.2). $V$를 2차식으로 한정하면 전역 인증이 불가능한 계가 있고, 차수를 올리면 가능해지는 경우가 있다. SOS 분해로 리아푸노프 함수를 구성하는 접근은 Papachristodoulou와 Prajna(2002, 2005)가 다룬다(제목과 서지만 확인했다) (확인 필요: 구성 세부).

도달 영역은 고정한 $V$와 $c$에 대해 $-\dot V-\varepsilon\lVert x\rVert^2-s(x)\,(c-V(x))$가 제곱합이고 승수 $s$가 제곱합이면 $\{V\le c\}\setminus\{0\}$에서 $\dot V<0$이므로 $\{V\le c\}$가 도달 영역의 부분집합이라는 것이다(S-절차). $V$가 양정부호이면 이 집합은 유계이다. $c$는 이분법으로 최대화한다. $V$와 $s$를 동시에 미지수로 두면 쌍선형이 되어 번갈아 최적화하는 방식이 사용되며 (확인 필요: Tan·Packard 2008의 구성), 이 장은 $V$를 고정한 경우만 계산한다. 로봇에서는 이 인증을 궤적 주위의 안전 영역(funnel)에 사용한 연구가 있다(Tedrake 외 2010, Majumdar·Tedrake 2017 — 제목과 서지만 확인했다).

1.17.3.6 수치 해와 인증 사이의 간극

결론: SDP 해법기는 부동소수점 근사해를 반환하므로 Gram 행렬이 정확히 반정부호이고 계수가 정확히 일치한다는 보장이 없다. 인증은 이 근사해를 정확한 유리수 증명으로 바꾸는 별도의 단계이며, 성공 여부는 해의 여유(엄격 실현 가능성)와 반올림 분모에 의존한다.

수치 해 $\hat Q$에는 두 가지 결함이 있다. 계수 잔차 $p-z^\top\hat Qz$가 0이 아니고, $\lambda_{\min}(\hat Q)$가 해법기 허용오차 크기의 음수일 수 있다. 다항식이 영점을 가지면(예: 모츠킨 곱은 $\lvert x\rvert=\lvert y\rvert=1$에서 0) 모든 실현 가능 Gram 행렬이 특이해서 여유가 없고, 해법기의 해는 허용오차 수준의 음의 고유값을 가진다. 이때 "$\lambda_{\min}\ge0$" 검사는 항상 실패한다.

정확한 인증은 세 단계이다. ① $\hat Q$를 분모 $N$의 유리수로 반올림한다. ② 각 단항식의 계수 잔차를 그 단항식을 만드는 칸에 균등하게 나누어 $z^\top Rz=p$가 정확히 성립하는 $R$로 투영한다. ③ $R$의 유리수 LDL$^\top$를 계산해 모든 피벗이 0 이상이고 0인 피벗의 열이 0이면 $R\succeq0$이다. 성공하면 $p=\sum_kd_k(l_k^\top z)^2$이 유리수 계수의 항등식으로 성립하며 이후의 증명은 부동소수점에 의존하지 않는다. 이 계열의 방법은 Peyrl과 Parrilo(2008), Kaltofen 외(2012)가 다룬다 (확인 필요: 본문 미확인, 이 장의 구현은 이 장이 구성한 단순한 변형). 반올림과 투영이 바꾸는 크기가 $\lambda_{\min}(\hat Q)$보다 작으면 $R$은 양정부호이다(바일의 고유값 섭동 부등식). 여유가 없는 해에서는 이 논리가 성립하지 않고 반올림과 투영이 음의 고유값을 만들 수 있다. 다항식에 $\delta\sum_iz_i^2$를 더하면 여유가 $\delta$ 이상이 되지만 증명하는 대상이 바뀐다. 제곱합 계획의 전처리와 후처리는 Löfberg(2009)가 다룬다(서지만 확인했다).

1.17.4 알고리즘

sos_certify(p, 기저 z, 분모 N):                        (p의 계수는 유리수)
  Q̂ ← SDP 해  [ Σ_{β+γ=α} Q_βγ = p_α (모든 α),  Q ⪰ 0 ]      (수치)
  R ← round(Q̂, N), 대칭화                                    (유리수)
  각 단항식 α: r_α ← p_α − (zᵀRz)_α ;  α를 만드는 칸마다 r_α / (칸 수)를 더한다
  (d, L) ← LDLᵀ(R) (유리수 연산)
  d_k < 0 이거나, d_k = 0 인데 그 열에 0이 아닌 성분이 있으면 실패
  성공하면  p = Σ d_k (l_kᵀ z)²  (항등식)
lyap_search(f, 차수 2d, ε):
  V ← 차수 2..2d 단항식의 미지 계수 다항식 ;  V' ← ∇V · f  (계수의 선형식)
  SDP: V − ε‖x‖² = z₁ᵀQ₁z₁ ,  −V' − ε‖x‖² = z₂ᵀQ₂z₂ ,  Q₁, Q₂ ⪰ 0
  기저 축소: 해에서 Q의 대각이 0인 단항식을 z에서 제거하고 다시 푼다
  V 의 계수를 유리수로 반올림해 V' 를 정확히 계산하고 sos_certify 로 Q₁, Q₂ 를 확인
roa(V, f): c 를 이분법으로 올린다; 각 c 에서  −V' − ε‖x‖² − s (c − V) = SOS,  s = SOS  의 실현 가능성

1.17.5 풀이 예제 — 리아푸노프 방정식·제곱합 분해·인증·SOS 리아푸노프 함수·도달 영역

다섯 계산을 수행한다. 결론부터 적으면 다음과 같다. ① 무작위 안정 4차 행렬 400개에서 방정식의 해 $P$가 모두 양정부호이고 불안정 400개에서는 하나도 양정부호가 아니다. 두 꼭짓점 모델에서는 방정식의 해가 공통 $P$가 아니며 LMI 해가 공통 $P$이다. ② 4차식의 Gram 행렬은 $\lambda\in[-3,\,-0.766]$에서 반정부호이다. ③ 모츠킨 다항식은 제곱합이 아니고 $(x^2+y^2+1)M$은 다섯 제곱의 합이며, 기본 허용오차의 해법기는 최소 고유값이 $-1.66\times10^{-8}$~$-3.11\times10^{-8}$이고 SCS $10^{-8}$ 설정에서도 $-1.85\times10^{-14}$여서 고유값 검사에 모두 실패하지만 유리수 투영과 정확한 LDL 검사는 통과한다. ④ 두프 유형 관절 모델은 2차 $V$가 없고 4차 $V$를 SDP가 찾으며 유리수 인증을 통과한다. ⑤ 반 데르 폴 역시간계에서 SOS로 인증한 수준집합은 독립 계산과 0.1 % 안에서 일치하고 극한 순환에 내접하는 최대 $V$ 수준집합 넓이의 60.3 %이다.

구현. lyap_solve·round_project·ldl_exact·certify(코드 블록). 1.1의 LU 분해·행렬 곱(스크립트의 solve_lu), 1.9.5의 eigsym

from fractions import Fraction as Fr

def lyap_solve(A, Q):
    """A^T P + P A = -Q 의 크로네커 벡터화 풀이"""
    n = len(A)
    M = [[0.0] * (n * n) for _ in range(n * n)]
    for i in range(n):
        for j in range(n):
            for k in range(n):
                M[i * n + j][k * n + j] += A[k][i]
                M[i * n + j][i * n + k] += A[k][j]
    b = [-Q[i][j] for i in range(n) for j in range(n)]
    x, _ = solve_lu(M, b)
    return [x[i * n:(i + 1) * n] for i in range(n)]

def pmul(p, q):
    """다항식은 {지수 튜플: 계수}"""
    r = {}
    for a, u in p.items():
        for b, v in q.items():
            m = tuple(i + j for i, j in zip(a, b))
            r[m] = r.get(m, 0) + u * v
    return r

def lie(V, f):
    """V' = sum_i (dV/dx_i) f_i"""
    r = {}
    for i, fi in enumerate(f):
        dV = {m[:i] + (m[i] - 1,) + m[i + 1:]: m[i] * v
              for m, v in V.items() if m[i]}
        for m, v in pmul(dV, fi).items():
            r[m] = r.get(m, 0) + v
    return r

def gram_poly(basis, Q):
    """z^T Q z 의 계수"""
    r = {}
    for i, a in enumerate(basis):
        for j, b in enumerate(basis):
            m = tuple(map(sum, zip(a, b)))
            r[m] = r.get(m, 0) + Q[i][j]
    return r

def round_project(basis, p, Q, den=10 ** 6):
    """Q를 분모 den의 유리수로 반올림, z^T R z = p 로 투영"""
    n = len(basis)
    R = [[Fr(round((Q[i][j] + Q[j][i]) * den / 2), den)
          for j in range(n)] for i in range(n)]
    pairs = {}
    for i in range(n):
        for j in range(n):
            m = tuple(map(sum, zip(basis[i], basis[j])))
            pairs.setdefault(m, []).append((i, j))
    g = gram_poly(basis, R)
    for m in set(p) | set(g):
        v = p.get(m, 0) - g.get(m, 0)
        if v and m not in pairs:
            return None
        for i, j in pairs.get(m, []):
            R[i][j] += v / len(pairs[m])
    return R

def ldl_exact(Q):
    """유리수 LDL^T: (피벗, L). 비반정부호이면 L = None"""
    n = len(Q)
    A = [r[:] for r in Q]
    L = [[Fr(i == j) for j in range(n)] for i in range(n)]
    d = []
    for k in range(n):
        d.append(A[k][k])
        if A[k][k] < 0:
            return d, None
        for i in range(k + 1, n):
            if A[k][k] == 0:
                if A[i][k] != 0:
                    return d, None
                continue
            L[i][k] = A[i][k] / A[k][k]
            for j in range(k + 1, n):
                A[i][j] -= L[i][k] * A[k][j]
    return d, L

def certify(basis, p, Q, den=10 ** 6):
    """Gram 행렬 Q의 정확한 인증: (성공, 양의 피벗 수)"""
    R = round_project(basis, p, Q, den)
    if R is None:
        return False, 0
    d, L = ldl_exact(R)
    return L is not None, sum(1 for x in d if x > 0)

① 리아푸노프 방정식과 LMI. 잔차는 $\lVert A^\top P+PA+Q\rVert_{\max}$를 $\lVert P\rVert_{\max}$로 나눈 값이다.

LMI는 $P\succeq I$, $A_i^\top P+PA_i\preceq-I$를 만족하는 $\mathrm{tr}\,P$ 최소 해를 cvxpy·Clarabel로 구한 것이며, 이 $P$를 순수 파이썬 고유분해로 점검하면 $\lambda_{\max}(A_i^\top P+PA_i+I)\le1.61\times10^{-9}$, $\lambda_{\min}(P-I)=0.125$이다. 꼭짓점 1의 방정식 해 $P_1$($Q=I$)을 꼭짓점 2에 적용하면 $\lambda_{\max}(A_2^\top P_1+P_1A_2)=0.081>0$이어서 $P_1$은 공통 리아푸노프 함수가 아니다. 불안정 행렬에서 $\lambda_{\min}(P)$의 최솟값이 매우 작은 것은 $\lambda_i+\lambda_j\approx0$ 근방에서 계수 행렬이 거의 특이해지기 때문이다.

② 4차식의 Gram 행렬과 제곱합 복원. $Q(\lambda)\succeq0$인 구간과 정확한 분해는 다음과 같다. 순수 파이썬 삼분 탐색의 최대점과 Clarabel의 최대 여유 해는 $\lambda$가 $7\times10^{-5}$ 다르나 $\lambda_{\min}$은 소수 여섯째 자리까지 같다(정점 근방이 평탄하다).

$\lambda=-3$은 구간의 경계로 세 번째 피벗이 0이어서 제곱이 2개이며, 곧 $\tfrac12(2x^2+xy-3y^2)^2+\tfrac12(3xy+y^2)^2$이다(손 계산으로 전개해 확인했다). 경계 밖의 $\lambda$에서는 $\lambda_{\min}<0$이다.

③ 모츠킨 다항식과 인증. $M-\gamma$는 $\gamma=-1,\,-10^3,\,-10^6$에서 cvxpy·Clarabel이 모두 비실현(infeasible)으로 판정했고 Drake도 $M$에 대해 kInfeasibleConstraints를 반환했다(SOS·DSOS·SDSOS 모두). 이는 1.17.3.3의 짧은 논증과 일치한다. 곱 $(x^2+y^2+1)M$에 대해서는 항등식 $(x^2+y^2+1)M=(x^2y-y)^2+(xy^2-x)^2+(x^2y^2-1)^2+\tfrac34(xy^3+x^3y-2xy)^2+\tfrac14(xy^3-x^3y)^2$의 계수 차이가 유리수 연산으로 0이다. 해법기별 결과는 다음과 같다. 반올림 분모 $N$마다 유리수 투영과 LDL 검사의 통과 여부를 적었다.

곱의 Gram 행렬은 유일한 것으로 보인다. 무작위 목적함수 4개로 푼 해 사이의 최대 차이가 $4.5\times10^{-7}$이다. 분모 $10^3$으로 반올림한 행렬의 원소는 $0,\,\pm1,\,3,\,-\tfrac32,\,\tfrac12$이고 LDL의 양의 피벗은 5개로 수치 계수와 같다. 분모 $10^6$에서 실패하는 행이 있고 통과 여부가 $N$에 대해 단조롭지 않다. 해법기 오차($10^{-8}$~$10^{-5}$)가 반올림 격자 간격과 비슷하거나 크면 반올림이 정확한 유리수 행렬로 수렴하지 못하기 때문으로 보이며 (추정), $p+10^{-2}\sum z_i^2$의 분모 10 실패는 격자 0.1이 여유 0.01보다 거칠기 때문으로 보인다 (추정). 이 다항식은 Gram 행렬이 분모가 작은 유리수이므로 거친 반올림으로 정확한 행렬이 복구되었고, 일반 다항식에서는 이 성질이 보장되지 않는다.

④ 두프 유형 관절의 SOS 리아푸노프 함수. 2차 $V$는 Clarabel이 비실현으로 판정했고 다음 논증으로도 확인된다. $V=x^\top Px$이면 $\dot V(tx)=t^2q(x)+t^4h(x)$이고 4차 동차 부분은 $h(x)=-2x_1^3(P_{12}x_1+P_{22}x_2)$이다. 모든 $x$에서 $h(x)\le0$이어야 하는데 $P_{22}>0$이면 $x_1=1$, $x_2$를 충분히 작은 음수로 잡을 때 $h>0$이다. 4차 $V=ax_1^2+bx_1x_2+cx_2^2+dx_1^4+\cdots$는 SDP가 찾았고 Gram 기저는 반복 축소로 줄었다(표). 기저에 $x_1^3x_2$를 만드는 단항식 쌍이 없으므로 $\dot V$의 $x_1^3x_2$ 계수 $4d-2c$가 0이어야 한다. 그래서 부동소수점 해의 계수를 100분의 1로 반올림하되 $c=2d$로 두었다. 결과는 $V=0.49x_1^2 + 0.4x_1x_2 + 0.5x_2^2 + 0.25x_1^4$이고 미분은 $\dot V=-0.4x_1^2 - 0.42x_1x_2 - 0.6x_2^2 - 0.4x_1^4$이다.

$-\dot V$는 이차 형식 $[x_1\ x_2]\begin{bmatrix}0.4&0.21\\0.21&0.6\end{bmatrix}[x_1\ x_2]^\top$(행렬식 $0.24-0.0441>0$)과 $0.4x_1^4$의 합이어서 손으로 양정부호임을 확인할 수 있다. 같은 두 다항식을 Drake AddSosConstraint에 넣으면 기저 3개로 모두 실현 가능하고, $V_0=\lVert x\rVert^2$의 $-\dot V_0$는 비실현이다. 샘플 점검은 peval로 $V$와 $\dot V$를 점마다 평가해 위반을 세는 반복문이다. $V_0$의 반례는 즉시 나타나지만 인증된 $V$의 위반은 한 점도 나타나지 않으며, 이것이 증명은 아니다.

⑤ 도달 영역 추정. $V=1.5x_1^2-x_1x_2+x_2^2$에서 $\dot V=-r^2+r^4g(\theta)$, $g=\cos^2\theta\sin\theta(2\sin\theta-\cos\theta)$이므로 $\dot V\ge0$인 점의 최소 $V$는 $c^\ast=\min_{g>0}q(\theta)/g(\theta)$($q(\theta)=V(\cos\theta,\sin\theta)$)로 독립 계산된다.

승수 차수 4의 값은 Clarabel이 예외(Rust panic Eigval error: Eigen(1) 2회, SolverError 2회)로 끝나 SCS로 대체한 4회의 평가를 포함한다. 인증된 최대 $c_{\mathrm{SOS}}=2.3022$는 독립 계산 2.3045보다 0.1 % 작다(여유 $\varepsilon$와 이분법 허용오차의 영향으로 보이며 (추정)). 승수 차수를 올려도 이 예에서는 개선되지 않았다. $V$를 2차식으로 고정했기 때문에 인증된 집합이 극한 순환에 내접하는 최대 수준집합보다 작다.

한계. 입력은 합성 모델이다. 무작위 행렬은 시드 35로 생성한 400개이며 특정 응용의 분포를 대표하지 않는다. ③의 통과·실패 패턴은 이 다항식의 유일하고 작은 분모의 Gram 행렬에 의존한다. Gram 행렬이 유일하다는 것은 수치 증거이며, 정확한 인증이 성공했다는 사실을 다른 입력에 일반화할 수 없다. ⑤는 $V$를 고정한 보수적인 추정이다.

견해: 안정성 증거로 SOS 해를 제출할 때 해법기 출력의 고유값 검사만으로는 증거로 보지 않고, 계수 일치를 정확히 만족하는 유리수 행렬의 정부호 검사를 별도의 단계로 두는 것이 바람직하다고 본다. 근거는 ③의 표에서 영점이 있는 입력에 대해 고유값 검사가 거짓 음성을 내고(모든 해법기에서 실패) 유리수 검사는 통과했다는 점이다. 반대 방향, 곧 해법기가 비실현인 다항식을 실현으로 반환하는 경우는 이 장에서 측정하지 않았다.

1.17.6 설계 트레이드오프 — 인증 방식의 선택

공개 문헌에서 확인되는 선택지는 네 가지다.

• ① 제곱합(SOS, SDP). 가장 포괄적인 다항 비음성 충분조건이다. Gram 행렬이 $\binom{n+d}{d}$ 크기여서 변수 수와 차수에 제한된다.
• ② DSOS·SDSOS. Gram 행렬을 대각 우세 또는 척도 대각 우세로 제한해 LP·2차 원뿔 계획으로 푼다(Ahmadi·Majumdar 2019, 제목과 서지만 확인). Drake가 kDsos·kSdsos로 제공한다. 이 장의 실행에서 4차식은 세 방식 모두 실현 가능했고 모츠킨 곱은 DSOS·SDSOS가 비실현이었다(Drake 1.58.0).
• ③ 샘플 점검. 반례 탐색에 비용이 가장 낮다. 위반이 없어도 증명이 아니다.
• ④ 정확한 형식 증명. 정리 증명기를 이용하는 방법으로 26.14가 다룬다.

Gram 행렬의 크기 $m=\binom{n+d}{d}$와 독립 변수 수는 다음과 같다.

견해: 상태 차원이 6 이상이고 차수가 3 이상인 모델에서는 SOS를 곧바로 적용하기보다 모델을 다항식으로 근사한 오차와 희소성·대각 우세 근사의 보수성을 먼저 평가해야 한다고 본다. 근거는 위 표의 Gram 행렬 크기 증가이며, 보수성의 정도는 이 장에서 측정하지 않았다.

1.17.7 응용 축 비교

이 표는 이 장의 정리이며 각 축에서 이 방법이 실제로 사용된다는 뜻이 아니다.

1.17.8 관련 규격·프로토콜

제곱합 계획에 국제 표준은 없다. 공개된 구현과 해법기의 사양을 아래에 정리한다. 조회·실행 2026-11-03이며 버전·저장소 상태는 시점 의존이다.

푸시 날짜는 유지의 대리 지표일 뿐이다(0.18). 문서·표준 번호의 목록은 A.3가 모은다.

1.17.9 관련 규제·인증 요구와의 연결

이 장의 인증은 수학적 증명이며 이를 직접 요구하는 규제는 확인하지 못했다. 제어기의 안정성 증명을 안전 증거로 제출할 수 있는지는 적용하는 규격이 정한다. 기능안전은 26.5, 시험·시뮬레이션 기반 검증과 안전 논증은 26.13, 정리 증명과 모델 검사는 26.14, 소프트웨어 안전과 품질 표준은 26.20이 다룬다. 수치 해법기와 이 장의 인증 코드를 안전 증거의 도구로 사용할 때의 도구 신뢰성 요건은 해당 규격의 조항을 확인하지 않았으므로 (확인 필요)이다.

1.17.10 한계·유의점·미해결

• 정리의 출처. 힐베르트·모츠킨·뉴턴 다면체 기저 축소·강한 쌍대성·S-절차의 정리 번호와 원 출처, Peyrl–Parrilo·Kaltofen 외의 방법 세부는 확인하지 않았다 (확인 필요).
• 정확한 인증의 범위. 이 장의 유리수 검사는 이 장의 구현이다. 입력 다항식에 영점이 있고 Gram 행렬이 분모가 큰 유리수이거나 무리수이면 반올림 방식은 실패할 수 있다. 이 경우를 다루는 방법(예: 면 축소)은 이 장에서 구현하지 않았다 (확인 필요: Permenter·Parrilo 2017은 서지만 확인).
• 모델 근사. 로봇의 삼각함수·마찰을 다항식으로 근사하면 인증은 근사 모델에 대한 것이다. 근사 오차를 포함하는 방법은 이 장에서 다루지 않았다.
• 규모. 상태 차원과 차수가 오르면 Gram 행렬 크기가 급증한다. DSOS·SDSOS·희소성 이용의 보수성은 측정하지 않았다.
• 라이브러리. SOSTOOLS·SPOTless·SumOfSquares.jl은 실행하지 않았다. Clarabel 0.11.1은 승수 차수 4의 도달 영역 문제에서 예외를 냈다. 원인은 분석하지 않았다.
• 다룬 범위. 다항식 전역 최적화의 모멘트 이완(Lasserre 2001, 서지만 확인)은 이 장이 다루지 않았다.
• 도달 영역. $V$를 고정한 추정만 계산했고 $V$와 승수를 번갈아 갱신하는 방법은 구현하지 않았다.

1.17.11 체크포인트·연구 질문

체크포인트:

1. SDP의 원 형태와 쌍대 형태를 적고 약한 쌍대성을 간단히 증명할 수 있는가.
2. 선형계의 리아푸노프 방정식을 크로네커 곱으로 풀고 불안정 행렬에서 $P$가 양정부호가 아닌 이유를 설명할 수 있는가.
3. 다항식이 제곱합일 조건을 Gram 행렬로 나타내고 계수 일치 제약을 세울 수 있는가.
4. 모츠킨 다항식이 제곱합이 아닌 이유를 반 뉴턴 다면체로 설명할 수 있는가.
5. $V-\varepsilon\lVert x\rVert^2$와 $-\dot V-\varepsilon\lVert x\rVert^2$의 제곱합 조건이 전역 점근 안정성을 보이는 이유를 설명할 수 있는가.
6. S-절차로 $\{V\le c\}$가 도달 영역의 부분집합임을 보이는 조건을 쓸 수 있는가.
7. 수치 해의 $\lambda_{\min}<0$이 인증의 실패를 뜻하지 않는 경우와 뜻하는 경우를 구분할 수 있는가.
8. 유리수 반올림·정확한 투영·유리수 LDL의 세 단계와 실패 조건을 설명할 수 있는가.

연구 질문(47.12에 수록한다):

• 영점이 있는 다항식과 일반 다항식에서 반올림·투영 방식의 정확한 인증이 성공하는 비율은 해법기 허용오차와 분모에 따라 어떻게 달라지는가.
• 로봇 모델의 다항식 근사 오차를 SOS 인증에 포함하는 방법은 인증된 도달 영역을 얼마나 줄이는가.
• 희소성·대각 우세 근사는 상태 차원이 큰 로봇 모델에서 인증된 영역의 크기와 계산 비용을 어떻게 맞바꾸는가.

1차 출처

• L. Vandenberghe, S. Boyd, 「Semidefinite Programming」, SIAM Review 38, 49–95, 1996(doi:10.1137/1038003) — 서지만 확인.
• S. Boyd, L. El Ghaoui, E. Feron, V. Balakrishnan, 『Linear Matrix Inequalities in System and Control Theory』, SIAM, 1994(doi:10.1137/1.9781611970777) — 서지만 확인.
• P. A. Parrilo, 「Semidefinite programming relaxations for semialgebraic problems」, Mathematical Programming 96, 293–320, 2003(doi:10.1007/s10107-003-0387-5) — 서지만 확인.
• J. B. Lasserre, 「Global optimization with polynomials and the problem of moments」, SIAM Journal on Optimization 11, 796–817, 2001(doi:10.1137/s1052623400366802) — 서지만 확인.
• D. Hilbert, 「Ueber die Darstellung definiter Formen als Summe von Formenquadraten」, Mathematische Annalen 32, 342–350, 1888(doi:10.1007/bf01443605) — 서지만 확인 (확인 필요: 정리 번호).
• E. Artin, 「Über die Zerlegung definiter Funktionen in Quadrate」, Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg 5, 100–115, 1927(doi:10.1007/bf02952513) — 서지만 확인.
• B. Reznick, 「Some concrete aspects of Hilbert's 17th Problem」, Contemporary Mathematics 253, 251–272, 2000(doi:10.1090/conm/253/03936) — 서지만 확인.
• V. Powers, T. Wörmann, 「An algorithm for sums of squares of real polynomials」, Journal of Pure and Applied Algebra 127, 99–104, 1998(doi:10.1016/s0022-4049(97)83827-3) — 서지만 확인.
• A. Papachristodoulou, S. Prajna, 「On the construction of Lyapunov functions using the sum of squares decomposition」, Proc. 41st IEEE CDC, 3482–3487, 2002(doi:10.1109/cdc.2002.1184414); 「A tutorial on sum of squares techniques for systems analysis」, Proc. ACC 2005, 2686–2700(doi:10.1109/acc.2005.1470374) — 서지만 확인.
• W. Tan, A. Packard, 「Stability region analysis using polynomial and composite polynomial Lyapunov functions and sum-of-squares programming」, IEEE Transactions on Automatic Control 53, 565–571, 2008(doi:10.1109/tac.2007.914221) — 서지만 확인.
• H. Peyrl, P. A. Parrilo, 「Computing sum of squares decompositions with rational coefficients」, Theoretical Computer Science 409, 269–281, 2008(doi:10.1016/j.tcs.2008.09.025) — 서지만 확인.
• E. Kaltofen, B. Li, Z. Yang, L. Zhi, 「Exact certification in global polynomial optimization via sums-of-squares of rational functions with rational coefficients」, Journal of Symbolic Computation 47, 1–15, 2012(doi:10.1016/j.jsc.2011.08.002) — 서지만 확인.
• J. Löfberg, 「Pre- and post-processing sum-of-squares programs in practice」, IEEE Transactions on Automatic Control 54, 1007–1011, 2009(doi:10.1109/tac.2009.2017144) — 서지만 확인.
• A. A. Ahmadi, A. Majumdar, 「DSOS and SDSOS optimization: more tractable alternatives to sum of squares and semidefinite optimization」, SIAM Journal on Applied Algebra and Geometry 3, 193–230, 2019(doi:10.1137/18m118935x) — 서지만 확인.
• F. Permenter, P. A. Parrilo, 「Partial facial reduction: simplified, equivalent SDPs via approximations of the PSD cone」, Mathematical Programming 171, 1–54(Crossref 등록 2017)(doi:10.1007/s10107-017-1169-9) — 서지만 확인.
• R. Tedrake, I. R. Manchester, M. Tobenkin, J. W. Roberts, 「LQR-trees: Feedback motion planning via sums-of-squares verification」, International Journal of Robotics Research 29, 1038–1052, 2010(doi:10.1177/0278364910369189); A. Majumdar, R. Tedrake, 「Funnel libraries for real-time robust feedback motion planning」, IJRR 36, 947–982, 2017(doi:10.1177/0278364917712421) — 서지만 확인.
• A. Papachristodoulou, J. Anderson, G. Valmorbida, S. Prajna, P. Seiler, P. A. Parrilo, M. M. Peet, D. Jagt, 「SOSTOOLS Version 4.00 Sum of Squares Optimization Toolbox for MATLAB」, arXiv:1310.4716(최초 제출 2013-10-17) — arXiv 메타데이터 확인.
• 소스·패키지(조회·실행 2026-11-03): Drake solvers/mathematical_program.h와 PyPI drake 1.58.0, cvxpy 1.9.3·SCS 3.3.1·Clarabel 0.11.1(PyPI), oxfordcontrol/SOSTOOLS(README·sosprogram.m, 태그 v4.03), spot-toolbox/spotless(doc/manual.tex), jump-dev/SumOfSquares.jl(README).

다음 장. 1.18은 수치 해석으로, ODE 적분기(룽게-쿠타·암시적·심플렉틱)와 자동 미분(순방향·역방향 모드), 수치 안정성을 다룬다. 이 장에서 사용한 부동소수점 반올림과 허용오차의 영향을 적분과 미분 계산의 오차 분석으로 확장하고, 이 장의 도달 영역 검증에서 사용한 4차 룽게-쿠타 적분의 정확도와 안정성을 다룬다.