Completeness contract
This article follows 19 of 19 pages of 5_Ch4-General-purpose gradient-based opt(1).pdf. Ledgers cover numbered and unnumbered displayed equations, meaningful inline mathematics, tables, figures, captions, multiple-choice questions, ??, blanks, footnotes, references, and legible handwriting. Source blanks and suspected errors are preserved; completed and corrected expressions receive separate statuses.

Keep three layers distinct.
Separate the 2025 PDF reconstruction, editorial and mathematical verification, and the research update dated August 18, 2026.

#Ledger status

• PDF: 19 of 19 pages
• PDF SHA-256: 23272c39a5ad9c0dddf24eb7d42fdebe8575344f74bac3de761b7844fd81e58c
• Total equation records: 211
• Source-derived equations: 188
• Displayed equations: 110; inline equations: 101
• Content records: 151
• Figures/tables: 10
• Handwritten annotations: 17
• Editorial completions/corrections: 23

#Reconstructing the PDF source

#4. General-purpose gradient-based optimization methods

Unconstrained optimization begins by minimizing cost function $\Psi:\mathbb{F}^{N}\to\mathbb{R}$:

Choose an initial estimate $x^{(0)}$, construct iterates $\{x^{(k)}\}_{k\ge 0}$, and seek $\|x^{(k)}-\widehat{x}\|\to 0\quad(k\to\infty)$ in a suitable norm.

The lecture uses $\mathbb{F}\in\{\mathbb{R},\mathbb{C}\}$ to cover real or complex applications. Its focus is smooth convex objectives with Lipschitz-continuous gradients, including least squares as a special case.

#Motivating application: edge-preserving image recovery

With measurement model $y=Ax+\varepsilon$, combine data fidelity and a convex smooth regularizer to solve:

The regularizer sums potentials over transform coefficients in form $R(x)=\sum_{j}\psi([Cx]_{j})$.

Lecture annotation — PDF p. 1. Brief notes connect contours, gradient directions, step sizes, and Lipschitz constants. Uncertain small handwriting is not expanded through guessing.

#4.1 Lipschitz continuity

A function $g:\mathbb{F}^{N}\to\mathbb{F}^{M}$ is Lipschitz continuous if some finite $L<\infty$ satisfies:

The smallest valid constant is the best Lipschitz constant. Unless stated otherwise, the lecture uses Euclidean norms.

Write the best constants for f and g as $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{??}}$

A true/false question asks whether products of Lipschitz functions are always Lipschitz on the full real line, leaving the answer blank.

A sufficient product condition and its proof are also left blank.

The next page asks whether boundedness is necessary: $f,g\text{must both be bounded?}\quad\boxed{\text{??}}$.

Lecture annotation — PDF p. 2. Handwritten additions indicate adding and subtracting terms before applying the triangle inequality, with boundedness marked. Uncertain small handwriting is not reconstructed speculatively.

#Smooth function: Lipschitz-continuous gradient

Here, smoothness means differentiability with gradient satisfying:

Complex derivatives require more care, so this definition is first made in real space.

For least-squares example $f(x)=\frac12\|Ax-y\|_2^2$, gradient $\nabla f(x)=A^{\mathsf T}(Ax-y)$ gives:

and hence:

For twice-differentiable functions, a Hessian spectral-norm bound

is sufficient for a Lipschitz gradient. The proof uses Taylor’s integral form

and the norm bound

together. The lecture explicitly states sufficiency rather than necessity.

Quadratic examples include $\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}$, and:

Lecture annotation — PDF p. 3. Notes trace least-squares gradients, Hessian spectral norms, and singular-value/eigenvalue relationships. Uncertain small handwriting is not reconstructed speculatively.

#Fair potential and edge-preserving regularization

The Fair potential is:

It satisfies:

,

It is approximately quadratic near zero and grows like |x| for large |x|. A nonnegative second derivative makes it convex.

The lecture asks whether the potential itself is Lipschitz continuous, leaving $\psi_\delta\text{ itself Lipschitz continuous?}\quad\boxed{\text{??}}$.

An exercise derives the regularizer gradient and Lipschitz constant by composition, beginning with:

and leaving $f(x)=Cx,\qquad g(u)=\dot\psi_{\cdot}(u),\qquad h(v)=C^{\mathsf T}v$ and

,

,

,

as blanks.

Lecture annotation — PDF p. 4. Notes connect the Fair potential’s quadratic regime with edge preservation and mark chain-rule order beside the regularizer exercise. Uncertain small writing is not reconstructed speculatively.

#4.2 Gradient descent for smooth convex functions

Assume 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$, and step size $0<\alpha<\frac{2}{L}$. The iteration is:

Listed properties include monotone cost $\Psi(x^{(k+1)})\le\Psi(x^{(k)})$, monotone distance to a minimizer $\|x^{(k+1)}-\widehat{x}\|_2\le\|x^{(k)}-\widehat{x}\|_2$, and convergence to a minimizer. For $0<\alpha\le1/L$, the lecture gives:

It conjectures that the same bound also holds for $\frac1L<\alpha<\frac2L$.

Convergence rates consider objective gap $\Psi(x^{(k)})\to\Psi(\widehat{x})$, gradient norm $\|\nabla\Psi(x^{(k)})\|\to0$, and iterate error $\|x^{(k)}-\widehat{x}\|\to0$, globally or locally. GD with fixed α=1/L has tight worst-case objective bound:

Nesterov FGM achieves rate $O(k^{-2})$.

The slow least-squares example uses $A=\begin{bmatrix}1&0\\0&2\end{bmatrix}$ and $y=0$. Even an optimal fixed step zigzags through elongated contours. The lecture proposes preconditioning and line search as practical acceleration routes.

Lecture annotation — PDF p. 5. Notes compare O(1/k) with O(1/k²) and link large condition numbers to zigzagging. Uncertain small writing is not reconstructed speculatively.

#4.3 Preconditioned steepest descent and PGD

PSD combines 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)})$, and update:

Quadratics admit analytical line search $\alpha^{(k)}=\operatorname*{arg\,min}_{\alpha}\frac12\|y-Ax^{(k)}-\alpha Ad^{(k)}\|_2^2$. Under $P\succ0$, strict decrease when needed gives $\Psi(x^{(k+1)})\le\Psi(x^{(k)})$, but nonquadratic objectives incur line-search costs each iteration.

The first-order condition for exact line search is:

Thus the next gradient is orthogonal to the current search direction. Inexact searches give only approximate orthogonality.

Fixed-step PGD uses:

With $P=TT^{\mathsf T}$ and coordinate change $z=T^{-1}x$, transform the original problem into:

Lecture annotation — PDF p. 6. Marks indicate post-search gradient/direction orthogonality and note that FGM/OGM need no line search when L is known. Uncertain small writing is not reconstructed speculatively.

The chain rule gives transformed-coordinate GD: