**diff options**

author | Michaël Baudin <michael.baudin@scilab.org> | 2009-10-02 11:47:32 +0200 |
---|---|---|

committer | Michaël Baudin <michael.baudin@scilab.org> | 2009-10-02 11:47:32 +0200 |

commit | f2b0c4b9e01b9d13b0a6218d79ddb6f3e0fa0e5d (patch) | |

tree | 5932000f730d00b774a7fd8883f2916ec414c854 /scilab_doc | |

parent | dd87ade6726805c65775028c97b9b45e0e60d80b (diff) | |

parent | e9e36c37b07e407827d95ebb62243b2eef696593 (diff) | |

download | scilab-f2b0c4b9e01b9d13b0a6218d79ddb6f3e0fa0e5d.zip scilab-f2b0c4b9e01b9d13b0a6218d79ddb6f3e0fa0e5d.tar.gz |

Updated Spendley's chapter

Diffstat (limited to 'scilab_doc')

-rw-r--r-- | scilab_doc/neldermead/introduction.tex | 8 | ||||

-rw-r--r-- | scilab_doc/neldermead/method-spendley.tex | 110 | ||||

-rw-r--r-- | scilab_doc/neldermead/neldermead-introduction-so.pdf | bin | 286702 -> 286698 bytes | |||

-rw-r--r-- | scilab_doc/neldermead/neldermead-spendley-so.pdf | bin | 323141 -> 322977 bytes | |||

-rw-r--r-- | scilab_doc/neldermead/neldermead.bib | 2 |

5 files changed, 62 insertions, 58 deletions

diff --git a/scilab_doc/neldermead/introduction.tex b/scilab_doc/neldermead/introduction.tex index 11b20ef..cc4b0a3 100644 --- a/scilab_doc/neldermead/introduction.tex +++ b/scilab_doc/neldermead/introduction.tex | |||

@@ -32,9 +32,9 @@ vertices. | |||

32 | The goal of this toolbox is to provide a Nelder-Mead (1965) direct search optimization method to solve the | 32 | The goal of this toolbox is to provide a Nelder-Mead (1965) direct search optimization method to solve the |

33 | following unconstrained optimization problem | 33 | following unconstrained optimization problem |

34 | \begin{eqnarray} | 34 | \begin{eqnarray} |

35 | \min f(x) | 35 | \min f(\bx) |

36 | \end{eqnarray} | 36 | \end{eqnarray} |

37 | where $x\in \RR^n$, $n$ is the number of optimization parameters and $f$ is the objective | 37 | where $\bx\in \RR^n$, $n$ is the number of optimization parameters and $f$ is the objective |

38 | function $f:\RR^n\rightarrow \RR$. | 38 | function $f:\RR^n\rightarrow \RR$. |

39 | In order to solve the unconstrained optimization problem, the Nelder-Mead | 39 | In order to solve the unconstrained optimization problem, the Nelder-Mead |

40 | algorithm uses a variable shape simplex. The toolbox also provide Spendley's et al. | 40 | algorithm uses a variable shape simplex. The toolbox also provide Spendley's et al. |

@@ -43,9 +43,9 @@ by Nelder and Mead was designed as an improvement on Spendley's et al. algorithm | |||

43 | The Box complex algorithm \cite{Box1965} (1965), which is an extension of Spendley's et al. algorithm, solves the | 43 | The Box complex algorithm \cite{Box1965} (1965), which is an extension of Spendley's et al. algorithm, solves the |

44 | following constrained problem | 44 | following constrained problem |

45 | \begin{eqnarray} | 45 | \begin{eqnarray} |

46 | &&\min f(x)\\ | 46 | &&\min f(\bx)\\ |

47 | &&\ell_i \leq x_i \leq u_i, \qquad i = 1,n\\ | 47 | &&\ell_i \leq x_i \leq u_i, \qquad i = 1,n\\ |

48 | &&g_j(x)\geq 0, \qquad j = 1, m\\ | 48 | &&g_j(\bx)\geq 0, \qquad j = 1, m\\ |

49 | \end{eqnarray} | 49 | \end{eqnarray} |

50 | where $m$ is the number of nonlinear, positive constraints and $\ell_i,u_i\in \RR^n$ are the lower | 50 | where $m$ is the number of nonlinear, positive constraints and $\ell_i,u_i\in \RR^n$ are the lower |

51 | and upper bounds of the variables. | 51 | and upper bounds of the variables. |

diff --git a/scilab_doc/neldermead/method-spendley.tex b/scilab_doc/neldermead/method-spendley.tex index c8d58a0..b099261 100644 --- a/scilab_doc/neldermead/method-spendley.tex +++ b/scilab_doc/neldermead/method-spendley.tex | |||

@@ -1,12 +1,12 @@ | |||

1 | \chapter{Spendley's et al. method} | 1 | \chapter{Spendley's et al. method} |

2 | 2 | ||

3 | In this section, we present Spendley's et al. algorithm \cite{Spendley1962} for | 3 | In this chapter, we present Spendley's et al. algorithm \cite{Spendley1962} for |

4 | unconstrained optimization. | 4 | unconstrained optimization. |

5 | 5 | ||

6 | We begin by presenting a global overview of the algorithm. | 6 | We begin by presenting a global overview of the algorithm. |

7 | Then we present various geometric situations which might occur | 7 | Then we present various geometric situations which might occur |

8 | during the algorithm. In the second section, we present several | 8 | during the algorithm. In the second section, we present several |

9 | numerical experiments which allow to get some insight of the behaviour | 9 | numerical experiments which allow to get some insight in the behaviour |

10 | of the algorithm on some simple situations. The two first cases | 10 | of the algorithm on some simple situations. The two first cases |

11 | are involving only 2 variables and are based on a quadratic function. | 11 | are involving only 2 variables and are based on a quadratic function. |

12 | The last numerical experiment explores the behaviour of the algorith | 12 | The last numerical experiment explores the behaviour of the algorith |

@@ -22,93 +22,88 @@ Then we present various geometric situations which might occur | |||

22 | during the algorithm. This allows to understand when exactly a reflection | 22 | during the algorithm. This allows to understand when exactly a reflection |

23 | or a shrink is performed in practice. | 23 | or a shrink is performed in practice. |

24 | 24 | ||

25 | \subsection{Algorithm} | 25 | \subsection{Overview} |

26 | 26 | ||

27 | The goal of Spendley's et al. algorithm is to solve the | 27 | The goal of Spendley's et al. algorithm is to solve the |

28 | following unconstrained optimization problem | 28 | following unconstrained optimization problem |

29 | \begin{eqnarray} | 29 | \begin{eqnarray} |

30 | \min f(x) | 30 | \min f(\bx) |

31 | \end{eqnarray} | 31 | \end{eqnarray} |

32 | where $x\in \RR^n$, $n$ is the number of optimization parameters and $f$ is the objective | 32 | where $\bx\in \RR^n$, $n$ is the number of optimization parameters and $f$ is the objective |

33 | function $f:\RR^n\rightarrow \RR$. | 33 | function $f:\RR^n\rightarrow \RR$. |

34 | 34 | ||

35 | The simplex algorithms are based on the iterative update of | 35 | The simplex algorithms are based on the iterative update of |

36 | a \emph{simplex} made of $n+1$ points $S=\{x_i\}_{i=1,n+1}$. Each point | 36 | a \emph{simplex} made of $n+1$ points $S=\{\bx_i\}_{i=1,n+1}$. Each point |

37 | in the simplex is called a \emph{vertex} and is associated with | 37 | in the simplex is called a \emph{vertex} and is associated with |

38 | a function value $f_i=f(x_i), i=1,n+1$. | 38 | a function value $f_i=f(x_i)$ for $i=1,n+1$. |

39 | 39 | ||

40 | The vertices are sorted by increasing function values so that the | 40 | The vertices are sorted by increasing function values so that the |

41 | \emph{best} vertex has index 1 and the \emph{worst} vertex | 41 | \emph{best} vertex has index 1 and the \emph{worst} vertex |

42 | has index $n+1$ | 42 | has index $n+1$ |

43 | |||

44 | \begin{eqnarray} | 43 | \begin{eqnarray} |

45 | \label{sorted-vertices-fv} | 44 | \label{sorted-vertices-fv} |

46 | f_1 \leq f_2 \leq \ldots \leq f_n \leq f_{n+1}. | 45 | f_1 \leq f_2 \leq \ldots \leq f_n \leq f_{n+1}. |

47 | \end{eqnarray} | 46 | \end{eqnarray} |

48 | 47 | ||

49 | The \emph{next-to-worst} vertex with index $n$ has a | 48 | The $\bx_1$ vertex (resp. the $\bx_{n+1}$ vertex) is called the \emph{best} |

50 | special role in simplex algorithms. | 49 | vertex (resp. \emph{worst}), because it is associated with the lowest (resp. highest) |

51 | 50 | function value. As we are going to see, the \emph{next-to-worst} vertex $\bx_n$ has a | |

52 | The centroid of the simplex is the center of the vertices | 51 | special role in this algorithm. |

53 | where the vertex with index $j=1,n+1$ has been | ||

54 | excluded | ||

55 | 52 | ||

53 | The centroid of the simplex $\overline{\bx} (j)$ is the center of the vertices | ||

54 | where the vertex $\bx_j$ has been | ||

55 | excluded. This centroid is | ||

56 | \begin{eqnarray} | 56 | \begin{eqnarray} |

57 | \label{centroid-generalized} | 57 | \label{centroid-generalized} |

58 | \overline{x} (j) = \frac{1}{n} \sum_{i=1,n+1, i\neq j}x_i | 58 | \overline{\bx} (j) = \frac{1}{n} \sum_{i=1,n+1, i\neq j} \bx_i. |

59 | \end{eqnarray} | ||

60 | |||

61 | The first move of the algorithm is based on the centroid | ||

62 | where the worst vertex with index $j=n+1$ has been excluded | ||

63 | |||

64 | \begin{eqnarray} | ||

65 | \label{centroid-worst} | ||

66 | \overline{x} (n+1) = \frac{1}{n} \sum_{i=1,n}x_i | ||

67 | \end{eqnarray} | 59 | \end{eqnarray} |

68 | 60 | The algorithm makes use | |

69 | The algorithm attemps to replace one vertex | 61 | of one coefficient $\rho>0$, called the reflection factor. The standard |

70 | $x_j$ by a new point $x(\mu,j)$ between the centroid | 62 | value of this coefficient is $\rho=1$. |

71 | $\overline{x}$ and the vertex $x_j$ and defined by | 63 | The algorithm attemps to replace some vertex |

64 | $\bx_j$ by a new vertex $\bx(\rho,j)$ on the line from the vertex $\bx_j$ | ||

65 | to the centroid $\overline{\bx}(j)$. The new vertex $\bx(\rho,j)$ is defined by | ||

72 | \begin{eqnarray} | 66 | \begin{eqnarray} |

73 | \label{interpolate-generalized} | 67 | \label{interpolate-generalized} |

74 | x(\mu,j) = (1+\mu)\overline{x}(j) - \mu x_j | 68 | \bx(\rho,j) = (1+\rho)\overline{\bx}(j) - \rho \bx_j. |

75 | \end{eqnarray} | 69 | \end{eqnarray} |

76 | 70 | ||

77 | The Spendley et al. \cite{Spendley1962} algorithm makes use | 71 | \subsection{Algorithm} |

78 | of one coefficient, the reflection $\rho>0$. The standard | ||

79 | value of this coefficient is $\rho=1$. | ||

80 | |||

81 | The first move of the algorithm is based on the reflection | ||

82 | with respect to the worst point $x_{n+1}$ so that the reflection point is | ||

83 | computed by | ||

84 | 72 | ||

73 | The first step of the algorithm is based on the centroid | ||

74 | where the worst vertex $\bx_{n+1}$ has been excluded. This centroid | ||

75 | $\overline{\bx} (n+1)$ is | ||

76 | \begin{eqnarray} | ||

77 | \label{centroid-worst} | ||

78 | \overline{\bx} (n+1) = \frac{1}{n} \sum_{i=1,n} \bx_i. | ||

79 | \end{eqnarray} | ||

80 | This step is a reflection with respect to the worst vertex $\bx_{n+1}$ so that the | ||

81 | reflected point $\bx_r$ is defined by | ||

85 | \begin{eqnarray} | 82 | \begin{eqnarray} |

86 | \label{interpolate-worst} | 83 | \label{interpolate-worst} |

87 | x(\rho,n+1) = (1+\rho)\overline{x}(n+1) - \rho x_{n+1} | 84 | \bx_r = \bx(\rho,n+1) = (1+\rho)\overline{\bx}(n+1) - \rho \bx_{n+1} |

88 | \end{eqnarray} | 85 | \end{eqnarray} |

89 | 86 | ||

90 | The algorithm first computes the reflection point | 87 | We then compute the function value of the reflected |

91 | with respect to the worst point excluded with $x_r=x(\rho,n+1)$ | 88 | point $f_r=f(\bx_r)$. If the function value $f_r$ is better than the worst function |

92 | and evaluates the function value of the reflection | 89 | value $f_{n+1}$, i.e. if $f_r < f_{n+1}$, then the worst point $\bx_{n+1}$ is rejected from the |

93 | point $f_r=f(x_r)$. If that value $f_r$ is better than the worst function | 90 | simplex and the reflected point $\bx_r$ is accepted. If the reflection point |

94 | value $f_{n+1}$, the worst point $x_{n+1}$ is rejected from the | 91 | does not improve the function value $f_{n+1}$, we consider the centroid |

95 | simplex and the reflection point $x_r$ is accepted. If the reflection point | 92 | $\overline{\bx} (n)$, i.e. the centroid where the vertex $\bx_n$ has been excluded. |

96 | does not improves, the next-to-worst point $x_n$ is reflected and the | 93 | We then consider the reflected vertex $\bx_r^\prime$, computed from the |

97 | function is evaluated at the new reflected point. If the function | 94 | next-to-worst vertex $\bx_n$ and the centroid $\overline{\bx} (n)$. |

98 | value improves over the worst function value $f_{n+1}$, the new reflection point is | 95 | We compute the function value $f_r^\prime = f(\bx_r^\prime)$. If the function |

99 | accepted. | 96 | value $f_r^\prime$ improves over the worst function value $f_{n+1}$, the new reflection vertex |

97 | $\bx_r^\prime$ is accepted. | ||

100 | 98 | ||

101 | At that point of the algorithm, neither the reflection with respect to | 99 | At that point of the algorithm, neither the reflection with respect to |

102 | $x_{n+1}$ nor the reflection with respect to $x_n$ has improved. | 100 | $\bx_{n+1}$ nor the reflection with respect to $\bx_n$ were able to improve over |

103 | The algorithm therefore shrinks the simplex toward the best point. | 101 | the worst function value $f_{n+1}$. |

102 | Therefore, the algorithm shrinks the simplex toward the best vertex $\bx_1$. | ||

104 | That last step uses the shrink coefficient $0<\sigma<1$. The standard | 103 | That last step uses the shrink coefficient $0<\sigma<1$. The standard |

105 | value for this coefficient is $\sigma=\frac{1}{2}$. | 104 | value for this coefficient is $\sigma=\frac{1}{2}$. |

106 | 105 | ||

107 | Spendley's et al. algorithm is presented in figure \ref{algo-spendley}. | 106 | Spendley's et al. algorithm is presented in figure \ref{algo-spendley}. |

108 | The figure \ref{fig-spendley-moves} presents the various | ||

109 | moves of the Spendley et al. algorithm. It is obvious from the | ||

110 | picture that the algorithm explores a pattern which is | ||

111 | entirely determined from the initial simplex. | ||

112 | 107 | ||

113 | \begin{figure}[htbp] | 108 | \begin{figure}[htbp] |

114 | \begin{algorithmic} | 109 | \begin{algorithmic} |

@@ -139,8 +134,10 @@ entirely determined from the initial simplex. | |||

139 | 134 | ||

140 | \subsection{Geometric analysis} | 135 | \subsection{Geometric analysis} |

141 | 136 | ||

142 | The figure \ref{fig-spendley-moves} presents the various moves of the | 137 | The figure \ref{fig-spendley-moves} presents the various |

143 | simplex in the Spendley et al. algorithm. | 138 | moves of the Spendley et al. algorithm. It is obvious from the |

139 | picture that the algorithm explores a pattern which is | ||

140 | entirely determined from the initial simplex. | ||

144 | 141 | ||

145 | \begin{figure} | 142 | \begin{figure} |

146 | \begin{center} | 143 | \begin{center} |

@@ -199,6 +196,11 @@ optimum is searched. | |||

199 | 196 | ||

200 | %% TODO... | 197 | %% TODO... |

201 | 198 | ||

199 | %% \subsection{General features of the algorithm} | ||

200 | |||

201 | %% TODO... | ||

202 | |||

203 | |||

202 | \section{Numerical experiments} | 204 | \section{Numerical experiments} |

203 | 205 | ||

204 | In this section, we present some numerical experiments | 206 | In this section, we present some numerical experiments |

diff --git a/scilab_doc/neldermead/neldermead-introduction-so.pdf b/scilab_doc/neldermead/neldermead-introduction-so.pdf index c2bf429..16beed5 100644 --- a/scilab_doc/neldermead/neldermead-introduction-so.pdf +++ b/scilab_doc/neldermead/neldermead-introduction-so.pdf | |||

Binary files differ | |||

diff --git a/scilab_doc/neldermead/neldermead-spendley-so.pdf b/scilab_doc/neldermead/neldermead-spendley-so.pdf index ecb3671..70b6ca5 100644 --- a/scilab_doc/neldermead/neldermead-spendley-so.pdf +++ b/scilab_doc/neldermead/neldermead-spendley-so.pdf | |||

Binary files differ | |||

diff --git a/scilab_doc/neldermead/neldermead.bib b/scilab_doc/neldermead/neldermead.bib index a92538f..384ad54 100644 --- a/scilab_doc/neldermead/neldermead.bib +++ b/scilab_doc/neldermead/neldermead.bib | |||

@@ -261,6 +261,8 @@ publisher= {}} | |||

261 | author = {Box, M. J.}, | 261 | author = {Box, M. J.}, |

262 | journal = {The Computer Journal}, | 262 | journal = {The Computer Journal}, |

263 | pages = {42--52}, | 263 | pages = {42--52}, |

264 | volume = {8}, | ||

265 | number = {1}, | ||

264 | title = {A New Method of Constrained Optimization and a Comparison With Other Methods}, | 266 | title = {A New Method of Constrained Optimization and a Comparison With Other Methods}, |

265 | year = {1965 } | 267 | year = {1965 } |

266 | } | 268 | } |