A finite positive-definite kernel flow converges for an attained convex cost

By [F1], $A$ has an orthonormal eigenbasis; self-adjointness and positive definiteness make each eigenvalue positive. Thus $A^{-1}$ exists, is self-adjoint and positive definite, and $\mathrm{\parallel }v{\mathrm{\parallel }}_{A^{-1}}^2:=⟨v,A^{-1}v⟩$ is a norm squared. Since $\mathrm{\nabla }C$ is locally Lipschitz, the vector field $-A\mathrm{\nabla }C$ is locally Lipschitz and [F3] gives a unique local solution.

For $0<s\le 1$, convexity gives $C(z+s(z_{\ast }-z))\le (1-s)C(z)+sC(z_{\ast })$. Subtract $C(z)$, divide by $s$, and let $s\downarrow 0$; differentiability and the definition of $\mathrm{\nabla }C$ give $⟨\mathrm{\nabla }C(z),z_{\ast }-z⟩\le C(z_{\ast })-C(z)$. Along any solution, expanding the squared inverse-metric norm to first order then gives $\frac{d}{dt}\mathrm{\parallel }z-z_{\ast }{\mathrm{\parallel }}_{A^{-1}}^2=-2⟨z-z_{\ast },\mathrm{\nabla }C(z)⟩\le -2(C(z)-C(z_{\ast }))\le 0.$ Hence the solution remains in the closed $A^{-1}$-metric ball centered at $z_{\ast }$ through $z_0$. In orthonormal coordinates its radius bounds the Euclidean norm because the smallest eigenvalue of $A^{-1}$ is positive, and continuity of that norm makes the ball closed. If $\dim V\ge 1$, [F4] makes it compact; if $\dim V=0$, it is a subset of the singleton $V=\{0\}$ and is compact.

The vector field is bounded and Lipschitz on a compact neighborhood of this ball. Picard–Lindelöf therefore supplies a uniform positive local existence time at every point of the ball. If the maximal forward solution had a finite endpoint, boundedness of the vector field would make $z(t)$ Cauchy as $t$ approached that endpoint; its limit lies in the ball, and the uniform local solution there extends the original solution, a contradiction. Thus the solution exists uniquely for all $t\ge 0$.

Integrating the inequality in step 2.1 over $[0,T]$ gives ${\int }_0^T(C(z(t))-C(z_{\ast }))dt\le \frac{1}{2}\mathrm{\parallel }{z}_0-z_{\ast }{\mathrm{\parallel }}_{A^{-1}}^2$. By [F5] and the flow equation, $\frac{d}{dt}C(z(t))=-⟨\mathrm{\nabla }C(z(t)),A\mathrm{\nabla }C(z(t))⟩\le 0$. The gap is therefore nonnegative, nonincreasing and integrable; it tends to zero.

The trajectory lies in a compact set, so it has a convergent subsequence $z(t_j)\to \bar{z}$ with $t_j\to \mathrm{\infty }$. Continuity of $C$ and step 4.1 give $C(\bar{z})=C(z_{\ast })$, so $\bar{z}$ is a global minimizer. Apply step 2.1 with $\bar{z}$ in place of $z_{\ast }$: the distance $\mathrm{\parallel }z(t)-\bar{z}{\mathrm{\parallel }}_{A^{-1}}$ is nonincreasing and has a subsequence tending to zero, hence tends to zero. Thus the full trajectory converges to $\bar{z}$.

For a finite data set, [F2] makes $K$ symmetric positive semidefinite; if it is positive definite, then $A=K\mathrm{/}N$ is self-adjoint positive definite because $N\ge 1$. The preceding argument applies.