Acknowledgements and further readings
Example from
: Implicit function differentiation of iterative implementationsChapter 11 of The Elements of Differentiable Programming book
See DiffOpt.jl for implicit differentiation of
optimization problems.
We need to solve the system $At_k = Bt_{k-1}$ once by forward tangent, so once by entry of $s_0$ in case of forward-mode AD. We may also pre-compute $A^{-1}B$ by solving one linear system by column of $B$. In both case, we need to solve several linear system with the same $A$ matrix.
For arbitrary $r, t$, we have
$$\begin{align} \langle (A^{-1})^*r, t\rangle &= \langle r, A^{-1} t\rangle\\ &= \langle A^*(A^*)^{-1} r, A^{-1} t \rangle\\ &= \langle (A^*)^{-1} r, AA^{-1} t\rangle\\ &= \langle (A^*)^{-1} r, t\rangle. \end{align}$$
Since $r, t$ are arbitrary, we have $(A^{-1})^* = (A^*)^{-1}$.
In a sense, the implicit function theorem can be thought as the mother theorem, as it can be used to prove envelope theorems, the adjoint state method and the inverse function theorem. Section 11.6 of The Elements of Differentiable Programming book
Assume
$f : \mathcal{W} \to \mathcal{W}$ is $C^2$
$\partial f(w_0)$ is invertible
Then
$f$ is bijective from a neighborhood of $w_0$ to a neighborhood of $f(w_0)$
For $\omega$ in a neighborhood of $f(w_0)$, $f^{-1}$ is $C^2$ and $\partial f^{-1}(\omega) = (\partial f(f^{-1}(\omega)))^{-1}$
If the matrix is positive semidefinite, we can use the Conjugate Gradient method. Otherwise, GMRES or BiCGSTAB are options.
To illustrate consider this Jax example rewriting $x^2 = a$ into $2x^2 = x^2 + a$ or $x = (x + a/x)/2$
Example from 
: Implicit function differentiation of iterative implementations
Chapter 11 of The Elements of Differentiable Programming book
See DiffOpt.jl for implicit differentiation of 
optimization problems.
Consider the primal-dual pair of programs
$$\begin{align} \min & \,\, c^\top x & \max & \,\, b^\top y\\ Ax & = b & A^\top y & \le c\\ x & \ge 0 \end{align}$$
The Lagrangian function is
$$\mathcal{L}(x, y) = c^\top x - y^\top (Ax - b) = y^\top b - (A^\top y - c)^\top x$$
The KKT condition give
$$\begin{align} \frac{\partial \mathcal{L}}{\partial y} & = Ax - b = 0 & \Leftrightarrow \qquad Ax & = b\\ (A^\top y - c) & \perp x \ge 0 & \Leftrightarrow \qquad \text{Diag}(x)(A^\top y - c) & = 0 \end{align}$$
As $L$ and $U$ are triangular, solving the linear systems $LUx = b$ can now be done by solving two simple linear systems (and permutation in case of pivoting)
$Lc = b$
$Ux = c$
Assume
$F: \mathcal{W} \times \Lambda \to \mathcal{W}$
$(w_0, \lambda_0)$ such that $F(w_0, \lambda_0) = 0$ and $\partial_1 F(w_0, \lambda_0)$ is invertible
$F(w, \lambda)$ is $C^2$ in a neighborhood $\mathcal{U}$ of $(w_0, \lambda_0)$
Then there exists a neighborhood $\mathcal{V} \subseteq \mathcal{U}$ where exists $w^\star(\lambda)$ such that
$$\begin{align} w^\star(\lambda_0) & = w_0\\ F(w^\star(\lambda), \lambda) & = 0, \qquad\qquad\qquad \forall(w^\star(\lambda),\lambda)\in \mathcal{V}\\ \partial w^\star(\lambda) & = -\partial_1 F(w^\star(\lambda), \lambda)^{-1}\partial_2 F(w^\star(\lambda), \lambda) \end{align}$$
Consider a program that numerically converge to solutions:
function f(x)
while abs(error) > tol
y += # Make some step in the right direction
error = # update error
end
return y
end
mimetext/htmlrootassigneelast_run_timestampAڸتBenoît Legat
mimetext/htmlrootassigneelast_run_timestampAڸإs@persist_js_state·has_pluto_hook_features$e1b83a0b-2e8f-4db6-ac2f-7a7c2ccce965running§runtime ødepends_on_skipped_cellsµpublished_object_keyserrored§cell_id$e1b83a0b-2e8f-4db6-ac2f-7a7c2ccce965depends_on_disabled_cells¦queued¤logsoutputbodyqx ? Forward, reverse, something else ?We could throw dual numbers at it and it would work, but f would be twice slower with dual numbers and we would need to do it as many times as the dimension of x.
We could also create the expression graph to run reverse diff but the graph may be quite large as well.
Some programs may be external libraries written in Fortran or C so we can't easily run AD through it.
Instead, we could run the iteration through the end and once we get the pair x, y, we can see if there isn't a better way to find the derivative without rerunning the numerical iterations. This will be implicit differentiation.
Classical Gaussian elimination finds the solution for one vector only, even though the same row operations would be applied for different vectors.
The pullback operation is the adjoint of the pushforward operator:
$$\langle r, A^{-1} B t\rangle = \langle (A^{-1})^* r, B t\rangle = \langle (A^*)^{-1} r, B t\rangle = \langle B^*(A^*)^{-1} r , t\rangle$$
So the pullback operator maps $r$ to $B^*(A^*)^{-1} r$.
This means that it first solves the linear system $A^*v = r$ (possibly in a matrix-free way) and then returns $B^*v$.
How can we integrate implicit function in a chain of functions ? Say, $s_{k-1} = \lambda$ and $f_k(\lambda) = w^\star(\lambda)$ such that $F(w^\star(\lambda), \lambda) = 0$.
Assume
$F: \mathbb{R} \times \mathbb{R} \to \mathbb{R}$
$(w_0, \lambda_0)$ such that $F(w_0, \lambda_0) = 0$ and $\partial_1 F(w_0, \lambda_0) \neq 0$
$F(w, \lambda)$ is $C^2$ in a neighborhood $\mathcal{U}$ of $(w_0, \lambda_0)$
Then there exists a neighborhood $\mathcal{V} \subseteq \mathcal{U}$ where exists $w^\star(\lambda)$ such that
$$\begin{align} w^\star(\lambda_0) & = w_0\\ F(w^\star(\lambda), \lambda) & = 0, \qquad\qquad\qquad \forall(w^\star(\lambda),\lambda)\in \mathcal{V}\\ \partial w^\star(\lambda) & = -\frac{\partial_2 F(w^\star(\lambda), \lambda)}{\partial_1 F(w^\star(\lambda), \lambda)} \end{align}$$
As $\mathcal{X}$ and $\mathcal{Y}$ have the same dimension, this is equivalent to the $\mathrm{Ker}(A^*) = \{0\}$. Consider an arbitrary $y \in \text{Ker}(A^*)$. Since $A^*(y) = 0$, for all $x \in \mathcal{X}$, we have
$$\begin{align} \langle x, A^*(y) \rangle & = 0\\ \langle A(x), y \rangle & = 0 \end{align}$$
As this is true for all $x$, this is true in particular for $x = A^{-1}(y)$ hence we have $\langle y, y \rangle$ hence $y = 0$.
Implicit relation between $x$ and $y$:
$$x^2 + y^2 = 1$$
Two possible explicit functions:
$$\begin{align} y^+(x) & = \sqrt{1 - x^2}\\ y^-(x) & = -\sqrt{1 - x^2} \end{align}$$
Let $F(y, x) = x^2 + y^2 - 1$. Given an initial point $(x_0, y_0)$ with $x_0^2 + y_0^2 = 1$,
if $y_0 > 0$ then IFT holds and $y^\star(x) = y^+(x)$,
if $y_0 < 0$ then IFT holds and $y^\star(x) = y^-(x)$,
if $y_0 = 0$ then $\partial_1 F(y_0, x_0) = 2y_0 = 0$ so IFT does not hold.
text/htmlmime,application/vnd.pluto.reactdomelement+objectrootassigneelast_run_timestampAڸثY{gpersist_js_state·has_pluto_hook_features$f369cf71-6eea-4aaa-b75d-79c2629ce88erunning§runtime 5Ÿdepends_on_skipped_cellsµpublished_object_keyserrored§cell_id$f369cf71-6eea-4aaa-b75d-79c2629ce88edepends_on_disabled_cells¦queued¤logsoutputbody-Consider a linear map $A : \mathcal{X} \to \mathcal{Y}$ between linear spaces of the same dimension. Assume $A$ is invertible, what is the adjoint of $A^{-1}$ ?
Let $A = -\partial_1 F(w^\star(\lambda), \lambda)$ and $B = \partial_2 F(w^\star(\lambda), \lambda)$. Assuming the condition of the IFT holds, we have
$$A \partial w^\star(\lambda)/\partial s_0 = B \partial \lambda/\partial s_0$$
Given a forward tangent $t_{k-1} = \partial \lambda / \partial s_0$, the forward tangent $t_{k} = \partial w^\star(\lambda) / \partial s_0$ can be obtained by solving the linear system:
$$\begin{align} A t_k & = B t_{k-1}\\ t_k & = A^{-1} B t_{k-1} \end{align}$$
The system of equation to consider for the IFT is therefore
$$F((x, y), (A, b, c)) = (Ax - b, \text{Diag}(x)(A^\top y - c))$$
We have
$$\begin{align} \partial_1 F & = \begin{bmatrix} A & 0\\ \text{Diag}(A^\top y - c) & \text{Diag}(x) A^\top \end{bmatrix} \end{align}$$
See OptNet: Differentiable optimization as a layer in neural networks for a generalization to quadratic objective.
LU decomposition remember the row operations to make $U$ triangular in the $L$ matrix.
Define $f(\lambda, w) = (\lambda, F(w, \lambda))$. The Jacobian is
$$\partial f(\lambda, w) = \begin{bmatrix} I & 0\\ \partial_2 F(w, \lambda) & \partial_1 F(w, \lambda) \end{bmatrix}$$
By assumption, $\partial_1 F(w, \lambda)$ is invertible so $\det(\partial f(\lambda, w)) = \det(I)\det(\partial_1 F(w, \lambda)) \neq 0$. By the inverse function theorem, the inverse of $f$ around $f(\lambda_0, w_0) = (\lambda_0, 0)$ is $C^2$. Let $w^\star(\lambda)$ be the second component of $f^{-1}(\lambda, 0)$: $(\lambda, w^\star(\lambda)) = f^{-1}(\lambda, 0)$. The Jacobian $\partial w^\star(\lambda)$ is the derivative of the second component of $f^{-1}(\lambda, 0)$ with respect to its first input so it is the block 21 in the Jacobian
$$\partial f^{-1}(\lambda, 0) = \begin{bmatrix} \sim & \sim\\ \partial w^\star(\lambda) & \sim \end{bmatrix}$$
By the inverse function theorem
$$\partial f^{-1}(\lambda, 0) = (\partial f(\lambda, w))^{-1} = \begin{bmatrix} I & 0\\ \partial_2 F(w, \lambda) & \partial_1 F(w, \lambda) \end{bmatrix}^{-1}$$
We can then use the following result:
Schur complement: If $A$ is an invertible matrix then for any matrices $M, B, C, D$ of compatible dimensions:
$$M^{-1} = \begin{bmatrix} A & B\\ C & D \end{bmatrix}^{-1} = \begin{bmatrix} \sim & \sim\\ -(M/A)^{-1}CA^{-1} & \sim \end{bmatrix}$$
where the Schur complement of the block $A$, denoted by $M/A$, is $M/A=D - CA^{-1}B$.
In our case the Schur complement of the block $I$ is $\partial f(\lambda, w)/I = \partial_1 F(w, \lambda)$, this means that
$$\partial w^\star(\lambda) = -\partial_1 F(w, \lambda)^{-1}\partial_2 F(w, \lambda).$$
IFT...
The proof of bijectivity and that $f$ is $C^2$ in the neighborhood of $f(w_0)$ are in Section 11.5.3 of The Elements of Differentiable Programming book. The formula for $\partial f^{-1}(\omega)$ is a direct consequence of the chain rule:
$$\begin{align} f \circ f^{-1}(\omega) & = \omega\\ \partial f(f^{-1}(\omega)) \partial f^{-1}(\omega) & = I. \end{align}$$
` if `question.content[]` is `Markdown.Paragraph` # This will print the question on a new line and we don't want that: h = HTML(_inline_html(question.content[])) return qa(h, answer) end end$c9603b16-113b-4e05-8517-d814b0879ab8metadatadisabled©show_logsîskip_as_script§cell_id$c9603b16-113b-4e05-8517-d814b0879ab8code_foldedäcodeBmd""" # Implicit function theorem > *In a sense, the implicit function theorem can be thought as the mother theorem, as it can be used to prove envelope theorems, the adjoint state method and the inverse function theorem.* Section 11.6 of [The Elements of Differentiable Programming book](https://diffprog.github.io/) """$c3b59d62-144e-4541-9007-19187f2fea1cmetadatadisabled©show_logsîskip_as_script§cell_id$c3b59d62-144e-4541-9007-19187f2fea1ccode_folded¤coderref([A b])$b23a4c1d-cf35-42e6-b286-7fbcdddfd424metadatadisabled©show_logsîskip_as_script§cell_id$b23a4c1d-cf35-42e6-b286-7fbcdddfd424code_foldedäcodelmd""" ## Inverse function theorem Assume * ``f : \mathcal{W} \to \mathcal{W}`` is ``C^2`` * ``\partial f(w_0)`` is **invertible** Then * ``f`` is bijective from a neighborhood of ``w_0`` to a neighborhood of ``f(w_0)`` * For ``\omega`` in a neighborhood of ``f(w_0)``, ``f^{-1}`` is ``C^2`` and ``\partial f^{-1}(\omega) = (\partial f(f^{-1}(\omega)))^{-1}`` """$cbfc0129-9361-4edb-a467-1456a1f3aeaemetadatadisabled©show_logsîskip_as_script§cell_id$cbfc0129-9361-4edb-a467-1456a1f3aeaecode_foldedäcodesbegin struct Path path::String end function imgpath(path::Path) file = path.path if !('.' in file) file = file * ".png" end return joinpath(joinpath(@__DIR__, "images", file)) end function img(path::Path, args...; kws...) return PlutoUI.LocalResource(imgpath(path), args...) end struct URL url::String end function save_image(url::URL, html_attributes...; name = split(url.url, '/')[end], kws...) path = joinpath("cache", name) return PlutoTeachingTools.RobustLocalResource(url.url, path, html_attributes...), path end function img(url::URL, args...; kws...) r, _ = save_image(url, args...; kws...) return @htl("$r") end function img(file::String, args...; kws...) if startswith(file, "http") img(URL(file), args...; kws...) else img(Path(file), args...; kws...) end end end$fa019742-c473-4f1d-86ce-a795edbd1f92metadatadisabled©show_logsîskip_as_script§cell_id$fa019742-c473-4f1d-86ce-a795edbd1f92code_folded¤codeA = [1 2; 3 4]$528326dd-1344-4baa-9edd-5b09f63669ddmetadatadisabled©show_logsîskip_as_script§cell_id$528326dd-1344-4baa-9edd-5b09f63669ddcode_foldedäcodeqa(md"Can we also solve the linear system with only access to the matrix-vector product of the linear map ``\partial_1 F(w^\star(\lambda), \lambda)`` ? (aka matrix-free inversion)", md""" If the matrix is positive semidefinite, we can use the [Conjugate Gradient method](https://en.wikipedia.org/wiki/Conjugate_gradient_method). Otherwise, [GMRES](https://en.wikipedia.org/wiki/Generalized_minimal_residual_method) or [BiCGSTAB](https://en.wikipedia.org/wiki/Biconjugate_gradient_stabilized_method) are options. """)$cb886515-1635-43d7-82fd-a2604d1e3ad6metadatadisabled©show_logsîskip_as_script§cell_id$cb886515-1635-43d7-82fd-a2604d1e3ad6code_folded¤code1FiniteDifferences.central_fdm(5, 1)(my_sqrt, 2.0)$d907c5d7-f517-467a-a840-f94868ad7680metadatadisabled©show_logsîskip_as_script§cell_id$d907c5d7-f517-467a-a840-f94868ad7680code_foldedäcodemd""" ## Square root example To illustrate consider [this Jax example](https://docs.jax.dev/en/latest/advanced-autodiff.html#example-implicit-function-differentiation-of-iterative-implementations) rewriting ``x^2 = a`` into ``2x^2 = x^2 + a`` or ``x = (x + a/x)/2`` """$9d883700-0959-4ccd-be50-9ee316a6077emetadatadisabled©show_logsîskip_as_script§cell_id$9d883700-0959-4ccd-be50-9ee316a6077ecode_foldedäcode}md"""## Acknowledgements and further readings * Example from $(img("https://upload.wikimedia.org/wikipedia/commons/8/86/Google_JAX_logo.svg", :height => 16)) : [Implicit function differentiation of iterative implementations](https://docs.jax.dev/en/latest/advanced-autodiff.html#example-implicit-function-differentiation-of-iterative-implementations) * Chapter 11 of [The Elements of Differentiable Programming book](https://diffprog.github.io/) * See [DiffOpt.jl](https://github.com/jump-dev/DiffOpt.jl) for implicit differentiation of $(img("https://jump.dev/assets/jump-logo-with-text.svg", :height => 20)) optimization problems. """$23049939-1b3a-4328-b159-99c3f1470e39metadatadisabled©show_logsîskip_as_script§cell_id$23049939-1b3a-4328-b159-99c3f1470e39code_foldedäcodemd"## AD through fixed point"$5c39f536-346c-48bd-a3c7-acaefb849b9fmetadatadisabled©show_logsîskip_as_script§cell_id$5c39f536-346c-48bd-a3c7-acaefb849b9fcode_folded¤codejfunction fixed_point(f, x) fx = f(x) while abs(x - fx) > 1e-6 x = fx fx = f(x) end return x end$17f3594f-b568-416f-9a19-38bfd4d99dd0metadatadisabled©show_logsîskip_as_script§cell_id$17f3594f-b568-416f-9a19-38bfd4d99dd0code_foldedäcodeF = lu(A)$10ca4307-929a-4e5f-942b-5d6c0e28e2bemetadatadisabled©show_logsîskip_as_script§cell_id$10ca4307-929a-4e5f-942b-5d6c0e28e2becode_foldedäcode@md""" # Sensitivity of a linear program Consider the primal-dual pair of programs ```math \begin{align} \min & \,\, c^\top x & \max & \,\, b^\top y\\ Ax & = b & A^\top y & \le c\\ x & \ge 0 \end{align} ``` The Lagrangian function is ```math \mathcal{L}(x, y) = c^\top x - y^\top (Ax - b) = y^\top b - (A^\top y - c)^\top x ``` The KKT condition give ```math \begin{align} \frac{\partial \mathcal{L}}{\partial y} & = Ax - b = 0 & \Leftrightarrow \qquad Ax & = b\\ (A^\top y - c) & \perp x \ge 0 & \Leftrightarrow \qquad \text{Diag}(x)(A^\top y - c) & = 0 \end{align} ``` """$6f8714a1-1372-42f4-9b51-da93ef2ed4c9metadatadisabled©show_logsîskip_as_script§cell_id$6f8714a1-1372-42f4-9b51-da93ef2ed4c9code_foldedäcodemd"""As ``L`` and ``U`` are triangular, solving the linear systems ``LUx = b`` can now be done by solving two simple linear systems (and permutation in case of pivoting) 1. ``Lc = b`` 2. ``Ux = c`` """$c1efb93f-efd8-487a-94d2-aa7ecedb61b8metadatadisabled©show_logsîskip_as_script§cell_id$c1efb93f-efd8-487a-94d2-aa7ecedb61b8code_foldedäcodeift( "multivariate", md"``F: \mathcal{W} \times \Lambda \to \mathcal{W}``", md"``\partial_1 F(w_0, \lambda_0)`` is invertible", md""" ```math \begin{align} w^\star(\lambda_0) & = w_0\\ F(w^\star(\lambda), \lambda) & = 0, \qquad\qquad\qquad \forall(w^\star(\lambda),\lambda)\in \mathcal{V}\\ \partial w^\star(\lambda) & = -\partial_1 F(w^\star(\lambda), \lambda)^{-1}\partial_2 F(w^\star(\lambda), \lambda) \end{align} ``` """, )$64250438-9ba6-44f7-b4a0-fcd5d72f05e5metadatadisabled©show_logsîskip_as_script§cell_id$64250438-9ba6-44f7-b4a0-fcd5d72f05e5code_folded¤codeusing LinearAlgebra, RowEchelon$f1ba3d3c-d0a5-4290-ab73-9ce34bd5e5f6metadatadisabled©show_logsîskip_as_script§cell_id$f1ba3d3c-d0a5-4290-ab73-9ce34bd5e5f6code_folded¤codeOusing PlutoUI, PlutoUI.ExperimentalLayout, HypertextLiteral, PlutoTeachingTools$abee47e4-1b75-4466-908a-e14113b181abmetadatadisabled©show_logsîskip_as_script§cell_id$abee47e4-1b75-4466-908a-e14113b181abcode_folded¤codemy_sqrt(2)$d6797e7b-fa78-4366-b88f-9925f72a5d0fmetadatadisabled©show_logsîskip_as_script§cell_id$d6797e7b-fa78-4366-b88f-9925f72a5d0fcode_foldedäcode md""" # Differentiating numerical procedures Consider a program that numerically converge to solutions: ```julia function f(x) while abs(error) > tol y += # Make some step in the right direction error = # update error end return y end ``` """$b6f76d2d-3389-4dec-9aef-b7feeb7e0793metadatadisabled©show_logsîskip_as_script§cell_id$b6f76d2d-3389-4dec-9aef-b7feeb7e0793code_foldedäcode img("Blondel_Rouvet_Figure_8_3")$40baa108-eb68-433f-9917-ac334334f198metadatadisabled©show_logsîskip_as_script§cell_id$40baa108-eb68-433f-9917-ac334334f198code_foldedäcode@htl("""
Implicit Differentiation
Benoît Legat
$(PlutoTeachingTools.ChooseDisplayMode()) $(PlutoUI.TableOfContents(depth=1)) """)$e1b83a0b-2e8f-4db6-ac2f-7a7c2ccce965metadatadisabled©show_logsîskip_as_script§cell_id$e1b83a0b-2e8f-4db6-ac2f-7a7c2ccce965code_foldedäcodeqa(md"How can we differentiate with respect to `x` ? Forward, reverse, something else ?", md""" * We could throw dual numbers at it and it would work, but `f` would be twice slower with dual numbers and we would need to do it as many times as the dimension of `x`. * We could also create the expression graph to run reverse diff but the graph may be quite large as well. * Some programs may be external libraries written in Fortran or C so we can't easily run AD through it. * Instead, we could run the iteration through the end and once we get the pair `x, y`, we can see if there isn't a better way to find the derivative without rerunning the numerical iterations. This will be implicit differentiation. """)$1de5d608-dc91-4f4a-995b-3dcfad38b81cmetadatadisabled©show_logsîskip_as_script§cell_id$1de5d608-dc91-4f4a-995b-3dcfad38b81ccode_foldedäcodeٖmd"Classical Gaussian elimination finds the solution for one vector only, even though the same row operations would be applied for different vectors."$66a8b541-b06f-403a-a45d-23461a2c539bmetadatadisabled©show_logsîskip_as_script§cell_id$66a8b541-b06f-403a-a45d-23461a2c539bcode_folded¤code/import ForwardDiff, FiniteDifferences, Mooncake$08c4ac83-4361-41d5-b036-789c2475ff8emetadatadisabled©show_logsîskip_as_script§cell_id$08c4ac83-4361-41d5-b036-789c2475ff8ecode_folded¤code.DI.derivative(my_sqrt, DI.AutoMooncake(), 2.0)$ea41e038-21d8-4321-bc17-25eab0a8cbb2metadatadisabled©show_logsîskip_as_script§cell_id$ea41e038-21d8-4321-bc17-25eab0a8cbb2code_foldedäcodemd""" ## Pullback operator (VJP) The pullback operation is the adjoint of the pushforward operator: ```math \langle r, A^{-1} B t\rangle = \langle (A^{-1})^* r, B t\rangle = \langle (A^*)^{-1} r, B t\rangle = \langle B^*(A^*)^{-1} r , t\rangle ``` So the pullback operator maps ``r`` to ``B^*(A^*)^{-1} r``. This means that it first solves the linear system ``A^*v = r`` (possibly in a matrix-free way) and then returns ``B^*v``. """$bb4e1c20-1d24-494a-82ae-433e8ba56110metadatadisabled©show_logsîskip_as_script§cell_id$bb4e1c20-1d24-494a-82ae-433e8ba56110code_foldedäcodemd""" # Implicit VJP and JVP How can we integrate implicit function in a chain of functions ? Say, ``s_{k-1} = \lambda`` and ``f_k(\lambda) = w^\star(\lambda)`` such that ``F(w^\star(\lambda), \lambda) = 0``. """$2b30ae9e-e537-4ad1-a25e-570709c7d517metadatadisabled©show_logsîskip_as_script§cell_id$2b30ae9e-e537-4ad1-a25e-570709c7d517code_foldedäcodeift( "univariate", md"``F: \mathbb{R} \times \mathbb{R} \to \mathbb{R}``", md"``\partial_1 F(w_0, \lambda_0) \neq 0``", md""" ```math \begin{align} w^\star(\lambda_0) & = w_0\\ F(w^\star(\lambda), \lambda) & = 0, \qquad\qquad\qquad \forall(w^\star(\lambda),\lambda)\in \mathcal{V}\\ \partial w^\star(\lambda) & = -\frac{\partial_2 F(w^\star(\lambda), \lambda)}{\partial_1 F(w^\star(\lambda), \lambda)} \end{align} ``` """, )$30afb6e9-1ce0-4004-807b-dca57b789573metadatadisabled©show_logsîskip_as_script§cell_id$30afb6e9-1ce0-4004-807b-dca57b789573code_foldedäcodeqa(md"Is the adjoint ``A^*`` always invertible ?", md""" As ``\mathcal{X}`` and ``\mathcal{Y}`` have the same dimension, this is equivalent to the ``\mathrm{Ker}(A^*) = \{0\}``. Consider an arbitrary ``y \in \text{Ker}(A^*)``. Since ``A^*(y) = 0``, for all ``x \in \mathcal{X}``, we have ```math \begin{align} \langle x, A^*(y) \rangle & = 0\\ \langle A(x), y \rangle & = 0 \end{align} ``` As this is true for all ``x``, this is true in particular for ``x = A^{-1}(y)`` hence we have ``\langle y, y \rangle`` hence ``y = 0``. """)$d701392f-0b25-4c27-989a-a61c23c41d9cmetadatadisabled©show_logsîskip_as_script§cell_id$d701392f-0b25-4c27-989a-a61c23c41d9ccode_foldedäcodeHhbox([ md""" Implicit relation between ``x`` and ``y``: ```math x^2 + y^2 = 1 ``` Two possible explicit functions: ```math \begin{align} y^+(x) & = \sqrt{1 - x^2}\\ y^-(x) & = -\sqrt{1 - x^2} \end{align} ``` $circle_qa """, Div(html" ", style = Dict("flex-grow" => "1")), img("Blondel_Rouvet_Figure_11_3", :height => 300), ])$f369cf71-6eea-4aaa-b75d-79c2629ce88emetadatadisabled©show_logsîskip_as_script§cell_id$f369cf71-6eea-4aaa-b75d-79c2629ce88ecode_foldedäcodeٰmd""" Consider a linear map ``A : \mathcal{X} \to \mathcal{Y}`` between linear spaces of the same dimension. Assume ``A`` is invertible, what is the adjoint of ``A^{-1}`` ? """$0867ec30-4fd7-4338-9256-4a84215ad5aametadatadisabled©show_logsîskip_as_script§cell_id$0867ec30-4fd7-4338-9256-4a84215ad5aacode_folded¤code$ForwardDiff.derivative(my_sqrt, 2.0)$0fc437e3-37cc-4905-8bf9-3e8b9155d6e8metadatadisabled©show_logsîskip_as_script§cell_id$0fc437e3-37cc-4905-8bf9-3e8b9155d6e8code_foldedäcode-md""" ## Pushforward operator (JVP) Let ``A = -\partial_1 F(w^\star(\lambda), \lambda)`` and ``B = \partial_2 F(w^\star(\lambda), \lambda)``. Assuming the condition of the IFT holds, we have ```math A \partial w^\star(\lambda)/\partial s_0 = B \partial \lambda/\partial s_0 ``` Given a forward tangent ``t_{k-1} = \partial \lambda / \partial s_0``, the forward tangent ``t_{k} = \partial w^\star(\lambda) / \partial s_0`` can be obtained by solving the linear system: ```math \begin{align} A t_k & = B t_{k-1}\\ t_k & = A^{-1} B t_{k-1} \end{align} ``` """$6f4e1705-22f2-4be6-9f93-cbaabf809e84metadatadisabled©show_logsîskip_as_script§cell_id$6f4e1705-22f2-4be6-9f93-cbaabf809e84code_foldedäcodemd""" ## IFT for linear programs The system of equation to consider for the IFT is therefore ```math F((x, y), (A, b, c)) = (Ax - b, \text{Diag}(x)(A^\top y - c)) ``` We have ```math \begin{align} \partial_1 F & = \begin{bmatrix} A & 0\\ \text{Diag}(A^\top y - c) & \text{Diag}(x) A^\top \end{bmatrix} \end{align} ``` See [OptNet: Differentiable optimization as a layer in neural networks](https://dl.acm.org/doi/abs/10.5555/3305381.3305396) for a generalization to quadratic objective. """$64c4e42c-e444-44f1-8318-befed7d11bb5metadatadisabled©show_logsîskip_as_script§cell_id$64c4e42c-e444-44f1-8318-befed7d11bb5code_foldedäcodeْmd""" ## Solution: precompute the LU decomposition LU decomposition remember the row operations to make ``U`` triangular in the ``L`` matrix. """$b19451b4-2a9e-4c25-888e-d72a13eb7589metadatadisabled©show_logsîskip_as_script§cell_id$b19451b4-2a9e-4c25-888e-d72a13eb7589code_foldedäcode$md"## Interlude: Adjoint of inverse"$d0c4b33b-63e2-49dd-aff2-d9bd1bbb4661metadatadisabled©show_logsîskip_as_script§cell_id$d0c4b33b-63e2-49dd-aff2-d9bd1bbb4661code_folded¤codeb = [5, 6]$0b091706-da13-41f8-9852-4fa685a0fa95metadatadisabled©show_logsîskip_as_script§cell_id$0b091706-da13-41f8-9852-4fa685a0fa95code_foldedäcodemd"""## Example"""$114b2603-81da-4a5c-baa1-4d95f456aeb3metadatadisabled©show_logsîskip_as_script§cell_id$114b2603-81da-4a5c-baa1-4d95f456aeb3code_foldedäcodefunction ift(case, F_def, ift_inv, ift_eq) return md""" ## Implicit function theorem ($case case) Assume * $F_def * ``(w_0, \lambda_0)`` such that ``F(w_0, \lambda_0) = 0`` and $(ift_inv.content[].content) * ``F(w, \lambda)`` is ``C^2`` in a neighborhood ``\mathcal{U}`` of ``(w_0, \lambda_0)`` Then there exists a neighborhood ``\mathcal{V} \subseteq \mathcal{U}`` where exists ``w^\star(\lambda)`` such that $ift_eq """ end;$f22bfdc8-c25d-4844-98e3-08d05533ba56metadatadisabled©show_logsîskip_as_script§cell_id$f22bfdc8-c25d-4844-98e3-08d05533ba56code_foldedäcode qa(md"**Proof**", md""" Define ``f(\lambda, w) = (\lambda, F(w, \lambda))``. The Jacobian is ```math \partial f(\lambda, w) = \begin{bmatrix} I & 0\\ \partial_2 F(w, \lambda) & \partial_1 F(w, \lambda) \end{bmatrix} ``` By assumption, ``\partial_1 F(w, \lambda)`` is invertible so ``\det(\partial f(\lambda, w)) = \det(I)\det(\partial_1 F(w, \lambda)) \neq 0``. By the inverse function theorem, the inverse of ``f`` around ``f(\lambda_0, w_0) = (\lambda_0, 0)`` is ``C^2``. Let ``w^\star(\lambda)`` be the second component of ``f^{-1}(\lambda, 0)``: ``(\lambda, w^\star(\lambda)) = f^{-1}(\lambda, 0)``. The Jacobian ``\partial w^\star(\lambda)`` is the derivative of the second component of ``f^{-1}(\lambda, 0)`` with respect to its first input so it is the block 21 in the Jacobian ```math \partial f^{-1}(\lambda, 0) = \begin{bmatrix} \sim & \sim\\ \partial w^\star(\lambda) & \sim \end{bmatrix} ``` By the inverse function theorem ```math \partial f^{-1}(\lambda, 0) = (\partial f(\lambda, w))^{-1} = \begin{bmatrix} I & 0\\ \partial_2 F(w, \lambda) & \partial_1 F(w, \lambda) \end{bmatrix}^{-1} ``` We can then use the following result: > [**Schur complement**](https://en.wikipedia.org/wiki/Schur_complement): If ``A`` is an invertible matrix then for any matrices ``M, B, C, D`` of compatible dimensions: > ```math > M^{-1} = > \begin{bmatrix} > A & B\\ > C & D > \end{bmatrix}^{-1} = \begin{bmatrix} > \sim & \sim\\ > -(M/A)^{-1}CA^{-1} & \sim > \end{bmatrix} > ``` > where the *Schur complement* of the block ``A``, denoted by ``M/A``, is ``M/A=D - CA^{-1}B``. In our case the Schur complement of the block ``I`` is ``\partial f(\lambda, w)/I = \partial_1 F(w, \lambda)``, this means that ```math \partial w^\star(\lambda) = -\partial_1 F(w, \lambda)^{-1}\partial_2 F(w, \lambda). ``` """)$383b3a50-ef75-4ccd-a6ea-1ddb87d6e9d2metadatadisabled©show_logsîskip_as_script§cell_id$383b3a50-ef75-4ccd-a6ea-1ddb87d6e9d2code_foldedäcodevqa(md"Can't we do something simpler using the solution of the fixed point and the fixed point equation ?", md"IFT...")$f1f1a354-cecc-4fb2-8d1e-096f51e4cf88metadatadisabled©show_logsîskip_as_script§cell_id$f1f1a354-cecc-4fb2-8d1e-096f51e4cf88code_foldedäcodeqa(md"**Proof sketch**", md""" The proof of bijectivity and that ``f`` is ``C^2`` in the neighborhood of ``f(w_0)`` are in Section 11.5.3 of [The Elements of Differentiable Programming book](https://diffprog.github.io/). The formula for ``\partial f^{-1}(\omega)`` is a direct consequence of the chain rule: ```math \begin{align} f \circ f^{-1}(\omega) & = \omega\\ \partial f(f^{-1}(\omega)) \partial f^{-1}(\omega) & = I. \end{align} ``` """)$878bec4d-9d8a-4e92-9817-ddcd95bd8d35metadatadisabled©show_logsîskip_as_script§cell_id$878bec4d-9d8a-4e92-9817-ddcd95bd8d35code_folded¤code%import DifferentiationInterface as DI$0fc99cae-bfe4-4517-a578-453cab15d977metadatadisabled©show_logsîskip_as_script§cell_id$0fc99cae-bfe4-4517-a578-453cab15d977code_foldedäcodecircle_qa = qa(md"Does that contradict the Implicit Function Theorem (IFT) ?", md""" Let ``F(y, x) = x^2 + y^2 - 1``. Given an initial point ``(x_0, y_0)`` with ``x_0^2 + y_0^2 = 1``, * if ``y_0 > 0`` then IFT holds and ``y^\star(x) = y^+(x)``, * if ``y_0 < 0`` then IFT holds and ``y^\star(x) = y^-(x)``, * if ``y_0 = 0`` then ``\partial_1 F(y_0, x_0) = 2y_0 = 0`` so IFT does not hold. """);last_hot_reload_time cell_dependencies 1$e9fd46e4-78ce-4cba-b20f-1c997c80e842precedence_heuristic cell_id$e9fd46e4-78ce-4cba-b20f-1c997c80e842downstream_cells_mapupstream_cells_map@md_strgetindex$877c563a-2ce3-4f97-9746-7d8329c0178aprecedence_heuristic cell_id$877c563a-2ce3-4f97-9746-7d8329c0178adownstream_cells_mapupstream_cells_mapqa$81deb227-a822-4857-a584-a51cc8ff51f4@md_strgetindex$b16f6225-1949-4b6d-a4b0-c5c230eb4c7fprecedence_heuristic cell_id$b16f6225-1949-4b6d-a4b0-c5c230eb4c7fdownstream_cells_mapupstream_cells_map@md_strgetindex$a73e6557-9fed-4a1e-9e8e-c67e500eba5bprecedence_heuristic cell_id$a73e6557-9fed-4a1e-9e8e-c67e500eba5bdownstream_cells_mapmy_sqrt$abee47e4-1b75-4466-908a-e14113b181ab$cb886515-1635-43d7-82fd-a2604d1e3ad6$0867ec30-4fd7-4338-9256-4a84215ad5aa$08c4ac83-4361-41d5-b036-789c2475ff8eupstream_cells_map/+fixed_point$5c39f536-346c-48bd-a3c7-acaefb849b9f$81deb227-a822-4857-a584-a51cc8ff51f4precedence_heuristic cell_id$81deb227-a822-4857-a584-a51cc8ff51f4downstream_cells_mapqa$e1b83a0b-2e8f-4db6-ac2f-7a7c2ccce965$383b3a50-ef75-4ccd-a6ea-1ddb87d6e9d2$f1f1a354-cecc-4fb2-8d1e-096f51e4cf88$0fc99cae-bfe4-4517-a578-453cab15d977$f22bfdc8-c25d-4844-98e3-08d05533ba56$528326dd-1344-4baa-9edd-5b09f63669dd$30afb6e9-1ce0-4004-807b-dca57b789573$877c563a-2ce3-4f97-9746-7d8329c0178a_inline_htmlupstream_cells_mapHypertextLiteral$f1ba3d3c-d0a5-4290-ab73-9ce34bd5e5f6HypertextLiteral.content@htlHypertextLiteral.ResultMarkdownsprintHTMLHypertextLiteral.Bypass$c9603b16-113b-4e05-8517-d814b0879ab8precedence_heuristic cell_id$c9603b16-113b-4e05-8517-d814b0879ab8downstream_cells_mapupstream_cells_map@md_strgetindex$c3b59d62-144e-4541-9007-19187f2fea1cprecedence_heuristic cell_id$c3b59d62-144e-4541-9007-19187f2fea1cdownstream_cells_mapupstream_cells_maprrefA$fa019742-c473-4f1d-86ce-a795edbd1f92b$d0c4b33b-63e2-49dd-aff2-d9bd1bbb4661$b23a4c1d-cf35-42e6-b286-7fbcdddfd424precedence_heuristic cell_id$b23a4c1d-cf35-42e6-b286-7fbcdddfd424downstream_cells_mapupstream_cells_map@md_strgetindex$cbfc0129-9361-4edb-a467-1456a1f3aeaeprecedence_heuristic cell_id$cbfc0129-9361-4edb-a467-1456a1f3aeaedownstream_cells_mapimg$d701392f-0b25-4c27-989a-a61c23c41d9c$b6f76d2d-3389-4dec-9aef-b7feeb7e0793$9d883700-0959-4ccd-be50-9ee316a6077eURL$cbfc0129-9361-4edb-a467-1456a1f3aeaesave_imageimgpathPath$cbfc0129-9361-4edb-a467-1456a1f3aeaeupstream_cells_map HypertextLiteral$f1ba3d3c-d0a5-4290-ab73-9ce34bd5e5f6HypertextLiteral.contentStringHypertextLiteral.Result@htlPlutoUI.LocalResourcePlutoUI$f1ba3d3c-d0a5-4290-ab73-9ce34bd5e5f6URL$cbfc0129-9361-4edb-a467-1456a1f3aeaejoinpath!HypertextLiteral.BypassHypertextLiteral.attribute_pairinstartswith&PlutoTeachingTools.RobustLocalResourcesplit@__DIR__Path$cbfc0129-9361-4edb-a467-1456a1f3aeae*PlutoTeachingTools$f1ba3d3c-d0a5-4290-ab73-9ce34bd5e5f6$fa019742-c473-4f1d-86ce-a795edbd1f92precedence_heuristic cell_id$fa019742-c473-4f1d-86ce-a795edbd1f92downstream_cells_mapA$c3b59d62-144e-4541-9007-19187f2fea1c$17f3594f-b568-416f-9a19-38bfd4d99dd0upstream_cells_map$528326dd-1344-4baa-9edd-5b09f63669ddprecedence_heuristic cell_id$528326dd-1344-4baa-9edd-5b09f63669dddownstream_cells_mapupstream_cells_mapqa$81deb227-a822-4857-a584-a51cc8ff51f4@md_strgetindex$cb886515-1635-43d7-82fd-a2604d1e3ad6precedence_heuristic cell_id$cb886515-1635-43d7-82fd-a2604d1e3ad6downstream_cells_mapupstream_cells_mapFiniteDifferences.central_fdmFiniteDifferences$66a8b541-b06f-403a-a45d-23461a2c539bmy_sqrt$a73e6557-9fed-4a1e-9e8e-c67e500eba5b$d907c5d7-f517-467a-a840-f94868ad7680precedence_heuristic cell_id$d907c5d7-f517-467a-a840-f94868ad7680downstream_cells_mapupstream_cells_map@md_strgetindex$9d883700-0959-4ccd-be50-9ee316a6077eprecedence_heuristic cell_id$9d883700-0959-4ccd-be50-9ee316a6077edownstream_cells_mapupstream_cells_mapimg$cbfc0129-9361-4edb-a467-1456a1f3aeae@md_strgetindex=>$23049939-1b3a-4328-b159-99c3f1470e39precedence_heuristic cell_id$23049939-1b3a-4328-b159-99c3f1470e39downstream_cells_mapupstream_cells_map@md_strgetindex$5c39f536-346c-48bd-a3c7-acaefb849b9fprecedence_heuristic cell_id$5c39f536-346c-48bd-a3c7-acaefb849b9fdownstream_cells_mapfixed_point$a73e6557-9fed-4a1e-9e8e-c67e500eba5bupstream_cells_mapisless<->abs$17f3594f-b568-416f-9a19-38bfd4d99dd0precedence_heuristic cell_id$17f3594f-b568-416f-9a19-38bfd4d99dd0downstream_cells_mapFupstream_cells_mapluA$fa019742-c473-4f1d-86ce-a795edbd1f92$10ca4307-929a-4e5f-942b-5d6c0e28e2beprecedence_heuristic cell_id$10ca4307-929a-4e5f-942b-5d6c0e28e2bedownstream_cells_mapupstream_cells_map@md_strgetindex$6f8714a1-1372-42f4-9b51-da93ef2ed4c9precedence_heuristic cell_id$6f8714a1-1372-42f4-9b51-da93ef2ed4c9downstream_cells_mapupstream_cells_map@md_strgetindex$c1efb93f-efd8-487a-94d2-aa7ecedb61b8precedence_heuristic cell_id$c1efb93f-efd8-487a-94d2-aa7ecedb61b8downstream_cells_mapupstream_cells_map@md_strgetindexift$114b2603-81da-4a5c-baa1-4d95f456aeb3$64250438-9ba6-44f7-b4a0-fcd5d72f05e5precedence_heuristiccell_id$64250438-9ba6-44f7-b4a0-fcd5d72f05e5downstream_cells_mapLinearAlgebraRowEchelonupstream_cells_map$f1ba3d3c-d0a5-4290-ab73-9ce34bd5e5f6precedence_heuristiccell_id$f1ba3d3c-d0a5-4290-ab73-9ce34bd5e5f6downstream_cells_mapHypertextLiteral$40baa108-eb68-433f-9917-ac334334f198$cbfc0129-9361-4edb-a467-1456a1f3aeae$81deb227-a822-4857-a584-a51cc8ff51f4PlutoUI$40baa108-eb68-433f-9917-ac334334f198$cbfc0129-9361-4edb-a467-1456a1f3aeaeExperimentalLayoutPlutoTeachingTools$40baa108-eb68-433f-9917-ac334334f198$cbfc0129-9361-4edb-a467-1456a1f3aeaeupstream_cells_map$abee47e4-1b75-4466-908a-e14113b181abprecedence_heuristic cell_id$abee47e4-1b75-4466-908a-e14113b181abdownstream_cells_mapupstream_cells_mapmy_sqrt$a73e6557-9fed-4a1e-9e8e-c67e500eba5b$d6797e7b-fa78-4366-b88f-9925f72a5d0fprecedence_heuristic cell_id$d6797e7b-fa78-4366-b88f-9925f72a5d0fdownstream_cells_mapupstream_cells_map@md_strgetindex$b6f76d2d-3389-4dec-9aef-b7feeb7e0793precedence_heuristic cell_id$b6f76d2d-3389-4dec-9aef-b7feeb7e0793downstream_cells_mapupstream_cells_mapimg$cbfc0129-9361-4edb-a467-1456a1f3aeae$40baa108-eb68-433f-9917-ac334334f198precedence_heuristic cell_id$40baa108-eb68-433f-9917-ac334334f198downstream_cells_mapupstream_cells_mapHypertextLiteral$f1ba3d3c-d0a5-4290-ab73-9ce34bd5e5f6HypertextLiteral.content$PlutoTeachingTools.ChooseDisplayModeHypertextLiteral.Result@htlPlutoUI.TableOfContentsPlutoUI$f1ba3d3c-d0a5-4290-ab73-9ce34bd5e5f6PlutoTeachingTools$f1ba3d3c-d0a5-4290-ab73-9ce34bd5e5f6HypertextLiteral.Bypass$e1b83a0b-2e8f-4db6-ac2f-7a7c2ccce965precedence_heuristic cell_id$e1b83a0b-2e8f-4db6-ac2f-7a7c2ccce965downstream_cells_mapupstream_cells_mapqa$81deb227-a822-4857-a584-a51cc8ff51f4@md_strgetindex$1de5d608-dc91-4f4a-995b-3dcfad38b81cprecedence_heuristic cell_id$1de5d608-dc91-4f4a-995b-3dcfad38b81cdownstream_cells_mapupstream_cells_map@md_strgetindex$66a8b541-b06f-403a-a45d-23461a2c539bprecedence_heuristic cell_id$66a8b541-b06f-403a-a45d-23461a2c539bdownstream_cells_mapMooncakeForwardDiff$0867ec30-4fd7-4338-9256-4a84215ad5aaFiniteDifferences$cb886515-1635-43d7-82fd-a2604d1e3ad6upstream_cells_map$08c4ac83-4361-41d5-b036-789c2475ff8eprecedence_heuristic cell_id$08c4ac83-4361-41d5-b036-789c2475ff8edownstream_cells_mapupstream_cells_mapDI.AutoMooncakeDI.derivativeDI$878bec4d-9d8a-4e92-9817-ddcd95bd8d35my_sqrt$a73e6557-9fed-4a1e-9e8e-c67e500eba5b$ea41e038-21d8-4321-bc17-25eab0a8cbb2precedence_heuristic cell_id$ea41e038-21d8-4321-bc17-25eab0a8cbb2downstream_cells_mapupstream_cells_map@md_strgetindex$bb4e1c20-1d24-494a-82ae-433e8ba56110precedence_heuristic cell_id$bb4e1c20-1d24-494a-82ae-433e8ba56110downstream_cells_mapupstream_cells_map@md_strgetindex$2b30ae9e-e537-4ad1-a25e-570709c7d517precedence_heuristic cell_id$2b30ae9e-e537-4ad1-a25e-570709c7d517downstream_cells_mapupstream_cells_map@md_strgetindexift$114b2603-81da-4a5c-baa1-4d95f456aeb3$30afb6e9-1ce0-4004-807b-dca57b789573precedence_heuristic cell_id$30afb6e9-1ce0-4004-807b-dca57b789573downstream_cells_mapupstream_cells_mapqa$81deb227-a822-4857-a584-a51cc8ff51f4@md_strgetindex$d701392f-0b25-4c27-989a-a61c23c41d9cprecedence_heuristic cell_id$d701392f-0b25-4c27-989a-a61c23c41d9cdownstream_cells_mapupstream_cells_mapBase.getindex=>Base.Docs.HTMLBasehboximg$cbfc0129-9361-4edb-a467-1456a1f3aeae@html_strDiv@md_strcircle_qa$0fc99cae-bfe4-4517-a578-453cab15d977Dict$f369cf71-6eea-4aaa-b75d-79c2629ce88eprecedence_heuristic cell_id$f369cf71-6eea-4aaa-b75d-79c2629ce88edownstream_cells_mapupstream_cells_map@md_strgetindex$0867ec30-4fd7-4338-9256-4a84215ad5aaprecedence_heuristic cell_id$0867ec30-4fd7-4338-9256-4a84215ad5aadownstream_cells_mapupstream_cells_mapForwardDiff.derivativeForwardDiff$66a8b541-b06f-403a-a45d-23461a2c539bmy_sqrt$a73e6557-9fed-4a1e-9e8e-c67e500eba5b$0fc437e3-37cc-4905-8bf9-3e8b9155d6e8precedence_heuristic cell_id$0fc437e3-37cc-4905-8bf9-3e8b9155d6e8downstream_cells_mapupstream_cells_map@md_strgetindex$6f4e1705-22f2-4be6-9f93-cbaabf809e84precedence_heuristic cell_id$6f4e1705-22f2-4be6-9f93-cbaabf809e84downstream_cells_mapupstream_cells_map@md_strgetindex$64c4e42c-e444-44f1-8318-befed7d11bb5precedence_heuristic cell_id$64c4e42c-e444-44f1-8318-befed7d11bb5downstream_cells_mapupstream_cells_map@md_strgetindex$b19451b4-2a9e-4c25-888e-d72a13eb7589precedence_heuristic cell_id$b19451b4-2a9e-4c25-888e-d72a13eb7589downstream_cells_mapupstream_cells_map@md_strgetindex$d0c4b33b-63e2-49dd-aff2-d9bd1bbb4661precedence_heuristic cell_id$d0c4b33b-63e2-49dd-aff2-d9bd1bbb4661downstream_cells_mapb$c3b59d62-144e-4541-9007-19187f2fea1cupstream_cells_map$0b091706-da13-41f8-9852-4fa685a0fa95precedence_heuristic cell_id$0b091706-da13-41f8-9852-4fa685a0fa95downstream_cells_mapupstream_cells_map@md_strgetindex$114b2603-81da-4a5c-baa1-4d95f456aeb3precedence_heuristic cell_id$114b2603-81da-4a5c-baa1-4d95f456aeb3downstream_cells_mapift$2b30ae9e-e537-4ad1-a25e-570709c7d517$c1efb93f-efd8-487a-94d2-aa7ecedb61b8upstream_cells_map@md_strgetindex$f22bfdc8-c25d-4844-98e3-08d05533ba56precedence_heuristic cell_id$f22bfdc8-c25d-4844-98e3-08d05533ba56downstream_cells_mapupstream_cells_mapqa$81deb227-a822-4857-a584-a51cc8ff51f4@md_strgetindex$383b3a50-ef75-4ccd-a6ea-1ddb87d6e9d2precedence_heuristic cell_id$383b3a50-ef75-4ccd-a6ea-1ddb87d6e9d2downstream_cells_mapupstream_cells_mapqa$81deb227-a822-4857-a584-a51cc8ff51f4@md_strgetindex$f1f1a354-cecc-4fb2-8d1e-096f51e4cf88precedence_heuristic cell_id$f1f1a354-cecc-4fb2-8d1e-096f51e4cf88downstream_cells_mapupstream_cells_mapqa$81deb227-a822-4857-a584-a51cc8ff51f4@md_strgetindex$878bec4d-9d8a-4e92-9817-ddcd95bd8d35precedence_heuristic cell_id$878bec4d-9d8a-4e92-9817-ddcd95bd8d35downstream_cells_mapDI$08c4ac83-4361-41d5-b036-789c2475ff8eupstream_cells_map$0fc99cae-bfe4-4517-a578-453cab15d977precedence_heuristic cell_id$0fc99cae-bfe4-4517-a578-453cab15d977downstream_cells_mapcircle_qa$d701392f-0b25-4c27-989a-a61c23c41d9cupstream_cells_mapqa$81deb227-a822-4857-a584-a51cc8ff51f4@md_strgetindexshortpathimplicit.jllast_save_timeAڸأ?notebook_id$44a6855e-d3ab-11f1-9b4d-7fb352cd59d9nbpkgbusy_packages,waiting_for_permission_but_probably_disabled§enabledðterminal_outputsLinearAlgebra [0m[1mResolving...[22m [90m===[39m [36m[1m Project[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_ljpzskbqrc/Project.toml` [32m[1m Updating[22m[39m `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_ljpzskbqrc/Manifest.toml` [90m[deac9b47] [39m[93m↑ LibCURL_jll v8.18.0+1 ⇒ v8.22.0+0[39m [90m[29816b5a] [39m[93m↑ LibSSH2_jll v1.11.103+0 ⇒ v1.11.104+0[39m [90m[14a3606d] [39m[93m↑ MozillaCACerts_jll v2026.8.13 ⇒ v2026.10.20[39m [90m[458c3c95] [39m[93m↑ OpenSSL_jll v3.5.6+0 ⇒ v3.5.8+0[39m [90m[83775a58] [39m[93m↑ Zlib_jll v1.3.1+2 ⇒ v1.3.2+0[39m [90m[8e850ede] [39m[93m↑ nghttp2_jll v1.67.1+0 ⇒ v1.70.0+0[39m [0m[1mInstantiating...[22m [90m===[39m [0m[1mPrecompiling...[22m [90m===[39m Waiting for notebook process to start... Done. Starting precompilation...RowEchelon [0m[1mResolving...[22m [90m===[39m [36m[1m Project[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_ljpzskbqrc/Project.toml` [32m[1m Updating[22m[39m `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_ljpzskbqrc/Manifest.toml` [90m[deac9b47] [39m[93m↑ LibCURL_jll v8.18.0+1 ⇒ v8.22.0+0[39m [90m[29816b5a] [39m[93m↑ LibSSH2_jll v1.11.103+0 ⇒ v1.11.104+0[39m [90m[14a3606d] [39m[93m↑ MozillaCACerts_jll v2026.8.13 ⇒ v2026.10.20[39m [90m[458c3c95] [39m[93m↑ OpenSSL_jll v3.5.6+0 ⇒ v3.5.8+0[39m [90m[83775a58] [39m[93m↑ Zlib_jll v1.3.1+2 ⇒ v1.3.2+0[39m [90m[8e850ede] [39m[93m↑ nghttp2_jll v1.67.1+0 ⇒ v1.70.0+0[39m [0m[1mInstantiating...[22m [90m===[39m [0m[1mPrecompiling...[22m [90m===[39m Waiting for notebook process to start... Done. Starting precompilation...HypertextLiteral [0m[1mResolving...[22m [90m===[39m [36m[1m Project[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_ljpzskbqrc/Project.toml` [32m[1m Updating[22m[39m `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_ljpzskbqrc/Manifest.toml` [90m[deac9b47] [39m[93m↑ LibCURL_jll v8.18.0+1 ⇒ v8.22.0+0[39m [90m[29816b5a] [39m[93m↑ LibSSH2_jll v1.11.103+0 ⇒ v1.11.104+0[39m [90m[14a3606d] [39m[93m↑ MozillaCACerts_jll v2026.8.13 ⇒ v2026.10.20[39m [90m[458c3c95] [39m[93m↑ OpenSSL_jll v3.5.6+0 ⇒ v3.5.8+0[39m [90m[83775a58] [39m[93m↑ Zlib_jll v1.3.1+2 ⇒ v1.3.2+0[39m [90m[8e850ede] [39m[93m↑ nghttp2_jll v1.67.1+0 ⇒ v1.70.0+0[39m [0m[1mInstantiating...[22m [90m===[39m [0m[1mPrecompiling...[22m [90m===[39m Waiting for notebook process to start... Done. Starting precompilation...Mooncake [0m[1mResolving...[22m [90m===[39m [36m[1m Project[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_ljpzskbqrc/Project.toml` [32m[1m Updating[22m[39m `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_ljpzskbqrc/Manifest.toml` [90m[deac9b47] [39m[93m↑ LibCURL_jll v8.18.0+1 ⇒ v8.22.0+0[39m [90m[29816b5a] [39m[93m↑ LibSSH2_jll v1.11.103+0 ⇒ v1.11.104+0[39m [90m[14a3606d] [39m[93m↑ MozillaCACerts_jll v2026.8.13 ⇒ v2026.10.20[39m [90m[458c3c95] [39m[93m↑ OpenSSL_jll v3.5.6+0 ⇒ v3.5.8+0[39m [90m[83775a58] [39m[93m↑ Zlib_jll v1.3.1+2 ⇒ v1.3.2+0[39m [90m[8e850ede] [39m[93m↑ nghttp2_jll v1.67.1+0 ⇒ v1.70.0+0[39m [0m[1mInstantiating...[22m [90m===[39m [0m[1mPrecompiling...[22m [90m===[39m Waiting for notebook process to start... Done. Starting precompilation...PlutoUI [0m[1mResolving...[22m [90m===[39m [36m[1m Project[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_ljpzskbqrc/Project.toml` [32m[1m Updating[22m[39m `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_ljpzskbqrc/Manifest.toml` [90m[deac9b47] [39m[93m↑ LibCURL_jll v8.18.0+1 ⇒ v8.22.0+0[39m [90m[29816b5a] [39m[93m↑ LibSSH2_jll v1.11.103+0 ⇒ v1.11.104+0[39m [90m[14a3606d] [39m[93m↑ MozillaCACerts_jll v2026.8.13 ⇒ v2026.10.20[39m [90m[458c3c95] [39m[93m↑ OpenSSL_jll v3.5.6+0 ⇒ v3.5.8+0[39m [90m[83775a58] [39m[93m↑ Zlib_jll v1.3.1+2 ⇒ v1.3.2+0[39m [90m[8e850ede] [39m[93m↑ nghttp2_jll v1.67.1+0 ⇒ v1.70.0+0[39m [0m[1mInstantiating...[22m [90m===[39m [0m[1mPrecompiling...[22m [90m===[39m Waiting for notebook process to start... Done. Starting precompilation...nbpkg_sync [0m[1mResolving...[22m [90m===[39m [36m[1m Project[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_ljpzskbqrc/Project.toml` [32m[1m Updating[22m[39m `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_ljpzskbqrc/Manifest.toml` [90m[deac9b47] [39m[93m↑ LibCURL_jll v8.18.0+1 ⇒ v8.22.0+0[39m [90m[29816b5a] [39m[93m↑ LibSSH2_jll v1.11.103+0 ⇒ v1.11.104+0[39m [90m[14a3606d] [39m[93m↑ MozillaCACerts_jll v2026.8.13 ⇒ v2026.10.20[39m [90m[458c3c95] [39m[93m↑ OpenSSL_jll v3.5.6+0 ⇒ v3.5.8+0[39m [90m[83775a58] [39m[93m↑ Zlib_jll v1.3.1+2 ⇒ v1.3.2+0[39m [90m[8e850ede] [39m[93m↑ nghttp2_jll v1.67.1+0 ⇒ v1.70.0+0[39m [0m[1mInstantiating...[22m [90m===[39m [0m[1mPrecompiling...[22m [90m===[39m Waiting for notebook process to start... Done. Starting precompilation...ForwardDiff [0m[1mResolving...[22m [90m===[39m [36m[1m Project[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_ljpzskbqrc/Project.toml` [32m[1m Updating[22m[39m `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_ljpzskbqrc/Manifest.toml` [90m[deac9b47] [39m[93m↑ LibCURL_jll v8.18.0+1 ⇒ v8.22.0+0[39m [90m[29816b5a] [39m[93m↑ LibSSH2_jll v1.11.103+0 ⇒ v1.11.104+0[39m [90m[14a3606d] [39m[93m↑ MozillaCACerts_jll v2026.8.13 ⇒ v2026.10.20[39m [90m[458c3c95] [39m[93m↑ OpenSSL_jll v3.5.6+0 ⇒ v3.5.8+0[39m [90m[83775a58] [39m[93m↑ Zlib_jll v1.3.1+2 ⇒ v1.3.2+0[39m [90m[8e850ede] [39m[93m↑ nghttp2_jll v1.67.1+0 ⇒ v1.70.0+0[39m [0m[1mInstantiating...[22m [90m===[39m [0m[1mPrecompiling...[22m [90m===[39m Waiting for notebook process to start... Done. Starting precompilation...FiniteDifferences [0m[1mResolving...[22m [90m===[39m [36m[1m Project[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_ljpzskbqrc/Project.toml` [32m[1m Updating[22m[39m `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_ljpzskbqrc/Manifest.toml` [90m[deac9b47] [39m[93m↑ LibCURL_jll v8.18.0+1 ⇒ v8.22.0+0[39m [90m[29816b5a] [39m[93m↑ LibSSH2_jll v1.11.103+0 ⇒ v1.11.104+0[39m [90m[14a3606d] [39m[93m↑ MozillaCACerts_jll v2026.8.13 ⇒ v2026.10.20[39m [90m[458c3c95] [39m[93m↑ OpenSSL_jll v3.5.6+0 ⇒ v3.5.8+0[39m [90m[83775a58] [39m[93m↑ Zlib_jll v1.3.1+2 ⇒ v1.3.2+0[39m [90m[8e850ede] [39m[93m↑ nghttp2_jll v1.67.1+0 ⇒ v1.70.0+0[39m [0m[1mInstantiating...[22m [90m===[39m [0m[1mPrecompiling...[22m [90m===[39m Waiting for notebook process to start... Done. Starting precompilation...PlutoTeachingTools [0m[1mResolving...[22m [90m===[39m [36m[1m Project[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_ljpzskbqrc/Project.toml` [32m[1m Updating[22m[39m `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_ljpzskbqrc/Manifest.toml` [90m[deac9b47] [39m[93m↑ LibCURL_jll v8.18.0+1 ⇒ v8.22.0+0[39m [90m[29816b5a] [39m[93m↑ LibSSH2_jll v1.11.103+0 ⇒ v1.11.104+0[39m [90m[14a3606d] [39m[93m↑ MozillaCACerts_jll v2026.8.13 ⇒ v2026.10.20[39m [90m[458c3c95] [39m[93m↑ OpenSSL_jll v3.5.6+0 ⇒ v3.5.8+0[39m [90m[83775a58] [39m[93m↑ Zlib_jll v1.3.1+2 ⇒ v1.3.2+0[39m [90m[8e850ede] [39m[93m↑ nghttp2_jll v1.67.1+0 ⇒ v1.70.0+0[39m [0m[1mInstantiating...[22m [90m===[39m [0m[1mPrecompiling...[22m [90m===[39m Waiting for notebook process to start... Done. Starting precompilation...DifferentiationInterface [0m[1mResolving...[22m [90m===[39m [36m[1m Project[22m[39m No packages added to or removed from `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_ljpzskbqrc/Project.toml` [32m[1m Updating[22m[39m `~/.julia/scratchspaces/c3e4b0f8-55cb-11ea-2926-15256bba5781/pkg_envs/env_ljpzskbqrc/Manifest.toml` [90m[deac9b47] [39m[93m↑ LibCURL_jll v8.18.0+1 ⇒ v8.22.0+0[39m [90m[29816b5a] [39m[93m↑ LibSSH2_jll v1.11.103+0 ⇒ v1.11.104+0[39m [90m[14a3606d] [39m[93m↑ MozillaCACerts_jll v2026.8.13 ⇒ v2026.10.20[39m [90m[458c3c95] [39m[93m↑ OpenSSL_jll v3.5.6+0 ⇒ v3.5.8+0[39m [90m[83775a58] [39m[93m↑ Zlib_jll v1.3.1+2 ⇒ v1.3.2+0[39m [90m[8e850ede] [39m[93m↑ nghttp2_jll v1.67.1+0 ⇒ v1.70.0+0[39m [0m[1mInstantiating...[22m [90m===[39m [0m[1mPrecompiling...[22m [90m===[39m Waiting for notebook process to start... Done. Starting precompilation...waiting_for_permission·restart_recommended_msgrestart_required_msginstalled_versionsHypertextLiteral1.0.0RowEchelon0.2.1Mooncake0.5.57PlutoUI0.7.83!__internal_julia_manifest_version1.13.3LinearAlgebrastdlib__internal_julia_version1.13.3FiniteDifferences0.12.34ForwardDiff1.4.6PlutoTeachingTools0.4.7DifferentiationInterface0.7.21install_time_nsinstantiatedípluto_versionv1.1.0in_temp_dir