Page 202 - Video Coding for Mobile Communications Efficiency, Complexity, and Resilience

Section 8.3. The Simplex Minimization (SM) Optimization Method 179

1. The method is initialized with N + 1 points, p 1 ;:::; p N +1 , de:ning an initial nondegenerate
simplex where each point is in N dimensions, p i =(p i; 1 ;:::;p i; N ). The function to be
minimized, f, is then evaluated at those initial vertices to produce the function values
f 1 = f(p 1 );:::;f N +1 = f(p N +1 ).
2. The highest, f h = max i f i , second highest, f s = max i = h f i , and lowest, f l = min i f i , func-
tion values are determined and the corresponding vertices are marked as p h , p s, and p l ,
respectively. The centroid, p m, of the simplex with the highest point removed is then
evaluated using
1 �
p m = p i : (8.3)
N
i = h

3. It would seem reasonable to move away from p h . Thus, the simplex is re'ected from its
highest point about its centroid using
p r = − p h +(1+ )p m; (8.4)
where p r is the reCected point and ≥ 0isthe re'ection coe(cient. The function is then
evaluated at this new reCected point, giving f r = f(p r ).

4. IF (f r ¡f l ), then reCection has produced the lowest function value. Therefore, the direc-
tion from p m to p r seems to be a good one to move along. Thus, the simplex is expanded
in this direction using
p e = p r +(1 − )p m; (8.5)

where p e is the expanded point and ≥ 1isthe expansion coe(cient. The function is
then evaluated at this new expanded point, giving f e = f(p e ). There are now two possible
cases:
(a) IF (f e¡f l ), then the expansion step was in the right direction. Thus, p h is removed
from the simplex and replaced by p e. The search then proceeds to step 8 to test for
convergence.
(b) ELSE it seems that the expansion step moved too far in the direction from p m to p r .
Thus, p e is abandoned. Since p r is already known to produce an improvement, p h
is removed from the simplex and replaced by p r . The search then proceeds to step
8 to test for convergence.
5. ELSE IF (f r ¿f l AND f r ¡f s ), then the reCected point is an improvement over the worst
two points of the simplex. Thus, p h is removed from the simplex and replaced by p r . The
search then proceeds to step 8 to test for convergence.
6. ELSE IF (f r ¿f i , for all i = h), then there are two possible cases:
(a) IF (f r ¿f h ), then the search proceeds directly to the contraction step (step 7).
(b) ELSE p h is :rst removed from the simplex and replaced by p r and then the search
proceeds to the contraction step (step 7).

Figure 8.2: Simplex method for function minimization