# An improvement of the adaptive transformation network method by a new global minimization algorithm and its application to forecasts of air pollutions

Norio Baba, François Delebecque

► To cite this version:

Norio Baba, François Delebecque. An improvement of the adaptive transformation network method by a new global minimization algorithm and its application to forecasts of air pollutions. [Research Report] IRIA-RR-368, IRIA. 1979, pp.23. hal-04716626

HAL Id: hal-04716626

https://inria.hal.science/hal-04716626v1

Submitted on 1 Oct 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
INV: 07817 RR 368

RIA
laboria

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
B. P. 105 78150 - Le Chesnay
France
Tél.: 954 90 20

laboratoire de recherche
en informatique
et automatique

<figure><img src="image_2.png" /></figure>

AN IMPROVEMENT OF THE
ADAPTIVE TRANSFORMATION
NETWORK METHOD
BY A NEW GLOBAL
MINIMIZATION ALGORITHM
AND ITS APPLICATION TO
FORECASTS OF AIR POLLUTIONS

Norio BABA
François DELEBECQUE

Rapport de Recherche N° 368

Novembre 1979
BY A NEW GLOBAL MINIMIZATION ALGORITHM

AND ITS APPLICATION TO FORECASTS OF AIR POLLUTIONS

Norio BABA (*)

François DELEBECQUE (**)

**RESUME** : On propose dans ce papier une amélioration de la méthode du réseau de transformation adaptative qui peut être utilisée à la prévision à court terme de la pollution de l'air. On étudie un algorithme mixte, combinaison de méthodes d'optimisation déterministe (D.F.P. ou gradient conjugué) et d'optimisation avec recherche aléatoire.

**ABSTRACT** : This paper deals with an improvement of the Adaptive Transformation Network Method which is known as a useful tool for the prediction of air pollution. The improvement consists in using a new hybrid algorithm of minimization, combining the D.F.P. method (or conjugate gradient method) with the random optimization method.

<footnote>(*) Tokushima University, JAPAN.</footnote>

<footnote>(**) IRIA/Laboria</footnote>
# 1. - INTRODUCTION

Air pollution is one of the most serious problems for the people who live in big cities or industrial areas : This phenomenon has harmful influences upon human health and farm products. Various trials have been presented to try to give accurate forecasts of air pollution density. Among these, the Adaptive Transformation Network Method proposed by R.L. Barron [1] may be one of the most powerful tools to give good forecast of air pollution density. However, in the utilization of the Adaptive Transformation Network Method, one is faced with several difficult problems. Among these problems, one of the most important comes from the fact "It takes a lot of time to find out an appropriate parameter vector included in the Adaptive Transformation Network Method".

In this paper, we will propose a new combined algorithm of the DFP method (or conjugate gradient method) and the random optimization method. Further it is shown that the Adaptive Transformation Network Method is improved by the application of our proposed hybrid algorithm. In the first part of this paper, a brief explanation of the Adaptive Transformation Network Method is given. In the second part of this paper, we point out one of the most important problems of the Adaptive Transformation Network Method. In the third part of this paper, a hybrid algorithm of the DFP method (or conjugate gradient method) and the random optimization method is proposed in order to solve the problem of the Adaptive Transformation Network Method. Further, a convergence theorem of our hybrid algorithm is given. In order to investigate the speed of convergence, several numerical examples are also given.
## 2. ADAPTIVE TRANSFORMATION NETWORK METHOD AND ITS APPLICATION TO THE FORECAST OF AIR POLLUTION DENSITY

In this section, we will give a brief introduction of the Adaptive Transformation Network Method with the examples of its application to the forecast of air pollution density.

Generally, the phenomena of air pollutions are very complicated and it is quite difficult to describe them by mathematical models because they are influenced by too many factors. And so, to give accurate forecasts of air pollutions is also very difficult.

Up to now, several trials have been presented with the object of giving good forecasts of pollutions. As shown in [3], the Adaptive Transformation Network Method proposed by R.L. Barron is one of the most powerful instruments for that object.

The Adaptive Transformation Network Method was developed in order to give an approximate inputs-output relation of the real complex system using the past data. In the following four steps, we will show how to apply the Adaptive Transformation Network Method to give good forecasts of air pollutions.

Suppose that one is faced with the problem to forecast a specific value y measuring a level of air pollution density such as SO₂, NO₂, dust, etc.

**Step 1:** Pick out the inputs $x_i$ ($i = 1,...,N$) that have significant influences upon the output y.

**Step 2:** Construct a transformation network, combining such elements of 2 inputs-output relation as shown in Figure 1.

<figure><img src="image_3.png" /></figure>

$x_\ell, x_m$ : inputs

Y : output

$$Y = w_0 + w_1 x_\ell + w_2 x_m + w_3 x_\ell x_m$$

$$(\text{or } Y = w_0 + w_1 x_\ell + w_2 x_m + w_3 x_\ell x_m + w_4 x_\ell^2 + w_5 x_m^2)$$

<caption>Figure 1</caption>
In Figure 2 and Figure 3, two examples of transformation networks are
given.

<figure><img src="image_4.png" /><figcaption>Figure 2</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>Figure 3</figcaption></figure>
**Step 3:** A transformation network contains a lot of unknown parameters. (For an example, the transformation network of Figure 2 contains 28 unknown parameters).

In this third step, we must find out an appropriate parameter vector $\hat{w}$ in order to construct a transformation network that gives a good inputs-output relation. (Further details of this step will be given in Section 3.)

R.L. Barron proposes that this procedure can be done by the random optimization method. However, as it will be mentioned in Section 3, we must do many iterations in order to find out $\hat{w}$.

**Step 4:** Give forecasts using the transformation network that includes the parameter vector $\hat{w}$. To this purpose, we can easily implement the inputs-output relation on computer which will give a very fast response to the real inputs.

In Figure 4, forecasts of $SO_2$ density at noon (From November 13, 1970 to November 30, 1970; Tokyo, Japan) are given using the informations up to 7 o'clock [3]. In this example, we improved the parameter vector $w$ using the data from October 22, 1970 to November 11, 1970.

In Figure 5, forecasts of $SO_2$ density at 3 p.m. (From June 1, 1975 to June 30, 1975; Tokushima, Japan) are given using the informations up to 1 p.m. 8 inputs are selected in the above two examples and the transformation network shown in Figure 2 is used. (For further details, see [3].)

### 3. A PROBLEM INVOLVED IN THE ADAPTIVE TRANSFORMATION NETWORK METHOD

As shown in [3], the Adaptive Transformation Network Method is one of the most powerful tools to give good forecasts of air pollutions. However, there exist several problems to be settled. It seems that the third step (to find out an appropriate parameter vector $\hat{w}$) is most difficult among the four steps in Section 2.

This step can be reduced to the nonlinear programming problem. In order to explain this briefly, let us consider the following problem:
"Give accurate forecast of SO₂ density at T o'clock using the informations of the past N days".

Let F(x,w) be the inputs-output relation of the Adaptive Transformation Network.

(It should be noted that it is rather difficult to write the explicit form of the F functions. However, the computation can be done easily in a recursive way by computing the outputs of each elements of the network and then entering these outputs as inputs for other elements.)

Let $\bar{z}_j, \bar{x}_j$ and w be SO₂ density at T o'clock of the j-th day, input vector of the j-th day, and parameter vector included in the Adpative Transformation Network respectively.

Now, let us consider the following objective function :

$$G(w) \triangleq \sum_{j=1}^{N} (\bar{z}_j - F(\bar{x}_j, w))^2$$

In the third step, we must find out an appropriate parameter w that gives small value of G(w). (This means that the third step can be reduced to the nonlinear minimization problem.) However, G(w) is not necessarily a unimodal performance function : G(w) admits several local minima, and therefore, an ordinary descent algorithm will generally lead to a local minimum. R.L. Barron uses the random optimization method in order to find out the global minimum. Although it is shown that the global minimum is found out by the Matyas' random optimization method [5] without regard to the selection of the initial point [6], it takes a lot of time to find out the global minimum as shown by the numerical examples of the next section. In the next section, we propose a new combined algorithm that ensures convergence to a global minimum and gives a faster rate of convergence.
<figure><img src="image_6.png" /><figcaption>Figure 4 : Forecasts of SO₂ density at noon</figcaption></figure>
<figure><img src="image_7.png" /><figcaption>Figure 5 : Forecasts of SO₂ density at 3 p.m.</figcaption></figure>
## 4. A HYBRID ALGORITHM TO FIND THE GLOBAL MINIMUM AND ITS UTILIZATION TO IMPROVE THE ADAPTIVE TRANSFORMATION NETWORK METHOD

In this section, we describe a new combined descent algorithm of the random optimization method and the DFP method (or conjugate gradient method) in order to find out the global minimum of the objective function f(x), x ∈ S, S: the subset of Eⁿ, in a small number of steps. First of all, let us briefly refer to the random optimization method and the DFP method. (As to the conjugate gradient method, see [9] and [11].)

### 4.a.1. - Random Optimization Method

The random optimization method was originally proposed by Rastrigin [4]. After that, various modified algorithms of his original random optimization method have been contrived.

The following algorithm is known as Matyas' random optimization method [5][6].

Let $\xi^{(i)}$ be n-dimensional random vectors with zero mean ($i=1,...$) and have the following property.

There exists some positive number $\theta$ such that :

$$ \theta = \inf_{x,y \in S} q(x-y) > 0 $$

(Here, $q(\cdot)$ is the probability density function of $\xi^{(i)}$ ($i=1,...$).)

**Step 1:** Select an initial point $x^{(1)} \in S$ and compute $f(x^{(1)})$

**Step 2:** The next point is determined as follows.

If $x^{(1)} + \xi^{(1)} \in S$, compute $f(x^{(1)} + \xi^{(1)})$.

If $f(x^{(1)} + \xi^{(1)}) < f(x^{(1)})$, $x^{(2)} \triangleq x^{(1)} + \xi^{(1)}$.

If $f(x^{(1)} + \xi^{(1)}) \ge f(x^{(1)})$, $x^{(2)} \triangleq x^{(1)}$.

If $x^{(1)} + \xi^{(1)} \notin S$, let $x^{(2)} \triangleq x^{(1)}$.
**Step 3**: In the general k-th step, $x^{(k+1)}$ is determined as follows. (k= 1,...)

$$ \text{If } x^{(k)} + \xi^{(k)} \in S, \text{ compute } f(x^{(k)} + \xi^{(k)}). $$

$$ \text{If } f(x^{(k)} + \xi^{(k)}) < f(x^{(k)}), \quad x^{(k+1)} \triangleq x^{(k)} + \xi^{(k)}. $$

$$ \text{If } f(x^{(k)} + \xi^{(k)}) \geq f(x^{(k)}), \quad x^{(k+1)} \triangleq x^{(k)}. $$

$$ \text{If } x^{(k)} + \xi^{(k)} \notin S, \text{ let } x^{(k+1)} \triangleq x^{(k)}. $$

This algorithm converges to the global minimum without regard to the location of the initial point [6].

### 4.a.2. - DFP method

The DFP (Davidon-Fletcher-Powell) Method is defined as follows.

**Step 1**: Select an initial point $x^{(1)} \in S$ and a symmetric positive definite matrix $S_1$.

Let $k = 1$.

**Step 2**: Set $d_k = -S_k g_k$ ($g_k = \nabla f(x^{(k)})'$).

**Step 3**: Minimize $f(x^{(k)} + \alpha d_k)$ to get $x^{(k+1)}$. $\alpha \ge 0$

$$ x^{(k+1)} \triangleq x^{(k)} + \alpha_k d_k, \quad p_k \triangleq \alpha_k d_k, $$

$$ g_{k+1} \triangleq \nabla f(x^{(k+1)})', \text{ and } q_k \triangleq g_{k+1} - g_k. $$

**Step 4**:

$$ S_{k+1} \triangleq S_k + \frac{p_k p_k'}{p_k' q_k} - \frac{S_k q_k q_k' S_k}{g_k' S_k q_k} $$

Let $k = k+1$ and return to step 2.

This algorithm converges in a finite number of steps for a positive definite quadratic problem. For non-quadratic convex objective functions this algorithm has a nice property of n-step quadratic convergence [10].
### 4.b. - Combined Algorithm

We will propose a new combined algorithm that makes use of both merits of the random optimization method and the DFP (or conjugate gradient) method.

An outline of this hybrid algorithm is shown in Figure 6.

Let us explain it briefly. First, minimization procedure is carried out using the DFP method. When the decrease of the value of the objective function becomes smaller than a specified value $ε_1$, we change the overall descent algorithm from the DFP method to the random optimization method in order to prevent it from stopping at a local minimum point. If the decrease of the value of the objective function becomes larger than a specified value G, we change the overall descent algorithm from the random optimization method to the DFP method. (The object of this switching is to speed up our minimization process.) The same procedures as above are used repeatedly.

When the total number of steps exceeds a specified number M, the overall descent algorithm is stopped.

The real problem can often be stated as "Find the smallest possible value of a performance function within a given number of steps M." Probably, our proposed hybrid algorithm is suitable to solve such problems where the performance function admits several local minima.

**Remark :** In order to find out an appropriate parameter value of the Adaptive Transformation Network Method, we must generally deal with multi-dimensional problems. In such a case, the following practical method can be used to execute our overall descent algorithm, when the computer capacity is not sufficient.

Let $w^{(k)}$ be the parameter vector at the k-th step of the transformation network.

$$ (w^{(k)}) \triangleq (w_1^{(k)}, \dots, w_m^{(k)})' $$
<figure><img src="image_8.png" /><figcaption>Figure 6 : Combined Algorithm of the DFP method and the Random Optimization method</figcaption></figure>
Further, let us assume that $w^{(k)}$ was found by the random optimization method and the $(k+1)$-th step must be carried out to get $w^{(k+1)}$ using the DFP method. (See Figure 6). In this case, we only execute the $(k+1)$-th step of the minimization procedure concerning some $(L)$ of the elements of the parameter vector $w^{(k)}$ that correspond to the larger changes in the $k$-th step. $(L < m)$

(Suppose that :

$$|w_{\alpha_1}^{(k)} - w_{\alpha_1}^{(k-1)}| \ge |w_{\alpha_2}^{(k)} - w_{\alpha_2}^{(k-1)}| \ge \dots \ge |w_{\alpha_L}^{(k)} - w_{\alpha_L}^{(k-1)}| \\ \ge \dots \ge |w_{\alpha_m}^{(k)} - w_{\alpha_m}^{(k-1)}|$$

$$(\alpha_i \neq \alpha_j \ (i \neq j) \ | \le \alpha_t \le m \ (t=1,...,m)).$$

In this case, we fix the parameters $w_{\alpha_{L+1}}^{(k)}$, ..., and $w_{\alpha_m}^{(k)}$ and execute the $(k+1)$-th step of the minimization procedure concerning the elements $w_{\alpha_1}^{(k)}$, ..., and $w_{\alpha_L}^{(k)}$. The number $L$ must be decided from the point of view of computer capacity, etc.)

### 4.c. - Experimental Results

In this section, we consider the following three examples and compare our proposed algorithm with the random optimization method and the DFP method (or conjugate gradient method).

**Example (i) :** Minimize the following function :

$$f(x) = x_1^2 + 2x_1x_2 + 2x_2^2 + 6x_1 + 8x_2 + 1 \quad \text{for } x_1 \ge -4$$

$$f(x) = 2x_1^2 + 2x_1x_2 + x_2^2 + 16x_1 + 4x_2 + 5 \quad \text{for } x_1 < -4$$

The above objective function is a multimodal function that has the local minimum -9 at the point (-2, -1) and the global minimum -35 at the point (-6, 4).

$$\text{Let } \epsilon_1 \approx 0.003, \epsilon_2 \approx 2, \text{ and } \epsilon_3 \approx 50.$$

Further, we take (23, 25) as the initial point of this problem. The computational results are shown in table 1.
<table><caption>Table 1 : Value of the performance function
(Initial point (23, 25))</caption><thead><tr><th>Step N°</th><th>HA</th><th>ROM</th><th>DFP</th></tr></thead><tbody><tr><td>1</td><td>3268.00</td><td>3268.00</td><td>3268.00</td></tr><tr><td>2</td><td>7.08</td><td>3213.86</td><td>7.08</td></tr><tr><td>3</td><td>-9.00</td><td>3191.30</td><td>-9.00</td></tr><tr><td>4</td><td>-9.00</td><td>3129.22</td><td></td></tr><tr><td>5</td><td>*-9.00</td><td>3129.22</td><td></td></tr><tr><td>10</td><td>-11.79</td><td>2976.81</td><td></td></tr><tr><td>11</td><td>*-28.93</td><td>2848.55</td><td></td></tr><tr><td>12</td><td>-35.00</td><td>2848.55</td><td></td></tr><tr><td>13</td><td>-35.00</td><td>2848.55</td><td></td></tr><tr><td>20</td><td>-35.00</td><td>2429.63</td><td></td></tr><tr><td>50</td><td>-35.00</td><td>819.29</td><td></td></tr><tr><td>100</td><td></td><td>-30.74</td><td></td></tr><tr><td>150</td><td></td><td>-34.97</td><td></td></tr></tbody></table>

HA : Hybrid Algorithm of the DFP method and the Random Optimization Method
(* change),

DFP: Davidon Fletcher Powell Method,

ROM: Random Optimization Method.
**Example (ii) :** Minimize the following function

$$f(x) = (x_1 - 2)^2 + 3(x_2 - 2)^2 - 18 \quad \text{for } x_1 \ge 0, x_2 \ge -x_1$$

$$f(x) = 2x_1^2 + 2x_1x_2 + x_2^2 + 16x_1 + 4x_2 + 10 \quad \text{for } x_1 < 0, x_2 \ge 0.2x_1$$

$$f(x) = 4x_1^2 - 2x_1x_2 + 2x_2^2 + 4x_1 + 2x_2 - 10 \quad \text{for another region.}$$

The above function has the local minima -18 and -12.28 at the points (2, 2) and (-5/7, -6/7) respectively.

It has the global minimum -30 at the point (-6, 4). Let (-10, -30) be the initial point and $\epsilon_1 \approx 0.003$, $G \approx 2$, $M \approx 50$.

The computational results of the above problem are shown in Table 2.

**Example (iii) :** Minimize the following function

$$f(x) = 5x_1^2 - 6x_1x_2 + 2x_2^2 - 12x_1 + 12x_2 + 36 + 1000 \sin(\pi(x_1+1)/10) + 5 \cos(\pi(x_2-8)/20).$$

The above function has the global minimum -1005 at the point (-6, -12). We choose (-50, 50) as the initial point and let $\epsilon_1 \approx 0.003$, $G \approx 2$, and $M \approx 50$.

The computational results of the above problem are shown in Table 3.

### 4.d. - Theoretical Considerations of the Proposed Hybrid Algorithm

In the preceding section, several numerical examples that indicate the effectiveness of our proposed hybrid algorithm were given. However, our proposed hybrid algorithm would become meaningless if we could not give any theoretical results that ensure convergence to the global minimum.
<table><caption>Table 2 : Value of the performance function
(Initial point (-10, -30))</caption><thead><tr><th>Step N°</th><th>HA</th><th>ROM</th><th>DFP</th></tr></thead><tbody><tr><td>1</td><td>1490.00</td><td>1490.00</td><td>1490.00</td></tr><tr><td>2</td><td>68.33</td><td>1490.00</td><td>68.33</td></tr><tr><td>3</td><td>- 12.29</td><td>1472.41</td><td>- 12.29</td></tr><tr><td>4</td><td>- 12.29</td><td>1472.41</td><td></td></tr><tr><td>5</td><td>*- 12.29</td><td>1472.41</td><td></td></tr><tr><td>10</td><td>- 12.29</td><td>1284.09</td><td></td></tr><tr><td>14</td><td>- 12.29</td><td>1106.82</td><td></td></tr><tr><td>15</td><td>- 17.40</td><td>1087.03</td><td></td></tr><tr><td>16</td><td>*- 18.00</td><td>1087.03</td><td></td></tr><tr><td>29</td><td>- 18.00</td><td>980.91</td><td></td></tr><tr><td>30</td><td>- 20.51</td><td>905.54</td><td></td></tr><tr><td>48</td><td>- 20.51</td><td>492.20</td><td></td></tr><tr><td>49</td><td>- 26.78</td><td>492.20</td><td></td></tr><tr><td>50</td><td>*- 29.94</td><td>492.20</td><td></td></tr><tr><td>51</td><td>(- 30.00)</td><td>(492.20)</td><td></td></tr><tr><td>60</td><td></td><td>153.41</td><td></td></tr><tr><td>100</td><td></td><td>0.97</td><td></td></tr><tr><td>200</td><td></td><td>- 29.99</td><td></td></tr></tbody></table>
<table><caption>Table 3 : Value of the performance function
(Initial point (-50, 50))</caption><thead><tr><th>Step N°</th><th>HAD</th><th>HAC</th><th>DFP</th><th>ROM</th></tr></thead><tbody><tr><td>1</td><td>33431.73</td><td>33431.73</td><td>33431.73</td><td>33431.73</td></tr><tr><td>2</td><td>-789.28</td><td>-789.28</td><td>-789.28</td><td>33336.01</td></tr><tr><td>3</td><td>-792.33</td><td>-792.79</td><td>-792.33</td><td>33336.01</td></tr><tr><td>4</td><td>-801.85</td><td>-795.29</td><td>-801.85</td><td>33336.01</td></tr><tr><td>5</td><td>-801.85</td><td>-801.83</td><td></td><td>31666.62</td></tr><tr><td>6</td><td>*-801.85</td><td>*-801.83</td><td></td><td></td></tr><tr><td>21</td><td>-801.85</td><td></td><td></td><td></td></tr><tr><td>22</td><td>-900.84</td><td></td><td></td><td></td></tr><tr><td>23</td><td>*-944.05</td><td></td><td></td><td></td></tr><tr><td>24</td><td>-1004.996</td><td></td><td></td><td></td></tr><tr><td>25</td><td>-1005.00</td><td></td><td></td><td></td></tr><tr><td>26</td><td>*-1005.00</td><td></td><td></td><td></td></tr><tr><td>35</td><td></td><td>-801.83</td><td></td><td>23168.20</td></tr><tr><td>36</td><td></td><td>-932.91</td><td></td><td>23168.20</td></tr><tr><td>37</td><td></td><td>*-953.58</td><td></td><td>23168.20</td></tr><tr><td>38</td><td></td><td>-1005.00</td><td></td><td>23168.20</td></tr><tr><td>39</td><td></td><td>-1005.00</td><td></td><td></td></tr><tr><td>40</td><td></td><td>*-1005.00</td><td></td><td></td></tr><tr><td>50</td><td>-1005.00</td><td>-1005.00</td><td></td><td>21089.64</td></tr><tr><td>100</td><td></td><td></td><td></td><td>8869.63</td></tr><tr><td>300</td><td></td><td></td><td></td><td>-1003.53</td></tr></tbody></table>

HAD : Hybrid Algorithm of the DFP Method and the Random Optimization Method

HAC : Hybrid Algorithm of the Conjugate Gradient Method and the Random Optimization Method.
In the following, we will give some convergence result concerning our proposed hybrid algorithm.

**Theorem**

Let $f(x)$ be a $C^1$ function, defined on a subset $S$ of $E^n$.

Let $\hat{x} \in S$ be the point such that

$$f(\hat{x}) = \min_{x \in S} f(x)$$

Further, let $R_\epsilon$ be a region such that :

$$R_{\epsilon} = \{x \mid |f(x) - f(\hat{x})| < \epsilon, x \in S\}.$$

Assume the following.

For any positive number $\delta$, the Euclidean measure of $U_\delta(\hat{x}) \cap S$ is positive.

$$(U_\delta(\hat{x}) = \{x \mid \|x - \hat{x}\| < \delta\})$$

Further, assume that we can calculate $x^{(i)}$ ($i=1, \dots$) infinitely. (Let $M$ be infinity.)

Then, for any positive number $\epsilon$, the sequence $\{x^{(k)}\}$ obtained by the above algorithm converges with probability 1 to the region $R_\epsilon$.

$$\lim_{k \to \infty} P\{\omega \mid x^{(k)} \in R_{\epsilon}\} = 1.$$

[Proof]

Let us consider the process with which the point $\{x^{(k)}\}$ is sought. In particular, let us consider the case when the DFP method is used.

We can consider the following three cases (a), (b), and (c).

(a) In the first step, we use the DFP method in order to get $x^{(2)}$ from $x^{(1)}$.
(b) The preceding research is done by the DFP method and the absolute value of the decrease of the objective function is larger than $\epsilon_1$.

(c) The preceding research is done by the random optimization method and the absolute value of the decrease of the objective function is larger than G.

Let $N_a, N_b$, and $N_c$ be the numbers of times of occurrences of the case (a), the case (b), and the case (c) respectively.

Further, let :

$$ (1) \qquad t_1 \le \epsilon_1 \le f(x^{(1)}) - f(\hat{x}) $$

$$ (2) \qquad t_2 \le G_2 \le f(x^{(1)}) - f(\hat{x}) $$

$$ (3) \qquad h \le [t_1] $$

$$ (4) \qquad S \le [t_2] $$

, where $[t_i]$ means the largest integer which is smaller than $t_i$ ($i=1,2$).

$$ (5) \qquad \text{Clearly, } N_a = 1 $$

From the definition of (1) ~ (4) and the fact that $f(x^{(i)})$ ($i=1,...$) is a monotone decreasing function of i, the following relations hold.

$$ (6) \qquad N_b \le h + 1 $$

$$ (7) \qquad N_c \le S + 1 $$

The random optimization method is used at the time when the DFP method is not used. Therefore, it becomes clear that the random optimization method is used more than T times to get $x^{(k)}$, where :

$$ T = (k-1) - (1 + (h+1) + (S+1)) $$

$$ (8) \qquad = k - (h+S+4). $$
Since (h+S+4) is bounded, T tends to infinity if k tends to infinity.

Now, we will prove the above convergence theorem using the convergence property of the random optimization method.

Since $f(x)$ is a continuous function, there exists $\hat{\delta} > 0$ such that the following relation holds.

$$ (9) \qquad \text{If } \|x-\hat{x}\| < \hat{\delta}, \text{ then } |f(x)-f(\hat{x})| < \varepsilon $$

Let us consider the following region A.

$$ (10) \qquad \begin{gathered} A \triangleq \{x \mid \|x-\hat{x}\| < \hat{\delta}, x \in S\} \\ ( = U_{\hat{\delta}}(\hat{x}) \cap S) \end{gathered} $$

From (9) and the definition of $R_\varepsilon$,

$$ (11) \qquad R_{\varepsilon} \supset A $$

Let:

$$ (12) \qquad \theta \triangleq \inf_{x,y \in S} q(x-y) $$

Now, assume that the (i+1)-th point $x^{(i+1)}$ will be found out by the random optimization method. And, let $P_A\{x^{(i)}\}$ be the probability with which the (i+1)-th point $x^{(i+1)}$ enters into the region A. (i=1,2,...)

Then, this probability will be estimated as follows:

$$ (13) \qquad P_A\{x^{(i)}\} \ge \theta M(A) \quad \text{for all } x^{(i)} \in S $$

$$ (14) \qquad , \text{ where } M(A) \text{ is the measure of } A \text{ in } E^n. $$

$$ (15) \qquad \text{Let } \gamma \text{ be } \theta M(A). $$

From the assumption of the theorem, $M(A)$ is positive. Then,

$$ (16) \qquad 0 < \gamma \le 1 $$
Let $P_{R_{\varepsilon}}\{x^{(i)}\}$ be the probability with which the $(i+1)$-th point $x^{(i+1)}$ enters into the region $R_{\varepsilon}$. $(i=1,2,...)$

$$ (17) \quad \text{Since } R_{\varepsilon} \supset A, P_{R_{\varepsilon}}\{x^{(i)}\} \ge P_{A}\{x^{(i)}\}. $$

From (13), (15), and (16),

$$ (18) \quad P_{R_{\varepsilon}}\{x^{(i)}\} \ge \gamma > 0 $$

If the point $x^{(j)}$ enters into the region $R_{\varepsilon}$, $\{x^{(t)}\}$ ($t=j+1, j+2,...$) do not leave this region. ($f(x^{(i)})$ is a monotone decreasing function of $i$.)

Therefore, the region $R_{\varepsilon}$ is an absorbing region.

Consequently,

$$ (19) \quad \begin{gathered} P\{x^{(k)} \in R_{\varepsilon}\} \ge 1 - (1-\gamma)^T \\ (T = k - (h+S+4) \quad (8)) \end{gathered} $$

Hence,

$$ \begin{align*} & \lim_{k \to \infty} P\{x^{(k)} \in R_{\varepsilon}\} \\ & \ge \lim_{k \to \infty} \{1 - (1-\gamma)^T\} \\ & = 1 \end{align*} $$

## Acknowledgements

This work was achieved within the collaboration between IRIA-Laboria and the Department of Applied Mathematics and Physics of Kyoto University. We would like to take the opportunity to thank Prof. Lions (IRIA), Prof. Bensoussan (IRIA), and Prof. Sawaragi (Kyoto University) for permitting us to work together.
REFERENCES

[1] R.L. Barron, "Adaptive Transformation Networks for Modelling, Prediction, and Control", 1971 IEEE Systems, Man, and Cybernetics Group Annual Symposium Record, October 21, pp. 254-263, 1971.

[2] A.G. Ivakhnenko, "Polynomial Theory of Complex System", IEEE Trans. Systems, Man, and Cybernetics, Vol. SMC-1, pp. 368-378, 1971.

[3] N. Baba, T. Soeda, and Y. Sawaragi, "Forecasts of Air Pollutions Using Adaptive Transformation Method", Proceedings of IFAC Symposium, 1976, USSR, pp. 67-79.

[4] L.A. Rastrigin, "The convergence of the random search method in the extremal control of a many parameter system", Automation and Remote Control, Vol. 24, pp. 1337-1342, 1963.

[5] J. Matyas, "Random optimization", Automation and Remote Control, Vol. 28, pp. 246-253, 1965.

[6] N. Baba, T. Shoman, and Y. Sawaragi, "A Modified Convergence Theorem for a Random Optimization Method", Information Sciences, Vol. 13, pp. 159-166, 1977.

[7] W.C. Davidon, "Variable Metric Method for Minimization", A.E.C. Res. and Develop. Rept. ANL-5990. Argonne Nat'l Lab., Argonne, Illinois, 1959.

[8] R. Fletcher and M.J.D. Powell, "A rapidly Convergent Descent Method For Minimization", The Computer Journal, Vol. 6, pp. 163-168, 1963.

[9] R. Fletcher and C.M. Reeves, "Function Minimization by Conjugate Gradients", The Computer Journal, Vol. 7, pp. 149-154, 1964.

[10] W. Burmeister, "Die Konvergenzordnung des Fletcher-Powell-Algorithmus", ZAMM 53, pp. 693-699, 1973.

[11] D.G. Luenberger, "Introduction to Linear and Nonlinear Programming", Mass. Addison-Wesley Publishing Company, 1973.