3. Algorithm representation

We consider first-order algorithms that solve (2.1) that can be represented as a discrete-time linear time‐varying system in state-space form in feedback interconnection with the potentially nonlinear and set-valued operators \((\partial f_{i})_{i\in\IndexFunc}\) and \((G_{i})_{i\in\IndexOp}\) that define the problem.

Before presenting the algorithm representation, we introduce some notation:

  1. \(\NumFunc = \abs{\IndexFunc}\) denotes the number of functional components in (2.1);

  2. \(\NumOp = \abs{\IndexOp}\) denotes the number of operator components in (2.1);

  3. \(\NumEval_{i}\in\mathbb{N}\) denotes the number of evaluations of \(\partial f_{i}\) and \(G_{i}\) per iteration, for \(i\in\IndexFunc\) and \(i\in\IndexOp\), respectively;

  4. \(\NumEvalFunc = \sum_{i\in\IndexFunc} \NumEval_{i}\) denotes the total number of subdifferential evaluations per iteration;

  5. \(\NumEvalOp = \sum_{i\in\IndexOp} \NumEval_{i}\) denotes the total number of operator evaluations per iteration; and

  6. \(\NumEval = \NumEvalFunc + \NumEvalOp\) denotes the combined total number of evaluations per iteration.

Since we consider algorithms that allow for multiple evaluation of \((\partial f_{i})_{i\in\IndexFunc}\) and \((G_{i})_{i\in\IndexOp}\) per iteration, we define \(\bfcn_{i}:\calH^{\NumEval_{i}}\to\p{\reals\cup\{\pm\infty\}}^{\NumEval_{i}}\) such that

\[\begin{split}\begin{aligned} \Bigp{ \begin{array}{@{}c@{}} \forall i\in\IndexFunc \\ \forall \by_{i}=\p{y_{i,1},\ldots,y_{i,\NumEval_{i}}}\in \calH^{\NumEval_{i}} \end{array} } \quad \bfcn_{i}(\by_{i})&=\p{f_i\p{y_{i,1}},\ldots,f_{i}\p{y_{i,\NumEval_{i}}}},\end{aligned}\end{split}\]

\(\bm{\partial}\bfcn_{i}:\calH^{\NumEval_{i}}\rightrightarrows\calH^{\NumEval_{i}}\) such that

\[\begin{split}\begin{aligned} \Bigp{ \begin{array}{@{}c@{}} \forall i\in\IndexFunc \\ \forall \by_{i}=\p{y_{i,1},\ldots,y_{i,\NumEval_{i}}}\in \calH^{\NumEval_{i}} \end{array} } \quad \bm{\partial}\bfcn_{i}(\by_{i})&= \prod_{j=1}^{\NumEval_{i}} \partial f_{i}\p{y_{i,j}},\end{aligned}\end{split}\]

and \(\bm{G}_{i}: \calH^{\NumEval_{i}} \rightrightarrows \calH^{\NumEval_{i}}\) such that

\[\begin{split}\begin{aligned} \Bigp{ \begin{array}{@{}c@{}} \forall i\in\IndexOp \\ \forall \by_{i}=\p{y_{i,1},\ldots,y_{i,\NumEval_{i}}}\in \calH^{\NumEval_{i}} \end{array} } \quad \bm{G}_{i}\p{\by_{i}}=\prod_{j=1}^{\NumEval_{i}} G_{i}\p{y_{i,j}}.\end{aligned}\end{split}\]

We are now ready to give the algorithm representation: Pick an initial \(\bx_{0}\in\calH^{n}\), an iteration horizon \(K\in\naturals\cup\set{\infty}\), and let

(3.1)\[\begin{split} \p{\forall k \in\llbracket0,K\rrbracket} \quad \left[ \begin{aligned} &\bx^{k+1} = \p{A_{k} \kron \Id} \bx^{k} + \p{B_{k} \kron \Id} \bu^{k}, \\ &\by^{k} = \p{C_{k} \kron \Id} \bx^{k} + \p{D_{k} \kron \Id} \bu^{k}, \\ &\p{\bu^{k}_{i}}_{i\in\IndexFunc} \in \prod_{i\in\IndexFunc}\bm{\partial}\bfcn_{i}\p{\by_{i}^{k}}, \\ &\p{\bu^{k}_{i}}_{i\in\IndexOp} \in \prod_{i\in\IndexOp}\bm{G}_{i}\p{\by_{i}^{k}}, \\ &\bFcn^{k} =\p{\bfcn_{i}\p{\by_{i}^{k}} }_{i\in\IndexFunc}, \end{aligned} \right.\end{split}\]

where

\[\begin{split}\begin{aligned} \bx^{k} &= \p{x_1^k,\ldots,x_n^k} \in \calH^n, \\ \bu^{k} &= \p{\bu^{k}_{1},\ldots,\bu^{k}_{m}} \in \prod_{i=1}^{m}\calH^{\NumEval_{i}}, \\ \by^{k} &= \p{\by^{k}_{1},\ldots,\by^{k}_{m}} \in \prod_{i=1}^{m}\calH^{\NumEval_{i}}, \\ \bFcn^{k} &\in \reals^{\NumEvalFunc}. \end{aligned}\end{split}\]

are the algorithm variables, and

(3.2)\[\begin{aligned} A_{k}&\in\reals^{n\times n},& B_{k}&\in\reals^{n\times {\NumEval}},& C_{k}&\in\reals^{{\NumEval}\times n},& D_{k}&\in\reals^{{\NumEval}\times {\NumEval}}\end{aligned}\]

are matrices containing the parameters of the algorithm at hand.

We close this page with Assumption 3.1 (Well-posedness). It is satisfied by practical algorithms and ensures that the subsequent theoretical results are well-posed.

Assumption 3.1 (Well-posedness).

We assume that the parameter sequence

\[\p{A_{k},B_{k},C_{k},D_{k}}_{k=0}^{K}\]

is chosen such that, for each

\[\bx_{0}\in\calH^{n}, \qquad \p{f_{i}}_{i\in\IndexFunc} \in \prod_{i\in\IndexFunc} \mathcal{F}_{i}, \qquad \p{G_i}_{i\in\IndexOp} \in \prod_{i\in\IndexOp} \mathcal{G}_i,\]

there exists a sequence

\[\p{\bx^{k},\bu^{k},\by^{k},\bFcn^{k}}_{k=0}^{K}\]

satisfying (3.1).

In this context, the symbol \(\Pi\) denotes Cartesian products. For interface documentation in AutoLyap, see Algorithms. In particular: