Finite-budget exact or safeguarded inexact Newton-Kleinman policy iteration

Inputs are CARE data with $Q=C^{\ast }C⪰0$, $R\succ 0$, a supplied stabilizing gain $K_0$, a nonnegative integer outer budget $N$, and either exact or safeguarded-inexact solve mode. Each exact-mode pass takes an admissible control packet for Finite-budget Bartels-Stewart solve for a Sylvester equation: pivot threshold ${\tau }_{\mathrm{B}\mathrm{S}}\ge 0$, a fixed $c_0>0$, nonnegative integer Schur sweep budgets $N_A,N_B\le c_{0}n$, and Schur controls for each coefficient matrix (deflation tolerance, positive integer stagnation period, finite exceptional-shift tables, arithmetic/range controls, and any supplied encoding or evaluator). Use its bounded-controller mode with a supplied nonnegative integer instruction budget $K_{\mathrm{B}\mathrm{S}}$ and its built-in discriminant-sign controller. In inexact mode, also supply a nonnegative integer line-search limit $L$; each pass takes a Hermitian proposal ${\tilde{P}}_j$, a stored candidate ${\widehat{X}}_j$ and approximate inverses for the finite Lyapunov systems below, and finite factorization witnesses for each trial. Stored inputs and point-solve proposals in this mode are exact dyadics; derived gains and coefficients are retained as exact rational expressions. Every point call uses the operationwise controller of Finite precision point linear solve certificate with explicit status; every scalar enclosure uses a finite outward evaluator with a declared work budget. Write $S(K)=Q+K^{\ast }RK$ and ${\mathcal{L}}_A(P)=A^{\ast }P+PA$.

For $j=0,\dots ,N-1$, put $A_j=A-B{K}_j$. In exact mode, call Finite-budget Bartels-Stewart solve for a Sylvester equation with coefficient matrices $A_j^{\ast },A_j$, right-hand side $-S(K_j)$, and that pass's complete control packet to solve ${\mathcal{L}}_{A_j}(X_j)=-S(K_j)\mathrm{.}$ If it does not return success, stop with its status. Otherwise set $K_{j+1}=R^{-1}{B}^{\ast }{X}_j$, append the gain and residual, and continue.

In safeguarded-inexact mode, $X_j$ denotes the unique exact solution of ${\mathcal{L}}_{A_j}(X_j)=-S(K_j)$; it exists because $K_0$ is stabilizing and every previously accepted trial has a Hurwitz witness. Under column vectorization, use the point matrix $I_n\otimes A_j^{\ast }+A_j^T\otimes I_n$ for ${\mathcal{L}}_{A_j}$, as in Column vectorization is an isometry and represents the Sylvester map by a Kronecker sum. Before the current-cost point call, clear a common positive integer denominator $d_j$ from this exact rational coefficient matrix and from $-\mathrm{vec}(S(K_j))$. Call Finite precision point linear solve certificate with explicit status on the resulting dyadic system, with the supplied inverse proposal for the scaled coefficient and ${\widehat{X}}_j$ as the solution proposal. Scaling both sides by $d_j$ preserves the exact solution $X_j$; if the scaled entries cannot be stored exactly in the declared point format, return range-failure. A range-failure returns that status; an inconclusive result returns safeguard-inconclusive. Let its solution ball have center ${\widehat{X}}_j$ and radius $s_j$, replacing the center by its Hermitian part if needed. Set $D_j={\tilde{P}}_j-{\widehat{X}}_j$ and compute the outward Gershgorin upper bound ${\eta }_j=s_j+{\max }_i((D_j{)}_{ii}+{\sum }_{k\mathrm{\ne }i}\mathrm{\mid }(D_j{)}_{ik}\mathrm{\mid })\mathrm{.}$ For Hermitian $D_j$, the maximum row bound above is at least ${\lambda }_{\max }(D_j)$, by applying the eigenvector equation at a coordinate of maximal modulus. Define ${\tilde{K}}_j=R^{-1}{B}^{\ast }{\tilde{P}}_j$ and inspect the finite line-search list ${\theta }_{\mathrm{\ell }}=2^{-\mathrm{\ell }}$, $0\le \mathrm{\ell }\le L$. For each trial $K_{\mathrm{\ell }}=K_j+{\theta }_{\mathrm{\ell }}({\tilde{K}}_j-K_j)$, let $A_{\mathrm{\ell }}=A-B{K}_{\mathrm{\ell }}$ and use its supplied exact factor witnesses $W_{\mathrm{\ell }}=L_{\mathrm{\ell }}^{\ast }{L}_{\mathrm{\ell }}$ with nonsingular $L_{\mathrm{\ell }}$, and $Z_{\mathrm{\ell }}$ satisfying $A_{\mathrm{\ell }}^{\ast }{W}_{\mathrm{\ell }}+W_{\mathrm{\ell }}{A}_{\mathrm{\ell }}⪯-{\mu }_{\mathrm{\ell }}I,$ where ${\mu }_{\mathrm{\ell }}>0$ and $-A_{\mathrm{\ell }}^{\ast }{W}_{\mathrm{\ell }}-W_{\mathrm{\ell }}{A}_{\mathrm{\ell }}-{\mu }_{\mathrm{\ell }}I=Z_{\mathrm{\ell }}^{\ast }{Z}_{\mathrm{\ell }}$. Verify these exact factor identities; otherwise reject the trial and continue. Vectorize ${\mathcal{L}}_{A_{\mathrm{\ell }}}$ using the same coefficient matrix as for $A_j$. Outward-evaluate $I-R_{\mathrm{\ell }}{\mathcal{L}}_{A_{\mathrm{\ell }}}$ and let $q_{\mathrm{\ell }}$ be a Frobenius upper bound. If no finite enclosure is available or $q_{\mathrm{\ell }}\ge 1$, reject the trial and continue. Set ${\kappa }_{\mathrm{\ell }}=\mathrm{\parallel }{R}_{\mathrm{\ell }}{\mathrm{\parallel }}_F\mathrm{/}(1-q_{\mathrm{\ell }})$; the Neumann estimate and $\mathrm{\parallel }T{\mathrm{\parallel }}_2\le \mathrm{\parallel }T{\mathrm{\parallel }}_F$ give ${\kappa }_{\mathrm{\ell }}\ge \mathrm{\parallel }{\mathcal{L}}_{A_{\mathrm{\ell }}}^{-1}{\mathrm{\parallel }}_{F\to F}$. Separately outward-evaluate the raw residual and set $r_{\mathrm{\ell }}$ to an upper bound for ${\mathcal{L}}_{A_{\mathrm{\ell }}}({\tilde{P}}_j)+Q+K_{\mathrm{\ell }}^{\ast }R{K}_{\mathrm{\ell }},$ with Frobenius norm. Accept the first trial satisfying ${\eta }_j+{\kappa }_{\mathrm{\ell }}{r}_{\mathrm{\ell }}\le 0$; then set $K_{j+1}=K_{\mathrm{\ell }}$, append the accepted gain and its certificates, and proceed to pass $j+1$. If no trial passes, return safeguard-inconclusive without changing $K_j$. Any unavailable outward bound is inconclusive. The inverse bound above follows from the Neumann estimate, and $r_{\mathrm{\ell }}$ bounds the raw residual separately; the preconditioned residual in Verified point and uniform linear residual certificate data is a different quantity. All certificate witnesses and bounds use the finite outward evaluator; a non-finite operation returns its range status. After at most $N$ accepted updates return the gain sequence, solve residuals, cost-matrix data and terminal status. An arbitrary approximate Lyapunov solve is never accepted without the separate stability and descent checks above.