완전성 계약(Completeness contract)
이 글은 5_Ch4-General-purpose gradient-based opt(1).pdf 19 / 19쪽을 기준으로 작성했다. 번호식뿐 아니라 번호 없는 표시식, 의미 있는 인라인 수학, 표·그림·캡션, 객관식·??·공란, 각주·참고문헌, 판독 가능한 손글씨를 원장에 연결했다. 원문 빈칸·오류 의심 표기는 보존하고 완성식과 교정식은 별도 상태로 등록한다.

세 층을 섞지 않는다.
① 2025 PDF 원자료 재구성, ② 편집·수학 검증, ③ 2026-08-18 최신 연구 업데이트를 분리한다.

#원장 현황

• PDF: 19 / 19쪽
• PDF SHA-256: 23272c39a5ad9c0dddf24eb7d42fdebe8575344f74bac3de761b7844fd81e58c
• 전체 수식 record: 211개
• source-derived 수식: 188개
• display formula: 110개, inline formula: 101개
• content record: 151개
• figures/tables: 10개
• handwritten annotations: 17개
• editorial completion/correction: 23개

#PDF 원자료 재구성

#4. 범용 기울기 기반 최적화 방법(General-purpose gradient-based optimization methods)

비제약 최적화는 비용함수(cost function) $\Psi:\mathbb{F}^{N}\to\mathbb{R}$의 최소화 문제

에서 시작한다. 초기 추정 $x^{(0)}$을 정한 뒤 반복열 $\{x^{(k)}\}_{k\ge 0}$을 만들고, 어떤 norm에서 $\|x^{(k)}-\widehat{x}\|\to 0\quad(k\to\infty)$가 되기를 기대한다.

강의자료는 응용에 따라 실수 또는 복소수 공간을 함께 다루기 위해 $\mathbb{F}\in\{\mathbb{R},\mathbb{C}\}$를 사용한다. 이 장의 중심은 convex하고 gradient가 Lipschitz continuous인 smooth objective이며, least-squares는 그 특수한 경우다.

#동기 응용: edge-preserving image recovery

측정모델은 $y=Ax+\varepsilon$이고, data fidelity와 convex smooth regularizer를 결합해

를 푼다. 정규화항은 transform coefficient마다 potential을 더하는 $R(x)=\sum_{j}\psi([Cx]_{j})$의 형태다.

강의 주석 — PDF p.1. 우측 필기에서 등고선, gradient 방향, step size와 Lipschitz constant를 연결하는 짧은 메모가 보인다. 판독이 확정되지 않는 작은 글씨는 추측해 문장으로 만들지 않았다.

#4.1 Lipschitz 연속성(Lipschitz continuity)

함수 $g:\mathbb{F}^{N}\to\mathbb{F}^{M}$에 대해 어떤 유한한 $L<\infty$이 존재하여

을 만족하면 Lipschitz continuous라 한다. 가능한 상수 중 가장 작은 값을 best Lipschitz constant라고 하며, 자료는 특별한 언급이 없으면 Euclidean norm을 사용한다.

이하에서 f와 g의 best constants를 $L_f,\,L_g$로 둔다.

• Scaling: $h(x)=\alpha f(x)+\beta\quad\Longrightarrow\quad L_h=|\alpha|L_f$
• Translation: $h(x)=f(x-x_0)\quad\Longrightarrow\quad L_h=L_f$
• Addition: $h(x)=f(x)+g(x)\quad\Longrightarrow\quad L_h\le L_f+L_g$
• Composition: $h(x)=f(g(x))\quad\Longrightarrow\quad L_h\le L_fL_g$
• Affine transformation: $h(x)=Ax+b\quad\Longrightarrow\quad L_h=\|A\|_2$
• Multiplication: $h(x)=f(x)g(x)\quad\Longrightarrow\quad L_h=\boxed{\text{??}}$

자료는 두 Lipschitz 함수의 곱도 전체 실수축에서 항상 Lipschitz인지 True/False로 묻고 답을 비운다.

곱에 대한 충분조건과 proof도 빈칸 상태로 제시된다.

다음 페이지는 boundedness가 필요한 조건인지 다시 묻는다. $f,g\text{가 모두 bounded여야 하는가?}\quad\boxed{\text{??}}$

강의 주석 — PDF p.2. 곱의 차이를 한 항씩 더하고 빼서 triangle inequality를 적용하는 proof 방향과 boundedness 표시가 손으로 보강되어 있다. 판독이 확정되지 않는 작은 글씨는 추측해 문장으로 만들지 않았다.

#Smooth function: Lipschitz-continuous gradient

이 장에서 smooth function은 differentiable하고 gradient가

을 만족하는 함수다. 복소수 공간의 derivative는 더 미묘하므로 이 정의는 우선 실수공간에 둔다.

Least-squares 예제 $f(x)=\frac12\|Ax-y\|_2^2$의 gradient는 $\nabla f(x)=A^{\mathsf T}(Ax-y)$이며,

에서

을 얻는다.

두 번 미분 가능하고 Hessian spectral norm이

처럼 bounded이면 gradient Lipschitz의 충분조건이다. Taylor integral form

과 norm bound

가 proof를 이룬다. 자료는 이 조건이 sufficient이지만 necessary는 아니라고 명시한다.

Quadratic examples로 $\nabla^2f=A^{\mathsf T}A,\qquad \|\nabla^2f\|_2=\|A\|_2^2$와 rank-one form $f(x)=x^{\mathsf T}\begin{bmatrix}1&2\\2&4\end{bmatrix}x$, $z^{\mathsf T}=\begin{bmatrix}1&2\end{bmatrix}$,

을 제시한다.

강의 주석 — PDF p.3. least-squares gradient, Hessian의 spectral norm, singular value와 eigenvalue 관계를 따라가는 필기가 보인다. 판독이 확정되지 않는 작은 글씨는 추측해 문장으로 만들지 않았다.

#Fair potential과 edge-preserving regularizer

Fair potential은

이며,

,

을 만족한다. 원점 근처에서는 roughly quadratic, 큰 |x|에서는 |x|처럼 증가하고, 두 번째 도함수가 nonnegative라 convex다.

자료는 potential 자체도 Lipschitz continuous인지 $\psi_\delta\text{ itself Lipschitz continuous?}\quad\boxed{\text{??}}$로 질문한다.

Regularizer gradient와 그 Lipschitz constant를 합성함수로 계산하는 exercise는

에서 시작해 $f(x)=Cx,\qquad g(u)=\dot\psi_{\cdot}(u),\qquad h(v)=C^{\mathsf T}v$,

,

,

,

의 빈칸을 남긴다.

강의 주석 — PDF p.4. Fair potential 그래프에는 quadratic regime와 edge-preserving 성질을 연결하는 메모가 있고, regularizer exercise 옆에는 chain rule 순서가 표시되어 있다. 판독이 확정되지 않는 작은 글씨는 추측해 문장으로 만들지 않았다.

#4.2 Smooth convex 함수의 gradient descent

가정은 finite minimizer $-\infty<\Psi(\widehat{x})\le\Psi(x),\qquad \forall x\in\mathbb{R}^{N}$, Lipschitz gradient $\|\nabla\Psi(x)-\nabla\Psi(z)\|_2\le L\|x-z\|_2$, 그리고 step size $0<\alpha<\frac{2}{L}$이다. 이때 iteration은

이다.

자료가 열거하는 properties는 cost monotonicity $\Psi(x^{(k+1)})\le\Psi(x^{(k)})$, minimizer까지 거리의 monotonicity $\|x^{(k+1)}-\widehat{x}\|_2\le\|x^{(k)}-\widehat{x}\|_2$, minimizer convergence다. $0<\alpha\le1/L$에서는

을 제시하고, 같은 bound가 $\frac1L<\alpha<\frac2L$에도 성립할 것이라는 conjecture를 적는다.

Convergence rate는 objective gap $\Psi(x^{(k)})\to\Psi(\widehat{x})$, gradient norm $\|\nabla\Psi(x^{(k)})\|\to0$, iterate error $\|x^{(k)}-\widehat{x}\|\to0$를 global/local하게 본다. fixed step α=1/L인 GD의 tight worst-case objective bound는

이고, Nesterov FGM은 $O(k^{-2})$ rate를 갖는다.

느린 example은 least-squares에서 $A=\begin{bmatrix}1&0\\0&2\end{bmatrix}$, $y=0$를 사용한다. optimal fixed step을 써도 길쭉한 level set 때문에 iteration이 zig-zag한다. 자료는 acceleration의 두 실무 방향으로 preconditioner와 line search를 제시한다.

강의 주석 — PDF p.5. O(1/k)와 O(1/k²) 비교, condition number가 큰 타원에서 zig-zag가 생긴다는 메모가 보인다. 판독이 확정되지 않는 작은 글씨는 추측해 문장으로 만들지 않았다.

#4.3 Preconditioned steepest descent(PSD)와 PGD

PSD는 negative preconditioned gradient $d^{(k)}=-P\nabla\Psi(x^{(k)})$, one-dimensional line search $\alpha^{(k)}=\operatorname*{arg\,min}_{\alpha}\Psi(x^{(k)}+\alpha d^{(k)})$, update

를 결합한다.

Quadratic case에는 analytic line search $\alpha^{(k)}=\operatorname*{arg\,min}_{\alpha}\frac12\|y-Ax^{(k)}-\alpha Ad^{(k)}\|_2^2$가 가능하다. $P\succ0$이면 strict decrease가 필요한 경우 $\Psi(x^{(k+1)})\le\Psi(x^{(k)})$를 얻지만, nonquadratic objective에서는 매 iteration의 line search 비용이 생긴다.

Exact line search의 first-order condition은

이므로 다음 gradient와 현재 search direction이 orthogonal하다. inexact line search라면 approximate orthogonality만 기대한다.

Fixed-step PGD는

다. $P=TT^{\mathsf T}$와 coordinate change $z=T^{-1}x$를 쓰면 원문 문제를

로 바꾼다.

강의 주석 — PDF p.6. line search 후 gradient와 search direction이 직교한다는 표시, FGM/OGM은 L을 알면 line search가 필요 없다는 메모가 보인다. 판독이 확정되지 않는 작은 글씨는 추측해 문장으로 만들지 않았다.

Chain rule을 적용한 transformed-coordinate GD는