Construction of Periodic Counterexamples to
the Discrete-Time Kalman Conjecture

The discrete-time absolute stability problem considers the Lurye system of a discrete-time, linear time-invariant (LTI) plant in negative feedback with a nonlinearity. Let $k_{AS}$ denote the supremum of the set of values of $k$ for which the Lurye system is stable for all nonlinearities whose slope is restricted to $[0,k]$. It remains an open question to provide necessary and sufficient conditions to compute this maximal stability interval $k_{AS}$. The LTI Zames–Falb multipliers [1, 2, 3, 4, 5, 6] provide a sufficient condition for stability. Specifically, the search over discrete-time Zames-Falb multipliers in [7] provides a lower bound $k_{ZF}\leq k_{AS}$. It has been conjectured in [8, 9] that this condition is actually necessary and sufficient, i.e. $k_{ZF}=k_{AS}$. In other words, the conjecture is that if a Zames-Falb multiplier does not exist for some $k$ then there exists a destabilizing nonlinearity whose slope remains within $[0,k]$.

The main contribution of this paper is a method to systematically construct destabilizing nonlinearities for the Lurye system. Such nonlinearities provide upper bounds $\bar{k}\geq k_{AS}$ and hence are complementary to the Zames-Falb conditions. The construction is based on a frequency-domain condition developed in [9] from the dual problem of the Zames-Falb condition. The construction is first described for Lurye systems with monotone nonlinearities (Section V-A). If the plant satisfies a phase condition at one frequency then there is a monotone nonlinearity such that the Lurye system has a non-trivial periodic solution. The destabilizing nonlinearity is explicitly constructed from the periodic solution. Next, the results are extended to Lurye systems with slope-restricted nonlinearities via a loop transformation (Section V-B).

The only existing method to systematically construct a destabilizing nonlinearity is, to our knowledge, given by the Nyquist criterion. This provides the smallest linear gain, referred to as the Nyquist gain $k_{N}$, that destabilizes the Lurye system (Section VI). The Nyquist gain provides another upper bound $k_{N}\geq k_{AS}$ but it is known that this upper bound is conservative. Specifically, the discrete-time Kalman conjecture is that $k_{N}=k_{AS}$. This conjecture was shown to be false in [10, 11] and hence $k_{N}>k_{AS}$ in general. Our paper constructs destabilizing nonlinearities with slope restricted to $[0,\bar{k}]$. If $\bar{k}<k_{N}$ then the destabilizing nonlinearity represents a counterexample to the Kalman conjecture.

It is worth noting that the construction of counterexamples of the continuous-time Kalman Conjecture has been investigated since the sixties. It still attracts interest due to the ill-posed numerical issues [12, 13, 14, 15]. For the Aizerman conjecture, a systematic analysis of the existence of periodic cycles for second-order systems has been explored in [16, 17]. In the context of optimization, construction of nonlinearities for worst-case convergence rate has been used in [18].

The set of integers and positive, natural numbers are denoted as $\mathbb{Z}$ and $\mathbb{N}^{+}$, respectively. $\mathbb{RH}_{\infty}$ denotes the space of real, rational functions with all poles inside the open unit disk. This space corresponds to transfer functions for stable, LTI discrete-time systems. A function $\phi:\mathbb{R}\rightarrow\mathbb{R}$ has slope restricted to $[0,k]$ for some finite $k>0$ if:

$S_{0,k}$ with $k<\infty$ denotes the set of all functions with slope restricted to $[0,k]$ The notation $S_{0,k}$ with $k=\infty$ corresponds to the special case where $\phi$ is multivalued and monotone: $y_{2}\geq y_{1}$ implies $\phi(y_{2})\geq\phi(y_{1})$. In this case, $u\in\phi(y)$ will denote that $u$ is one of the values taken by $\phi$ at $y$. In addition, $S_{0,k}^{\text{odd}}$ denotes the set of all odd functions with slope restricted to $[0,k]$, i.e. $\phi(x)=-\phi(-x)$ for all $x\in\mathbb{R}$.

Finally, let $\{h_{0},h_{1},\ldots,h_{T-1}\}$ denote a finite sequence of real numbers. We will often stack such sequences into a column vector $H_{T}:=[h_{0},\,h_{1},\ldots,\,h_{T-1}]^{\top}\in\mathbb{R}^{T}$. The circulant matrix for a given finite sequence $H_{T}$ is defined as:

Let $G$ be a discrete-time system that is LTI and single-input, single-output (SISO). We consider the Lurye system of $G$ in negative feedback with a nonlinearity $\phi:\mathbb{R}\rightarrow\mathbb{R}$ as shown in Figure 1. The Lurye system is expressed as

We consider functions in $S_{0,k}$ with $k>0$ and $\phi(0)=0$. Lurye systems with both $k<\infty$ and $k=\infty$ will be considered. These cases are related by a loop transformation as discussed later in the paper. Additional details on this formulation can be found in [19].

We provide conditions on $G$ for the existence of non-trivial periodic solutions to the Lurye system in Figure 1. Specifically, let the plant $G$, slope constant $k>0$, and time horizon $T\in\mathbb{N}^{+}$ be given. We provide sufficient conditions for the existence of a nonlinearity $\phi\in S_{0,k}$ with $\phi(0)=0$ such that the Lurye system has a non-trivial $T$-periodic solution. If the conditions are feasible then the proof provides a construction for the periodic signals $U_{T}\in\mathbb{R}^{T}$ and $Y_{T}\in\mathbb{R}^{T}$. A nonlinearity $\phi\in S_{0,k}$ can then be constructed to interpolate $(Y_{T},-U_{T})$ and $(0,0)$.

This section presents two preliminary results that are used in the derivation of the main results.

The next result provides a necessary and sufficient condition to interpolate finite sequences by a multi-valued function in $S_{0,\infty}$. This result appears in Section 8 of [20] and more general finite interpolation results appear in [21] and [22].

A formal proof is given in [20]. If the finite sequences satisfy Equation 8 then there is, in general, more than one $\phi\in S_{0,\infty}$ that interpolates the data. Here we will provide an explicit formula for a $\phi\in S_{0,\infty}$ that interpolates the data. First, re-order the points so that $y_{0}\leq y_{1}\leq\cdots\leq y_{T-1}$ and $-u_{0}\leq-u_{1}\leq\cdots\leq-u_{T-1}$. This re-ordering is possible since the data satisfy Equation 8. Next note that there can be repeats in the input data: $y_{i}=y_{i+1}=\cdots=y_{i+r}$ for some $r>0$. In this case the nonlinearity $\phi$ is multi-valued: $\phi(y_{i})\in[-u_{i},-u_{i+r}]$. Finally, the re-ordered sequences are interpolated by the following multi-valued function:

This corresponds to linear interpolation or multi-valued output for any input $y\in[y_{0},y_{T-1}]$ and nearest neighbor extrapolation otherwise. This specific nonlinearity has the following useful property:

The constructed nonlinearity is valid for each ($\alpha$,$\beta$) where the phase condition is satisfied at the frequency $\omega=\frac{\alpha\pi}{\beta}$. This provides an upper bound $\bar{k}$ on the stability boundary $k_{AS}$ for the absolute stability problem. The Nyquist gain provides an alternative upper bound using the class of linear gains.

The constructed nonlinearity only provides new information if $\bar{k}<k_{N}$. To clarify further, recall the Discrete-Time Kalman Conjecture (DTKC) is that $k_{N}=k_{AS}$ as stated next.

Our nonlinear construction does not provide any valuable information beyond the Nyquist value for plants where $k_{ZF}\simeq k_{N}$. However, as DTKC is false in general [11], the Nyquist gain is a conservative upper bound. Our construction becomes relevant for the plants used in absolute stability literature such as the examples in [7], where there is a significant gap between $k_{ZF}$ and $k_{N}$ (see Tables I and II in [9]). For all the six examples in [9], our construction leads to counterexamples of the DTKC, i.e. $\bar{k}<k_{N}$ (see Table III in [9]).

This paper shows the connection between frequency-domain duality conditions for Zames-Falb multipliers developed in [9] and periodic behaviour of the Lurye system for slope-restricted nonlinearity. We develop an analytical construction for destabilizing nonlinearities. For all examples in [7], the construction yields systematic counterexamples of the discrete-time Kalman conjecture, and therefore less conservative upper bounds for absolute stability.