제1부 수학적 기초

1.14 최적화 III: 비선형 계획법(SQP·내점법)과 혼합정수 계획법 — IPOPT·SNOPT·Gurobi

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

이 장은 등식·부등식 제약이 있는 비선형 최적화 문제(비선형 계획법, NLP)와 변수의 일부가 정수인 문제(혼합정수 계획법, MIP)를 푸는 방법을 다룬다. 로봇공학에서 역기구학의 관절 한계·충돌 회피 제약, 궤적 최적화의 동역학 제약, 접촉 모드의 선택은 모두 이 문제 계열로 정식화된다. 앞 장(1.12)은 제약이 없는 비선형 최소제곱을, 1.13은 볼록 문제와 QP를 다룬다. 이 장은 그 위에서 제약 있는 비볼록 문제의 국소 해법(SQP·내점법)과 이산 선택의 전역 해법(분기한정)을 맡는다. 다룰 질문은 다섯 가지다. 국소 최적해는 어떤 조건을 만족하며 그 조건은 언제 성립하지 않는가, SQP는 어떤 부문제를 풀고 어떻게 수렴을 보장하는가, 내점법은 부등식을 어떻게 다루고 IPOPT는 무엇을 더하는가, 분기한정은 LP 완화로 어떻게 최적성을 증명하는가, 같은 문제를 여러 해법기에 주었을 때 결과는 어디서 갈리는가.

배우는 것:

• 최적성 조건 — KKT 조건, 제약 규약(LICQ·MFCQ), 2차 충분조건, 규약이 깨지는 예(상보성 제약).
• SQP — QP 부문제, 정확 헤시안과 감쇠 BFGS, $\ell_1$ 병합 함수, 불가능한 선형화의 처리.
• 원-쌍대 내점법 — 장벽 문제, 감축 KKT 계통, 관성 보정, 필터 선탐색, IPOPT의 기본 옵션.
• 혼합정수 계획법 — LP 완화, 분기한정, 절단평면, big-M 정식화와 그 함정.
• 해법기 — IPOPT·SNOPT·Gurobi·HiGHS·SciPy의 공개된 설계·라이선스·인터페이스와 실행으로 확인한 거동.

선수 지식: 1.1(LU·QR), 1.2(최소제곱·숄레스키), 1.12(비선형 최소제곱), 1.13(볼록 최적화·QP). 표기는 BK-05와 A.2을 따른다.

특히 중요한 독자: 제약 있는 궤적·자세 최적화를 구현하는 엔지니어, 접촉 모드·작업 순서 선택을 혼합정수 문제로 정식화하는 연구자, 해법기의 종료 판정과 라이선스를 비교하는 시스템 설계자.

출처 방침. 기준 시점은 2026-11-03이다. 서지는 Crossref 응답으로 확인했다(목록은 이 장 끝). 직접 읽은 자료: ① IPOPT 소스(coin-or/Ipopt 태그 releases/3.14.19)의 옵션 등록 코드·IpMonotoneMuUpdate.cpp·IpFilterLSAcceptor.cpp·README.md·doc/main.dox, ② SciPy 1.18.1 소스(minimize 문서·_slsqp_py.py·src/slsqp.c), ③ SNOPT 공개 안내 페이지(UCSD CCoM)와 Drake의 snopt_solver.h·ipopt_solver.h(master), ④ Gurobi 공개 문서(docs.gurobi.com, 13.0)와 PyPI의 gurobipy 메타데이터, ⑤ HiGHS README.md·LICENSE.txt. 직접 실행한 것: CasADi 3.8.2가 번들한 IPOPT 3.14.19(MUMPS 5.8.2), SciPy 1.18.1(SLSQP·trust-constr·milp의 HiGHS), NumPy 2.5.4. 실행하지 않은 것: SNOPT·Gurobi(상용 해법기이므로 실행·성능 비교를 하지 않았다). 읽지 못한 것: 인용한 교과서·논문의 본문(정리·장 번호는 (확인 필요)), SNOPT 7.7 사용자 안내서, Gurobi의 MIP 내부 알고리즘 문서. 이 장의 수치는 순수 파이썬 구현으로 계산했고 1.1의 LU·QR, 1.2의 숄레스키를 불러와 사용했다. 스크립트와 출력은 robotics/fig-src/1.14-*.py와 robotics/fig-src/data/1.14-*-output.txt에 있다.

1.14.2 개념 — 제약 있는 비선형 문제와 이산 선택

세 가지 질문이 이 장의 문제를 나눈다. 첫째, 목적 함수와 제약이 매끄럽지만 볼록하지 않을 때 어디까지 보장할 수 있는가. 둘째, 부등식 제약 가운데 어느 것이 최적해에서 활성인지를 어떻게 정하는가. 셋째, 변수 일부가 "접촉한다·하지 않는다" 같은 이산 선택일 때 연속 해법을 어떻게 확장하는가.

첫째 질문의 답은 국소성이다. 비볼록 NLP 해법은 시작점 근방의 국소 최적해 하나를 찾으며 전역 최적성은 보장하지 않는다. IPOPT 문서도 목표를 "국소 해"라고 적는다(doc/main.dox). 둘째 질문에는 두 가지 접근이 있다. SQP는 선형화한 제약으로 만든 QP 안에서 활성 집합을 직접 추정하고, 내점법은 활성 집합을 정하지 않고 부등식을 장벽 함수로 바꿔 여유 변수가 양수로 유지되도록 반복점을 갱신한다. 셋째 질문의 답은 분기한정이다. 정수 조건을 버린 LP 완화로 하한을 얻고, 분수 값이 나온 변수로 문제를 분할하며 하한이 최선 해를 넘는 가지를 폐기한다. 해법기 하나가 세 질문에 모두 답하지는 않으므로 이 장은 세 방법의 입력(도함수·정수 변수)과 출력(국소해·최적성 증명)을 구분해 비교한다.

1.14.3 원리

1.14.3.1 정식화·KKT 조건·제약 규약

결론: 제약 규약(constraint qualification)이 성립하는 국소 최적해는 KKT 조건을 만족하고, 규약이 깨지면 최적해에서도 KKT 조건이 성립하지 않을 수 있다. 해법기의 종료 판정은 KKT 잔차이므로 규약이 깨진 문제에서는 판정 자체가 실패한다.

$$\min_{x\in\mathbb{R}^n}\ f(x)\quad\text{s.t.}\quad c_E(x)=0,\ \ c_I(x)\ge0,\qquad \mathcal{L}(x,\lambda,z)=f(x)-\lambda^\top c_E(x)-z^\top c_I(x)$$

$J_E$·$J_I$를 제약의 야코비 행렬이라 하면 국소 최적해 $x^*$에서 다음 KKT 조건을 만족하는 승수 $(\lambda,z)$가 존재한다(제약 규약 아래).

$$\nabla f-J_E^\top\lambda-J_I^\top z=0,\qquad c_E=0,\qquad c_I\ge0,\qquad z\ge0,\qquad z_i\,c_{I,i}=0$$

LICQ(선형독립 제약 규약)는 활성 제약의 기울기가 선형독립이라는 조건이며 승수가 유일함을 보장한다. MFCQ는 등식 기울기가 선형독립이고, 등식 기울기에 직교하면서 모든 활성 부등식의 값을 엄격히 증가시키는 방향이 존재한다는 더 약한 조건이다. 두 조건 모두 해의 존재가 아니라 승수의 존재를 위한 가정이다. 2차 충분조건은 임계 방향 $d\ne0$에서 $d^\top\nabla^2_{xx}\mathcal{L}\,d>0$이다. 활성 제약만으로 해가 정해지는 정점(활성 제약 수가 변수 수와 같은 경우)에서는 임계 방향이 없으므로 이 조건이 자명하게 성립한다.

규약이 깨지는 가장 단순한 예는 $\min x$, $-x^2\ge0$이다. 실현 가능 집합이 $\{0\}$이므로 $x^*=0$이지만 $\nabla f=1$, $\nabla c=0$이어서 $1-z\cdot0=0$을 만족하는 $z$가 없다. 로봇공학에서 흔한 경우는 접촉의 상보성 $0\le x\perp y\ge0$이다. 이를 $x\ge0$, $y\ge0$, $-xy\ge0$으로 나타내면 실현 가능한 점 $(a,0)$, $a>0$에서 활성 기울기가 $(0,1)$과 $(0,-a)$이고 두 값을 동시에 증가시키는 방향이 없으므로 MFCQ가 성립하지 않는다. 원점에서는 $-xy$의 기울기가 0이다. 따라서 모든 실현 가능한 점에서 MFCQ가 성립하지 않는다. 이 현상은 상보성 제약을 가진 수리계획(MPCC)의 알려진 결과이며 정리 번호는 (확인 필요)이다. 접촉 모델은 3.12, 접촉 암시 궤적 최적화는 11.8가 다룬다.

1.14.3.2 SQP — 국소 2차 근사와 병합 함수

결론: SQP는 매 반복에서 목적을 2차, 제약을 1차로 근사한 QP를 풀어 얻은 방향으로 이동한다. 정확한 라그랑주 헤시안을 사용하면 해 근방에서 2차 수렴하고, 준뉴턴 근사를 사용하면 초선형 수렴한다(Nocedal·Wright (확인 필요: 정리 번호)). 선형화한 제약이 서로 모순되면 QP가 불가능하며, 이를 처리하는 방식이 구현의 차이를 만든다.

$$\min_d\ \nabla f^\top d+\tfrac12\,d^\top B\,d\quad\text{s.t.}\quad c_E+J_Ed=0,\ \ c_I+J_Id\ge0$$

$B$는 $\nabla^2_{xx}\mathcal{L}$(정확 헤시안) 또는 준뉴턴 근사이다. 감쇠 BFGS는 $s=x_{k+1}-x_k$와 $y=\nabla_x\mathcal{L}(x_{k+1},\lambda_{k+1})-\nabla_x\mathcal{L}(x_k,\lambda_{k+1})$로 $B$를 $B\leftarrow B-\dfrac{Bss^\top B}{s^\top Bs}+\dfrac{yy^\top}{s^\top y}$로 갱신한다. $s^\top y<0.2\,s^\top Bs$이면 $y\leftarrow\theta y+(1-\theta)Bs$, $\theta=\dfrac{0.8\,s^\top Bs}{s^\top Bs-s^\top y}$로 감쇠해 $B$의 양정부호를 유지한다(Powell, 1978; Nocedal·Wright (확인 필요: 식 번호)). 전역 수렴을 위한 병합 함수는 목적과 위반량의 가중합이다. Han(1977)이 SQP에 도입한 $\ell_1$ 병합 함수가 널리 인용된다 (확인 필요: 본문 미확인).

$$\phi_\nu(x)=f(x)+\nu\big(\lVert c_E(x)\rVert_1+\lVert\max(0,-c_I(x))\rVert_1\big),\qquad D=\nabla f^\top d-\nu\,v$$

$v$는 현재 점의 위반량이고 $D$는 $\phi_\nu$의 방향 도함수 상한이다. $\nu$는 $D<0$이 되도록 $\nu\ge\dfrac{\nabla f^\top d+\frac{\sigma}{2}d^\top Bd}{(1-\rho)\,v}$로 정한다($\sigma=1$이면 $d^\top Bd>0$, 아니면 0이며 Nocedal·Wright (확인 필요: 식 번호)). 이 장의 구현은 $\rho=0.9$를 사용한다. 선형화가 모순되어 QP가 불가능하면 구현마다 처리가 다르다. Powell(1978)의 방식은 위반한 제약의 상수항에 $\delta\in(0,1]$를 곱해 실행 가능하게 만들고, SNOPT는 공개 안내 페이지에 따르면 비선형 제약에 신축 경계(elastic bounds)를 두어 위반량의 합을 최소화한다. 필터 방식(Fletcher·Leyffer, 2002. 논문 제목이 병합 함수를 사용하지 않는다고 밝힌다)은 (위반량, 목적)의 쌍을 서로 비교한다.

1.14.3.3 원-쌍대 내점법 — 장벽 문제와 필터 선탐색

결론: 내점법은 부등식에 여유 변수 $s>0$를 두고 장벽 항 $-\mu\sum\ln s_i$를 목적에 더한 문제를 $\mu\downarrow0$으로 풀며, 각 $\mu$에서 섭동 KKT 조건에 뉴턴법을 적용한다. 활성 집합을 추정하지 않고 $\mu$를 줄여 가며 얻는 장벽 문제의 해의 열을 추적한다. IPOPT는 여기에 필터 선탐색·관성 보정·복원 단계를 더한다.

$$\nabla f-J_E^\top\lambda-J_I^\top z=0,\quad c_E=0,\quad c_I-s=0,\quad Sz=\mu e$$

여유 변수와 $z$를 소거한 감축 뉴턴 계통은 $\Sigma=S^{-1}Z$, $r_c=c_I-s$, $r_d=\nabla f-J_E^\top\lambda-J_I^\top z$에 대해 다음과 같다.

$$\begin{bmatrix}W+J_I^\top\Sigma J_I&-J_E^\top\\-J_E&0\end{bmatrix}\begin{bmatrix}\Delta x\\\Delta\lambda\end{bmatrix}=\begin{bmatrix}-r_d+J_I^\top(\mu S^{-1}e-z-\Sigma r_c)\\c_E\end{bmatrix},\quad \Delta s=J_I\Delta x+r_c,\ \ \Delta z=\mu S^{-1}e-z-\Sigma\Delta s$$

$W=\nabla^2_{xx}\mathcal{L}$이다. 계수 행렬이 올바른 관성(양의 고유값 $n$개, 음의 고유값 $m_E$개)을 가지려면 영공간에서 $W+J_I^\top\Sigma J_I$가 양정부호여야 하고, 아니면 대각에 $\delta_w I$를 더한다. 이 장의 구현은 영공간 기저로 이 조건을 검사하며, IPOPT는 선형 해법기가 반환하는 고유값 개수로 관성을 판정한다(IpPDFullSpaceSolver.cpp의 check_inertia). 보폭은 경계 비율 $\tau=\max(0.99,1-\mu)$로 제한한다. 필터 선탐색은 시험점의 위반량 $\theta=\lVert(c_E,\,c_I-s)\rVert_1$과 장벽 목적 $\varphi_\mu=f-\mu\sum\ln s_i$를 사용하며, 시험점($+$ 표시)의 수락 조건은 세 가지이다.

• ① 위반량 또는 장벽 목적이 충분히 감소한다: $\theta^+\le(1-\gamma_\theta)\theta$ 또는 $\varphi_\mu^+\le\varphi_\mu-\gamma_\varphi\theta$.
• ② $\theta\le\theta_{\min}$이고 $\alpha(-\nabla\varphi_\mu^\top d)^{s_\varphi}>\delta\,\theta^{s_\theta}$인 f형 단계에서는 ①을 Armijo 조건 $\varphi_\mu^+\le\varphi_\mu+\eta_\varphi\alpha\nabla\varphi_\mu^\top d$로 대체한다.
• ③ 과거 반복점이 쌓은 필터의 어느 항목에도 지배되지 않는다.

장벽 매개변수는 장벽 문제의 오차가 $\kappa_\varepsilon\mu$ 이하가 되면 $\mu\leftarrow\max\{\epsilon_{\mathrm{tol}}/(\kappa_\varepsilon+1),\ \min\{\kappa_\mu\mu,\ \mu^{\theta_\mu}\}\}$로 줄인다. 상수의 기본값은 소스에서 읽은 값이며 아래 표와 같다.

IPOPT 소스는 필터 선탐색을 선택하면 복원 단계 객체를 만든다(IpAlgBuilder.cpp의 주석). 복원 단계의 세부는 읽지 않았으므로 이 장의 자작 구현에는 포함하지 않았다.

1.14.3.4 혼합정수 계획법 — LP 완화·분기한정·절단평면

결론: 혼합정수 선형 계획(MILP)은 정수 조건을 버린 LP 완화의 값이 하한이 된다는 사실을 이용해 문제를 나누고 하한이 최선 해를 넘는 가지를 버린다. 탐색이 끝나면 최선 해의 최적성이 증명된다는 점이 국소 NLP 해법과 다르다.

$$\min_x\ c^\top x\quad\text{s.t.}\quad Ax\le b,\ \ l\le x\le u,\ \ x_i\in\mathbb{Z}\ (i\in\mathcal{I})$$

분기한정(Land·Doig, 1960)은 노드마다 LP 완화를 풀어 ① 불가능, ② 값이 최선 해 이상, ③ 정수 해의 세 경우에 가지를 닫고, 그렇지 않으면 분수 값 $x_i^*$을 가진 변수로 $x_i\le\lfloor x_i^*\rfloor$, $x_i\ge\lceil x_i^*\rceil$ 두 자식을 만든다. 다음에 열 노드는 하한이 가장 낮은 노드(최저 하한 우선) 또는 가장 깊은 노드(깊이 우선)로 고른다. 절단평면(Gomory, 1958)은 LP 최적해를 잘라 내되 정수 해를 보존하는 유효 부등식을 더해 하한을 높이며, 분기한정과 결합한 방식을 분기절단이라 한다. 이진 변수를 도입하는 big-M 정식화는 "이진 변수가 0이면 제약이 활성, 1이면 상수 $M$만큼 느슨해진다"는 논리 조건을 선형으로 만들며, $M$이 크면 LP 완화가 약해진다. 이차 목적을 가진 MIQP는 같은 틀에서 QP 완화를 풀고(1.13), 비선형 제약이 있는 MINLP는 별도의 이론과 해법이 필요하다(Belotti 외, 2013 (확인 필요: 장 번호)). Gurobi의 공개 문서는 비선형 제약을 공간 분기한정으로 전역 최적까지 푼다고 적으며, 이 점에서 국소 해를 찾는 해법기와 다르다고 밝힌다.

1.14.3.5 해법기의 공개된 설계·라이선스·인터페이스

결론: 같은 NLP를 푸는 해법기도 공개된 설계 대상이 다르다. IPOPT는 대규모 비선형 최적화 패키지로, SNOPT는 함수와 기울기의 평가가 비싼 비선형 문제에 특히 효과적인 희소 SQP로 소개된다(각 공식 안내). 라이선스는 도입 가능성을 직접 정한다.

Drake의 SnoptSolver 헤더는 SNOPT를 상용 라이선스 해법기로 소개하고, 소스 빌드에는 기본으로 포함하지 않으며 미리 컴파일한 배포판에는 포함된다고 적는다. SNOPT 안내 페이지는 개발 중인 SNOPT 9가 정확한 2차 도함수를 사용할 수 있다고 적는다. IPOPT의 최신 릴리스는 3.14.20(2026-08-27)이며 이 장은 CasADi 3.8.2가 번들한 3.14.19를 실행했다. 해법기를 한 입력 형식으로 묶는 모델링 계층은 1.15이 다룬다.

1.14.4 알고리즘

SQP·내점법·분기한정의 반복 구조

SQP(x0):  B ← I,  (λ, z) ← 0,  ν ← 1
  KKT 잔차 ≤ tol 이면 종료
  QP 부문제 풀이 → (d, λ⁺, z⁺)       불가능이면 제약 상수에 δ = 0.5, 0.25, … 를 곱한다
  ν ← max(ν, (∇fᵀd + ½·max(0, dᵀBd)) / (0.1·v))
  α ← Armijo 역추적(φ_ν, d, D = ∇fᵀd − ν·v)
  x ← x + α·d,  (λ, z) ← (λ⁺, z⁺)
  B ← 정확 헤시안(필요하면 대각 이동) 또는 감쇠 BFGS(B, α·d, y)

내점법(x0):  s ← max(c_I(x0), 0.1),  z ← 1,  μ ← 0.1
  오차 E₀ ≤ tol 이면 종료
  E_μ ≤ 10·μ 인 동안  μ ← max(tol/11, min(0.2·μ, μ^1.5)),  필터 초기화
  관성 보정한 감축 KKT 계통 → (Δx, Δλ, Δs, Δz)
  α ← 경계 비율(τ = max(0.99, 1−μ))로 정한 최대 보폭
  필터 수락 조건을 만족할 때까지 α ← α/2        (실패하면 복원 단계가 필요하다)
  (x, s) ← (x, s) + α·(Δx, Δs),  λ ← λ + α·Δλ,  z ← z + α_z·Δz

분기한정(MILP):  최선 해 ← ∞,  열린 노드 ← {루트}
  노드 선택(최저 하한 우선 또는 깊이 우선), 하한 ≥ 최선 해이면 폐기
  LP 완화 풀이 → (값, x)
  불가능이거나 값 ≥ 최선 해이면 가지치기
  정수 변수가 모두 정수이면 최선 해 ← 값, 아니면 가장 분수인 x_i로 두 자식 생성

구현은 1.14.5의 코드에 있다. QP 부문제의 풀이(qp_enum)와 반복 구동부, LP 완화를 푸는 단체법(lp)은 소규모 전용이므로 스크립트 robotics/fig-src/1.14-nlp.py에만 두었다. 실제 QP 해법은 1.13이 다룬다.

1.14.5 풀이 예제 — 2링크 팔의 제약 NLP와 장애물 우회 MILP

평면 2링크 팔의 손끝을 벽에 접촉시키는 최소 관절 변위 문제를 SQP·내점법으로 풀어 KKT 잔차·수렴 속도·초기값 민감도를 측정하고, 상자 장애물을 피하는 경로 문제를 big-M MILP로 만들어 분기한정의 노드 수를 센다. 같은 입력을 SciPy와 IPOPT에 주어 비교한다. 결론부터 적으면 다음과 같다. ① 자작 구현은 HS71 시험 문제에서 IPOPT·SLSQP와 같은 해(목적값 약 17.01402)에 수렴한다. ② 2링크 문제에는 국소해 세 개가 있고 목적값이 0.1043·0.9240·2.2847로 갈린다. ③ 한 시작점에서 정확 헤시안 SQP는 7회, 감쇠 BFGS는 10회, 내점법은 8회에 KKT 잔차 $10^{-8}$ 이하에 도달한다. ④ 625개 시작점 가운데 해법별로 19~51%에서 해에 도달하지 못했고 IPOPT는 이를 모두 국소 불가능으로 보고했다. ⑤ SLSQP는 17개 시작점에서 KKT 점이 아닌 곳에서 성공을 보고했다. ⑥ MILP에서 점 제약만 부과한 정식화의 해는 구간 하나가 장애물을 통과했고, 구간 제약으로 바꾸면 목적값이 6.00에서 8.00으로 바뀐다. ⑦ 분기한정의 노드 수는 이진 변수 4개당 2.0~2.1배로 늘었다.

세 해는 정점에 가까운 해(B·C)와 활성 부등식이 없는 해(A)로 나뉜다. A의 영공간 곡률은 양수이고, B·C는 활성 제약이 둘이라 임계 방향이 없으며 승수 $z$가 엄격히 양수이므로 2차 충분조건이 성립한다. 기준해는 SQP 해를 활성 집합 KKT 방정식의 뉴턴법으로 다듬어 얻었고 KKT 잔차가 $10^{-13}$ 이하이다. 다음은 이 장의 핵심 코드이며, 같은 구간이 스크립트의 모의 구간과 단일 출처이다. 코드는 1.1의 solve_lu·qr·matmul·transpose와 1.2의 chol을 사용한다. QP 풀이·반복 구동부·단체법(lp)은 스크립트에만 있다. 단체법은 무작위 LP 400개(불가능 181개, 최적 219개)에서 HiGHS와 판정이 모두 같고 최적값이 $4.4\times10^{-15}$ 이내로 일치했다.

import math

def dot(a, b):
    return sum(x * y for x, y in zip(a, b))

def kkt(g, Je, Ji, ce, ci, lam, z):
    """KKT 잔차(무한 노름): 정상성·실현성·상보성의 최댓값"""
    col = lambda M, j: [row[j] for row in M]
    r = [gj - dot(lam, col(Je, j)) - dot(z, col(Ji, j))
         for j, gj in enumerate(g)]
    bad = [max(0.0, -v) for v in ci + z]
    comp = [w * v for w, v in zip(z, ci)]
    return max(abs(v) for v in r + ce + bad + comp)

def bfgs(B, s, y):
    """감쇠 BFGS(Powell 1978): B를 양정부호로 유지"""
    Bs = [dot(r, s) for r in B]
    sBs, sy = dot(s, Bs), dot(s, y)
    if sy < 0.2 * sBs:                # 곡률 조건 위반: y 감쇠
        t = 0.8 * sBs / (sBs - sy)
        y = [t * a + (1 - t) * b for a, b in zip(y, Bs)]
        sy = dot(s, y)
    n = len(s)
    return [[B[i][j] - Bs[i] * Bs[j] / sBs + y[i] * y[j] / sy
             for j in range(n)] for i in range(n)]

def merit_search(phi, x, d, D):
    """l1 병합 함수 phi의 Armijo 역추적(D: 방향 도함수)"""
    xa = lambda a: [u + a * v for u, v in zip(x, d)]
    a, p0 = 1.0, phi(x)
    while phi(xa(a)) > p0 + 1e-4 * a * D:
        a *= 0.5
        if a < 1e-12:
            return None
    return a

def ipm_step(W, g, Je, ce, Ji, ci, s, lam, z, mu):
    """장벽 문제의 뉴턴 단계(감축 KKT): (dx, dlam, ds, dz)"""
    n, me, mi = len(g), len(ce), len(ci)
    sg = [a / b for a, b in zip(z, s)]            # z / s
    rc = [a - b for a, b in zip(ci, s)]           # ci - s
    H = [[W[i][j] + sum(sg[k] * Ji[k][i] * Ji[k][j]
                        for k in range(mi))
          for j in range(n)] for i in range(n)]
    rd = [g[j] - sum(lam[k] * Je[k][j] for k in range(me))
          - sum(z[k] * Ji[k][j] for k in range(mi))
          for j in range(n)]
    q = [mu / s[k] - z[k] - sg[k] * rc[k] for k in range(mi)]
    rhs = [-rd[j] + sum(Ji[k][j] * q[k] for k in range(mi))
           for j in range(n)]
    Z = [r[me:] for r in qr(transpose(Je))[0]]  # 영공간
    dw = 0.0
    while True:                                   # 관성 보정
        Hd = [[H[i][j] + dw * (i == j) for j in range(n)]
              for i in range(n)]
        if chol(matmul(transpose(Z), matmul(Hd, Z))):
            break
        dw = 1e-4 if dw == 0 else 8 * dw
    K = ([Hd[i] + [-r[i] for r in Je] for i in range(n)]
         + [[-v for v in r] + [0.0] * me for r in Je])
    sol = solve_lu(K, rhs + ce)[0]
    dx, dl = sol[:n], sol[n:]
    ds = [dot(Ji[k], dx) + rc[k] for k in range(mi)]
    dz = [mu / s[k] - z[k] - sg[k] * ds[k] for k in range(mi)]
    return dx, dl, ds, dz

def filter_ok(tn, pn, t0, p0, gp, a, filt, tmax, tmin):
    """필터 선탐색 수락 판정(IPOPT 기본 상수).
    tn·pn: 시험점의 위반량·장벽 함수, gp: 방향 도함수"""
    ftype = (gp < 0 and a * (-gp) ** 2.3 > t0 ** 1.1
             and t0 <= tmin)
    if ftype:                         # f형 단계: Armijo
        ok = pn <= p0 + 1e-8 * a * gp
    else:                             # 위반량·장벽 함수 감소
        ok = tn <= (1 - 1e-5) * t0 or pn <= p0 - 1e-8 * t0
    ok = ok and tn <= tmax
    return (ok and all(tn < tf or pn < pf for tf, pf in filt),
            ftype)

def next_mu(mu, tol):
    """단조 장벽 갱신: kappa_mu=0.2, theta_mu=1.5"""
    return max(tol / 11, min(0.2 * mu, mu ** 1.5))

def branch_bound(c, A, b, lb, ub, ints, best_first=True):
    """MILP: min c'x, Ax<=b, lb<=x<=ub, x[i] 정수(i in ints).
    LP 완화(lp)를 풀고 가장 분수인 변수로 분기.
    반환: (값, x, 노드 수)"""
    best, xb, nodes = math.inf, None, 0
    open_ = [(-math.inf, lb, ub)]        # (부모의 하한, 경계)
    while open_:
        if best_first:                   # 하한 최소 노드
            open_.sort(key=lambda t: t[0])
            bound, l, u = open_.pop(0)
        else:                            # 깊이 우선
            bound, l, u = open_.pop()
        if bound >= best - 1e-9:
            continue                     # 하한 초과: 가지치기
        nodes += 1
        val, x = lp(c, A, b, l, u)       # LP 완화
        if x is None or val >= best - 1e-9:
            continue                     # 불가능·가지치기
        fr = [i for i in ints
              if abs(x[i] - round(x[i])) > 1e-6]
        if not fr:
            best, xb = val, x            # 정수 해: 갱신
            continue
        i = max(fr, key=lambda i: abs(x[i] - round(x[i])))
        u1, l2 = u[:], l[:]
        u1[i], l2[i] = math.floor(x[i]), math.ceil(x[i])
        open_ += [(val, l, u1), (val, l2, u)]
    return best, xb, nodes

① 구현 검증과 한 시작점의 수렴. HS71은 IPOPT 안내서의 예제와 같은 4변수 문제이다(Hock·Schittkowski, 1981의 71번). 시작점 $(1,5,5,1)$에서 모든 구현이 같은 해에 수렴한다.

2링크 문제의 시작점 $q_0=(1.5,-1.5)$에서 모든 해법이 해 A로 수렴한다. 반복 횟수는 해법마다 다르고, 종료 시점의 정확도는 해법의 기본 허용 오차를 따른다.

정확 헤시안 SQP의 해와의 거리 $\lVert x_k-x^*\rVert_\infty$는 마지막 세 반복에서 $1.7\times10^{-2}$, $8.7\times10^{-5}$, $2.5\times10^{-9}$로 줄어 $e_{k+1}\approx0.3\,e_k^2$ 꼴의 2차 수렴과 일치한다. 감쇠 BFGS의 거리는 $1.1\times10^{-2}$, $1.1\times10^{-4}$, $1.5\times10^{-6}$, $2.5\times10^{-9}$, $6.7\times10^{-16}$으로 연속 비율이 계속 작아지는 초선형 수렴이다. IPOPT가 출력한 $\lg\mu$ 열은 $-1.0$, $-1.7$, $-2.5$, $-3.8$, $-5.7$, $-8.6$이며, 이는 소스에서 읽은 갱신식 $\mu\leftarrow\min\{0.2\mu,\mu^{1.5}\}$의 수열과 일치하고 이 장의 구현이 만든 수열과도 같다. 같은 실행의 lg(rg) 열은 반복 2와 5에서 $2.0$과 $1.5$이며, 이는 헤시안의 정칙화 항이 각각 약 $10^2$, $10^{1.5}$로 적용되었음을 보인다(doc/output.dox의 열 정의).

② 초기값 민감도. 625개 시작점(관절 상자의 25×25 격자)에서 각 해법을 실행해 도달한 해를 분류했다. 판정은 해법이 성공을 보고하고 기준해와 $10^{-3}$ 이내일 때 해당 해로, 성공을 보고했으나 기준해와 다르면 기타로, 성공을 보고하지 않으면 미수렴으로 센다.

세 해의 도달 영역은 시작점 평면에서 서로 얽힌 모양으로 나뉘고(위 관절공간 도해), 해법마다 경계가 다르다. 미수렴의 사유는 해법별로 기록했다. 자작 SQP는 QP 부문제 불가능이 241개(정확 헤시안)·249개(감쇠 BFGS), 자작 내점법은 선탐색 실패가 303개이다. SLSQP는 "Positive directional derivative for linesearch" 251개, "Inequality constraints incompatible" 39개, "Iteration limit reached" 29개이다. trust-constr는 "Constraint violation exceeds 'gtol'" 62개와 평가 횟수 초과 54개이다. IPOPT는 291개 모두 Infeasible_Problem_Detected, 곧 제약 위반량의 정류점에서 멈췄다고 보고했다. 문제 자체는 세 해를 가지므로 이것은 비볼록 제약의 국소 불가능 영역에 시작점이 놓인 결과이다.

SLSQP는 기본 ftol$=10^{-6}$에서 17개 시작점에서 "Optimization terminated successfully"를 보고했으나 기준해에서 $10^{-3}$ 이상 떨어져 있었고, 이 점들의 KKT 잔차는 $2.3\times10^{-2}$~$1.3$이었다. 한 예로 시작점 $(-1.508,-1.508)$(격자 셀 중심)은 $\texttt{ftol}=10^{-6}$과 $10^{-8}$ 모두에서 15~16회 반복해 $q=(1.1535,-1.8058)$, 목적값 2.3758에서 성공을 보고했다. 이 점은 장애물 제약의 여유가 0.229로 비활성이고, SLSQP가 반환한 승수로 계산한 라그랑주 기울기의 무한 노름이 0.12이므로 KKT 점이 아니다. $\texttt{ftol}=10^{-10}$에서는 같은 시작점에서 44회 반복해 해 C(라그랑주 기울기 $2\times10^{-14}$)에 수렴한다. 소스(src/slsqp.c)의 수렴 판정은 $\lvert g^\top s\rvert+\sum_j\lvert\mu_jc_j\rvert<\texttt{acc}$이고 위반량의 합도 $\texttt{acc}$ 미만이어야 한다($s$는 QP의 단계). 문서의 ftol 설명은 라그랑주 기울기를 낮춰야 한다고 적는다. 두 서술은 같지 않다. 단계가 작아진 원인이 준뉴턴 행렬의 큰 스케일에 있다는 설명은 확인하지 않은 (추정)이다.

시작점 $(0,0)$에서는 등식 제약의 기울기가 0이므로 LICQ가 성립하지 않는다. 자작 SQP는 QP 불가능, 자작 내점법은 특이 계통으로 종료했고, SLSQP는 "Singular matrix C in LSQ subproblem"으로 종료했다. trust-constr는 해 A로, IPOPT는 15회 반복해 해 C로 수렴했다. 제약 규약이 깨진 시작점에서 해법기마다 다른 결과를 내므로 이 결과를 해법기의 우열로 읽을 수 없다.

③ 혼합정수 예제. 예제 A는 $\min -8x_1-5x_2$, $x_1+x_2\le6$, $9x_1+5x_2\le45$, $x\in\mathbb{Z}_{\ge0}^2$이며 LP 완화의 해 $(3.75,\,2.25)$에서 시작해 7개 노드를 평가하고 최적해 $(5,0)$, 값 $-40$을 얻는다(1.14.3.4의 트리 도해). 두 노드 선택 규칙의 노드 수는 7로 같고, HiGHS는 보고한 노드 수(mip_node_count)가 1이다. 경로 문제는 시작점 $(0,0)$에서 목표 $(6,6)$까지 $T$단계로 이동하며 가운데 점들이 상자 $[2,4]^2$ 밖에 있도록 한다. 비용은 단계의 $\ell_\infty$ 길이 합이고 단계 크기는 2 이하이다. 구간 제약 정식화는 구간의 두 끝점이 같은 변의 바깥에 있어야 한다는 조건을 구간마다 이진 변수 4개로 나타낸다. $T=3$은 단계 크기 한도 안에서 불가능하다.

이진 변수가 4개 늘 때 자작 분기한정(최저 하한 우선)의 노드 수는 35, 75, 155, 315로 2.0~2.1배씩 늘었다. 루트 LP 하한은 6.00이고 최적값은 8.00이므로 LP 완화가 장애물을 고려하지 못해 하한이 약하다. HiGHS의 노드 수는 0~9로 작고, 전처리를 끄면 1~17로 늘어난다. 노드 수는 두 해법기가 다른 전처리·절단평면·휴리스틱을 사용하므로 직접 비교할 수 없다. 점 제약만 부과한 첫 정식화는 값 6.00에서 가운데 점 $(2,2)$와 $(4,4)$를 잡았고, 그 구간이 상자 내부를 지나는 것을 선분-상자 교차 검사로 확인했다. 구간 제약으로 고치자 값이 8.00이 되었고 교차하는 구간이 없다. 단, 구간 제약은 축 정렬 변 하나에 대한 충분 조건이므로 보수적이다. 최적 경로는 상자 경계에 접한다(여유 0).

한계. 수치는 합성 문제 하나(2링크)와 시험 문제 하나(HS71), MILP 두 가지이며 해법기 성능의 일반적인 순위를 뜻하지 않는다. 자작 구현은 소규모 전용이고 복원 단계·2차 보정·IPOPT의 스케일링·승수 보정을 포함하지 않으며, 성능 지표는 반복 횟수이지 시간이 아니다. 미수렴 비율은 시작점 격자(관절 한계 상자 전체)에 의존한다. SLSQP·trust-constr·IPOPT는 기본 옵션(SLSQP는 ftol=$10^{-6}$)으로 실행했다. 상용 해법기(SNOPT·Gurobi)는 실행하지 않았다. 정확 헤시안 SQP의 QP는 환산 헤시안이 양정부호이면서 $\lVert d\rVert$가 최소인 후보를 고르는 휴리스틱을 사용한다.

견해: 제약 있는 비볼록 문제의 해법기 평가는 수렴한 사례의 반복 횟수보다 "어디서 어떻게 실패하는가"를 함께 보고해야 한다고 본다. 근거는 위 표에서 수렴한 시작점의 반복 횟수 중앙값이 5~17회로 같은 자릿수인데 미수렴 비율이 19~51%로 갈렸고, SLSQP는 KKT 점이 아닌 곳에서 성공을 보고했다는 점이다. 반대로 이 장의 격자는 관절 한계 상자 전체를 균등하게 덮으므로 실제 응용의 시작점 분포(이전 해로부터의 웜 스타트)와 다르며, 웜 스타트에서는 미수렴 비율이 낮을 수 있다.

1.14.6 설계 트레이드오프 — 해법 계열의 선택

공개 문헌과 위 측정에서 확인되는 선택지는 세 가지다.

• ① SQP(활성 집합 QP 기반). 활성 집합을 추정하므로 웜 스타트에 유리하다고 알려져 있으며 (확인 필요: 출처), 실시간 반복(MPC의 연속 문제)에 알맞다. 선형화가 불가능하면 별도 처리가 필요하다. SNOPT·SLSQP가 이 계열이다.
• ② 내점법. 부등식이 많은 대규모 희소 문제에 알맞고 선형 계통의 관성이 해를 정한다. 웜 스타트에는 경계 승수를 포함한 전 공간 정보가 필요하다고 IPOPT 문서가 적는다(doc/special.dox). IPOPT·trust-constr가 이 계열이다.
• ③ 혼합정수 분기한정. 이산 선택의 전역 최적성을 증명하지만 노드 수가 이진 변수 수에 따라 지수적으로 늘 수 있다. 이 장의 측정에서 이진 변수 4개당 약 2배였다.

견해: 접촉 모드가 많은 문제에서는 이진 변수로 모드를 열거하기 전에 상보성 제약을 완화한 NLP나 접촉 순서를 고정한 하위 문제로 줄일 수 있는지 먼저 확인하는 편이 낫다고 본다. 근거는 이 장의 측정에서 이진 변수 4개 증가가 노드 수를 약 2배로 만들었고, 상보성 제약은 모든 실현 가능점에서 MFCQ를 깨뜨려 KKT 조건의 성립을 보장하는 가정이 사라진다는 점이다(1.14.3.1). 두 경로가 모두 어려우므로 문제별 측정이 필요하다.

1.14.7 응용 축 비교

이 표는 이 책의 정리이며 장별 요구는 다르다.

1.14.8 관련 규격·프로토콜

비선형 계획·혼합정수 계획의 해법기 인터페이스에 국제 표준은 확인하지 못했다. MPS 형식의 정식 명세 문서는 확인하지 못했다 (확인 필요). 규격·표준의 색인은 A.3가 다룬다.

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

직접 적용되는 규제는 없다. 최적화 해법기를 안전 기능의 경로에 두면 해법기의 반복 횟수와 종료 상태가 실시간 제약과 고장 분석의 대상이 된다. 이 장의 측정에서 수렴한 시작점의 반복 횟수는 해법마다 중앙값 5~17회, 최대 29~165회로 갈렸고 미수렴 때 보고하는 상태가 해법기마다 달랐으므로, 미수렴을 안전 상태로 연결하는 설계가 필요하다. 결정적 실행은 15.9, 기능안전은 26.5, 소프트웨어 안전과 품질 표준은 26.20, 산업 로봇의 안전 표준은 27.10이 다룬다.

1.14.10 한계·유의점·미해결

• 국소성. NLP 해법기는 국소해를 찾는다. 이 장의 2링크 문제에서 같은 해법이 시작점에 따라 목적값 0.1043·0.9240·2.2847의 서로 다른 해에 도달했다. 전역 최적성이 필요하면 다중 시작·분기한정·전역 해법이 필요하다.
• 제약 규약. 상보성 제약과 중복 제약은 LICQ·MFCQ를 깨뜨린다. 종료 판정이 KKT 잔차이므로 이 경우 해법기의 보고를 그대로 믿을 수 없다.
• 종료 상태 해석. success·Solve_Succeeded는 해법기가 정의한 판정이며 KKT 점임을 뜻하지 않는다. 이 장에서 SLSQP는 17개 시작점에서 KKT 점이 아닌 곳에서 성공을 보고했다.
• big-M. $M$이 크면 LP 완화가 약해지고 정수성 허용 오차가 제약 위반으로 이어질 수 있다는 점이 알려져 있다 (확인 필요: 출처). 이 장의 측정은 $M=4$~100에서 루트 LP 하한이 모두 6.00이고 노드 수가 62~75로 거의 같았으며 허용 오차에 의한 장애물 침범은 관찰되지 않았다.
• 구간 제약. 점 제약만으로는 연속 시간 충돌을 보장하지 못한다.
• 미확인. SNOPT·Gurobi의 내부 알고리즘과 성능, IPOPT 복원 단계의 세부, SQP의 마라토스 효과와 2차 보정의 정리 번호는 확인하지 않았다 (확인 필요).
• 다른 장의 몫. 볼록 문제·QP는 1.13, 모델링·코드 생성은 1.15, 무미분 최적화는 1.16, 반정부호 계획법은 1.17가 다룬다.

1.14.11 체크포인트·연구 질문

체크포인트:

1. NLP의 KKT 조건을 작성하고 LICQ가 성립할 때 승수가 유일한 이유를 설명할 수 있는가.
2. 상보성 제약이 MFCQ를 깨뜨리는 이유를 활성 기울기로 보일 수 있는가.
3. SQP의 QP 부문제와 감쇠 BFGS 갱신, $\ell_1$ 병합 함수의 방향 도함수를 쓸 수 있는가.
4. 선형화한 제약이 모순될 때 SQP가 취할 수 있는 조치를 두 가지 말할 수 있는가.
5. 내점법의 섭동 KKT 조건과 감축 뉴턴 계통, 관성 보정의 목적을 설명할 수 있는가.
6. 필터 선탐색의 수락 조건 세 가지와 IPOPT 기본값을 말할 수 있는가.
7. 분기한정이 가지를 닫는 세 경우와 LP 완화가 하한을 주는 이유를 설명할 수 있는가.
8. 해법기의 성공 보고를 KKT 잔차로 검증해야 하는 이유를 이 장의 SLSQP 측정으로 설명할 수 있는가.

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

• 비볼록 제약이 있는 궤적 최적화에서 이전 해를 웜 스타트로 사용하는 경우 국소 불가능 영역으로의 수렴 비율은 얼마나 줄어드는가.
• 접촉 상보성 제약을 이진 변수·완화된 NLP·접촉 순서 고정 중 어느 방식으로 정식화할 때 해의 질과 계산 시간이 어떻게 갈리는가.
• 구간 제약 정식화의 보수성(축 정렬 변 하나)이 경로 비용을 얼마나 높이며 더 촘촘한 분리 조건이 노드 수를 얼마나 늘리는가.

1차 출처

• J. Nocedal, S. J. Wright, 『Numerical Optimization』, 2nd ed., Springer, 2006(doi:10.1007/978-0-387-40065-5) (확인 필요: 장·정리 번호).
• A. Wächter, L. T. Biegler, 「On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming」, Mathematical Programming 106(1), 25–57, 2006(doi:10.1007/s10107-004-0559-y) — 서지만 확인.
• A. Wächter, L. T. Biegler, 「Line search filter methods for nonlinear programming: Motivation and global convergence」, SIAM J. Optim. 16(1), 1–31, 2005(doi:10.1137/s1052623403426556) — 서지만 확인.
• R. Fletcher, S. Leyffer, 「Nonlinear programming without a penalty function」, Mathematical Programming 91(2), 239–269, 2002(doi:10.1007/s101070100244) — 서지만 확인.
• P. E. Gill, W. Murray, M. A. Saunders, 「SNOPT: An SQP algorithm for large-scale constrained optimization」, SIAM Review 47(1), 99–131, 2005(doi:10.1137/s0036144504446096) — 서지만 확인. SNOPT 7.7 사용자 안내서(CCoM 18-1, 2018)는 UCSD 안내 페이지의 서지 표기만 확인했다.
• M. J. D. Powell, 「A fast algorithm for nonlinearly constrained optimization calculations」, Lecture Notes in Mathematics 630, 144–157, 1978(doi:10.1007/bfb0067703) — 서지만 확인.
• S.-P. Han, 「A globally convergent method for nonlinear programming」, J. Optim. Theory Appl. 22(3), 297–309, 1977(doi:10.1007/bf00932858) — 서지만 확인.
• R. H. Byrd, J. C. Gilbert, J. Nocedal, 「A trust region method based on interior point techniques for nonlinear programming」, Mathematical Programming 89(1), 149–185, 2000(doi:10.1007/pl00011391) — SciPy minimize 문서가 인용하는 문헌 가운데 하나이며 서지만 확인.
• A. H. Land, A. G. Doig, 「An automatic method of solving discrete programming problems」, Econometrica 28(3), 497쪽부터, 1960(doi:10.2307/1910129) — 서지만 확인. Crossref에는 시작 쪽만 있어 끝 쪽은 적지 않는다.
• R. E. Gomory, 「Outline of an algorithm for integer solutions to linear programs」, Bull. Amer. Math. Soc. 64(5), 275–278, 1958(doi:10.1090/s0002-9904-1958-10224-4) — 서지만 확인.
• P. Belotti, C. Kirches, S. Leyffer, J. Linderoth, J. Luedtke, A. Mahajan, 「Mixed-integer nonlinear optimization」, Acta Numerica 22, 1–131, 2013(doi:10.1017/s0962492913000032) — 서지만 확인.
• A. Bemporad, M. Morari, 「Control of systems integrating logic, dynamics, and constraints」, Automatica 35(3), 407–427, 1999(doi:10.1016/s0005-1098(98)00178-2) — 서지만 확인.
• T. Schouwenaars, B. De Moor, E. Feron, J. How, 「Mixed integer programming for multi-vehicle path planning」, ECC 2001, 2603–2608(doi:10.23919/ecc.2001.7076321) — 서지만 확인. A. Richards, J. How, 「Aircraft trajectory planning with collision avoidance using mixed integer linear programming」, ACC 2002, 1936–1941(doi:10.1109/acc.2002.1023918) — 서지만 확인.
• R. Deits, R. Tedrake, 「Footstep planning on uneven terrain with mixed-integer convex optimization」, Humanoids 2014, 279–286(doi:10.1109/humanoids.2014.7041373); T. Marcucci 외, 「Motion planning around obstacles with convex optimization」, Science Robotics 8(84), 2023(doi:10.1126/scirobotics.adf7843) — 서지만 확인.
• M. Posa, C. Cantu, R. Tedrake, 「A direct method for trajectory optimization of rigid bodies through contact」, IJRR 33(1), 69–81, 2014(doi:10.1177/0278364913506757) — 서지만 확인.
• S. Scheel, S. Scholtes, 「Mathematical programs with complementarity constraints: Stationarity, optimality, and sensitivity」, Math. Oper. Res. 25(1), 1–22, 2000(doi:10.1287/moor.25.1.1.15213) — 서지만 확인. 모든 실현 가능점에서 MFCQ가 성립하지 않는다는 서술의 정리 번호는 (확인 필요).
• W. Hock, K. Schittkowski, 『Test Examples for Nonlinear Programming Codes』, Lecture Notes in Economics and Mathematical Systems 187, Springer, 1981(doi:10.1007/978-3-642-48320-2) — 서지만 확인.
• J. A. E. Andersson 외, 「CasADi: a software framework for nonlinear optimization and optimal control」, Mathematical Programming Computation 11(1), 1–36(Crossref 등록 2018; doi:10.1007/s12532-018-0139-4) — 서지만 확인.
• Q. Huangfu, J. A. J. Hall, 「Parallelizing the dual revised simplex method」, Mathematical Programming Computation 10(1), 119–142, 2018(doi:10.1007/s12532-017-0130-5) — HiGHS의 단체법 문헌이며 서지만 확인.
• 공식 코드·문서(조회 2026-11-03): coin-or/Ipopt 태그 releases/3.14.19(옵션 등록 코드·IpMonotoneMuUpdate.cpp·IpFilterLSAcceptor.cpp·README.md·doc/main.dox; 소스 실행은 CasADi 3.8.2 번들), scipy/scipy 태그 v1.18.1(src/slsqp.c·minimize 문서), ERGO-Code/HiGHS(README.md·LICENSE.txt), RobotLocomotion/drake(snopt_solver.h·ipopt_solver.h), UCSD CCoM 최적화 소프트웨어 페이지(SNOPT·라이선스), Gurobi Optimizer Reference Manual 13.0(features/nonlinear.html·reference/fileformats/modelformats.html), PyPI gurobipy 13.0.3(2026-08-25 업로드).

다음 장. 1.15은 최적화 모델링과 코드 생성으로, CasADi·acados·CVXPY가 이 장의 NLP·QP를 기호 모델에서 자동 미분과 함께 구성하고 임베디드 실시간 솔버로 생성하는 방식을 다룬다. 이 장에서 다룬 IPOPT·SQP 해법기가 그 계층에서 어떻게 호출되는지, 기울기와 헤시안의 희소 구조가 어떻게 전달되는지를 확인한다.