STUDY OF THE TRANSIENT PROCESS IN DISCRETE AUTOMATIC EXTREMUM-SEEKING SYSTEMS

N. F. Galashov

(Presented by the scientific and technical conference of the AVTF)

Let us consider a system that performs an automatic search for the extremum of a multiparameter function \(x=F(\bar v_1,\ldots,\bar v_n)=F(\bar v_n)\), where \(\bar v_n\) denotes an \(n\)-dimensional vector with components \(v_1,\ldots,v_n\). Suppose that the space of vectors \(\bar v_n \in V_n\) is discrete, and that the automatic search can be described by a Markov chain with probabilities of one-step transitions \(p(\bar v_n,\bar w_n)\), \(\bar v_n\bar w_n \in V_n\).

As a characteristic of the transient process of automatic extremum seeking, one may choose the mean time of transition of the system from the state \(\bar v_n\) to the state \(\bar w_n\)—\(T(\bar v_n,\bar w_n)\). Such a characteristic for the one-dimensional case was considered, for example, in works [1, 2, 3, 4].

In the multidimensional case the matter becomes considerably more complicated. Obtaining an analytical expression for \(T(\bar v_n,\bar w_n)\) in exact form is practically impossible even for the simplest extremal systems. Therefore, below an attempt is made to find an upper estimate for \(T(\bar v_n,\bar w_n)\), which is asymptotically exact as the dimensionality of the automatic-search system increases.

By definition,

\[ T(\bar v_n,\bar w_n)=\sum_{t=0}^{\infty} t p^1(\bar v_n,\bar w_n;t), \qquad \bar v_n,\bar w_n \in V_n, \tag{1} \]

where \(t\) is discrete time, and \(p^1(\bar v_n,\bar w_n;t)\) denotes the probability that the system passes in \(t\) steps from the state \(\bar v_n\) for the first time into the state \(\bar w_n\).

Taking into account that

\[ p^1(\bar v_n,\bar w_n;t)=Q(\bar v_n,\bar w_n;t)-Q(\bar v_n,\bar w_n;t-1)= \]

\[ =R(\bar v_n,\bar w_n;t-1)-R(\bar v_n,\bar w_n;t), \]

where \(Q(\bar v_n,\bar w_n;t)\) is the probability that during \(t\) steps the system has visited the state \(\bar w_n\) at least once, if at the initial moment it was in the state \(\bar v_n\); \(R(\bar v_n,\bar w_n;t)\) is the probability of the opposite event, one can obtain the following expression for \(T(\bar v_n,\bar w_n)\):

\[ T(\bar v_n,\bar w_n)=\sum_{t=0}^{\infty} R(\bar v_n,\bar w_n;t), \qquad \bar v_n,\bar w_n \in V_n. \tag{2} \]

The function \(R(\bar v_n,\bar w_n;t)\) can be written in the form

\[ R(\bar v_n,\bar w_n;t)=\prod_{s=1}^{t}\left[1-\lambda(\bar v_n,\bar w_n;s)\right], \qquad \bar v_n,\bar w_n\in V_n, \]

where \(\lambda(\bar v_n,\bar w_n;t)\) is the probability that, at the \(t\)-th step, the system will be in the state \(\bar w_n\), under the condition that during the preceding \((t-1)\) steps it has never once been in this state.

After rather complicated transformations, one can obtain a recurrent expression for \(\lambda(\bar v_n,\bar w_n;t)\) in the following form:

\[ \lambda(\bar v_n,\bar w_n;t)= \]

\[ = \frac{ p(\bar v_n,\bar w_n;t) - \sum_{\kappa=1}^{t-1} p(\bar v_n,\bar w_n;t-\kappa)\, \lambda(\bar w_n,\bar w_n;\kappa) \prod_{i=0}^{\kappa}\left[1-\lambda(\bar w_n,\bar w_n;i)\right] }{ \prod_{\kappa=1}^{t-1}\left[1-\lambda(\bar v_n,\bar w_n;\kappa)\right] }, \tag{3} \]

where \(p(\bar v_n,\bar w_n;t)\) is the probability of transition of the system from the state \(\bar v_n\) to the state \(\bar w_n\) in \(t\) steps.

The following interesting assertion can be proved:

\[ \lim_{t\to\infty}\lambda(\bar v_n,\bar w_n;t)=\lambda(\bar w_n)=P(\bar w_n), \tag{4} \]

where \(P(\bar w_n)\) is the final probability of the state \(\bar w_n\in V_n\).

One of the principal performance indicators of an extremum-seeking system is its speed of response, which is characterized by the mean search time for the extremal state \(T_0(\bar v_n)\) (\(\bar v_n\) is the initial state, and as the extremal point, without loss of generality, one may take \(\bar w_n=(0,0,\ldots,0)\)).

Fig. 1

One can verify that if \(\theta(\bar v_n)\) is the time during which the operation of the system passes into the steady-state regime, then for \(t>\bar\theta(\bar v_n)\)*

\[ \text{* Characteristics marked with the subscript 0 correspond to transition to the extremal state.} \]

\[ R_{0}(\bar{v}_{n}, t)\leq [1-\lambda_{0}]^{\,t-\Theta(\bar{v}_{n})}. \]

\(\lambda_{0}\) is the established value \(\lambda_{0}(\bar{v}_{n})\). Therefore the following inequality is valid:

\[ T_{0}(\bar{v}_{n}) \leq \Theta(\bar{v}_{n})+\frac{1}{\lambda_{0}}, \quad \bar{v}_{n}\in V_{n}. \tag{5} \]

Thus, the quantity

\[ \overline{T}_{0}(\bar{v}_{n})=\Theta(\bar{v}_{n})+\frac{1}{\lambda_{0}} \]

is an upper bound for the mean time of the extremum search. It can be shown that as \(n\to\infty\), i.e., as the dimensionality of the system increases, the quantity \(\nu=T_{0}(\bar{v}_{n})/\overline{T}_{0}(\bar{v}_{n})\) asymptotically tends to 1; moreover, the rate of convergence to unity is apparently the greater, the weaker the dependence between the extremum-search processes along each of the coordinates. Figure 1 shows the dependence of the quantity \(\nu\) on the dimensionality \(n\) for the case of an autonomous extremum search along each of the coordinates.

REFERENCES

1. A. A. Pervozvanskii. On the search time in discrete systems of extremal regulation. Izv. AN SSSR, “Energetika i avtomatika,” No. 5, 1960.

2. A. A. Feldbaum. On the influence of random factors on the process of automatic search. In: Theory and Application of Discrete Automatic Systems. Proceedings of a Conference. Izd-vo AN SSSR, 1960.

3. B. A. Besedin, G. A. Medvedev. Speed of response of step-type automatic search systems under the action of random disturbances. Tekhnicheskaya kibernetika, No. 2, 1963.

4. N. F. Galashov. Speed of response of step-type automatic search systems in the presence of drift of the extremal characteristic of the controlled object. Avtomatika i telemekhanika, No. 1, 1969.