Iteration-dependent analysis

class autolyap.IterationDependent

Bases: object

Iteration-dependent Lyapunov analysis utilities.

For the mathematical formulation, notation, and convergence statements, see Iteration-dependent analyses.

This class provides the corresponding computational interface, with search_lyapunov() as the main entry point.

static get_parameters_distance_to_solution(

algo: Algorithm,

k: int,

i: int = 1,

j: int = 1,

) → ndarray | Tuple[ndarray, ndarray]

Compute Lyapunov parameters for the distance-to-solution metric at iteration \(k\).

For the matrix constructions used in this method, see Performance estimation via SDPs. For the role of \((Q_k,q_k)\), see Iteration-dependent analyses.

Resulting lower bounds

With this choice of \((Q_k,q_k)\),

\[\mathcal{V}(Q_k,q_k,k) = \|y_{i,j}^{k} - y^{\star}\|^{2}.\]

Matrix construction

The matrix \(Q_k\) is constructed as

\[Q_k = \left(P_{(i,j)}Y_k^{k,k} - P_{(i,\star)}Y_\star^{k,k}\right)^\top \left(P_{(i,j)}Y_k^{k,k} - P_{(i,\star)}Y_\star^{k,k}\right),\]

where:

• \(Y_k^{k,k}\) is retrieved via _get_Ys(), using k_min = k and k_max = k.

• \(Y_\star^{k,k}\) is retrieved via _get_Ys(), using k_min = k and k_max = k.

• \(P_{(i,j)}\) and \(P_{(i,\star)}\) are projection matrices retrieved via _get_Ps().

The remaining vector is set to zero:

• If \(\NumFunc > 0\), then \(q_k = 0\).

Parameters

• algo (Type[Algorithm]): Algorithm instance providing m, m_bar_is, _get_Ys(), and _get_Ps().

• k (int): Nonnegative iteration index \(k\).

• i (int): Component index, with \(i \in \llbracket 1, m\rrbracket\).

• j (int): Evaluation index for component i, with \(j \in \llbracket 1, \NumEval_i\rrbracket\).

Returns

• (Union[numpy.ndarray, Tuple[numpy.ndarray, numpy.ndarray]]): If algo.m_func == 0, returns \(Q_k\) with

  \[Q_k \in \sym^{n + \NumEval + m}.\]

  Otherwise, returns \((Q_k, q_k)\) with

  \[\begin{split}\begin{aligned} Q_k &\in \sym^{n + \NumEval + m},\\ q_k &\in \mathbb{R}^{\NumEvalFunc + \NumFunc}. \end{aligned}\end{split}\]

Raises

• ValueError: If an input is invalid or a required matrix is missing.

static get_parameters_fixed_point_residual(

algo: Algorithm,

k: int,

) → ndarray | Tuple[ndarray, ndarray]

Compute Lyapunov parameters for the fixed-point residual at iteration \(k\).

For the matrix constructions used in this method, see Performance estimation via SDPs. For the role of \((Q_k,q_k)\), see Iteration-dependent analyses.

Resulting lower bounds

With this choice of \((Q_k,q_k)\),

\[\mathcal{V}(Q_k,q_k,k) = \|\bx^{k+1} - \bx^{k}\|^{2}.\]

Matrix construction

The matrix \(Q_k\) is constructed as

\[Q_k = \left(X_{k+1}^{k,k} - X_k^{k,k}\right)^\top \left(X_{k+1}^{k,k} - X_k^{k,k}\right),\]

where:

• \(X_k^{k,k}\) is retrieved via _get_Xs(), using k_min = k and k_max = k.

• \(X_{k+1}^{k,k}\) is retrieved via _get_Xs(), using k_min = k and k_max = k.

The remaining vector is set to zero:

• If \(\NumFunc > 0\), then \(q_k = 0\).

Parameters

• algo (Type[Algorithm]): Algorithm instance providing dimensions and _get_Xs().

• k (int): Nonnegative iteration index \(k\).

Returns

• (Union[numpy.ndarray, Tuple[numpy.ndarray, numpy.ndarray]]): If algo.m_func == 0, returns \(Q_k\) with

  \[Q_k \in \sym^{n + \NumEval + m}.\]

  Otherwise, returns \((Q_k, q_k)\) with

  \[\begin{split}\begin{aligned} Q_k &\in \sym^{n + \NumEval + m},\\ q_k &\in \mathbb{R}^{\NumEvalFunc + \NumFunc}. \end{aligned}\end{split}\]

Raises

• ValueError: If an input is invalid or required \(X\) matrices are missing.

static get_parameters_function_value_suboptimality(

algo: Algorithm,

k: int,

j: int = 1,

) → Tuple[ndarray, ndarray]

Compute Lyapunov parameters for function-value suboptimality at iteration \(k\).

For the matrix constructions used in this method, see Performance estimation via SDPs. For the role of \((Q_k,q_k)\), see Iteration-dependent analyses.

Resulting lower bounds

With this choice of \((Q_k,q_k)\),

\[\mathcal{V}(Q_k,q_k,k) = f_{1}(y_{1,j}^{k}) - f_{1}(y^{\star}).\]

Matrix construction

This method applies only when \(m = \NumFunc = 1\).

The vector \(q_k\) is constructed as

\[q_k = \left(F_{(1,j,k)}^{k,k} - F_{(1,\star,\star)}^{k,k}\right)^\top,\]

where:

• \(F_{(1,j,k)}^{k,k}\) is retrieved via _get_Fs(), using k_min = k and k_max = k.

• \(F_{(1,\star,\star)}^{k,k}\) is retrieved via _get_Fs(), using k_min = k and k_max = k.

The remaining matrix is set to zero:

• \(Q_k = 0\).

Parameters

• algo (Type[Algorithm]): Algorithm instance with m = m_func = 1, m_bar_is, and _get_Fs().

• k (int): Nonnegative iteration index \(k\).

• j (int): Evaluation index for component 1, with \(j \in \llbracket 1, \NumEval_1\rrbracket\).

Returns

• (Tuple[numpy.ndarray, numpy.ndarray]): A tuple \((Q_k, q_k)\) with

  \[\begin{split}\begin{aligned} Q_k &\in \sym^{n + \NumEval + m},\\ q_k &\in \mathbb{R}^{\NumEvalFunc + \NumFunc}. \end{aligned}\end{split}\]

Raises

• ValueError: If an input is invalid, required \(F\) matrices are missing, or \(m \ne 1\) / \(\NumFunc \ne 1\).

static get_parameters_optimality_measure(

algo: Algorithm,

k: int,

) → ndarray | Tuple[ndarray, ndarray]

Compute Lyapunov parameters for the optimality measure at iteration \(k\).

For the matrix constructions used in this method, see Performance estimation via SDPs. For the role of \((Q_k,q_k)\), see Iteration-dependent analyses.

Resulting lower bounds

With this choice of \((Q_k,q_k)\),

\[\begin{split}\mathcal{V}(Q_k,q_k,k) = \begin{cases} \|u_{1,1}^{k}\|^{2}, & \text{if } m = 1, \\[0.5em] \left\|\sum_{i=1}^{m} u_{i,1}^{k}\right\|^{2} + \sum_{i=2}^{m} \|y_{1,1}^{k} - y_{i,1}^{k}\|^{2}, & \text{if } m > 1. \end{cases}\end{split}\]

Matrix construction

The matrix \(Q_k\) is constructed as

\[\begin{split}Q_k = \begin{cases} \left(P_{(1,1)}U_k^{k,k}\right)^\top \left(P_{(1,1)}U_k^{k,k}\right), & \text{if } m = 1, \\[1em] \left(\sum_{i=1}^{m} P_{(i,1)}U_k^{k,k}\right)^\top \left(\sum_{i=1}^{m} P_{(i,1)}U_k^{k,k}\right) + \sum_{i=2}^{m} \left(\left(P_{(1,1)} - P_{(i,1)}\right)Y_k^{k,k}\right)^\top \left(\left(P_{(1,1)} - P_{(i,1)}\right)Y_k^{k,k}\right), & \text{if } m > 1, \end{cases}\end{split}\]

where:

• \(U_k^{k,k}\) is retrieved via _get_Us(), using k_min = k and k_max = k.

• \(Y_k^{k,k}\) is retrieved via _get_Ys(), using k_min = k and k_max = k.

• \(P_{(i,1)}\) are projection matrices retrieved via _get_Ps().

The remaining vector is set to zero:

• If \(\NumFunc > 0\), then \(q_k = 0\).

Parameters

• algo (Type[Algorithm]): Algorithm instance providing m, m_bar, m_bar_is, _get_Us(), _get_Ys(), and _get_Ps().

• k (int): Nonnegative iteration index \(k\).

Returns

• (Union[numpy.ndarray, Tuple[numpy.ndarray, numpy.ndarray]]): If algo.m_func == 0, returns \(Q_k\) with

  \[Q_k \in \sym^{n + \NumEval + m}.\]

  Otherwise, returns \((Q_k, q_k)\) with

  \[\begin{split}\begin{aligned} Q_k &\in \sym^{n + \NumEval + m},\\ q_k &\in \mathbb{R}^{\NumEvalFunc + \NumFunc}. \end{aligned}\end{split}\]

Raises

• ValueError: If an input is invalid or required matrices are missing.

static get_parameters_state_component_cross_iteration_difference(

algo: Algorithm,

k: int,

ell: int = 1,

ell_prime: int = 1,

) → ndarray | Tuple[ndarray, ndarray]

Compute Lyapunov parameters for a cross-iteration state-component difference metric at iteration \(k\).

For the matrix constructions used in this method, see Performance estimation via SDPs. For the role of \((Q_k,q_k)\), see Iteration-dependent analyses.

Resulting lower bounds

With this choice of \((Q_k,q_k)\),

\[\mathcal{V}(Q_k,q_k,k) = \|x_{\ell}^{k+1} - x_{\ell^{\prime}}^{k}\|^{2}.\]

Matrix construction

The matrix \(Q_k\) is constructed as

\[Q_k = \left(e_\ell^\top X_{k+1}^{k,k} - e_{\ell^{\prime}}^\top X_k^{k,k}\right)^\top \left(e_\ell^\top X_{k+1}^{k,k} - e_{\ell^{\prime}}^\top X_k^{k,k}\right),\]

where:

• \(X_k^{k,k}\) and \(X_{k+1}^{k,k}\) are retrieved via _get_Xs(), using k_min = k and k_max = k.

• \(e_\ell, e_{\ell^\prime} \in \mathbb{R}^{n}\) are standard basis vectors.

The remaining vector is set to zero:

• If \(\NumFunc > 0\), then \(q_k = 0\).

Parameters

• algo (Type[Algorithm]): Algorithm instance providing dimensions and _get_Xs().

• k (int): Nonnegative iteration index \(k\).

• ell (int): State coordinate index at iteration \(k+1\), with \(\ell \in \llbracket 1, n\rrbracket\).

• ell_prime (int): State coordinate index at iteration \(k\), with \(\ell^\prime \in \llbracket 1, n\rrbracket\).

Returns

• (Union[numpy.ndarray, Tuple[numpy.ndarray, numpy.ndarray]]): If algo.m_func == 0, returns \(Q_k\) with

  \[Q_k \in \sym^{n + \NumEval + m}.\]

  Otherwise, returns \((Q_k, q_k)\) with

  \[\begin{split}\begin{aligned} Q_k &\in \sym^{n + \NumEval + m},\\ q_k &\in \mathbb{R}^{\NumEvalFunc + \NumFunc}. \end{aligned}\end{split}\]

Raises

• ValueError: If an input is invalid or a required matrix is missing.

static get_parameters_state_component_difference(

algo: Algorithm,

k: int,

ell: int = 1,

ell_prime: int = 1,

) → ndarray | Tuple[ndarray, ndarray]

Compute Lyapunov parameters for a same-iteration state-component difference metric at iteration \(k\).

For the matrix constructions used in this method, see Performance estimation via SDPs. For the role of \((Q_k,q_k)\), see Iteration-dependent analyses.

Resulting lower bounds

With this choice of \((Q_k,q_k)\),

\[\mathcal{V}(Q_k,q_k,k) = \|x_{\ell}^{k} - x_{\ell^{\prime}}^{k}\|^{2}.\]

Matrix construction

The matrix \(Q_k\) is constructed as

\[Q_k = \left(e_\ell^\top X_k^{k,k} - e_{\ell^{\prime}}^\top X_k^{k,k}\right)^\top \left(e_\ell^\top X_k^{k,k} - e_{\ell^{\prime}}^\top X_k^{k,k}\right),\]

where:

• \(X_k^{k,k}\) is retrieved via _get_Xs(), using k_min = k and k_max = k.

• \(e_\ell, e_{\ell^\prime} \in \mathbb{R}^{n}\) are standard basis vectors.

The remaining vector is set to zero:

• If \(\NumFunc > 0\), then \(q_k = 0\).

Parameters

• algo (Type[Algorithm]): Algorithm instance providing dimensions and _get_Xs().

• k (int): Nonnegative iteration index \(k\).

• ell (int): State coordinate index at iteration \(k\), with \(\ell \in \llbracket 1, n\rrbracket\).

• ell_prime (int): State coordinate index at iteration \(k\), with \(\ell^\prime \in \llbracket 1, n\rrbracket\).

Returns

• (Union[numpy.ndarray, Tuple[numpy.ndarray, numpy.ndarray]]): If algo.m_func == 0, returns \(Q_k\) with

  \[Q_k \in \sym^{n + \NumEval + m}.\]

  Otherwise, returns \((Q_k, q_k)\) with

  \[\begin{split}\begin{aligned} Q_k &\in \sym^{n + \NumEval + m},\\ q_k &\in \mathbb{R}^{\NumEvalFunc + \NumFunc}. \end{aligned}\end{split}\]

Raises

• ValueError: If an input is invalid or a required matrix is missing.

static get_parameters_state_component_distance_to_solution(

algo: Algorithm,

k: int,

ell: int = 1,

) → ndarray | Tuple[ndarray, ndarray]

Compute Lyapunov parameters for a state-component distance-to-solution metric at iteration \(k\).

For the matrix constructions used in this method, see Performance estimation via SDPs. For the role of \((Q_k,q_k)\), see Iteration-dependent analyses.

Resulting lower bounds

With this choice of \((Q_k,q_k)\),

\[\mathcal{V}(Q_k,q_k,k) = \|x_{\ell}^{k} - y^{\star}\|^{2}.\]

Matrix construction

The matrix \(Q_k\) is constructed as

\[Q_k = \left(e_\ell^\top X_k^{k,k} - P_{(1,\star)}Y_\star^{k,k}\right)^\top \left(e_\ell^\top X_k^{k,k} - P_{(1,\star)}Y_\star^{k,k}\right),\]

where:

• \(X_k^{k,k}\) is retrieved via _get_Xs(), using k_min = k and k_max = k.

• \(Y_\star^{k,k}\) is retrieved via _get_Ys(), using k_min = k and k_max = k.

• \(P_{(1,\star)}\) is retrieved via _get_Ps().

• \(e_\ell \in \mathbb{R}^{n}\) is the ell-th standard basis vector.

The remaining vector is set to zero:

• If \(\NumFunc > 0\), then \(q_k = 0\).

Parameters

• algo (Type[Algorithm]): Algorithm instance providing dimensions and _get_Xs(), _get_Ys(), and _get_Ps().

• k (int): Nonnegative iteration index \(k\).

• ell (int): State coordinate index, with \(\ell \in \llbracket 1, n\rrbracket\).

Returns

• (Union[numpy.ndarray, Tuple[numpy.ndarray, numpy.ndarray]]): If algo.m_func == 0, returns \(Q_k\) with

  \[Q_k \in \sym^{n + \NumEval + m}.\]

  Otherwise, returns \((Q_k, q_k)\) with

  \[\begin{split}\begin{aligned} Q_k &\in \sym^{n + \NumEval + m},\\ q_k &\in \mathbb{R}^{\NumEvalFunc + \NumFunc}. \end{aligned}\end{split}\]

Raises

• ValueError: If an input is invalid or a required matrix is missing.

static search_lyapunov(

prob: InclusionProblem,

algo: Algorithm,

K: int,

Q_0: ndarray,

Q_K: ndarray,

q_0: ndarray | None = None,

q_K: ndarray | None = None,

solver_options: SolverOptions | None = None,

verbosity: int = 1,

) → Mapping[str, Any]

Search for an iteration-dependent Lyapunov certificate via an SDP.

Given an inclusion problem, an algorithm, and user-specified targets \((Q_0,q_0,Q_K,q_K,K)\), this method formulates and solves a semidefinite feasibility problem for certificate variables \((\{Q_k,q_k\}_{k=1}^{K-1}, c_K)\).

Connection to theory

For the formal statement of the chained quadratic Lyapunov inequality and the role of \((Q_0,q_0,Q_K,q_K,K)\), see Iteration-dependent analyses.

User-specified targets

The tuple \((Q_0,q_0,Q_K,q_K)\) fixes the endpoint Lyapunov values \(\mathcal{V}(Q_0,q_0,0)\) and \(\mathcal{V}(Q_K,q_K,K)\). These endpoint parameters are fixed inputs to the SDP (not optimization variables).

Built-in constructors for choosing endpoint parameters are:

• get_parameters_distance_to_solution()

• get_parameters_state_component_distance_to_solution()

• get_parameters_state_component_difference()

• get_parameters_state_component_cross_iteration_difference()

• get_parameters_function_value_suboptimality()

• get_parameters_fixed_point_residual()

• get_parameters_optimality_measure()

The SDP then searches for intermediate \((Q_k,q_k)\) for \(k \in \llbracket 1, K-1\rrbracket\) and the minimum feasible \(c_K \ge 0\) so that the chained inequalities hold. When \(\NumFunc = 0\), the vectors \(q_k\) (and inputs q_0, q_K) are omitted.

Parameters

• prob (Type[InclusionProblem]): An InclusionProblem instance containing interpolation conditions.

• algo (Type[Algorithm]): An Algorithm instance providing dimensions and matrix helpers.

• K (int): A positive integer corresponding to \(K\) defining the iteration budget.

• Q_0 (numpy.ndarray): A symmetric matrix corresponding to \(Q_0 \in \sym^{n + \NumEval + m}\).

• Q_K (numpy.ndarray): A symmetric matrix corresponding to \(Q_K \in \sym^{n + \NumEval + m}\).

• q_0 (Optional[numpy.ndarray]): A vector corresponding to \(q_0 \in \mathbb{R}^{\NumEvalFunc + \NumFunc}\) for functional components (required if \(\NumFunc > 0\); otherwise None).

• q_K (Optional[numpy.ndarray]): A vector corresponding to \(q_K \in \mathbb{R}^{\NumEvalFunc + \NumFunc}\) for functional components (required if \(\NumFunc > 0\); otherwise None).

• solver_options (Optional[SolverOptions]): Optional backend and parameter settings. Defaults to SolverOptions(backend=”mosek_fusion”).

• verbosity (int): Nonnegative output level. Defaults to 1. Set 0 to disable user-facing diagnostics, 1 for concise summaries, and 2 for per-iteration detail.

Returns

• (Mapping[str, Any]): Result mapping with keys status, solve_status, c_K, and certificate.

  • status (str): One of “feasible”, “infeasible”, or “not_solved”.

  • solve_status (Optional[str]): Raw backend solve status (None when unavailable).

  • c_K (Optional[float]): Optimal objective value when status == “feasible”; otherwise None. This is the horizon-dependent scalar.

  • certificate (Optional[Mapping[str, Any]]): None unless status == “feasible”.

  When status == “feasible”, certificate has:

  {
    "Q_sequence": List[np.ndarray],   # length K+1, Q_sequence[k] = Q_k
    "q_sequence": List[np.ndarray] | None,  # None when m_func == 0
    "multipliers": {
      "operator_lambda": List[record],
      "function_lambda": List[record],
      "function_nu": List[record]
    }
  }
  

  Each multiplier list entry is a record with:

  record = {
    "iteration": int,
    "component": int,
    "interpolation_index": int,
    "pairs": List[{"j": int | "star", "k": int | "star"}],
    "value": float
  }
  

  Field meanings and ranges:

  • iteration corresponds to \(k\) and satisfies \(k \in \llbracket 0, K-1 \rrbracket\).

  • component corresponds to \(i\) and satisfies \(i \in \llbracket 1, m \rrbracket\).

  • interpolation_index corresponds to \(o\), where \(o\) is the zero-based index from \(\text{enumerate}(\text{prob.get_component_data}(i))\), so \(o \in \llbracket 0, \text{len}(\text{prob.get_component_data}(i)) - 1 \rrbracket\).

  • pairs is the concrete interpolation-pair list used by that multiplier. Its length is determined by _InterpolationIndices: 1 for “r1” and 2 for “r1<r2”, “r1!=r2”, “r1!=star”. Typical examples are [{“j”: 2, “k”: 5}] and [{“j”: 1, “k”: 5}, {“j”: “star”, “k”: “star”}].

    Pair entries satisfy

    \[\begin{split}\begin{aligned} j &\in \llbracket 1, \bar m_i \rrbracket \cup \{\star\}, \\ k_{\text{pair}} &\in \{k, k+1\} \cup \{\star\}, \end{aligned}\end{split}\]

    with \(j=\star \Leftrightarrow k_{\text{pair}}=\star\).

  • value is the scalar multiplier for that record.

Raises

• ValueError: If input dimensions or other conditions are violated.