제1부 수학적 기초

1.16 최적화 IV: 무미분·표본 기반 최적화 — 베이지안 최적화·CMA-ES·CEM·MPPI의 수학적 기초

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

이 장은 목적 함수의 값만 평가할 수 있을 때, 곧 기울기를 구할 수 없거나 믿을 수 없거나 평가 비용이 클 때 최적화하는 방법의 수학적 기초를 다룬다. 로봇에서는 롤아웃 비용만으로 제어열을 고르는 샘플링 MPC, 접촉이 있는 시뮬레이터 안의 정책 매개변수 탐색, 실기에서의 게인·보행 매개변수 조정이 이에 해당한다. 미분 정보를 사용하는 최적화는 1.12~1.15이 다루며, 이 장은 함수 평가 횟수를 비용으로 보는 방법을 다룬다.

배우는 것:

• 블랙박스 설정과 직접 탐색 — 평가 횟수를 비용으로 하는 성능 척도, 순위 기반 방법의 순서 보존 변환 불변성, 넬더–미드 단체법과 비정지점 수렴의 한계.
• 표본 분포 갱신 — 가중 최대우도라는 공통 구조, CEM, CMA-ES의 평균·진화 경로·공분산 갱신과 기본 매개변수.
• MPPI — 자유 에너지 상계에서 가중치 $\exp(-S/\lambda)$를 유도하는 정보 이론적 설명, CEM과의 관계, 유효 표본 수.
• 베이지안 최적화 — 가우시안 과정 사후 분포, 기대 개선량(EI)과 상한 신뢰 한계(UCB), 후회 한계.
• 한계 — 표본 복잡도, 다봉 함수, 유한 표본 편향, 라이브러리 사이의 차이.

선수 지식: 1.1·1.2(고유분해·숄레스키), 1.19·1.20(가우시안·KL 발산), 1.21(가우시안 과정), 12.15(최적 제어와 가치 함수). 표기는 BK-05와 A.2을 따른다.

특히 중요한 독자: 샘플링 기반 제어기와 정책 탐색을 구현하는 엔지니어, 미분할 수 없는 비용(충돌·접촉·이산 사건)을 최적화하는 연구자, 실기 매개변수 조정의 평가 횟수 예산을 정하는 사업·인증 담당자.

출처 방침. 서지는 Crossref·arXiv·JMLR 페이지로 확인했다(목록은 이 장 끝). 직접 읽은 자료(조회 2026-11-03): ① Hansen의 CMA-ES 튜토리얼 arXiv:1604.00772v2(0.3~0.4절, 식 (5)·(41)~(58), 표 1, 불변성 절), ② Williams 외의 정보 이론적 MPC arXiv:1707.02342 사전 인쇄본(3~5절, 식 (7)~(22), 알고리즘 1·2), ③ pycma 4.5.0·pytorch-mppi 0.9.1·SciPy 1.18.1(_minimize_neldermead)·bayesian-optimization 3.4.0의 소스(scikit-learn은 호출만), ④ IGO·Jamieson·Duchi·Srinivas·Wang·Wagener·Pinneri·Salimans 외의 arXiv 초록(본문은 읽지 않았다). 나머지 문헌은 서지만 확인했다. 직접 실행한 것: 이 장의 순수 파이썬 구현 전부와 라이브러리 5종(pycma·SciPy·scikit-learn·bayesian-optimization·pytorch-mppi; 1.16.5). 읽지 않은 정리·장 번호는 (확인 필요)로 둔다.

1.16.2 개념 — 평가 값만으로 최적화한다

함수 $f:\mathbb{R}^n\to\mathbb{R}$의 값만 얻을 수 있을 때 $f$를 작게 하는 점을 찾는 문제를 블랙박스 최적화라 한다. 비용은 평가 횟수이며, 로봇에서 평가 1회는 시뮬레이션 롤아웃 1회이거나 실기 시험 1회이다(정책 탐색의 개관은 Deisenroth 외의 서베이). 이 장의 방법은 세 계열로 나뉜다. 직접 탐색은 점 $n+1$개의 단체(simplex)를 변형한다. 표본 분포 갱신은 분포에서 표본을 추출·평가하고 그 결과로 분포를 다시 맞춘다. 대리 모델(surrogate model) 방법은 평가 값에 모델을 적합하고 모델이 유망하다고 판단하는 점 하나를 평가한다.

CMA-ES·CEM·MPPI는 같은 순환을 공유하며 가중치 함수만 다르다. 이 구조를 알면 MPPI의 지수 가중이 CEM의 상위 비율 선택과 어떤 관계인지, CMA-ES가 무엇을 추가로 학습하는지가 한 장의 식으로 비교된다. 베이지안 최적화는 평가가 비싸고 차원이 낮은 문제에 맞는 반대쪽 끝에 있다. 층 규칙(BK-08)에 따라 가우시안 과정의 일반 이론은 1.21, MPPI의 로봇 구현과 GPU 롤아웃은 12.19, 미분 정보를 사용하는 방법은 1.12~1.15이 맡는다.

1.16.3 원리

1.16.3.1 블랙박스 설정과 불변성

결론: 방법의 비교 기준은 평가 횟수당 도달한 $f$ 값이다. 비용 값의 순위만 입력으로 받는 방법(CEM·CMA-ES)은 $f$에 순서 보존 변환을 적용해도 같은 경로를 따르며, 지수 가중(MPPI)은 그렇지 않아 $\lambda$가 비용의 척도에 맞아야 한다.

탐색 비용을 실행한 함수 평가 횟수로 정의하고, 성능은 평가 횟수 대비 지금까지의 최소 $f$ 또는 목표 값에 도달한 평가 횟수로 보고한다(Hansen 튜토리얼 0.3절). 엄격하게 단조 증가하는 함수 $g$에 대해 $g\circ f$의 순위는 $f$의 순위와 같으므로 순위 기반 갱신은 같은 표본열에서 같은 결과를 낸다. 이 장은 $g=\ln(1+f)$에서 평균 벡터의 최대 차이가 CMA-ES·CEM에서 0, 지수 가중에서 1.8임을 확인했다(1.16.5). 튜토리얼은 CMA-ES의 불변성으로 순서 보존 변환, 회전·평행 이동, 스케일, 초기 분포를 함께 변환하는 조건에서의 아핀 변환을 든다.

1.16.3.2 직접 탐색: 넬더–미드

결론: 넬더–미드(NM)는 꼭짓점 $n+1$개의 단체를 함수 값의 순위만으로 반사·확장·수축·축소하며, 저차원에서 실용적이나 일반 함수에서 정지점 수렴을 보장하지 않는다.

가장 나쁜 꼭짓점 $x_{n+1}$을 제외한 꼭짓점의 중심 $\bar x$에 대해 표준 계수 $(\rho,\chi,\psi,\sigma)=(1,2,\tfrac12,\tfrac12)$로 다음 점을 시험한다(SciPy 소스의 비적응 기본값).

$$x_r=\bar x+\rho(\bar x-x_{n+1}),\quad x_e=\bar x+\chi\rho(\bar x-x_{n+1}),\quad x_c=\bar x\pm\psi\rho(\bar x-x_{n+1}),\quad x_i\leftarrow x_1+\sigma(x_i-x_1)$$

$f(x_r)$이 최선 값보다 작으면 $x_e$를 시험해 둘 중 좋은 쪽을 채택하고, 차선 꼭짓점의 값보다 작으면 $x_r$을 채택한다. 그렇지 않으면 수축하며(바깥 수축은 $+$, 안쪽 수축은 $-$), 수축도 실패하면 최선 꼭짓점을 향해 단체 전체를 축소한다. Lagarias 외(1998)는 낮은 차원의 수렴 성질을, McKinnon(1998)은 비정지점에 수렴하는 예를 다룬다(서지와 제목만 확인, 정리 번호 (확인 필요)). 이 장은 McKinnon 함수($\tau=2$, $\theta=6$, $\phi=60$ (확인 필요: 매개변수))에서 단체가 $(0,0)$에 정체하는 것을 재현했다. 최솟값은 $(0,-\tfrac12)$에서 $-\tfrac14$이다.

1.16.3.3 표본 분포 갱신의 공통 구조와 CEM

결론: CEM·CMA-ES·MPPI는 분포 $p_\theta$에서 $K$개 표본을 추출·평가한 뒤 가중치 $w_k$로 분포를 가중 최대우도로 다시 맞추는 같은 순환을 따르며, 가중치 함수 $W$만 다르다.

$$\theta^{+}=\arg\max_{\theta}\sum_{k=1}^{K}w_k\log p_\theta(x_k),\qquad w_k=W(S_1,\ldots,S_K),\quad \sum_kw_k=1,\quad S_k=f(x_k)$$

이 갱신은 가중 경험 분포 $\hat q=\sum_kw_k\delta_{x_k}$와 $p_\theta$ 사이의 교차 엔트로피를 최소화한다. $p_\theta=\mathcal N(m,C)$이면 닫힌 해는 $m^{+}=\sum_kw_kx_k$, $C^{+}=\sum_kw_k(x_k-m^{+})(x_k-m^{+})^\top$이다. 교차 엔트로피 방법(CEM; Rubinstein 1999, de Boer 외 2005)은 목표 분포를 $q^\ast(x)\propto\mathbb 1\{f(x)\le\gamma\}\,p(x)$로 두고 $\mathrm{KL}(q^\ast\Vert p_\theta)$를 줄이는 방향으로 갱신한다. 표본 근사에서 $\gamma$는 상위 $\nu$번째 값이고 가중치는 $w_k=1/\nu$이다(Williams 외 5절의 서술; 원문의 정리 번호 (확인 필요)).

Ollivier 외(2017)의 초록은 모수 분포 족에 대해 순위 기반 변환 목적 함수의 자연 기울기 상승(IGO)을 정의하고, CEM이 특수한 경우로, CMA-ES의 한 판이 가우시안의 경우로 복원된다고 밝힌다(초록 수준, 정리 번호 (확인 필요)).

1.16.3.4 CMA-ES: 평균·경로·공분산의 갱신

결론: CMA-ES는 $\mathcal N(m,\sigma^2C)$에서 $\lambda$개를 추출해 상위 $\mu$개의 가중 평균으로 평균을 옮기고, 선택된 단계의 공분산과 누적 경로로 $C$를, 경로 길이로 $\sigma$를 갱신한다. 이차 함수에서 $C$가 헤시안의 역행렬에 비례하도록 수렴하는 것이 설계 목표이다.

공분산 적응은 Hansen·Ostermeier(2001)의 계열이며, 튜토리얼의 갱신(식 (38)~(47))에서 $y_k\sim\mathcal N(0,C)$, $x_k=m+\sigma y_k$, $\langle y\rangle_w=\sum_{i=1}^{\mu}w_iy_{i:\lambda}$이다. $h_\sigma=0$일 때의 보정항은 생략했다.

$$m\leftarrow m+\sigma\langle y\rangle_w,\qquad p_\sigma\leftarrow(1-c_\sigma)p_\sigma+\sqrt{c_\sigma(2-c_\sigma)\mu_{\mathrm{eff}}}\,C^{-1/2}\langle y\rangle_w,\qquad \sigma\leftarrow\sigma\exp\Bigl(\frac{c_\sigma}{d_\sigma}\Bigl(\frac{\lVert p_\sigma\rVert}{E\lVert\mathcal N(0,I)\rVert}-1\Bigr)\Bigr)$$

$$p_c\leftarrow(1-c_c)p_c+h_\sigma\sqrt{c_c(2-c_c)\mu_{\mathrm{eff}}}\,\langle y\rangle_w,\qquad C\leftarrow(1-c_1-c_\mu)C+c_1p_cp_c^\top+c_\mu\sum_{i=1}^{\mu}w_iy_{i:\lambda}y_{i:\lambda}^\top$$

기본값은 표 1(2016년 기본값)에서 읽었다: $\lambda=4+\lfloor3\ln n\rfloor$, $\mu=\lfloor\lambda/2\rfloor$, $\mu_{\mathrm{eff}}=1/\sum_iw_i^2$, $c_\sigma=\frac{\mu_{\mathrm{eff}}+2}{n+\mu_{\mathrm{eff}}+5}$, $d_\sigma=1+2\max\bigl(0,\sqrt{\tfrac{\mu_{\mathrm{eff}}-1}{n+1}}-1\bigr)+c_\sigma$, $c_c=\frac{4+\mu_{\mathrm{eff}}/n}{n+4+2\mu_{\mathrm{eff}}/n}$, $c_1=\frac{2}{(n+1.3)^2+\mu_{\mathrm{eff}}}$, $c_\mu=\min\bigl(1-c_1,\ 2\frac{1/4+\mu_{\mathrm{eff}}+1/\mu_{\mathrm{eff}}-2}{(n+2)^2+\mu_{\mathrm{eff}}}\bigr)$. 기댓값 $E\lVert\mathcal N(0,I)\rVert=\sqrt2\,\Gamma(\tfrac{n+1}{2})/\Gamma(\tfrac n2)\approx\sqrt n(1-\tfrac1{4n}+\tfrac1{21n^2})$이다. 튜토리얼은 음의 가중치(능동 갱신)가 기본이라고 밝히며, 이 장의 구현은 양의 가중치만 사용한다.

$f(x)=\tfrac12x^\top Hx$에서 $C=H^{-1}$이면 탐색은 구면 함수와 같아진다(튜토리얼 0.4절). 튜토리얼은 이 대응의 최적성에 강한 직관과 경험적 증거가 있으나 엄밀한 증명은 없다고 적는다. 이 장의 계산에서 $C^{1/2}HC^{1/2}$의 조건수는 $H$의 $10^{4}$에서 평가 6,000회에 3.8로 줄었다.

1.16.3.5 MPPI의 정보 이론적 유도

결론: MPPI의 가중치 $\exp(-S/\lambda)$는 임의로 정한 변환이 아니라, 제어열 분포의 비용 기댓값에 기준 분포로부터의 KL 발산을 더한 자유 에너지 상계의 최적 분포 $Q^\ast\propto e^{-S/\lambda}P$에서 나온다. 갱신은 $Q^\ast$에 대한 평균을 중요도 표집(importance sampling)으로 추정한 것이다.

MPPI는 Williams 외의 2015~2018년 논문들에서 정리되었다. 제어열 $V=(v_0,\ldots,v_{T-1})$, $v_t=u_t+\varepsilon_t$, $\varepsilon_t\sim\mathcal N(0,\Sigma)$가 만드는 분포를 $Q_{U,\Sigma}$, 명목 제어 0인 비제어 분포를 기준 $P$, 롤아웃의 상태 비용을 $S(V)$라 한다. Jensen 부등식으로 다음 상계를 얻는다(Williams 외 식 (7)~(9)).

$$-\lambda\log E_P\bigl[e^{-S(V)/\lambda}\bigr]\ \le\ E_{Q}\bigl[S(V)\bigr]+\lambda\,D_{\mathrm{KL}}(Q\Vert P)$$

등호는 $q^\ast(V)=\tfrac1\eta e^{-S(V)/\lambda}p(V)$, $\eta=\int e^{-S/\lambda}p\,dV$일 때 성립한다(식 (14)·(15)). $Q^\ast$에 가장 가까운 $Q_{U,\Sigma}$를 $\min_UD_{\mathrm{KL}}(Q^\ast\Vert Q_{U,\Sigma})$로 정하면 $\Sigma$ 고정에서 해는 $u_t^\ast=E_{Q^\ast}[v_t]$이다(식 (20)). 이 기댓값을 현재 분포 $Q_{\hat U,\Sigma}$의 표본으로 추정하면 갱신이 얻어진다(식 (22)와 알고리즘 2, 기준 분포가 $\tilde U=0$인 경우).

$$u_t\leftarrow\hat u_t+\sum_{k=1}^{K}w_k\varepsilon_{k,t},\qquad S_k'=S_k+\lambda\sum_t\hat u_t^\top\Sigma^{-1}\varepsilon_{k,t},\qquad w_k=\frac{e^{-(S_k'-\rho)/\lambda}}{\sum_je^{-(S_j'-\rho)/\lambda}},\quad \rho=\min_kS_k'$$

섭동 비용 $\lambda\hat u^\top\Sigma^{-1}\varepsilon$은 기준 분포와 표집 분포의 우도비에서 나오며, $\lambda$가 온도와 제어 비용의 가중을 함께 정한다. Williams 외는 $\gamma=\lambda(1-\alpha)$로 둘을 분리하고, 이 장의 구현도 $\gamma$를 별도 인자로 받는다. $\lambda\to0$이면 가중치가 최선 표본에 집중하고 $\lambda\to\infty$이면 균등 평균이 된다. 유효 표본 수(effective sample size) $K_{\mathrm{eff}}=1/\sum_kw_k^2$는 이 사이를 1과 $K$ 사이의 값으로 나타낸다. 최소 비용 $\rho$를 빼는 이동은 수치 안정화이며 최적성에 영향이 없다(논문 3.D.1).

Williams 외 5절은 평균만 갱신하는 가우시안 CEM이 상위 $L$개의 비가중 평균을 취한다는 점에서만 정보 이론적 방법과 다르다고 밝힌다. 같은 절은 이 논문의 MPC가 표집 공분산을 갱신하지 않는 이유를, 수렴 후 공분산이 빠르게 줄어들기 때문이라고 적는다. 제어 아핀·잡음 아핀 계에서는 이 최적성이 경로 적분 제어(Kappen 2005, Theodorou 외 2010)의 최적 제어와 일치하고, 그 밖에서는 최적성의 개념이 다르다(논문 4절). Wagener 외의 초록은 MPC를 온라인 학습(동적 거울 하강)의 틀로 보면 기존 MPC 기법 여럿이 특수한 경우가 된다고 밝힌다.

1.16.3.6 베이지안 최적화: 대리 모델과 획득 함수

결론: 베이지안 최적화는 평가 값을 가우시안 과정으로 모델링하고 사후 평균과 표준편차에서 다음 평가점을 고르는 획득 함수(acquisition function)를 최대화한다. 평가마다 모델 적합과 획득 함수 최적화를 하므로 평가 1회가 비싸고 차원이 낮은 문제에 알맞다.

관측 $\{(x_i,y_i)\}$와 커널 $k$, 관측 잡음 분산 $\sigma_n^2$에 대해 사후 분포는 다음과 같다(1.21, Rasmussen–Williams 2006).

$$\mu(x)=k_\ast^\top(K+\sigma_n^2I)^{-1}y,\qquad s^2(x)=k(x,x)-k_\ast^\top(K+\sigma_n^2I)^{-1}k_\ast$$

현재까지의 최소 $y^\ast$에 대해 기대 개선량과 상한 신뢰 한계는 다음과 같다. 최대화 형식은 bayesian-optimization의 소스에서 읽었고 최소화 형식은 부호를 바꾼 것이다. EI를 사용하는 EGO는 Jones 외(1998)에 있다(서지 확인, EI의 기원은 (확인 필요)).

$$\mathrm{EI}(x)=(y^\ast-\mu)\Phi(z)+s\,\phi(z),\quad z=\frac{y^\ast-\mu}{s},\qquad \mathrm{UCB}(x)=-\mu(x)+\sqrt\beta\,s(x)$$

Srinivas 외(2010·2012)는 GP-UCB의 누적 후회를 최대 정보 이득으로 묶고 흔히 사용되는 커널별 서브선형 한계를 얻었다(초록 수준, 식·정리 번호 (확인 필요)). 커널 길이 척도와 같은 초매개변수는 주변우도로 선택한다. 개관은 Shahriari 외(2016)에 있다. Wang 외의 초록은 이 접근이 중간 차원 문제에 한정되어 왔다고 적고, 고유 차원이 낮다는 가정에서 무작위 임베딩(REMBO)을 제안한다.

1.16.3.7 수렴과 표본 복잡도의 한계

결론: 함수 값만 사용하는 방법은 기울기를 사용하는 방법보다 차원에 따라 불리하며 이는 알고리즘의 결함이 아니라 정보의 한계이다. 이 장의 측정에서 CMA-ES의 평가 횟수는 구면 함수에서 차원에 거의 비례했고, 표본 기반 방법은 모두 다봉 함수와 국소해에 대한 보장이 없다.

• 정보의 한계. Jamieson 외의 초록은 함수 평가만 사용하는 방법의 수렴 속도에 대한 하한을 보이고 기울기 접근 방법과의 불가피한 격차를 밝힌다. Duchi 외의 초록은 두 번 평가한 쌍으로 무작위 섭동 기울기를 추정하는 방법이 볼록 최적화에서 확률적 기울기법에 비해 속도에서 최대 $\sqrt d$ 인자를 잃으며 정보 이론적 하한이 이를 상수(때로 로그) 인자 안에서 맞춘다고 밝힌다. Nesterov–Spokoiny(2017)는 같은 부류의 난수 기울기 없는 방법을 다룬다 (확인 필요: 정리).
• 측정한 차원 의존성. 구면 함수에서 $f\le10^{-8}$에 도달하는 평가 횟수의 중앙값은 CMA-ES가 $n=2,5,10,20$에서 262.5·704·1,445.5·2,731.5회이며 차원당 131~145회이다. 모집단 크기 100으로 고정한 CEM(대각)은 2,572·4,098.5·5,657.5·8,169회이다(시드 8개).
• 다봉 함수. 대역 수렴의 보장이 없고 모집단 크기가 전역 탐색 능력을 좌우한다(튜토리얼이 같은 취지로 밝히며 Hansen·Kern(2004)이 다봉 시험 함수에서 평가했다). Rastrigin($n=5$)의 성공 횟수는 아래 표에 있다.
• 국소해. Rosenbrock($n=5$)의 실패 실행(NM 5회, CMA-ES 4회)은 모두 $f=3.931$에 정체했다. CMA-ES 실패 4회의 종점은 기울기 노름이 $10^{-6}$ 미만이고 헤시안의 최소 고유값이 0.595로 양수여서 국소 극소이다.

1.16.4 알고리즘

표본 분포 갱신(f, p_θ, 가중치 함수 W):
    반복:  x_k ~ p_θ,  S_k = f(x_k)   (k = 1..K)
           w = W(S)      # CEM 상위 ν개 균등, MPPI 지수 가중
           θ ← argmax Σ_k w_k log p_θ(x_k)  # CMA-ES 점진 갱신

MPPI 제어 주기(상태 x0, 명목 제어 U = (u_0..u_{T-1})):
    ε_k ~ N(0, Σ)^T,  V_k = U + ε_k      (k = 1..K)
    S_k = 롤아웃 비용(x0, V_k) + γ Σ_t u_t^T Σ^-1 ε_{k,t}
    w = exp(-(S-min S)/λ) 정규화;  U ← U + Σ_k w_k ε_k
    u_0 적용;  U ← (u_1..u_{T-1}, 0)

베이지안 최적화(f, 예산 N, 초기 n0점):
    n0점 평가;  while 평가 횟수 < N:
        z ← 평가 값 표준화
        ℓ ← 로그 주변우도 최대(길이 척도 격자)
        후보 중 EI(μ, s, min z) 또는 UCB가 최대인 x를 평가

1.16.5 풀이 예제 — 시험 함수·점 질량 제어·라이브러리 확인

순수 파이썬(표준 라이브러리)으로 구현한 방법들을 시험 함수와 작은 제어 문제에서 평가 횟수 대비 성능으로 측정하고 라이브러리 5종과 같은 입력으로 비교했다. 결론부터 적으면 다음과 같다. ① 구현은 SciPy의 넬더–미드, scikit-learn의 가우시안 과정, pytorch-mppi의 가중치와 일치하며, pycma의 기본 매개변수와는 $c_\sigma$·$d_\sigma$에서 다르다. ② 조건수 $10^{4}$의 10차원 회전 타원체에서 CMA-ES는 15회 모두 도달하고 대각 CEM은 한 번도 도달하지 못한다. ③ 2차원 Branin의 평가 40회에서 베이지안 최적화의 오차 중앙값은 무작위·CEM·CMA-ES보다 25배 이상 작다. ④ 점 질량의 MPC에서 $\lambda$는 도달률·비용·유효 표본 수를 서로 다른 방향으로 바꾸므로 한 가중 방식이 모든 지표를 지배하지 않는다.

핵심 코드는 다음과 같다. 순환 야코비 고유분해 eig_sym(약 25줄)은 스크립트에 있으며 1.9의 eigsym과 대조했다(eigsym은 회전마다 전체 행렬 곱을 하므로 CMA-ES의 세대마다 호출하기에 느리다). search의 a는 이전 값의 비중(평활)이고 adapt가 거짓이면 분산을 고정한다. 시험 함수·넬더–미드·측정 하니스는 robotics/fig-src/1.16-derivfree.py에 있다.

def w_cem(F, ne):                  # CEM: 상위 ne개 균등
    K = len(F)
    top = sorted(range(K), key=F.__getitem__)[:ne]
    return [1.0 / ne if k in top else 0.0 for k in range(K)]

def w_mppi(S, lam):                # MPPI: 지수 가중
    rho = min(S)
    e = [math.exp(-(s - rho) / lam) for s in S]
    z = sum(e)
    return [x / z for x in e]

def search(f, m, s, budget, rng, lam, wf, adapt=True, a=0.0):
    n, ev = len(m), 0
    m, s = m[:], s[:]
    while ev + lam <= budget:
        X = [[rng.gauss(m[i], s[i]) for i in range(n)]
             for _ in range(lam)]
        w = wf([f(x) for x in X])
        ev += lam
        for i in range(n):
            mi = sum(w[k] * X[k][i] for k in range(lam))
            if adapt:
                v = sum(w[k] * (X[k][i] - mi) ** 2
                        for k in range(lam))
                s[i] = math.sqrt(a * s[i] ** 2 + (1 - a) * v)
            m[i] = a * m[i] + (1 - a) * mi
    return m, s

def mv(M, x):
    return [sum(a * b for a, b in zip(r, x)) for r in M]

def cma_es(f, m, sg, budget, rng, lam=None):
    """(mu/mu_w, lambda)-CMA-ES, 양의 가중치만 사용"""
    n = len(m)
    lam = lam or 4 + int(3 * math.log(n))
    mu = lam // 2
    w = [math.log((lam + 1) / 2) - math.log(i + 1)
         for i in range(mu)]
    w = [x / sum(w) for x in w]
    me = 1 / sum(x * x for x in w)
    cs = (me + 2) / (n + me + 5)
    ds = 1 + 2 * max(0, ((me - 1) / (n + 1)) ** .5 - 1) + cs
    cc = (4 + me / n) / (n + 4 + 2 * me / n)
    c1 = 2 / ((n + 1.3) ** 2 + me)
    cm = min(1 - c1,
             2 * (me - 1.75 + 1 / me) / ((n + 2) ** 2 + me))
    chi = n ** .5 * (1 - 1 / (4 * n) + 1 / (21 * n * n))
    C = [[float(i == j) for j in range(n)] for i in range(n)]
    D, B = [1.0] * n, [r[:] for r in C]    # C = B D^2 B^T
    ps, pc, ev, g = [0.0] * n, [0.0] * n, 0, 0
    while ev + lam <= budget:
        Y = [mv(B, [rng.gauss(0, 1) * d for d in D])
             for _ in range(lam)]
        F = [f([a + sg * b for a, b in zip(m, y)]) for y in Y]
        ev, g = ev + lam, g + 1
        top = sorted(range(lam), key=F.__getitem__)[:mu]
        yw = [sum(w[k] * Y[t][i] for k, t in enumerate(top))
              for i in range(n)]
        m = [a + sg * b for a, b in zip(m, yw)]
        u = [v / d for v, d in zip(mv(list(zip(*B)), yw), D)]
        a = (cs * (2 - cs) * me) ** .5
        iy = mv(B, u)                           # C^-1/2 yw
        ps = [(1 - cs) * p + a * v for p, v in zip(ps, iy)]
        nps = sum(p * p for p in ps) ** .5
        hs = nps / (1 - (1 - cs) ** (2 * g)) ** .5 \
            < (1.4 + 2 / (n + 1)) * chi
        a = hs * (cc * (2 - cc) * me) ** .5
        pc = [(1 - cc) * p + a * v for p, v in zip(pc, yw)]
        k0 = 1 - c1 - cm + c1 * (1 - hs) * cc * (2 - cc)
        for i in range(n):
            for j in range(n):
                r = sum(w[k] * Y[t][i] * Y[t][j]
                        for k, t in enumerate(top))
                C[i][j] = (k0 * C[i][j] + c1 * pc[i] * pc[j]
                           + cm * r)
        sg *= math.exp(cs / ds * (nps / chi - 1))
        D, B = eig_sym(C)
        D = [max(d, 1e-30) ** .5 for d in D]
    return m, sg, C

def mppi_update(U, E, S, gam, sig, wf):
    """U 명목 제어, E[k] 잡음, S[k] 상태 비용 (T x m)"""
    K, T, M = len(S), len(U), len(U[0])
    def ue(e):                                  # U^T E
        return sum(U[t][c] * e[t][c]
                   for t in range(T) for c in range(M))
    w = wf([S[k] + gam / sig ** 2 * ue(E[k])
            for k in range(K)])
    dU = [[sum(w[k] * E[k][t][c] for k in range(K))
           for c in range(M)] for t in range(T)]
    return [[u + d for u, d in zip(a, b)]
            for a, b in zip(U, dU)], w

베이지안 최적화의 가우시안 과정과 EI는 다음과 같다. 숄레스키 chol·tri_solve는 1.2의 구현이며 획득 함수 최대화 순환은 1.16.4의 의사코드와 같다.

def kern(a, b, ell):                # 제곱 지수 커널
    d2 = sum((x - y) ** 2 for x, y in zip(a, b))
    return math.exp(-d2 / (2 * ell * ell))

def gp_fit(X, y, ell, jit=1e-6):
    """숄레스키 L, alpha = K^-1 y, 로그 주변우도"""
    n = len(X)
    K = [[kern(X[i], X[j], ell) + jit * (i == j)
          for j in range(n)] for i in range(n)]
    L = chol(K)
    Lt = [list(r) for r in zip(*L)]
    al = tri_solve(Lt, tri_solve(L, y, True), False)
    lml = (-0.5 * sum(a * b for a, b in zip(y, al))
           - sum(math.log(L[i][i]) for i in range(n))
           - 0.5 * n * math.log(2 * math.pi))
    return L, al, lml

def gp_pred(X, L, al, x, ell):
    """x에서의 사후 평균과 표준편차"""
    k = [kern(x, xi, ell) for xi in X]
    v = tri_solve(L, k, True)
    var = 1.0 - sum(t * t for t in v)
    mu = sum(a * b for a, b in zip(k, al))
    return mu, max(var, 1e-12) ** .5

def ei(mu, s, best):                # 최소화용 EI
    z = (best - mu) / s
    cdf = 0.5 * (1 + math.erf(z / 2 ** .5))
    pdf = math.exp(-z * z / 2) / (2 * math.pi) ** .5
    return (best - mu) * cdf + s * pdf

① 항등식과 수학 확인.

SciPy의 Nelder-Mead는 기본 허용 오차($10^{-4}$)에서 McKinnon 함수를 111회 평가 후 $(0,0)$에서 정상 종료로 보고한다(아래 라이브러리 확인). 이 장의 계산에서 단체는 평가 300회까지 $(0,0)$에 머물렀고 1,000회에서 벗어났으며, 반올림의 영향으로 본다 (추정). McKinnon의 결과 자체는 정확한 산술에서의 수렴이다 (확인 필요).

② 평가 횟수 대비 성능. 아래 표는 지금까지의 최소 $f$의 중앙값과 목표 $f\le10^{-8}$ 도달 횟수(시드 15개)이다.

CMA-ES와 NM은 타원체에 모두 도달한다. 평가 5,000회에서 $f$의 중앙값은 NM이 0.51, CMA-ES가 $10^{-12}$ 미만이며 도달 평가 횟수의 중앙값은 6,006회 대 3,781회이다. 대각 CEM은 표준편차 최댓값이 $1.5\times10^{-5}$ 이하로 수축한 채 평균이 최적점에서 5 이상 떨어진 상태에서 정체한다(위 표의 정체 행). 전체 공분산 CEM은 15회 중 5회 도달한다. Rosenbrock에서는 NM이 10회, CMA-ES가 11회 도달하고 실패한 실행은 모두 국소 극소 $f=3.931$에 있다. 학습률 없는 가중 최대우도 갱신이 정체하는 이유는 분산이 선택된 표본의 분산으로 곧바로 재설정되어 평균 이동보다 먼저 줄기 때문으로 본다 (추정).

③ 다봉 함수와 모집단 크기(Rastrigin, $n=5$).

④ 베이지안 최적화(Branin, 평가 횟수별 최적값과의 차, 중앙값(사분위), 시드 20개). 초기 5점이 평가 횟수에 포함된다. 무작위·CEM($\lambda=10$, 엘리트 3, 평활 0.5)·CMA-ES($\sigma_0=0.3$, $\lambda=6$)는 같은 평가 예산과 $[0,1]^2$ 균등 시작점에서 실행했다.

평가 40회에서 BO-EI의 중앙값은 0.018, BO-UCB는 0.0386으로 CMA-ES의 0.975보다 크게 작으며 두 획득 함수의 사분위 범위는 겹친다. 이 결과는 2차원 문제, 평가 40회, 이 장의 구현과 설정에 한정된다. BO의 모델 적합 비용은 평가 횟수와 함께 늘고, 이 구현은 순수 파이썬이므로 시간 비교는 하지 않았다.

⑤ 점 질량의 장애물 회피(샘플링 MPC). 장애물이 직선 경로를 가로막는 대칭 배치이다. 각 칸은 도달 횟수(16회 중, 충돌 없이 목표 0.3 m 안에 든 실행) · 닫힌 루프 비용 $J$의 평균 · 평균 유효 표본 수 $K_{\mathrm{eff}}$이다. $J$는 실제 궤적의 $\bigl(\lVert p-g\rVert^2+0.1\lVert v\rVert^2\bigr)\Delta t$ 합에 충돌 단계마다 $100\Delta t$를 더한 값이다.

$K=16$에서는 80회 중 5회(최선 표본 2, MPPI $\lambda=0.1$ 2, CEM형 1)에서 충돌이 있었고 $K=64$·256의 160회에서는 없었다. $\lambda$가 작으면 $K_{\mathrm{eff}}\approx1$이어서 최선 표본 1개와 같고, $\lambda=10$은 $K$에 비례해 $K_{\mathrm{eff}}$가 커지며 도달 횟수는 늘지만 $J$는 $K=256$에서 $\lambda=1$·CEM형(24.3·24.0)보다 큰 28.6이다. 같은 표본 64개로 첫 주기의 계획을 만들면 가중이 넓을수록 계획의 비용이 최선 표본의 비용에서 멀어진다.

비용이 $J$ 한 가지가 아니고 도달 횟수와 방향이 다르므로 $\lambda$의 선택은 지표의 선택이다. 닫힌 루프는 첫 주기의 계획이 나빠도 갱신을 반복해 목표에 도달한다(그림의 검은 선, $K=64$, $\lambda=10$, 시드 0). 이 설정은 가속 한계와 장애물 비용에 맞춘 한 문제이며 일반적 순위를 뜻하지 않는다.

⑥ 라이브러리 확인(실행 2026-11-03). 같은 입력으로 호출했다. 스크립트는 robotics/fig-src/1.16-libcheck.py(pycma·SciPy·scikit-learn·bayesian-optimization)와 1.16-libcheck-mppi.py(pytorch-mppi), 출력은 robotics/fig-src/data/1.16-libcheck-output.txt·1.16-libcheck-mppi-output.txt에 있다.

저장소 메타데이터(PyPI, 조회 2026-11-03): cma 4.5.0(BSD-3-Clause, 2026-09-13), bayesian-optimization 3.4.0(MIT, 2026-10-02), pytorch-mppi 0.9.1(MIT 라이선스문, 2026-03-15), SciPy 1.18.1. GitHub API는 속도 제한으로 응답하지 않아 푸시 날짜는 확인하지 못했다. 파이썬 3.12, NumPy 2.5.4, PyTorch 2.15.0은 격리된 가상환경에서 실행했다. 사전 릴리스는 사용하지 않았다.

한계. 수치는 합성 입력(시드 고정)이며 시험 함수 4종과 점 질량 문제 1개에서 측정했다. CEM(대각)의 평활 계수는 세 값(0·0.5·0.8)을, CEM(전체)의 $(\lambda,\text{엘리트},\text{평활})$는 세 조합 $(200,40,0)$·$(200,40,0.5)$·$(500,100,0)$을 예비로 시험해 정했고 어느 것도 타원체의 정체를 해소하지 못했다. 예비 실행은 책의 표에 넣지 않았다. BO의 길이 척도 격자와 후보 수는 임의로 정했다. 라이브러리 비교의 pycma·bayesian-optimization은 설정이 다르므로 이 장의 구현과 성능이 같다는 뜻이 아니다. pycma와의 도달 횟수 차이는 능동 갱신을 끈 실행에서 줄었으나(타원체 3,738 대 3,781) $c_\sigma$ 차이의 기여는 분리하지 않았다.

견해: 샘플링 기반 제어기의 성능 보고는 $\lambda$ 값만이 아니라 평균 유효 표본 수 $K_{\mathrm{eff}}$를 함께 적어야 비교할 수 있다고 본다. 근거는 표에서 같은 $\lambda=10$이 $K=16$에서 11.2, $K=256$에서 204.5의 $K_{\mathrm{eff}}$를 낳고 도달 횟수와 $J$가 서로 다른 방향으로 변하는 점이다. 비용을 $c$배 하면 같은 $K_{\mathrm{eff}}$를 얻기 위해 $\lambda$도 $c$배 해야 하므로 $\lambda$ 값 자체는 문제 사이에 이식되지 않는다.

1.16.6 설계 트레이드오프 — 방법의 선택

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

• ① 대리 모델(베이지안 최적화). 평가 횟수가 수십 회로 제한되고 차원이 낮을 때 이 장의 측정에서 오차가 가장 작았다(위 Branin 측정). 모델 적합 비용, 중간 차원 이상에서의 한계(Wang 외), 커널·초매개변수 선택이 부담이다.
• ② 공분산을 학습하는 표본 분포 갱신(CMA-ES). 평가가 수천~수십만 회 가능한 중차원 연속 문제에서 조건수와 비분리성을 다룬다. 다봉 함수에서는 모집단 크기를 키워야 하고 평가 횟수가 늘어난다.
• ③ 고정 공분산의 가중 평균(MPPI·CEM형 MPC). 주기마다 갱신 1회로 실시간 제어에 맞고 병렬 롤아웃에 적합하다. CEM형 계획기의 표본 효율을 높이는 변형(Pinneri 외 초록: 시간 상관 행동·기억, 표본 2.7~22배 감소 (공개 주장치))은 12.19가 다룬다. 정밀한 수렴은 목표가 아니며 $\lambda$·$\Sigma$·$K$가 성능을 정한다.

이 표의 평가 예산 범위는 이 장 측정의 규모와 문헌 서술을 정리한 것이며 일반적 한계가 아니다.

견해: 평가 1회가 수 초 이상이고 조정할 매개변수가 열 개 안팎이면 대리 모델 방법을 먼저 시험하고, 평가가 병렬로 싸고 매개변수가 수십 개이면 CMA-ES를, 폐루프 제어기의 주기 안에서 푸는 문제이면 샘플링 MPC를 고려하는 것이 합리적이라고 본다. 근거는 이 장의 Branin 측정(40회)과 타원체 측정, 튜토리얼과 Wang 외 초록의 서술이다. 반증은 비용 척도·차원·잡음이 다른 문제에서의 측정이다.

1.16.7 응용 축 비교

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

1.16.8 관련 규격·프로토콜

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

직접 적용되는 규제는 없다. 표본 기반 최적화는 난수와 유한 표본에 의존하므로 결과가 시드마다 다르고 최악 경우의 보장이 없다. 안전 기능에 사용하면 재현성과 시험 가능성이 문제가 되므로, 최적화를 안전 기능의 바깥에 두고 출력을 런타임 감시나 제어 장벽 필터로 걸러내는 구조를 고려할 수 있다(26.16, 12.25, 21.4). 소프트웨어 안전과 품질 표준은 26.20이 다루고 실험 보고와 시드 관리는 17.25이 다룬다.

1.16.10 한계·유의점·미해결

• 정리의 출처. Rubinstein·de Boer 외의 CEM 수렴 결과, Ollivier 외의 IGO 정리, Srinivas 외의 후회 한계식, Lagarias 외·McKinnon의 정리 번호, Nesterov–Spokoiny의 속도는 읽지 않았다 (확인 필요: 장·정리 번호). McKinnon 함수의 매개변수는 기억에 의존했다 (확인 필요).
• 라이브러리. pycma·bayesian-optimization은 설정이 다른 실행의 비교이며 pytorch-mppi는 확률적 갱신이 아닌 단일 갱신의 입력·출력 일치만 확인했다. 장기 안정성·GPU 경로·Nav2의 MPPI 제어기(14.3)는 실행하지 않았다.
• 측정의 범위. 시험 함수 4종과 점 질량 1개, 시드 8~20개이다. CEM의 설정은 예비 시험 세 값에서 정했다. 20차원을 넘는 차원, 잡음 있는 평가, 제약은 다루지 않았다.
• 가정. 구현은 모델 오차가 없는 시뮬레이션이다(점 질량 동역학을 계획과 플랜트가 공유). 모델 오차·지연·센서 잡음이 있는 실기에서의 MPPI 성능은 12.19와 16.12가 다룬다.
• 미해결. 평가 예산에 대한 방법 선택의 규칙, 고차원 베이지안 최적화의 로봇 적용, 샘플링 MPC의 안전 보증은 열린 문제이다.

1.16.11 체크포인트·연구 질문

체크포인트:

1. 블랙박스 설정에서 방법의 성능을 평가 횟수 대비 $f$로 정의하고 순위 기반 방법이 순서 보존 변환에 불변인 이유를 설명할 수 있는가.
2. CEM·CMA-ES·MPPI를 가중 최대우도 갱신 $\theta^{+}=\arg\max\sum_kw_k\log p_\theta(x_k)$의 가중치 함수 차이로 비교할 수 있는가.
3. CMA-ES의 $p_\sigma$·$p_c$·$c_1$·$c_\mu$가 각각 무엇을 갱신하는지 말할 수 있는가.
4. 자유 에너지 상계에서 $q^\ast\propto e^{-S/\lambda}p$와 MPPI의 갱신 식을 유도하고, 유효 표본 수 $K_{\mathrm{eff}}$를 계산해 $\lambda$·$K$의 선택에 반영할 수 있는가.
5. EI와 UCB의 식을 작성하고 평가 횟수·차원에 따라 베이지안 최적화가 알맞은 조건을 말할 수 있는가.
6. 표본 분포 갱신의 정체(분산 수축·국소해)를 구분해 진단하고, 넬더–미드가 정상 종료로 보고한 해가 정지점이 아닐 수 있음을 설명할 수 있는가.

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

• 접촉이 있는 시뮬레이터 안에서 미분 가능 최적화와 CMA-ES·MPPI의 평가 횟수 대비 성능은 문제 구조(접촉 수·차원)에 따라 어떻게 갈리는가.
• 샘플링 MPC에서 $\lambda$를 비용 척도에 맞춰 적응시키는 규칙(유효 표본 수 목표)은 주기 안의 안전·성능을 보장하는가.
• 평가 1회가 실기 시험인 보행·외골격 매개변수 조정에서 안전한 베이지안 최적화는 평가 횟수와 위반 확률을 어떻게 맞바꾸는가.

1차 출처

• N. Hansen, 「The CMA Evolution Strategy: A Tutorial」, arXiv:1604.00772(v2, 2023-03) — 직접 읽음(식 (5)·(38)~(58), 표 1, 0.3·0.4절, 불변성).
• N. Hansen, A. Ostermeier, 「Completely Derandomized Self-Adaptation in Evolution Strategies」, Evolutionary Computation 9(2):159–195, 2001(doi:10.1162/106365601750190398); N. Hansen, S. Kern, 「Evaluating the CMA Evolution Strategy on Multimodal Test Functions」, LNCS, 2004(doi:10.1007/978-3-540-30217-9_29) — 서지만 확인.
• G. Williams, P. Drews, B. Goldfain, J. M. Rehg, E. A. Theodorou, 「Information Theoretic Model Predictive Control: Theory and Applications to Autonomous Driving」, arXiv:1707.02342 사전 인쇄본 — 직접 읽음. 출판본은 IEEE Transactions on Robotics 34(6):1603–1622, 2018(doi:10.1109/tro.2018.2865891)로 서지만 확인했으며 식 번호는 사전 인쇄본 기준이다.
• G. Williams 외, 「Information theoretic MPC for model-based reinforcement learning」, ICRA 2017(doi:10.1109/icra.2017.7989202); G. Williams, A. Aldrich, E. Theodorou, 「Model Predictive Path Integral Control using Covariance Variable Importance Sampling」, arXiv:1509.01149 — 서지·초록만 확인.
• R. Y. Rubinstein, 「The Cross-Entropy Method for Combinatorial and Continuous Optimization」, Methodology and Computing in Applied Probability 1(2):127–190, 1999(doi:10.1023/a:1010091220143); P.-T. de Boer, D. P. Kroese, S. Mannor, R. Y. Rubinstein, 「A Tutorial on the Cross-Entropy Method」, Annals of Operations Research 134(1):19–67, 2005(doi:10.1007/s10479-005-5724-z) — 서지만 확인.
• Y. Ollivier, L. Arnold, A. Auger, N. Hansen, 「Information-Geometric Optimization Algorithms」, JMLR 18(18):1–65, 2017(arXiv:1106.3708) — 초록 확인. E. Theodorou, J. Buchli, S. Schaal, 「A Generalized Path Integral Control Approach to Reinforcement Learning」, JMLR 11(104):3137–3181, 2010; H. J. Kappen, 「Linear Theory for Control of Nonlinear Stochastic Systems」, Physical Review Letters 95(20), 2005(doi:10.1103/physrevlett.95.200201) — 서지 확인(JMLR 페이지 초록 확인).
• J. A. Nelder, R. Mead, 「A Simplex Method for Function Minimization」, The Computer Journal 7(4):308–313, 1965(doi:10.1093/comjnl/7.4.308); J. C. Lagarias 외, SIAM Journal on Optimization 9(1):112–147, 1998(doi:10.1137/s1052623496303470); K. I. M. McKinnon, SIAM Journal on Optimization 9(1):148–158, 1998(doi:10.1137/s1052623496303482) — 서지만 확인.
• D. R. Jones, M. Schonlau, W. J. Welch, 「Efficient Global Optimization of Expensive Black-Box Functions」, Journal of Global Optimization 13(4):455–492, 1998(doi:10.1023/a:1008306431147); B. Shahriari 외, 「Taking the Human Out of the Loop: A Review of Bayesian Optimization」, Proceedings of the IEEE 104(1):148–175, 2016(doi:10.1109/jproc.2015.2494218) — 서지만 확인.
• N. Srinivas, A. Krause, S. M. Kakade, M. Seeger, 「Gaussian Process Optimization in the Bandit Setting」, arXiv:0912.3995; IEEE Transactions on Information Theory 58(5):3250–3265, 2012(doi:10.1109/tit.2011.2182033) — 초록 확인. Z. Wang 외, 「Bayesian Optimization in a Billion Dimensions via Random Embeddings」, arXiv:1301.1942 — 초록 확인. C. E. Rasmussen, C. K. I. Williams, 『Gaussian Processes for Machine Learning』, MIT Press, 2006(doi:10.7551/mitpress/3206.001.0001) — 서지만 확인.
• K. G. Jamieson, R. D. Nowak, B. Recht, 「Query Complexity of Derivative-Free Optimization」, arXiv:1209.2434; J. C. Duchi 외, 「Optimal rates for zero-order convex optimization」, arXiv:1312.2139 — 초록 확인. Y. Nesterov, V. Spokoiny, Foundations of Computational Mathematics 17(2):527–566, 2017(doi:10.1007/s10208-015-9296-2) — 서지만 확인.
• 로봇 응용 서지(제목 수준만 확인): M. P. Deisenroth 외, 「A Survey on Policy Search for Robotics」, Foundations and Trends in Robotics 2(1–2):1–142(doi:10.1561/2300000021, Crossref는 첫 저자만 등록, 연도 2011로 등록 (확인 필요)); R. Calandra 외, 「Bayesian optimization for learning gaits under uncertainty」, Annals of Mathematics and Artificial Intelligence 76:5–23, 2015(doi:10.1007/s10472-015-9463-9); J. Zhang 외, 「Human-in-the-loop optimization of exoskeleton assistance during walking」, Science 356(6344):1280–1284, 2017(doi:10.1126/science.aal5054); T. Salimans 외, arXiv:1703.03864(초록 확인); C. Pinneri 외, arXiv:2008.06389(초록 확인, 샘플 수 감소 주장은 (공개 주장치)); N. Wagener 외, arXiv:1902.08967(초록 확인).
• 소스·실행(조회 2026-11-03): pycma 4.5.0, pytorch-mppi 0.9.1, SciPy 1.18.1, bayesian-optimization 3.4.0, scikit-learn 1.9.1의 PyPI 배포물과 소스.

다음 장. 1.17는 최적화 V로, 다항식 최적화와 인증 — 반정부호 계획법(SDP)·제곱합(SOS)·리아푸노프 함수 탐색을 다룬다. 이 장의 방법은 해의 최적성이나 안정성을 보장하지 않으므로, 1.17는 볼록 이완으로 그런 성질을 증명하는 방법과 한계를 다룬다.